ForunsBB

/*********************************************
*                                                                            *
*          Desenvolvido numa aula de prog2 por:          *
*                                                                            *
*                            João Pina                                  *
*                                                                            *
*********************************************/
import genclass.*;
import p2.*;
import static genclass.GenericIO.*;

public class Labirinto {
 
  public static final int pausa = 250; // tempo de espera em cada passo da procura [ms]

  public static void main(String[] args) {
    if (args.length != 1) {
      writelnString("USO: java -ea Labirinto MAPA");
      System.exit(1);
    }

    Mapa mapa = leMapa(args[0]);

    Coord pontoInicial = pontoDePartida(mapa);
    if (pontoInicial == null) {
      writelnString("Falta um ponto de partida!");
      System.exit(2);
    }
   
    limpaConsola();
    desenhaMapa (mapa);
    procuraCaminho(mapa, 0, pontoInicial.x, pontoInicial.y);
  }
 
  /** Procura o percurso até ao destino (X) utilizando backtracking
   * @param distancia número actual de steps
   * @param x coordenada actual
   * @param y coordenada actual
   * @return true se encontrou solução, false se não.
   */
  public static boolean procuraCaminho (Mapa mapa, int distancia, int x, int y) {
    boolean result = false;

    if (dentroDoMapa(mapa, x, y)) {
      /* Ponto de chegada? */
      if (eChegada(mapa,x,y)) {
        defineCursor(0,mapa.dimY + 1);
   writelnString("Encontrou o destino em " + distancia + " passos");
   writelnString("");
   result = true;
      } else if (posicaoLivre(mapa,x,y)) {
   marcaPosicao(mapa,x,y);    // marca este lugar
   if (procuraCaminho (mapa, distancia+1, x-1, y))       // Procura a Oeste
     result = true;
   else if (procuraCaminho (mapa, distancia+1, x, y+1))  // Procura a Sul
     result = true;
   else if (procuraCaminho (mapa, distancia+1, x+1, y))  // Procura a Este
     result = true;
   else if (procuraCaminho (mapa, distancia+1, x, y-1))  // Procura a Norte
     result = true;
   else {  // se não encontrou solução:
     limpaPosicao(mapa,x,y);  // desmarca este lugar
   }
      }
    }
    return result;
  }
 
  /** Estou dentro? */
  static boolean dentroDoMapa(Mapa mapa, int x, int y) {
    assert mapa != null;

    return  0 <= y && y < mapa.dimY &&
            0 <= x && x < mapa.celulas[y].length;
  }
 
  /** Atingi a chegada? */
  static boolean eChegada(Mapa mapa, int x, int y) {
    assert dentroDoMapa(mapa, x, y);

    return mapa.celulas[y][x] == mapa.CH_CHEGADA;
  }
 
  /** Ponto de partida */
  static boolean ePartida(Mapa mapa, int x, int y) {
    assert dentroDoMapa(mapa, x, y);

    return mapa.celulas[y][x] == mapa.CH_PARTIDA ||
           mapa.celulas[y][x] == mapa.CH_MARCA_PARTIDA;
  }
 
  /** Está livre? */
  static boolean posicaoLivre(Mapa mapa, int x, int y) {
    assert dentroDoMapa(mapa, x, y);

    return mapa.celulas[y][x] == mapa.CH_CAMINHO ||
           mapa.celulas[y][x] == mapa.CH_PARTIDA;
  }
 
  /** Está marcada? */
  static boolean posicaoMarcada(Mapa mapa, int x, int y) {
    assert dentroDoMapa(mapa, x, y);

    return mapa.celulas[y][x] == mapa.CH_MARCA ||
           mapa.celulas[y][x] == mapa.CH_MARCA_PARTIDA;
  }
 
  /** Coloca marca na posição (x,y) do mapa */
  static void marcaPosicao(Mapa mapa, int x, int y) {
    assert dentroDoMapa(mapa,x,y) && posicaoLivre(mapa,x,y);

    if (ePartida(mapa,x,y))
      mapa.celulas[y][x] = mapa.CH_MARCA_PARTIDA;
    else
      mapa.celulas[y][x] = mapa.CH_MARCA;
    desenhaPonto(mapa,x,y,mapa.celulas[y][x]);
  }

  /** Limpa marca da posição (x,y) do mapa */
  static void limpaPosicao(Mapa mapa, int x, int y) {
    assert dentroDoMapa(mapa,x,y) && posicaoMarcada(mapa,x,y);

    if (ePartida(mapa,x,y))
      mapa.celulas[y][x] = mapa.CH_PARTIDA;
    else
      mapa.celulas[y][x] = mapa.CH_CAMINHO;
    desenhaPonto(mapa,x,y,mapa.celulas[y][x]);
  }

  /**
   * Carrega o mapa do labirinto
   */ 
  public static Mapa leMapa(String nome) {
    TextFile file = new TextFile();
    if (! file.openForReading(FileName.parentDirectory(nome),
                         FileName.childName(nome)) ) {
      writelnString("Não consegui abrir "+file);
      System.exit(3);
    }
    Mapa mapa = new Mapa();
    int y;
    for(y=0; !file.endOfFile(); y++) {
      assert y < mapa.MAX_DIM_Y; // erro interno (falta de espaço no array)!
      mapa.celulas[y] = file.readlnString().toCharArray();
    }
    mapa.dimY = y;
    file.close();

    return mapa;
  }
 
  /**
   *  Imprime o mapa do labirinto
   */
  static void desenhaMapa(Mapa mapa) {
    assert mapa != null;

    defineCursor(0,0);
    for(int y=0; y<mapa.dimY; y++) {
      for (int x=0; x<mapa.celulas[y].length ; x++)
        writeChar(mapa.celulas[y][x]);
      writelnString("");
    }
    writelnString("");
  }

  static void desenhaPonto(Mapa mapa,int x,int y,char c) {
    defineCursor(x,y);
    writeChar(c);
    defineCursor(0,mapa.dimY + 1);
    wait_A_Bit(pausa);
  }

  /** Determina as coordenadas do ponto de partida do labirinto
   *  @return record tipo "Coord" com as coordenadas do ponto de partida
   */ 
  static Coord pontoDePartida(Mapa mapa) {
    assert mapa != null;

    Coord result = null;

    for(int y=0;(result == null) && y<mapa.dimY; y++)
      for (int x=0;(result == null) && x<mapa.celulas[y].length ; x++)
        if (ePartida(mapa,x,y)) {
          result = new Coord();
          result.y = y;
          result.x = x;
        }

    return result;
  }
 
  /**
   *  Limpa a Consola (stdout)
   */
  static void limpaConsola() {
    writeString("\u001B[2J");
  }

  /** Coloca o cursor numa determinada posição da consola
   *  @param x coordenada
   *  @param y coordenada
   */
  static void defineCursor(int x, int y) {
    assert 0<=x && 0<=y;
    // coordenadas começam em (0,0)
    writeString(String.format("\u001B[%d;%df", 1+y, 1+x));
  }
       
   /** Interrompe o programa por determinado período de tempo
   *  @param pausa período de tempo (1000 = 1 seg)
   */
  static void wait_A_Bit(long pausa) {
    try {
      Thread.sleep(pausa);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
  }
}

class Coord {
  int x;
  int y;
}

class Mapa {
  int dimY = 0;
  char[][] celulas = new char[MAX_DIM_Y][];

  static final int MAX_DIM_Y = 128;

  static final char CH_PARTIDA         = 'S';
  static final char CH_CHEGADA         = 'X';
  static final char CH_CAMINHO         = ' ';
  static final char CH_MARCA           = 'o';
  static final char CH_MARCA_PARTIDA   = 's';
}

########################
#          #       #   #
# ####### ## # #  #  # #
#     # #    # # ### # #
##### # ###### #   ### #
#   # #     ## ### # # #
## #  #####        #   #
## ## #### ### ##### ###
#   #      # # #  ## ###
# ######## # # ##     ##
# #   X    # # ###### ##
# # ###### # #    ##  ##
# # #      # #### #   ##
# # # ####      # # # ##
# # # ######### # # # ##
# # #         # # # # ##
# # #  # ## # # # # # ##
# # # # ## # ## # ### ##
#   #                  #
## ################ ####
## #####     #####     S
##     # # ###   ##### #
## # #   #     #       #
########################