Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* package whatever; // don't place package name! */
- import java.util.*;
- import java.lang.*;
- import java.io.*;
- import java.awt.Point;
- /* Name of the class has to be "Main" only if the class is public. */
- class Ideone
- {
- public static void main (String[] args) throws java.lang.Exception
- {
- Scanner in = new Scanner(System.in);
- int n = in.nextInt();
- int[][] field = new int[n][n];
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- field[i][j] = in.nextInt();
- }
- }
- Point start = new Point(in.nextInt() - 1, in.nextInt() - 1);
- Point end = new Point(in.nextInt() - 1, in.nextInt() - 1);
- List<Point> path = findPath(field, start, end);
- for (Point cell : path) {
- System.out.println((cell.x + 1) + " " + (cell.y + 1));
- }
- }
- final static int EMPTY = 0, WALL = 1;
- final static List<Point> NO_PATH = new ArrayList<>();
- static List<Point> findPath(int[][] field, Point start, Point end) {
- int n = field.length;
- final int INF = n * n + 1;
- int[][] distances = new int[n][n];
- for (int[] d1 : distances) Arrays.fill(d1, INF);
- Point[][] parents = new Point[n][n];
- Queue<Point> queue = new ArrayDeque<>();
- if (field[start.x][start.y] == WALL) return NO_PATH;
- distances[start.x][start.y] = 0;
- queue.add(start);
- int[][] steps = {
- { -1, -1 }, { -1, 0 }, { -1, 1 },
- { 0, -1 }, { 0, 1 },
- { 1, -1 }, { 1, 0 }, { 1, 1 }
- };
- while (queue.size() > 0) {
- Point from = queue.poll();
- for (int[] step : steps) {
- int toX = from.x + step[0];
- int toY = from.y + step[1];
- if (!checkCell(toX, n, toY, n)) continue;
- if (distances[toX][toY] != INF) continue;
- if (field[toX][toY] == WALL) continue;
- distances[toX][toY] = distances[from.x][from.y] + 1;
- queue.add(new Point(toX, toY));
- parents[toX][toY] = from;
- }
- }
- if (distances[end.x][end.y] == INF) return NO_PATH;
- List<Point> path = new ArrayList<>();
- for (Point cur = end; cur != parents[start.x][start.y];
- cur = parents[cur.x][cur.y]) {
- path.add(cur);
- }
- Collections.reverse(path);
- return path;
- }
- static boolean checkCell(int x, int n, int y, int m) {
- return checkIndex(x, n) && checkIndex(y, m);
- }
- static boolean checkIndex(int index, int size) {
- return 0 <= index && index < size;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement