题解 | #迷宫问题#

 /**
     * 迷宫的方向
     */
    private static final int[][] DIRECTIONS = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

import java.util.Scanner;
import java.util.Stack;

/**
 * HJ43 迷宫问题
 * 描述
 * 定义一个二维数组 N*M ，如 5 × 5 数组下所示：
 * int maze[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,
 * };
 * 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
 * 本题含有多组数据。
 * 输入描述：
 * 输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
 *
 * 输出描述：
 * 左上角到右下角的最短路径，格式如样例所示
 * 示例1
 * 输入：
 * 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
 * 复制
 * 输出：
 * (0,0)
 * (1,0)
 * (2,0)
 * (2,1)
 * (2,2)
 * (2,3)
 * (2,4)
 * (3,4)
 * (4,4)
 */
public class Main {
    /**
     * 迷宫的方向
     */
    private static final int[][] DIRECTIONS = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int m = in.nextInt();
            int n = in.nextInt();
            int[][] arr = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = in.nextInt();
                }
            }

            // 走迷宫
            Stack<Position> dfs = dfs(arr, m, n);
            for (Position e : dfs) {
                System.out.println("(" + e.x + "," + e.y + ")");
            }
        }
    }

    /**
     * 走迷宫
     * @param arr 迷宫数组
     * @param m 迷宫行数
     * @param n 迷宫列数
     * @return 迷宫的路径
     */
    private static Stack<Position> dfs(int[][] arr, int m, int n) {
        Stack<Position> stack = new Stack<>();

        // 定义起点为已经探索过的
        arr[0][0] = -1;

        // 设置起点，并将起点入栈
        Position position = new Position(0, 0, -1);
        stack.push(position);

        // 遍历栈
        while (!stack.isEmpty()){
            // 位置出栈
            Position p = stack.pop();
            int x = p.x;
            int y = p.y;
            // 获取方向，并加1取尝试
            int d = p.d + 1;

            while (d < 4){
                // 因为一个点，在迷宫的二维数组中只能向上下左右方向移动，但是可能会导致边界溢出，需要处理边界问题
                // DIRECTIONS[d][0]表示x坐标需要移动的位置，负数表示向左，整数表示向右
                // DIRECTIONS[d][1]表示y坐标需要移动的位置，负数表示向左，整数表示向右
                int i = x + DIRECTIONS[d][0];
                int j = y + DIRECTIONS[d][1];

                // 越界，或者值为1(表示墙，不能通行)，等都是不可操作的，继续调整探索的方向
                if (i < 0 || i >= m || j < 0 || j >= n || arr[i][j] != 0){
                    // 探索方向变化, 继续尝试
                    d++;
                    continue;
                }

                // 如果走到这里，说明当前点的值为0，并且下标不越界。可以通行，则数据入栈
                stack.push(new Position(x, y, d));
                // 重新迭代x,y,d，为下次迭代做准备
                x = i;
                y = j;
                d = 0;
                // 标记当前位置已经被探索过了
                arr[x][y] = -1;
                // 当遍历到最后一个点时，说明找到了迷宫的出口, 结束循环
                if (x == m - 1 && y == n - 1){
                    stack.push(new Position(x, y, d));
                    return stack;
                }
            }

        }
        return new Stack<>();
    }


    /**
     * 位置
     */
    public static class Position {
        // 横坐标方向
        int x;
        // 众坐标方向
        int y;
        // 探索的方向
        int d;
        public Position(int x, int y,int d) {
            this.d = d;
            this.x = x;
            this.y = y;
        }
    }

}