Prisao
Retirada de Spoj
Leonardo é inicialmente trancado na célula em uma prisão retangular de segurança máxima x . Ele deve alcançar o portão em 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 , então ele pode mover para se e somente se + e e
Leonardo consegue de alguma forma obter o mapa da prisão.
Se , então Leonardo pode passar de para sem matar guardas.
Se != , então Leonardo pode passar de para matando um guarda.
Entrada
A primeira linha consiste em um inteiro , o número de casos de teste. Para cada caso de teste, a primeira linha consiste em dois inteiros e representando a ordem da prisão retangular seguidos de cadeias 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
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 |