B2 - Bludisko 2

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Spoločnosť PalmaGamez s.r.o. priravuje reedíciu starej bludiskovej hry. Hracia plocha je rozdelená na nxm políčok. Každé políčko je buď prázdne alebo je na ňom stena. Na políčku v ľavom hornom rohu rohu je umiestnený Paľo, ktorý sa môže pohybovať na susedné voľné políčka - nahor, dole, doľava a doprava, pričom cieľom hry je dostať sa na políčko v pravom dolnom rohu.

Zamestanci firmy PalmaGamez hneď vytvorili pre túto hru niekoľko levelov. V záverečnej fáze však zistili, že nie každý z ich levelov je riešiteľný, tj. nie v každom bludisku sa Paľo vie dostať do cieľovej pozície. Takýto level môžete vidieť aj na našom obrázku. Autori hry by teraz chceli odstrániť niektoré políčka obsadené stenou tak, aby sa level stal riešiteľný. Nakoľko ale nechcú nové levely vytvoriť príliš ľahké, zaujímal by ich minimálny počet políčok steny, ktoré treba odstrániť.

Vstup

Prvý riadok vstupu obsahuje kladné celé číslo T, určujúce počet levelov hry (1≤T≤100). Zvyšok vstupu obsahuje popis T levelov spomínanej bludiskovej hry. Prvý riadok bludiska obsahuje dve kladné celé čísla n,m oddelené medzerou. Ďalej bude nasledovať n riadkov, obsahujúcich m znakov určujúcich plán bludiska pre daný level. Znak '.' označuje voľné políčko, znak '#' označuje stenu. Môžete predpokladať, že v ľavom hornom políčku a rovnako aj v pravom dolnom políčku bludiska je voľné políčko.

Výstup

Pre každé bludisko zo vstupu vypíšte minimálny počet políčok steny, ktoré treba odstrániť tak, aby sa bludisko stalo riešiteľné. Výstup má dohromady obsahovať T čísel, každé v samostatnom riadku.

B1

1 ≤ N,M ≤ 100
Môžete predpokladať, že každé bludisko na vstupe je buď riešiteľné, alebo sa dá vyriešiť odobratím jedinej steny (tj. výsledok je buď 0 alebo 1).

B2

1 ≤ N,M ≤ 100

Príklad vstupu

3
5 6
..#...
.###.#
####.#
#..#.#
..##..
3 6
.....#
###.##
##....
7 9
...#.#...
####.####
.#.####..
.#.......
##.######
.###.#.#.
..#..#...

Príklad výstupu

1
0
2

20 Domáce 1