SHARE
TWEET

Untitled

a guest Oct 21st, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.LinkedList;
  2. import java.util.Scanner;
  3. import javafx.util.Pair;
  4.  
  5. public class Test3
  6. {
  7.     public static void main(String[] args)
  8.     {
  9.         Scanner s = new Scanner(System.in);
  10.         int[][] maze = new int[10][5];
  11.         int startX = 0, startY = 0;
  12.        
  13.         for (int i = 0; i < 5; i++)
  14.         {
  15.             for (int j = 0; j < 10; j++)
  16.             {
  17.                 if (s.hasNextInt())
  18.                    
  19.                     maze[j][i] = s.nextInt();
  20.                 else
  21.                 {
  22.                     if (s.next().equalsIgnoreCase("S"))
  23.                     {
  24.                         maze[j][i] = 2;
  25.                         startX = j;
  26.                         startY = i;
  27.                     }
  28.                     else if (s.next().equalsIgnoreCase("E"))
  29.                         maze[j][i] = -1;
  30.                 }
  31.                 System.out.println("Recorded: (" + j + ", " + i + ")");
  32.             }
  33.         }
  34.         System.out.println("The shortest path to the exit: " + bfs(maze, new Pair<>(startX, startY)));
  35.  
  36.     }
  37.    
  38.     public static int bfs(int[][] maze, Pair<Integer, Integer> start)
  39.     {
  40.         boolean[][] visited = new boolean[10][5];
  41.         int[][] distance = new int[10][5];
  42.        
  43.         LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();
  44.         // Where the maze starts
  45.         queue.add(start);
  46.         distance[start.getKey()][start.getValue()] = 0;
  47.         visited[start.getKey()][start.getValue()] = true;
  48.  
  49.         while (!queue.isEmpty())
  50.         {
  51.             Pair<Integer, Integer> p = queue.poll();
  52.             int x = p.getKey(), y = p.getValue();
  53.            
  54.             // find neighbors
  55.             for (int i = -1; i <= 1; i += 2)
  56.             {
  57.                 if (x + i < 0 || y < 0 || x + i >= 10 || y >= 5 || maze[x + i][y] == 1)
  58.                     continue;
  59.                 else
  60.                     if (maze[x + i][y] == -1)
  61.                     {
  62.                         System.out.println("Visited: (" + (x + i) + ", " + (y) + ")");
  63.                         return distance[x][y] + 1;
  64.                     }
  65.                     else
  66.                         if (!visited[x + i][y])
  67.                         {
  68.                             visited[x + i][y] = true;
  69.                             distance[x + i][y] = distance[x][y] + 1;
  70.                             System.out.println("Distance of (" + (x + i) + ", " + (y) + ") is" + (distance[x][y] + 1));
  71.                             queue.push(new Pair<>(x + i, y));
  72.                             System.out.println("Origin: (" + x + ", " + y + "), Visited: (" + (x + i) + ", " + (y) + ")");
  73.                         }
  74.             }
  75.             for (int j = -1; j <= 1; j++)
  76.             {
  77.                 // valid neighbors
  78.                 if (x < 0 || y + j < 0 || x >= 10 || y + j >= 5 || maze[x][y + j] == 1)
  79.                     continue;
  80.                 else
  81.                     if (maze[x][y + j] == -1)
  82.                     {
  83.                         System.out.println("Visited: (" + (x) + ", " + (y + j) + ")");
  84.                         return distance[x][y] + 1;
  85.                     }
  86.                     else
  87.                         if (!visited[x][y + j])
  88.                         {
  89.                             visited[x][y + j] = true;
  90.                             distance[x][y + j] = distance[x][y] + 1;
  91.                             System.out.println("Distance of (" + (x) + ", " + (y + j) + ") is" + (distance[x][y] + 1));
  92.                             queue.push(new Pair<>(x, y + j));
  93.                             System.out.println("Origin: (" + x + ", " + y + "), Visited: (" + (x) + ", " + (y + j) + ")");
  94.                         }
  95.             }
  96.         }
  97.         return 0;
  98.     }
  99.    
  100. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top