Fişierul intrare/ieşire:homm.in, homm.outSursăFinala GInfo 2005
AutorMihai ScortaruAdăugată de
Timp execuţie pe test0.125 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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 (x1, y1) unde a avut loc ultima batalie in celula (x2, y2) 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 (x1, y1) si (x2, y2).

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 x1, y1, x2 si y2.

Date de Iesire

In fisierul de iesire homm.out se va scrie un singur numar care va reprezenta numarul total al drumurilor posibile.

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.inhomm.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content