Prisao
Retirada de Spoj
Leonardo é inicialmente trancado na célula $$(0,0)$$ em uma prisão retangular de segurança máxima $$R$$ x $$C$$. Ele deve alcançar o portão em $$(R-1, C-1)$$ para escapar da prisão. Leonardo pode se mover de qualquer célula para qualquer uma das 4 células adjacentes (norte, leste, oeste e sul). Se Leonardo está atualmente em $$(x_1, y_1)$$, então ele pode mover para $$(x_2, y_2)$$ se e somente se $$|x_2 – x_1$$ + $$|y_2 – y_1| = 1$$ e $$0 \leq x_2 <R$$ e $$0 \leq y_2 <C$$
Leonardo consegue de alguma forma obter o mapa da prisão.
Se $$map[x1][y1] = map[x2][y2]$$, então Leonardo pode passar de $$(x1, y1)$$ para $$(x2, y2)$$ sem matar guardas.
Se $$map[x1] [y1]$$ != $$map[x2][y2]$$, então Leonardo pode passar de $$(x1, y1)$$ para $$(x2, y2)$$ matando um guarda.
Entrada
A primeira linha consiste em um inteiro $$t$$, o número de casos de teste. Para cada caso de teste, a primeira linha consiste em dois inteiros $$R$$ e $$C$$ representando a ordem da prisão retangular seguidos de cadeias $$R$$ representando o mapa da prisão retangular.
Saída
Para cada caso de teste, encontre o número mínimo de guardas que Leonardo deve matar para escapar da prisão.
Restrições
$$1 \leq t \leq 10$$
$$2 \leq R \leq 1000$$
$$2 \leq C \leq 1000$$
$$’a’ \leq map[i][j] \leq ‘z’$$
Exemplos
| ENTRADA | SAÍDA |
| 4 2 2 aa aa 2 3 abc def 6 6 akaccc aaacfc amdfcc aokhdd zyxwdp zyxwdd 5 5 abbbc abacc aaacc aefci cdgdd |
0 3 2 2 |
Deixe um comentário