Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.34 KB | None | 0 0
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. import java.awt.Point;
  8.  
  9. /* Name of the class has to be "Main" only if the class is public. */
  10. class Ideone
  11. {
  12.     public static void main (String[] args) throws java.lang.Exception
  13.     {
  14.         Scanner in = new Scanner(System.in);
  15.        
  16.         int n = in.nextInt();
  17.         int[][] field = new int[n][n];
  18.         for (int i = 0; i < n; ++i) {
  19.             for (int j = 0; j < n; ++j) {
  20.                 field[i][j] = in.nextInt();
  21.             }
  22.         }
  23.        
  24.         Point start = new Point(in.nextInt() - 1, in.nextInt() - 1);
  25.         Point end = new Point(in.nextInt() - 1, in.nextInt() - 1);
  26.        
  27.         List<Point> path = findPath(field, start, end);
  28.         for (Point cell : path) {
  29.             System.out.println((cell.x + 1) + " " + (cell.y + 1));
  30.         }
  31.     }
  32.    
  33.     final static int EMPTY = 0, WALL = 1;
  34.     final static List<Point> NO_PATH = new ArrayList<>();
  35.    
  36.     static List<Point> findPath(int[][] field, Point start, Point end) {
  37.         int n = field.length;
  38.        
  39.         final int INF = n * n + 1;
  40.        
  41.         int[][] distances = new int[n][n];
  42.         for (int[] d1 : distances) Arrays.fill(d1, INF);
  43.        
  44.         Point[][] parents = new Point[n][n];
  45.         Queue<Point> queue = new ArrayDeque<>();
  46.        
  47.         if (field[start.x][start.y] == WALL) return NO_PATH;
  48.        
  49.         distances[start.x][start.y] = 0;
  50.         queue.add(start);
  51.        
  52.         int[][] steps = {
  53.             { -1, -1 }, { -1, 0 }, { -1, 1 },
  54.             { 0, -1 }, { 0, 1 },
  55.             { 1, -1 }, { 1, 0 }, { 1, 1 }
  56.         };
  57.        
  58.         while (queue.size() > 0) {
  59.             Point from = queue.poll();
  60.            
  61.             for (int[] step : steps) {
  62.                 int toX = from.x + step[0];
  63.                 int toY = from.y + step[1];
  64.                
  65.                 if (!checkCell(toX, n, toY, n)) continue;
  66.                 if (distances[toX][toY] != INF) continue;
  67.                 if (field[toX][toY] == WALL) continue;
  68.                
  69.                 distances[toX][toY] = distances[from.x][from.y] + 1;
  70.                 queue.add(new Point(toX, toY));
  71.                 parents[toX][toY] = from;
  72.             }
  73.         }
  74.        
  75.         if (distances[end.x][end.y] == INF) return NO_PATH;
  76.        
  77.         List<Point> path = new ArrayList<>();
  78.         for (Point cur = end; cur != parents[start.x][start.y];
  79.             cur = parents[cur.x][cur.y]) {
  80.             path.add(cur);
  81.         }
  82.         Collections.reverse(path);
  83.         return path;
  84.     }
  85.    
  86.     static boolean checkCell(int x, int n, int y, int m) {
  87.         return checkIndex(x, n) && checkIndex(y, m);
  88.     }
  89.    
  90.     static boolean checkIndex(int index, int size) {
  91.         return 0 <= index && index < size;
  92.     }
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement