题解 | #迷宫问题#

5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

/**
 * 广度优先算法，顺序可以是上左下右，也可以是上右下左。无论怎么走，都可以找出最短路径
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int row = 0;
        int column = 0;
        int[][] grid = null;
        while (in.hasNext()) {
            row = in.nextInt();
            column = in.nextInt();
            grid = new int[row][column];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < column; j++) {
                    grid[i][j] = in.nextInt();
                }
            }
            walk(grid, new Point(0, 0), new Point(row - 1, column - 1));
            if (grid != null) {
                // 从右下角网上遍历
                Stack<Point> all = new Stack<>();
                int endValue = grid[row - 1][column - 1];
                Point cPoint = new Point(row - 1, column - 1);
                all.push(cPoint);
                while (!(cPoint.i == 0 && cPoint.j
                        == 0)) {
                    Point p = find(grid, endValue, cPoint);
                    cPoint = p;
                    endValue -= 1;
                    all.push(new Point(p.i, p.j));
                }
                while (!all.isEmpty()) {
                    Point pp = all.pop();
                    System.out.println("("+pp.i + "," + pp.j +")");
                }
            }
        }

    }


    private static Point find(int[][] grid, int endValue, Point currentPoint) {
        currentPoint.goUp();
        if (isAvil(grid, currentPoint) && grid[currentPoint.i][currentPoint.j] == endValue - 1) {
            Point newPoint = new Point(currentPoint.i, currentPoint.j);
            currentPoint.resetUp();
            return newPoint;
        }
        currentPoint.resetUp();
        currentPoint.goLeft();
        if (isAvil(grid, currentPoint) && grid[currentPoint.i][currentPoint.j] == endValue - 1) {
            Point newPoint = new Point(currentPoint.i, currentPoint.j);
            currentPoint.resetLeft();
            return newPoint;
        }
        currentPoint.resetLeft();
        currentPoint.goDown();
        if (isAvil(grid, currentPoint) && grid[currentPoint.i][currentPoint.j] == endValue - 1) {
            Point newPoint = new Point(currentPoint.i, currentPoint.j);
            currentPoint.resetDown();
            return newPoint;
        }
        currentPoint.resetDown();
        currentPoint.goRight();
        if (isAvil(grid, currentPoint) && grid[currentPoint.i][currentPoint.j] == endValue - 1) {
            Point newPoint = new Point(currentPoint.i, currentPoint.j);
            currentPoint.resetRight();
            return newPoint;
        }
        currentPoint.goRight();
        return null;
    }

    private static class Point {
        private int i, j;

        public Point(int i, int j) {
            this.i = i;
            this.j = j;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "i=" + i +
                    ", j=" + j +
                    '}';
        }

        public void goUp() {
            i--;
        }

        public void resetUp() {
            i++;
        }

        public void goDown() {
            i++;
        }

        public void resetDown() {
            i--;
        }

        public void goLeft() {
            j--;
        }

        public void resetLeft() {
            j++;
        }

        public void goRight() {
            j++;
        }

        public void resetRight() {
            j--;
        }
    }

    private static ArrayList<Point> hasDones = new ArrayList<>();

    private static boolean isAvil(int[][] grid, Point point) {
        if (point.j < 0 || point.j >= grid[0].length) {
            return false;
        } else return point.i >= 0 && point.i < grid.length;
    }

    static int point = 10;

    /**
     * 开始走路了。
     *
     * @param grid
     * @param start
     * @param end
     */
    private static void walk(int[][] grid, Point start, Point end) {
        Point currentPoint = start;
        grid[start.i][start.j] = point;
        Stack<Point> array = new Stack<>();
        while (!currentPoint.toString().equals(end.toString())) {
            point++;
            lookAround(grid, currentPoint, array);
            hasDones.add(currentPoint);
            if (!array.isEmpty()) {
                currentPoint = array.pop();
                point = grid[currentPoint.i][currentPoint.j];
            }
        }
    }

    /**
     * @param grid
     * @param currentPoint
     */
    private static void lookAround(int[][] grid, Point currentPoint, Stack<Point> array) {
        currentPoint.goUp();
        save(grid, currentPoint, array);
        currentPoint.resetUp();
        currentPoint.goLeft();
        save(grid, currentPoint, array);
        currentPoint.resetLeft();
        currentPoint.goDown();
        save(grid, currentPoint, array);
        currentPoint.resetDown();
        currentPoint.goRight();
        save(grid, currentPoint, array);
        currentPoint.resetRight();
    }

    private static void save(int[][] grid, Point currentPoint, Stack<Point> array) {
        if (isAvil(grid, currentPoint)) {
            if (grid[currentPoint.i][currentPoint.j] == 0 && !hasCo(currentPoint)) {
                Point temp = new Point(currentPoint.i, currentPoint.j);
                array.push(temp);
                grid[currentPoint.i][currentPoint.j] = point;
            }
        }
    }

    private static boolean hasCo(Point currentPoint) {
        for (int i = 0; i < hasDones.size(); i++) {
            if (hasDones.get(i).toString().equals(currentPoint.toString())) {
                return true;
            }
        }
        return false;
    }
}