SHARE
TWEET

Untitled

a guest Oct 21st, 2019 92 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.                     maze[j][i] = s.nextInt();
  19.                 else
  20.                 {
  21.                     if (s.next().equalsIgnoreCase("S"))
  22.                     {
  23.                         maze[j][i] = 2;
  24.                         startX = j;
  25.                         startY = i;
  26.                     }
  27.                     else
  28.                         if (s.next().equalsIgnoreCase("E"))
  29.                             maze[j][i] = -1;
  30.                 }
  31.             }
  32.         }
  33.         System.out.println("The shortest path to the exit: " + bfs(maze, new Pair<>(startX, startY)));
  34.  
  35.     }
  36.  
  37.     public static int bfs(int[][] maze, Pair<Integer, Integer> start)
  38.     {
  39.         boolean[][] visited = new boolean[10][5];
  40.         int[][] distance = new int[10][5];
  41.  
  42.         LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();
  43.         // Where the maze starts
  44.         queue.add(start);
  45.         distance[start.getKey()][start.getValue()] = 0;
  46.         visited[start.getKey()][start.getValue()] = true;
  47.  
  48.         while (!queue.isEmpty())
  49.         {
  50.             Pair<Integer, Integer> p = queue.poll();
  51.             int x = p.getKey(), y = p.getValue();
  52.  
  53.             // find neighbors
  54.             for (int i = -1; i <= 1; i += 2)
  55.             {
  56.                 // valid neighbors
  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.                         return distance[x][y] + 1;
  62.                     else
  63.                         if (!visited[x + i][y])
  64.                         {
  65.                             visited[x + i][y] = true;
  66.                             distance[x + i][y] = distance[x][y] + 1;
  67.                             queue.push(new Pair<>(x + i, y));
  68.                         }
  69.             }
  70.             for (int j = -1; j <= 1; j++)
  71.             {
  72.                 // valid neighbors
  73.                 if (x < 0 || y + j < 0 || x >= 10 || y + j >= 5 || maze[x][y + j] == 1)
  74.                     continue;
  75.                 else
  76.                     if (maze[x][y + j] == -1)
  77.                         return distance[x][y] + 1;
  78.                     else
  79.                         if (!visited[x][y + j])
  80.                         {
  81.                             visited[x][y + j] = true;
  82.                             distance[x][y + j] = distance[x][y] + 1;
  83.                             queue.push(new Pair<>(x, y + j));
  84.                         }
  85.             }
  86.         }
  87.         return 0;
  88.     }
  89.  
  90. }
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