== include(page="template/taskheader" task_id="homm") ==
==Include(page="template/taskheader" task_id="homm")==
Poveste ...
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. Cerinta
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. Restrictii
...
h2. Date de intrare
...
h2. Date de Iesire
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. Exemplu
h2. Restrictii
| homm.in | homm.out |
| linia1
linia2
linia3
| linia1
linia2
|
* $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
table(example). |_. homm.in |_. homm.out |
| 5 5 10
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 | 34 |
| 5 5 10
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 | 0 |
== include(page="template/taskfooter" task_id="homm") ==
==Include(page="template/taskfooter" task_id="homm")==
