(UVA) 11352 - Crazy King - Solução

import java.io.*;
import java.util.*;

class Main {
    class Posicao {
        public Posicao(int l, int c) {
                linha = l;
                coluna = c;
            }
        public int linha;
        public int coluna;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        Main processando = new Main();
        processando.processa();
       
        System.exit(0);
    }
   
    int busca(char[][] mapa, int pontoPartidaL, int pontoPartidaC, int numLinhas, int numColunas) {
        int[][] matriz = new int[numLinhas][numColunas];
               
        for (int i = 0; i < numLinhas; i++) {
            for (int j = 0; j < numColunas; j++) {
                matriz[i][j] = 0;
            }
        }
       
        ArrayList<Posicao> filaVisitados = new ArrayList<Posicao>();
       
        filaVisitados.add(new Posicao(pontoPartidaL, pontoPartidaC));
       
        int lin = 0;
        int col = 0;
       
        int[] vetorLinha = {-1,0,0,+1,-1,-1,+1,+1};
        int[] vetorColuna = {0,-1,+1,0,-1,+1,-1,+1};       
        int inicioFila = 0;
        while (filaVisitados.size() != inicioFila) {
            lin = filaVisitados.get(inicioFila).linha;
            col = filaVisitados.get(inicioFila).coluna;
           
            for (int i = 0; i < 8; i++) {
                int nLinha = lin+vetorLinha[i];
                int nColuna = col+vetorColuna[i];
                if (nLinha >= 0 && nLinha < numLinhas && nColuna >= 0 && nColuna < numColunas) {
                    if (matriz[nLinha][nColuna] == 0 && mapa[nLinha][nColuna] != 'Z') {
                        matriz[nLinha][nColuna] = matriz[lin][col]+1;
                        if (mapa[nLinha][nColuna] == 'A') {
                            return matriz[nLinha][nColuna];
                        }
                        else {
                            filaVisitados.add(new Posicao(nLinha, nColuna));
                        }
                    }
                }
            }
           
            inicioFila++;
        }   
       
        return -1;
    }
   
    char[][] buscaCavalos(char[][] mapa, ArrayList<Posicao> filaVisitados, int numLinhas, int numColunas) {
        char[][] matriz = new char[numLinhas][numColunas];
               
        for (int i = 0; i < numLinhas; i++) {
            for (int j = 0; j < numColunas; j++) {
                if (mapa[i][j] == 'A') {
                    matriz[i][j] = 'A';               
                }
                else if (mapa[i][j] == 'B') {
                    matriz[i][j] = 'B';               
                }
                else {
                    matriz[i][j] = '.';
                }
            }
        }
       
        int lin = 0;
        int col = 0;
       
        int[] vetorLinha = {-2,+2,-2,+2,-1,+1,-1,+1,0};
        int[] vetorColuna = {-1,-1,+1,+1,-2,-2,+2,+2,0};       
        int inicioFila = 0;
        while (filaVisitados.size() != inicioFila) {
            lin = filaVisitados.get(inicioFila).linha;
            col = filaVisitados.get(inicioFila).coluna;
           
            for (int i = 0; i < 9; i++) {
                int nLinha = lin+vetorLinha[i];
                int nColuna = col+vetorColuna[i];
                if (nLinha >= 0 && nLinha < numLinhas && nColuna >= 0 && nColuna < numColunas) {
                    if (matriz[nLinha][nColuna] == '.' && mapa[nLinha][nColuna] != 'A' && mapa[nLinha][nColuna] != 'B') {
                        matriz[nLinha][nColuna] = 'Z';
                    //    filaVisitados.add(new Posicao(nLinha, nColuna));
                    }
                }
            }
            inicioFila++;
        }   
       
        return matriz;
    }
   
    void processa() throws NumberFormatException, IOException {
        String line = "";
       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        line = br.readLine();
        StringTokenizer tokenizer = new StringTokenizer(line);
        int qteCasos = Integer.valueOf(tokenizer.nextToken());
       
        for (int i = 0; i < qteCasos; i++) {
            line = br.readLine();
            tokenizer = new StringTokenizer(line);
            int numLinhas = Integer.valueOf(tokenizer.nextToken());
            int numColunas = Integer.valueOf(tokenizer.nextToken());
                            
            char[][] mapa = new char[numLinhas][numColunas];
                   
            int pontoPartidaL = 0;
            int pontoPartidaC = 0;
            int pontoPartidaLCav = 0;
            int pontoPartidaCCav = 0;
            ArrayList<Posicao> filaVisitados = new ArrayList<Posicao>();
            for (int j = 0; j < numLinhas; j++) {
                line = br.readLine();
                for (int k = 0; k < numColunas; k++) {
                    mapa[j][k] = line.charAt(k);
                    if (mapa[j][k] == 'B') {
                        pontoPartidaL = j;
                        pontoPartidaC = k;
                    }
                    else if (mapa[j][k] == 'Z') {
                        pontoPartidaLCav = j;
                        pontoPartidaCCav = k;
                        filaVisitados.add(new Posicao(pontoPartidaLCav, pontoPartidaCCav));           
                    }
                }   
            }
                   
            char[][] matrizComCavalos = buscaCavalos(mapa, filaVisitados, numLinhas, numColunas);

            int resposta = busca(matrizComCavalos, pontoPartidaL, pontoPartidaC, numLinhas, numColunas);

            if (resposta == -1) {
                System.out.println("King Peter, you can't go now!");
            }
            else {
                System.out.println("Minimal possible length of a trip is " + resposta);
            }
        }
           
        return;
    }
}