escape-1

Egy labirintusból kell kijutnunk legfeljebb $S$ lépést téve. A labirintusban vannak 0-val jelölt szabadon átjárható mezők, és ^v<> jelekkel jelölt szabad mezők: ezeknél az adott jellel jelölt mezőre csak rendre alulról, felülről, jobbról és balról léphetünk be - viszont az elhagyás iránya tetszőleges lehet (a szabályok betartásával). Az 1-el jelölt mezők tiltottak, ezekre nem léphetünk, innen nem indulhatunk. Egy lépésben a vízszintes vagy függőleges irányban található szomszédos szabad mezőre léphet. Ha elértük a labirintus szélét akkor kijutottunk… Döntsük el, hogy adott labirintus esetén hány olyan belső (nem a széleken levő) szabad mező van ($E$) melyről indulva $S$ lépésen belül meg tud menekülni.

Bemenet specifikáció

Az első sorban a labirintusok $T$ száma áll. Egy labirintus leírása: Az első sorban 3 szám $S~ R~ C$ áll, a maximálisan megtehető lépések száma a labirintus sorainak és oszlopainak száma. Ezután $R$ sor következik: mindegyikben egy $C$ hosszú sztring, a fent leírt jelekkel.

Kimenet specifikáció

$T$ sor, mindegyikben a keresett $E$ számmal.

Korlátok

$1\le T \le 15$
$1\le S \le 200$
$3\le R \le 100$
$3\le C \le 100$

1. példa bemenet

1. 5
2. 2 4 4
3. 1111
4. 1001
5. 1011
6. 0v11
7. 2 4 4
8. 1111
9. 1001
10. 1011
11. 0>11
12. 1 4 4
13. 1001
14. 1001
15. 1011
16. 0v11
17. 3 5 5
18. 00100
19. 00^00
20. 1<0>1
21. 00v00
22. 00100
23. 6 5 5
24. 00100
25. 00^00
26. 1<0>1
27. 00v00
28. 00100

1. példa kimenet

1. 2
2. 0
3. 3
4. 9
5. 9