Advertisement
Guest User

Untitled

a guest
Dec 9th, 2016
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.78 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class labirinto {
  5.     static final int CIMA = 1;
  6.     static final int BAIXO = 0;
  7.     static int l;
  8.     static int c;
  9.     static boolean visited[][][];  // Que nos ja foram visitados?
  10.     static char matriz[][];  // para ter acesso à minha matriz nas diferentes funções do meu programa
  11.     static int encontrado; // para contar as componentes ligadas (caminho) do meu grafo/matriz
  12.     static int contador; //para contar o nº de nós
  13.     static int maximo;
  14.  
  15.     static void dfs(int y, int x, int lado, int ipai, int jpai, int side) {
  16.  
  17.     if(x<c && x>=0 && y<l && y>=0 && !visited[y][x][lado]){
  18.         contador++;
  19.         System.out.println(contador);
  20.         if (lado == BAIXO){
  21.         visited[y][x][BAIXO] = true;
  22.         System.out.println("estou em baixo");
  23.         dfs(y+1, x, CIMA, ipai, jpai, side);
  24.        
  25.         if(matriz[y][x] == '/'){
  26.             if((x+1)<c && (x+1)>=0 && y<l && y>=0 && matriz[y][x+1] == '/')
  27.             dfs(y, x+1, CIMA, ipai, jpai, side);  //dependendo da barra  seguinte vou parar em CIMA ou em BAIXO
  28.             if((x+1)<c && (x+1)>=0 && y<l && y>=0 && matriz[y][x+1] == '\\')
  29.             dfs(y, x+1, BAIXO, ipai, jpai, side);
  30.         }
  31.         if(matriz[y][x] == '\\'){
  32.             if((x-1)<c && (x-1)>=0 && y<l && y>=0 && matriz[y][x-1] == '/')
  33.             dfs(y, x-1, BAIXO, ipai, jpai, side);  //dependendo da barra  seguinte vou parar em CIMA ou em BAIXO
  34.             if((x-1)<c && (x-1)>=0 && y<l && y>=0 && matriz[y][x-1] == '\\')
  35.             dfs(y, x-1, CIMA, ipai, jpai, side);
  36.         }
  37.         }
  38.         if(lado == CIMA){
  39.         visited[y][x][CIMA] = true;
  40.         System.out.println("estou em cima");
  41.         dfs(y-1, x, BAIXO, ipai, jpai, side);
  42.        
  43.         if(matriz[y][x] == '/'){
  44.             if((x-1)<c && (x-1)>=0 && y<l && y>=0 && matriz[y][x-1] == '/')
  45.             dfs(y, x-1, BAIXO, ipai, jpai, side);  //dependendo da barra  seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
  46.             if( (x-1)<c && (x-1)>=0 && y<l && y>=0 && matriz[y][x-1] == '\\')
  47.             dfs(y, x-1, CIMA, ipai, jpai, side);
  48.         }
  49.         if(matriz[y][x] == '\\'){
  50.             if((x+1)<c && (x+1)>=0 && y<l && y>=0 && matriz[y][x+1] == '/')
  51.             dfs(y, x+1, CIMA, ipai, jpai, side);  //dependendo da barra  seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
  52.             if((x+1)<c && (x+1)>=0 && y<l && y>=0 && matriz[y][x+1] == '\\')
  53.             dfs(y, x+1, BAIXO, ipai, jpai, side);
  54.         }
  55.         }
  56.     }
  57.     if(x<c && x>=0 && y<l && y>=0 && visited[y][x][lado] && contador>2){ //cheguei a um que já foi visitado
  58.         System.out.println("Entrei");
  59.         if(x==jpai && y==ipai && lado==side){ //vou vêr se é o que deu origem a dfs ("pai") // esta condição não é verificada, como posso verificar se o no onde me encontro é o no pai??
  60.         encontrado++;
  61.         System.out.println("papá!!!");
  62.         if (contador > maximo){
  63.             maximo = contador; //contei os nos do meu ciclo, comparo com o maximo e atualizo
  64.         }
  65.         }
  66.     }
  67.     }
  68.  
  69.     public static void main(String args[]) {
  70.     Scanner stdin = new Scanner(System.in);
  71.    
  72.     c = stdin.nextInt();
  73.         l = stdin.nextInt();
  74.     int lado = 2;
  75.     matriz  = new char [l][c];
  76.     visited = new boolean [l][c][lado];
  77.  
  78.     for(int k=0; k<l; k++){
  79.         matriz[k] = stdin.next().toCharArray();
  80.         //System.out.println(matriz[i]);
  81.     }
  82.  
  83.     for(int k=0; k<l; k++){
  84.         for(int m=0; m<c; m++){
  85.         visited[k][m][CIMA] = false;
  86.         visited[k][m][BAIXO] = false;
  87.         }
  88.     }
  89.  
  90.     encontrado = 0;
  91.  
  92.     for (int i=0; i<l; i++){
  93.         for (int j=0; j<c; j++){
  94.         if (!visited[i][j][BAIXO]) {
  95.             contador = 0;
  96.             dfs(i, j, BAIXO, i, j, CIMA);
  97.         }
  98.         if(!visited[i][j][CIMA]){
  99.             contador = 0;
  100.             dfs(i, j, CIMA, i, j, BAIXO);
  101.         }
  102.         }
  103.     }
  104.  
  105.     if(encontrado==0) //não encontrou nenhum ciclo
  106.         System.out.println("nao tem ciclos");
  107.     else
  108.         System.out.println(encontrado + " "+ maximo); // encontrou x ciclos, o ciclo maior tem y nos
  109.     }
  110. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement