public class NewClass {

    static final int linhas = 6,
                     colunas = 6,
                     tamanhoaberta = 200,
                     tamanhofechada = 200;

    public static int[][] preenchematriz (int[][] m) {

        for (int i=0; i < linhas; i++) {
            for (int j=0; j < colunas; j++) {
                m[i][j] = 0;
            }
        }
        m[2][1] = 2;
        m[3][1] = 1;
        m[2][4] = 2;
        m[3][4] = 2;
        m[4][4] = 2;
        m[3][5] = 3;
        return m;

    }

    public static void imprimematriz (int[][] m) {

        for (int i=0; i< linhas; i++) {
            for (int j=0; j < colunas; j++) {
                System.out.print (m[i][j]);
            }
            System.out.println();
        }
    }

    public static void atualizaposicao (int[][] m, ListaAberta[] aberta, int linha, int coluna, int posicao) {

        //Posicao uma linha abaixo
        aberta[posicao] = new ListaAberta();
        aberta[posicao].linha = linha + 1;
        aberta[posicao].coluna = coluna;
        aberta[posicao].f = obtemf(m,aberta[posicao].linha, aberta[posicao].coluna);

        //Posicao uma linha acima
        aberta[posicao+1] = new ListaAberta();
        aberta[posicao+1].linha = linha - 1;
        aberta[posicao+1].coluna = coluna;
        aberta[posicao+1].f = obtemf(m,aberta[posicao+1].linha, aberta[posicao+1].coluna);

        //Posicao uma coluna a direita
        aberta[posicao+2] = new ListaAberta();
        aberta[posicao+2].linha = linha;
        aberta[posicao+2].coluna = coluna + 1;
        aberta[posicao+2].f = obtemf(m,aberta[posicao+2].linha, aberta[posicao+2].coluna);

        //Posicao uma coluna a esquerda
        aberta[posicao+3] = new ListaAberta();
        aberta[posicao+3].linha = linha;
        aberta[posicao+3].coluna = coluna - 1;
        aberta[posicao+3].f = obtemf(m,aberta[posicao+3].linha, aberta[posicao+3].coluna);

        for (int i=posicao; i < posicao+4; i++) {
            aberta[i].pailinha = linha;
            aberta[i].paicoluna = coluna;
        }

        aberta[0].tamanholista += 4;
    }

    public static int obtemf (int[][] m, int linhapos, int colunapos) {
        int contlinhas = 0,
            contcolunas = 0,
            //Linha e Coluna do queijo (que é o alvo)
            linhaqueijo = 3,
            colunaqueijo = 5;

        //Se a linha do queijo nao for a mesma da posicao
        if (linhaqueijo != linhapos) {

            // Se a linha do queijo estiver acima da posicao
            if (linhaqueijo > linhapos) {
                do {
                    contlinhas += 1;
                    linhaqueijo -= 1;
                } while (linhaqueijo > linhapos);

            // Se a linha do queijo estiver abaixo da posicao
            } else {
                do {
                    contlinhas += 1;
                    linhaqueijo += 1;
                } while (linhaqueijo < linhapos);
            }

        }

        //Se a coluna do queijo nao for a mesma da posicao
        if (colunaqueijo != colunapos) {

            //Se a coluna do queijo estiver a direita posicao
            if (colunaqueijo > colunapos) {
                do {
                    contcolunas += 1;
                    colunaqueijo -= 1;
                } while (colunaqueijo > colunapos);

            //Se a coluna do queijo estiver a esquerda da posicao
            } else {
                do {
                    contcolunas += 1;
                    colunaqueijo += 1;
                } while (colunaqueijo < colunapos);
            }
        }

        //Retorna a soma da quantidade de colunas e linhas (Norte-Sul,Leste-Oeste)(H) da posicao ao Queijo
        //somadas ao G(10), se fosse diagonal seria 14.
                    //F = H + G
        return (contcolunas + contlinhas) + 10;

    }

    public static int verificaf (ListaAberta[] aberta, int posicao, int opcao) {
        //Assume que o menor f é o da posição que foi passada
        int menorf = aberta[posicao].f;

        //Variável auxiliar para armazenar a posição no vetor de menor f
        int aux = 0;

        for (int i=1; i < aberta[0].tamanholista; i++) {
            //Varrea lista, se a posição tiver o f menor, aux recebe a posição
            if (aberta[i].f < menorf) {
                aux = i;
            }
        }

        // Se a opcao foi 1, retorna a linha da posicao com menor f
        if (opcao == 1) {
            return aberta[aux].linha;

        // Se não, retorna a coluna da posição com menor f
        } else {
            return aberta[aux].coluna;
        }

    }

    public static void main (String[] args) {

        int[][] matriz = new int[linhas][colunas];
        ListaAberta[] laberta = new ListaAberta[tamanhoaberta];
        ListaFechada[] lfechada = new ListaFechada[tamanhofechada];
        int poslinha = 3, poscoluna = 1, posicao=1;

        preenchematriz(matriz);

        //Posicao inicial (RATO)
        laberta[0] = new ListaAberta();
        laberta[0].linha = 3;
        laberta[0].coluna = 1;
        laberta[0].tamanholista = 1;

        //Passa a lista, a posicao do rato e a posicao no vetor
        atualizaposicao(matriz,laberta,poslinha,poscoluna,posicao);

        poslinha = verificaf (laberta,posicao,1);
        poscoluna = verificaf(laberta,posicao,2);

        imprimematriz(matriz);

    }

}