Advertisement
Guest User

Untitled

a guest
Dec 6th, 2016
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.05 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class daa021 {
  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) {
  16.     if(visited[y][x][lado] && contador>2 && x<c && x>=0 && y<l && y>=0){
  17.         encontrado++;
  18.         if (contador > maximo) maximo = contador; //contei os nos do meu ciclo, comparo com o maximo e atualizo
  19.     }
  20.     if(!visited[y][x][lado] && x<c && x>=0 && y<l && y>=0){
  21.         contador++;
  22.         if (lado == BAIXO){
  23.         visited[y][x][BAIXO] = true;
  24.         dfs(y+1, x, CIMA);
  25.        
  26.         if(matriz[y][x] == '/'){
  27.             if(matriz[y][x+1] == '/' && (x+1)<c && (x+1)>=0 && y<l && y>=0)
  28.             dfs(y, x+1, CIMA);  //dependendo da barra  seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
  29.             if(matriz[y][x+1] == '\\' && (x+1)<c && (x+1)>=0 && y<l && y>=0)
  30.             dfs(y, x+1, BAIXO);
  31.         }
  32.         if(matriz[y][x] == '\\'){
  33.             if(matriz[y][x-1] == '/' && (x-1)<c && (x-1)>=0 && y<l && y>=0)
  34.             dfs(y, x-1, BAIXO);  //dependendo da barra  seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
  35.             if(matriz[y][x-1] == '\\' && (x-1)<c && (x-1)>=0 && y<l && y>=0)
  36.             dfs(y, x-1, CIMA);
  37.             dfs(y, x-1, lado);
  38.         }
  39.         }
  40.         if(lado == CIMA){
  41.         visited[y][x][CIMA] = true;
  42.         dfs(y-1, x, BAIXO);
  43.        
  44.         if(matriz[y][x] == '/'){
  45.             if(matriz[y][x-1] == '/' && (x-1)<c && (x-1)>=0 && y<l && y>=0)
  46.             dfs(y, x-1, BAIXO);  //dependendo da barra  seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
  47.             if(matriz[y][x-1] == '\\' && (x-1)<c && (x-1)>=0 && y<l && y>=0)
  48.             dfs(y, x-1, CIMA);
  49.         }
  50.         if(matriz[y][x] == '\\'){
  51.             if(matriz[y][x+1] == '/' && (x+1)<c && (x+1)>=0 && y<l && y>=0)
  52.             dfs(y, x+1, CIMA);  //dependendo da barra  seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
  53.             if(matriz[y][x+1] == '\\' && (x+1)<c && (x+1)>=0 && y<l && y>=0)
  54.             dfs(y, x+1, BAIXO);
  55.         }
  56.         }
  57.     }
  58.     }
  59.  
  60.     public static void main(String args[]) {
  61.     Scanner stdin = new Scanner(System.in);
  62.    
  63.     c = stdin.nextInt();
  64.         l = stdin.nextInt();
  65.     int lado = 2;
  66.     matriz  = new char [l][c];
  67.     visited = new boolean [l][c][lado];
  68.  
  69.     for(int k=0; k<l; k++){
  70.         matriz[k] = stdin.next().toCharArray();
  71.         //System.out.println(matriz[i]);
  72.  
  73.     encontrado = 0;
  74.  
  75.     for (int i=0; i<l; i++){
  76.         for (int j=0; j<c; j++){
  77.         if (!visited[i][j][BAIXO]) {
  78.             contador = 0;
  79.             dfs(i, j, BAIXO);
  80.         }
  81.         if(!visited[i][j][CIMA]){
  82.             contador = 0;
  83.             dfs(i, j, CIMA);
  84.         }
  85.         }
  86.     }
  87.  
  88.     if(encontrado==0) //não encontrou nenhum ciclo
  89.         System.out.println("nao tem ciclos");
  90.     else
  91.         System.out.println(encontrado + " "+ maximo); // encontrou x ciclos, o ciclo maior tem y nos
  92.     }
  93.     }
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement