Fişierul intrare/ieşire: | homm.in, homm.out | Sursă | Finala GInfo 2005 |
Autor | Mihai Scortaru | Adăugată de | |
Timp execuţie pe test | 0.125 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
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.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 |