题解 | #HJ043 迷宫问题#

import java.util.*;

/**
 * HJ43 迷宫问题 - 中等
 */
public class HJ043 {
    private static List<Point> points = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int row = sc.nextInt();// 行数
            int col = sc.nextInt();// 列数
            int[][] maze = new int[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    maze[i][j] = sc.nextInt();// 迷宫初始化
                }
            }
            //深度优先搜索
            dfsWalk(maze, 0, 0);
            for (Point point : points) {
                System.out.println("(" + point.x + "," + point.y + ")");
            }
        }
    }

    private static boolean dfsWalk(int[][] maze, int x, int y) {
        points.add(new Point(x, y));
        maze[x][y] = 1; // 走一步，并且当前位置设置为障碍
        int maxX = maze.length - 1;
        int maxY = maze[x].length - 1;
        // 完成
        if (x == maxX && y == maxY) {
            return true;
        }

        // 向下
        if (x + 1 <= maxX && maze[x + 1][y] == 0) {
            if (dfsWalk(maze, x + 1, y)) {
                return true;
            }
        }

        //向右
        if (y + 1 <= maxY && maze[x][y + 1] == 0) {
            if (dfsWalk(maze, x, y + 1)) {
                return true;
            }
        }

        // 向上
        if (x - 1 >= 0 && maze[x - 1][y] == 0) {
            if (dfsWalk(maze, x - 1, y)) {
                return true;
            }
        }

        //向左
        if (y - 1 >= 0 && maze[x][y - 1] == 0) {
            if (dfsWalk(maze, x, y - 1)) {
                return true;
            }
        }
        //找到死胡同，回溯，撤销i,j选择，当前位置设置为可走
        points.remove(points.size() - 1);
        maze[x][y] = 0;
        return false;
    }

    // 当前位置
    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}