Java机试题*：迷宫问题

描述

定义一个二维数组 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表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

import java.util.Scanner;

public class Main {
    // 二维数组迷宫的行数，全局变量的使用
    public static int m;
    // 二维数组迷宫的列数，全局变量的使用
    public static int n;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            m = scanner.nextInt();
            n = scanner.nextInt();
            int[][] maze = new int[m][n];
            // 构建迷宫
            for (int i=0; i) {
                for (int j=0; j) {
                    maze[i][j] = scanner.nextInt();
                }
            }
            // 找出路径
            String way = findWay(maze, 0, 0);
            for (String s : way.split("——")) {
                System.out.println(s);
            }
        }
    }

    /*
     * 使用递归，判断该点是否可走，该点可走，即它的下一个点，下下个点，能一直到右下角，即满足可走条件。 设置全面递归结束的条件
     * 递归式可以作为条件也可以作为结果等
     */
    public static String findWay(int[][] maze, int x, int y) {
        // 已抵达右下角终点
        if (maze[m-1][n-1] == 2) {
            return "";
        }
        // 超出边界
        if (x > m-1 || x < 0 || y > n-1 || y < 0) {
            return null;
        }
        // 判断当前点是否可走
        if (maze[x][y] == 0) {
            // 寻路策略：对于某个点，可以有四种走法，下 -> 右 -> 上 -> 左，有一个方向可走即满足可走。
            // 可走并且已走的到的位置设置为2，并返回坐标点
            maze[x][y] = 2;
            String point;
            if ((point = findWay(maze, x+1, y)) != null) {
                return "(" + x + "," + y + ")——" + point;
            }
            if ((point = findWay(maze, x, y+1)) != null) {
                return "(" + x + "," + y + ")——" + point;
            }
            if ((point = findWay(maze, x-1, y)) != null) {
                return "(" + x + "," + y + ")——" + point;
            }
            if ((point = findWay(maze, x, y-1)) != null) {
                return "(" + x + "," + y + ")——" + point;
            }
            // 不可走设置为1，并返回null
            maze[x][y] = 1;
            return null;
        }
        return null;
    }
}

参考链接：https://www.nowcoder.com/questionTerminal/cf24906056f4488c9ddb132f317e03bc