Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

fim!

By: a guest on May 27th, 2012  |  syntax: None  |  size: 7.41 KB  |  hits: 13  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <memory>
  4. #include <stdlib.h>
  5.  
  6. using namespace std;
  7.  
  8. /* THAÍS COSTELLA - EP 4 - O RATO E O QUEIJO
  9.  
  10.    O programa recebe como entrada dois números que correnspondem ao número
  11.    de linhas e colunas do labirinto e sua configuração (-1 para obstaculo, 0
  12.    para posição livre, -2 para o rato e -3 para o queijo. Ao final ele devolve
  13.    a menor distância a ser percorrida pelo rato até o queijo*/
  14.  
  15. struct Noh{
  16.        Noh(int valor = -17, int linha = -17, int coluna = -17, Noh* anterior = NULL, Noh* proximo = NULL){
  17.                distancia_ = valor;
  18.                linha_ = linha;
  19.                coluna_ = coluna;
  20.                anter_ = anterior;
  21.                prox_ = proximo;}    
  22.        int distancia_;
  23.        int linha_;
  24.        int coluna_;
  25.        Noh* prox_;
  26.        Noh* anter_;};
  27.  
  28. struct Fila{
  29.        Fila(Noh* comeco_ = NULL){comeco = comeco_;}
  30.        Noh* comeco;};
  31.  
  32. struct Entrada{
  33.        int n_;
  34.        int m_;
  35.        int** tabuleiro_;};
  36.        
  37. struct Posicao{
  38.         int linhar;
  39.         int colunar;
  40.         int linhaq;
  41.         int colunaq;};
  42.        
  43. //______________________FUNÇÕES DA FILA IMPLEMENTADA COM LISTA DUPLAMENTE LIGADA  
  44.  
  45. // Função que constrói e retorna um apontador para o final da fila
  46. Noh* finalDaFila(Fila* fila){
  47.      
  48.      Noh* final = new Noh();
  49.      if(fila->comeco->prox_ == NULL){
  50.         final->anter_ = fila->comeco;
  51.         fila->comeco->prox_ = final;          
  52.         return final;
  53.      }
  54.      else{
  55.          Noh* percorre = fila->comeco->prox_;    
  56.          while(percorre->prox_ != NULL){
  57.               percorre = percorre->prox_;
  58.          }
  59.          final->anter_ = percorre;
  60.          percorre->prox_ = final;
  61.          return final;
  62.      }
  63. }
  64.  
  65. void insere(Fila* fila, int valor, int linha, int coluna){
  66.      Noh* novo = new Noh(valor, linha, coluna);
  67.      if(fila->comeco->prox_ == NULL){
  68.         novo->anter_ = fila->comeco;
  69.         fila->comeco->prox_ = novo;
  70.         return;
  71.      }
  72.      else{
  73.          Noh* percorre = fila->comeco->prox_;
  74.          while(percorre->prox_!= NULL){
  75.                percorre = percorre->prox_;
  76.          }
  77.          percorre->prox_ = novo;
  78.          novo->anter_ = percorre;
  79.      }
  80. }
  81.  
  82. void remove(Fila* fila){
  83.      if(fila->comeco->prox_ == NULL){
  84.         return;
  85.      }
  86.      else{
  87.          if(fila->comeco->prox_->prox_ == NULL){ //ou seja, só há um
  88.              Noh* deletado = fila->comeco->prox_;
  89.              fila->comeco->prox_ = NULL;
  90.              delete deletado;
  91.              return;
  92.          }
  93.          Noh* deletado = fila->comeco->prox_;
  94.          deletado->prox_->anter_ = fila->comeco;
  95.          fila->comeco->prox_ = deletado->prox_;
  96.          delete deletado;
  97.          return;
  98.      }
  99. }
  100.  
  101. bool vazia(Fila* fila){
  102.      Noh* final = finalDaFila(fila);
  103.      if(final->anter_ == fila->comeco) return true;
  104.      else return false;
  105. }
  106.  
  107. //____________________________________________________________FUNÇÕES AUXILIARES
  108.  
  109. // Função para ler e armazenar os dados de entrada
  110. Entrada entrada(){
  111.      
  112.      Entrada dados;
  113.      scanf("%d", &dados.n_);
  114.      scanf("%d", &dados.m_);
  115.      int** tabuleiro = (int**) calloc (dados.n_, sizeof(int*));
  116.      for (int i = 0; i < dados.n_; i++)
  117.          tabuleiro[i] = (int*) calloc (dados.m_, sizeof(int));
  118.      
  119.      for(int i=0; i < dados.n_; i++){    
  120.        for(int j=0; j < dados.m_; j++){
  121.          scanf("%d", &tabuleiro[i][j]);  
  122.         }
  123.      }
  124.      dados.tabuleiro_ = tabuleiro;
  125.      return dados;
  126. }
  127. // Função que procura e armazena as posições do rato e do queijo  
  128. Posicao posicaoRatoEqueijo(Entrada dados){
  129.      Posicao posicao;
  130.      for(int i=0; i < dados.n_; i++){    
  131.        for(int j=0; j < dados.m_; j++){
  132.          if(dados.tabuleiro_[i][j] != -2 && dados.tabuleiro_[i][j] != -3)
  133.             continue;
  134.          else{
  135.              if(dados.tabuleiro_[i][j] == -2){
  136.                posicao.linhar = i;
  137.                posicao.colunar = j; }
  138.              if(dados.tabuleiro_[i][j] == -3){
  139.                posicao.linhaq = i;
  140.                posicao.colunaq = j;}
  141.          }
  142.        }
  143.      }
  144.   return posicao;
  145. }
  146.  
  147. // Checa a validade de uma posição como vizinho(abaixo a explicação)
  148. bool vizinhoOK(Entrada dados, int linha_v, int coluna_v){
  149.      
  150.      if(linha_v >= 0 && linha_v < dados.n_ && coluna_v >= 0 && coluna_v < dados.m_){
  151.        if(dados.tabuleiro_[linha_v][coluna_v] >= 0) return true;
  152.        if(dados.tabuleiro_[linha_v][coluna_v] == -2) return true;
  153.      }
  154.      else return false;
  155. }
  156. //______________________________________________________________FUNÇÃO PRINCIPAL
  157.  
  158.  
  159. // Função que vai retornar a distância entre o rato e o queijo.
  160. // Calcula, a partir do queijo, as distâncias dos seus adjascentes (e adjascentes
  161. // de adjascentes) até o rato.
  162.  
  163. int calculaDistancias(Entrada dados, Posicao ratoEqueijo, Fila* fila){
  164.    
  165.     int distancia = 0;
  166.     int linha = ratoEqueijo.linhaq;
  167.     int coluna = ratoEqueijo.colunaq;
  168.    
  169.     insere(fila, distancia, linha, coluna); // coloco o queijo na fila
  170.    
  171.     while(true){
  172.    
  173.        // coloco todos os adjascentes daquela posicao (se forem válidos)
  174.        // na fila ( distancia + 1, linha_vizinho, coluna_vizinho)
  175.        if(vizinhoOK(dados, linha+1, coluna)){
  176.          insere(fila, distancia+1, linha+1, coluna);
  177.          // se essa posicao for o rato, aumenta 1 a distancia e sai do looping
  178.          if(dados.tabuleiro_[linha+1][coluna] == -2){
  179.             distancia = distancia + 1;
  180.             break;
  181.          }
  182.          // senão, muda o tabuleiro com -1 para indicar que já foi pra fila
  183.          dados.tabuleiro_[linha+1][coluna] = -1;
  184.        }
  185.        if(vizinhoOK(dados, linha-1, coluna)){
  186.          insere(fila, distancia+1, linha-1, coluna);
  187.          if(dados.tabuleiro_[linha-1][coluna] == -2){
  188.             distancia = distancia + 1;
  189.             break;
  190.          }
  191.          dados.tabuleiro_[linha-1][coluna] = -1;
  192.        }
  193.        if(vizinhoOK(dados, linha, coluna+1)){
  194.          insere(fila, distancia+1, linha, coluna+1);
  195.          if(dados.tabuleiro_[linha][coluna+1] == -2){
  196.             distancia = distancia + 1;
  197.             break;
  198.          }
  199.          dados.tabuleiro_[linha][coluna+1] = -1;
  200.        }
  201.        if(vizinhoOK(dados, linha, coluna-1)){
  202.          insere(fila, distancia+1, linha, coluna-1);
  203.          if(dados.tabuleiro_[linha][coluna-1] == -2){
  204.             distancia = distancia + 1;
  205.             break;
  206.          }
  207.          dados.tabuleiro_[linha][coluna-1] = -1;
  208.        }
  209.          
  210.             //tira o da primeira posicao
  211.             if(!vazia(fila)){
  212.                 remove(fila);
  213.             // vê quem está na ponta da fila
  214.                 linha = fila->comeco->prox_->linha_;
  215.                 coluna = fila->comeco->prox_->coluna_;
  216.                 distancia = fila->comeco->prox_->distancia_;
  217.             }
  218.             else{
  219.                 cout<<"não há solução";
  220.                 return 0;
  221.             }
  222.    }
  223.    
  224.  return distancia;
  225. }  
  226.    
  227. int main(int argc, char *argv[])
  228. {
  229.     Fila* fila = new Fila();
  230.     Noh* comeco = new Noh();
  231.     fila->comeco = comeco;
  232.    
  233.     Entrada dados = entrada();
  234.     Posicao ratoEqueijo = posicaoRatoEqueijo(dados);
  235.    
  236.     int x = calculaDistancias(dados, ratoEqueijo,fila);  
  237.    
  238.     cout << "\n" << x;
  239.    
  240.     delete fila;
  241.     delete comeco;
  242.    
  243.     system("PAUSE");
  244.     return EXIT_SUCCESS;
  245.    
  246. }
create a new version of this paste RAW Paste Data