Heroes of Might & Magic

homm

==Include(page="template/taskheader" task_id="homm")==

== include(page="template/taskheader" task_id="homm") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| homm.in | homm.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="homm") ==

==Include(page="template/raw")==
 
Heroes of Might & Magic
 
Harta Erathiei este data sub forma unui caroiaj cu M linii si N coloane. Terenul este impartit in celule care pot fi accesibile (au valoarea 0) sau inaccesibile (au valoare diferita de 0).
 
Sir Christian doreste sa ajunga din celula de coordonate (x[1], y[1]) unde a avut loc ultima batalie in celula (x[2], y[2]) unde se afla Capitala regatului sau. Pentru aceasta el are la dispozitie K mutari. O mutare consta in deplasarea din celula curenta intr-o celula invecinata (pe orizontala sau verticala, nu si pe diagonala).
 
Va trebui sa determinati numarul variantelor pe care le poate alege Sir Christian. Un drum trebuie sa contina cel mult K mutari, iar Sir Christian poate trece de oricate ori prin aceeasi celula, inclusiv prin celulele (x[1], y[1]) si (x[2], y[2]).
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare homm.in se afla doua numere naturale M, N si K, reprezentand numarul liniilor si coloanelor caroiajului, respectiv numarul mutarilor pe care Sir Christian le are la dispozitie; aceste numere sunt separate printr-un spatiu. Urmatoarele M linii contin cate N numere intregi, separate printr-un spatiu, reprezentand elementele caroiajului. Pe ultima linie se vor afla patru numere intregi, reprezentand valorile x[1], y[1], x[2] si y[2].
 
h2. Date de Iesire
 
In fisierul de iesire homm.out se va scrie un singur numar care va reprezenta numarul total al drumurilor posibile.
 
h2. Restrictii
 
. 1 <= M, N <= 100;
 
. 1 <= K <= 20;
 
. Numarul total al drumurilor este intotdeauna mai mic decat 1.000.000.000;
 
. Toate coordonatele sunt date in ordinea linie (x), coloana (y).
 
 
 
Exemple
 
homm.in homm.out
 
5 5 10 34
 
0 0 0 0 0
 
0 2 0 3 0
 
0 0 1 0 0
 
0 2 0 0 0
 
0 0 0 0 0
 
1 1 5 5
 
 
 
homm.in homm.out
 
5 5 10 0
 
0 0 4 0 0
 
0 2 0 3 0
 
4 0 1 0 0
 
0 2 0 0 0
 
0 0 0 0 0
 
1 1 5 5
 
 
==Include(page="template/taskfooter" task_id="homm")==