fork(4) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone
  6. {
  7. 		public static void main(String[] args) {
  8.  
  9. 			Scanner scan = new Scanner(System.in);
  10. 			int tam = scan.nextInt();
  11. 			int inicio = scan.nextInt();
  12. 			int fim= scan.nextInt();
  13. 			int[][] ma = new int[8][8];
  14. 		    for (int i = 0; i < 8; ++i) {
  15. 		        for (int j = 0; j < 8; ++j) {
  16. 		            ma[i][j] = scan.nextInt();
  17. 		        }
  18. 		    }
  19. 		    scan.close();
  20.  
  21. 		    int distancias[] = buscaLateral(inicio, ma, 8);
  22. 		    System.out.println("Início: " + inicio);
  23. 		    System.out.println("Fim: " + fim);
  24. 			System.out.println("Menor distância do início ao fim: " + distancias[fim]);
  25. 		}
  26.  
  27. 		public static int[] buscaLateral(int inicio, int[][] ma, int tam){
  28.  
  29. 			int[] nivel = new int[tam];
  30. 			Queue<Integer> fila = new LinkedList<Integer>();
  31.  
  32. 			// Inicialinzando nivel de todos os vértices como -1
  33. 			for(int i=0; i<8; i++)
  34. 				nivel[i]=-1;
  35.  
  36. 			// O nível do vértice inicial é zero
  37. 			nivel[inicio] = 0;
  38. 			fila.add(inicio);
  39.  
  40. 			// Executando a busca lateral
  41. 			while(!fila.isEmpty()){
  42. 				int atual = fila.remove();
  43. 				for(int i = 0; i < 8; i++)
  44. 					if(ma(atual, i, ma) == 1 && nivel[i] == -1){
  45. 						nivel[i] = nivel[atual] + 1;
  46. 						fila.add(i);
  47. 					}
  48. 			}
  49.  
  50. 			return nivel;
  51. 		}
  52.  
  53. 		public static int ma(int i, int j, int[][] ma){
  54. 			if(i < j)
  55. 				return ma[i][j];
  56. 			else
  57. 				return ma[j][i];
  58. 		}
  59.  
  60. }
Success #stdin #stdout 0.06s 1373184KB
comments (?)
stdin
copy 
8 1 5
1 0 0 0 1 1 1 1
0 1 1 1 1 0 0 1
0 1 1 0 1 1 1 1
0 1 0 1 0 0 0 0
1 1 1 0 1 1 0 1
1 0 1 0 1 1 1 1
1 0 1 0 0 1 1 0
1 1 1 0 1 1 0 1
stdout
copy 
Início: 1
Fim: 5
Menor distância do início ao fim: 2
https://ideone.com/mOZexl
Resposta do Stack Overflow - Definir o menor caminho em grafos
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!