Heroes of Might & Magic

Heroes of Might & Magic

==Include(page="template/taskheader" task_id="homm")==
 
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
 
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/taskheader" 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")==

416