Laberint P34055

Us han dut en helicòpter a dins d’un laberint de mides n × m. Mentre baixàveu, heu tingut temps de memoritzar quines caselles tenen obstacles, per les quals no es pot passar si no s’enderroquen. Sabent que només us podeu moure horitzontalment o verticalment, quants obstacles haureu d’enderrocar per poder sortir del laberint?

Entrada

L’entrada conté diversos casos. Cada cas comença amb les mides n i m del laberint, seguides d’n files amb m caràcters cadascuna. Els obstacles es marquen amb ‘X’, i les posicions lliures amb punts. Hi ha exactament una ‘I’ que indica la posició inicial (que no té cap obstacle). Podeu suposar que tant n com m es troben entre 1 i 1000.

Sortida

Per a cada cas, escriviu el mínim nombre de caselles que cal tirar per sortir del laberint.

Puntuació

• Cas A:  ‍ Casos on la sortida és 0 o 1, com l’exemple d’entrada 1.  ‍60% Punts ‍

• Cas B:  ‍ Casos de tot tipus.  ‍40% Punts ‍