题解 | 华为机试 HJ43 #迷宫问题#

1. 最简单的情况：(i, j) 已经是目的地，我们返回 true 表示经过此坐标能到达目的地
2. 基于坐标 (i, j) 可以往左走一步，调用函数F，将往左一步的坐标 (i - 1, j) 作为参数，如果F返回true表示此路为通路，将此坐标记录下来，然后返回true
3. 基于坐标 (i, j) 可以往右走一步，调用函数F，将往右一步的坐标 (i + 1, j) 作为参数，如果F返回true表示此路为通路，将此坐标记录下来，然后返回true
4. 基于坐标 (i, j) 可以往上走一步，调用函数F，将往上一步的坐标 (i, j - 1) 作为参数，如果F返回true表示此路为通路，将此坐标记录下来，然后返回true
5. 基于坐标 (i, j) 可以往下走一步，调用函数F，将往下一步的坐标 (i, j + 1) 作为参数，如果F返回true表示此路为通路，将此坐标记录下来，然后返回true

1. 检查要去的坐标是否为墙壁，如果是墙壁肯定不能走
2. 检查要去的坐标之前是否已经去过，好马不吃回头草，去过的坐标咱们也不走

public class HJ43Maze {

    private static final List<String> pathList = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int m = Integer.parseInt(arr[0]);
        int n = Integer.parseInt(arr[1]);

        boolean[][] maze = new boolean[m][n];

        String[] split;
        for (short i = 0; i < m; i++) {
            split = br.readLine().split(" ");
            for (short j = 0; j < n; j++) {
                maze[i][j] = split[j].equals("0");
            }
        }

        boolean[][] visited = new boolean[m][n];
        search(maze, m, n, 0, 0, visited);
        for (String path : pathList) {
            System.out.println(path);
        }
    }

    private static boolean search(boolean[][] maze, int m, int n, int i, int j, boolean[][] visited) {
        // 标记当前坐标为已访问
        visited[i][j] = true;
        // 如果是终点
        if (i == m - 1 && j == n - 1) {
            pathList.add(0, "(" + i + "," + j + ")");
            return true;
        }
        // 寻找合法的可进入坐标
        int newI, newJ;
        boolean accessable;
        // go up
        if (i - 1 >= 0 && maze[i - 1][j] && !visited[i - 1][j]) {
            newI = i - 1;
            newJ = j;
            accessable = search(maze, m, n, newI, newJ, visited);
            if (accessable) {
                pathList.add(0, "(" + i + "," + j + ")");
                return true;
            }
        }
        // go down
        if (i + 1 < m && maze[i + 1][j] && !visited[i + 1][j]) {
            newI = i + 1;
            newJ = j;
            accessable = search(maze, m, n, newI, newJ, visited);
            if (accessable) {
                pathList.add(0, "(" + i + "," + j + ")");
                return true;
            }
        }
        // go left
        if (j - 1 >= 0 && maze[i][j - 1] && !visited[i][j - 1]) {
            newI = i;
            newJ = j - 1;
            accessable = search(maze, m, n, newI, newJ, visited);
            if (accessable) {
                pathList.add(0, "(" + i + "," + j + ")");
                return true;
            }
        }
        // go right
        if (j + 1 < n && maze[i][j + 1] && !visited[i][j + 1]) {
            newI = i;
            newJ = j + 1;
            accessable = search(maze, m, n, newI, newJ, visited);
            if (accessable) {
                pathList.add(0, "(" + i + "," + j + ")");
                return true;
            }
        }
        // 哪里都无法走
        return false;
    }
}