L3Q2

public class L3Q2 {

    static final int distMax = 218309120;

    public static int charToInt(char chrLetra) //Método que recebe uma letra (char) e retorna o valor inteiro atribuído a mesma.
    {
        int intLetra = 0;

        switch (chrLetra)
        {
        case 'a':
        {
            intLetra = 1;
            break;
        }
        case 'b':
        {
            intLetra = 2;
            break;
        }
        case 'c':
        {
            intLetra = 3;
            break;
        }
        case 'd':
        {
            intLetra = 4;
            break;
        }
        case 'e':
        {
            intLetra = 5;
            break;
        }
        case 'f':
        {
            intLetra = 6;
            break;
        }
        case 'g':
        {
            intLetra = 7;
            break;
        }
        case 'h':
        {
            intLetra = 8;
            break;
        }
        case 'i':
        {
            intLetra = 9;
            break;
        }
        case 'j':
        {
            intLetra = 10;
            break;
        }
        case 'k':
        {
            intLetra = 11;
            break;
        }
        case 'l':
        {
            intLetra = 12;
            break;
        }
        case 'm':
        {
            intLetra = 13;
            break;
        }
        case 'n':
        {
            intLetra = 14;
            break;
        }
        case 'o':
        {
            intLetra = 15;
            break;
        }
        case 'p':
        {
            intLetra = 16;
            break;
        }
        case 'q':
        {
            intLetra = 17;
            break;
        }
        case 'r':
        {
            intLetra = 18;
            break;
        }
        case 's':
        {
            intLetra = 19;
            break;
        }
        case 't':
        {
            intLetra = 20;
            break;
        }
        case 'u':
        {
            intLetra = 21;
            break;
        }
        case 'v':
        {
            intLetra = 22;
            break;
        }
        case 'w':
        {
            intLetra = 23;
            break;
        }
        case 'x':
        {
            intLetra = 24;
            break;
        }
        case 'y':
        {
            intLetra = 25;
            break;
        }
        case 'z':
        {
            intLetra = 26;
            break;
        }
        case '.':
        {
            intLetra = 1;
            break;
        }
        case 'F':
        {
            intLetra = 0;
            break;
        }
        default:
        {
            intLetra = distMax;
            break;
        }
        }
        return intLetra;
    }


    public static void main(String...Arguments) {
        Arquivo arquivo = new Arquivo("L3Q2.in", "L3Q2.out");
        int t, n, m, s, a, c; //T casos teste
//      long tempoInicio = System.currentTimeMillis();
        t = arquivo.readInt();
        while (t > 0)
        {

            n = arquivo.readInt();
            m = arquivo.readInt();
            s = arquivo.readInt();
            a = arquivo.readInt();
            c = arquivo.readInt();
            No inicio = null, fim = null;
            No mapa[][] = new No[n][m];
            Heap distancia = new Heap(n*m);
            for (int i = 0; i < n; i++)
            {

                String ler = arquivo.readString();
                for (int j = 0; j < m; j++)
                {
                    mapa[i][j] = new No(ler.charAt(j), charToInt(ler.charAt(j)), i, j);
                    if (mapa[i][j].c == 'F') {
                        mapa[i][j].pontoPartida();
                        inicio = mapa[i][j];
                    }
                    else if(mapa[i][j].c == 'R') {
                        fim = mapa[i][j];
                    }
                    distancia.inserir(mapa[i][j]);
                }
            }

//          for (int i = 0; i < n; i++) {
//              for (int j = 0; j < m; j++) {
//                  System.out.println(mapa[i][j].i + " " + mapa[i][j].j + " " + mapa[i][j].c + " Peso: " + mapa[i][j].peso);
//              }
//          }


            //Faz heap
            //mapa[distancia.heap[0].i][distancia.heap[0].j].visitar();
            //          System.out.println(distancia.remover().c);
            while (distancia.size > 0) {
                No u = distancia.remover();
                mapa[u.i][u.j].visitar();

                //              mapa[u.i][u.j].visitar();
//              System.out.println("Removido da vez: " + u.i + " " + u.j + " " + u.c);

                int[] I = { 0, 0, 1, -1 };
                int[] J = { 1, -1, 0, 0 };
                for(int x = 0; x < 4; x++)
                {
                    int tempI = u.i + I[x];
                    int tempJ = u.j + J[x];

                    if (tempI >= 0 && tempI < n && tempJ >= 0 && tempJ < m && mapa[tempI][tempJ].c != '#') {
                        if (mapa[tempI][tempJ].c == 'R' && !mapa[tempI][tempJ].visitado)
                            mapa[tempI][tempJ].peso = 0;
                        //System.out.println("entrou");
                        int v = mapa[tempI][tempJ].peso;
                        int aux = distancia.isInMinHeap(tempI, tempJ);
                        //                      System.out.println("Pos na heap:" + aux);

                        if (aux != -1) {
//                          System.out.println(distancia.heap[aux].i + " " + distancia.heap[aux].j + " " + distancia.heap[aux].c + " " + distancia.heap[aux].tempoChegada);
                            if (u.tempoChegada + v + 1<  mapa[tempI][tempJ].tempoChegada) {
                                //                              System.out.println("entrouAux");
                                mapa[tempI][tempJ].tempoChegada = u.tempoChegada + v + 1;
                                //distancia.inserir(mapa[tempI][tempJ]);
                                distancia.heap[aux].tempoChegada =  u.tempoChegada + v + 1;
                            }
                        }

                    }
                }
                //distancia.buildMinHeap();
            }
            /*          for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    System.out.println(mapa[i][j].c + "..." + mapa[i][j].tempoChegada);
                }
            }*/

            int saida = ((a - s)  - c - (fim.tempoChegada*2));
            arquivo.println(saida);
            t--;
        }
//      System.out.println("Tempo Total: "+(System.currentTimeMillis()-tempoInicio));

    }

}

class No{
    char c;
    int peso;
    int tempoChegada;
    int i;
    int j;
    No next;
    boolean visitado;
    int distMin;


    No (char c, int peso, int i, int j){
        this.c = c;
        this.peso = peso;
        this.i = i;
        this.j = j;
        tempoChegada = 218309120;
        visitado = false;
    }

    public void visitar() {
        this.visitado = true;

    }


    public void pontoPartida() {
        this.tempoChegada = 0;
    }
}


class Heap{
    No[] heap;
    int maxsize;
    int size;

    Heap(){
        heap = new No[10];
        maxsize = 10;
        size = 0;
    }

    public int isInMinHeap(int i, int j) {
        int aux = 0;
        while (aux < this.size) {
            if (this.heap[aux].i == i && this.heap[aux].j == j)
                break;
            aux++;
        }
        if (aux != this.size)
            return aux;
        else
            return -1;
    }

    Heap(int i) {
        heap = new No[i];
        maxsize = i;
        size = 0;
    }

    No[] duplica(){
        No[] aux = new No [2*maxsize];

        for (int i = 0; i < maxsize; i++) {
            aux[i] = heap[i];
        }
        maxsize =  2*maxsize;
        return aux;
    }

    void inserir(No n){
        if(size == maxsize){
            heap = duplica();
        }
        heap[size] = n;
        size++;
    }

    No remover (){
        No t =  null;
        buildMinHeap();

        if(heap[0] != null){
            t = heap[0];
            heap[0] = heap[size-1];
            heap[size-1] = null;
            size--;
        }
        return t;
    }


    void buildMinHeap(){
        for (int i = size/2; i >= 0; i--) {
            minHeapfy(i);
        }
    }
    void minHeapfy(int indice){
        int l = 2*indice +1, r = 2*indice + 2, max = indice;

        if(l < size && heap[l].tempoChegada < heap[max].tempoChegada){
            max = l;
        }
        if(r < size && heap[r].tempoChegada < heap[max].tempoChegada){
            max = r;
        }

        if(max != indice){
            No aux = heap[indice];
            heap[indice] = heap[max];
            heap[max] =aux;
            minHeapfy(max);
        }
    }


}