Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class daa021 {
- static final int CIMA = 1;
- static final int BAIXO = 0;
- static int l;
- static int c;
- static boolean visited[][][]; // Que nos ja foram visitados?
- static char matriz[][]; // para ter acesso à minha matriz nas diferentes funções do meu programa
- static int encontrado; // para contar as componentes ligadas (caminho) do meu grafo/matriz
- static int contador; //para contar o nº de nós
- static int maximo;
- static void dfs(int y, int x, int lado) {
- if(visited[y][x][lado] && contador>2 && x<c && x>=0 && y<l && y>=0){
- encontrado++;
- if (contador > maximo) maximo = contador; //contei os nos do meu ciclo, comparo com o maximo e atualizo
- }
- if(!visited[y][x][lado] && x<c && x>=0 && y<l && y>=0){
- contador++;
- if (lado == BAIXO){
- visited[y][x][BAIXO] = true;
- dfs(y+1, x, CIMA);
- if(matriz[y][x] == '/'){
- if(matriz[y][x+1] == '/' && (x+1)<c && (x+1)>=0 && y<l && y>=0)
- dfs(y, x+1, CIMA); //dependendo da barra seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
- if(matriz[y][x+1] == '\\' && (x+1)<c && (x+1)>=0 && y<l && y>=0)
- dfs(y, x+1, BAIXO);
- }
- if(matriz[y][x] == '\\'){
- if(matriz[y][x-1] == '/' && (x-1)<c && (x-1)>=0 && y<l && y>=0)
- dfs(y, x-1, BAIXO); //dependendo da barra seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
- if(matriz[y][x-1] == '\\' && (x-1)<c && (x-1)>=0 && y<l && y>=0)
- dfs(y, x-1, CIMA);
- dfs(y, x-1, lado);
- }
- }
- if(lado == CIMA){
- visited[y][x][CIMA] = true;
- dfs(y-1, x, BAIXO);
- if(matriz[y][x] == '/'){
- if(matriz[y][x-1] == '/' && (x-1)<c && (x-1)>=0 && y<l && y>=0)
- dfs(y, x-1, BAIXO); //dependendo da barra seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
- if(matriz[y][x-1] == '\\' && (x-1)<c && (x-1)>=0 && y<l && y>=0)
- dfs(y, x-1, CIMA);
- }
- if(matriz[y][x] == '\\'){
- if(matriz[y][x+1] == '/' && (x+1)<c && (x+1)>=0 && y<l && y>=0)
- dfs(y, x+1, CIMA); //dependendo da barra seguinte vou parar em CIMA ou em BAIXO, como vejo o seguinte???
- if(matriz[y][x+1] == '\\' && (x+1)<c && (x+1)>=0 && y<l && y>=0)
- dfs(y, x+1, BAIXO);
- }
- }
- }
- }
- public static void main(String args[]) {
- Scanner stdin = new Scanner(System.in);
- c = stdin.nextInt();
- l = stdin.nextInt();
- int lado = 2;
- matriz = new char [l][c];
- visited = new boolean [l][c][lado];
- for(int k=0; k<l; k++){
- matriz[k] = stdin.next().toCharArray();
- //System.out.println(matriz[i]);
- encontrado = 0;
- for (int i=0; i<l; i++){
- for (int j=0; j<c; j++){
- if (!visited[i][j][BAIXO]) {
- contador = 0;
- dfs(i, j, BAIXO);
- }
- if(!visited[i][j][CIMA]){
- contador = 0;
- dfs(i, j, CIMA);
- }
- }
- }
- if(encontrado==0) //não encontrou nenhum ciclo
- System.out.println("nao tem ciclos");
- else
- System.out.println(encontrado + " "+ maximo); // encontrou x ciclos, o ciclo maior tem y nos
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement