Laberint P34055

Us han dut en helicòpter a dins d’un laberint de mides $n \times 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.

• Cas B:   Casos de tot tipus.