1. 题目

读题

 HJ43 迷宫问题

考查点

2. 解法

思路

代码逻辑

具体实现

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        // 迷宫地图
        int[][] maze = {
                {0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 1, 0}
        };
        // 访问数组
        int[][] visited = new int[maze.length][maze[0].length];
        // 路径列表
        List<int[]> path = new ArrayList<>();
        // 调用递归函数
        dfs(maze, visited, path, 0 ,0);
    }

    // 定义一个递归函数，传入当前的坐标和一个列表来存储路径
    public static boolean dfs(int[][] maze, int[][] visited,
                              List<int[]> path,
                              int x ,int y) {
        // 将当前位置加入路径列表，并将访问数组对应位置设为1
        path.add(new int[]{x ,y});
        visited[x][y] = 1;
        // 判断是否到达了右下角，也就是终点
        if (x == maze.length -1 && y == maze[0].length -1) {
            // 打印出路径列表，并返回true
            for (int[] pos : path) {
                System.out.println("(" + pos[0] + "," + pos[1] + ")");
            }
            return true;
        }
        // 定义四个方向的移动
        int[] dx = {-1 ,1 ,0 ,0};
        int[] dy = {0 ,0 ,-1 ,1};
        // 尝试向四个方向移动
        for (int i = 0; i <4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 判断是否越界或者遇到墙壁或者已经访问过
            if (nx < 0 || nx >= maze.length || ny < 0 || ny >= maze[0].length ||
                    maze[nx][ny] ==1 || visited[nx][ny] ==1) {
                continue;
            }
            // 如果可以走，就递归调用自己
            if (dfs(maze ,visited ,path ,nx ,ny)) {
                return true;
            }
        }
        // 如果四个方向都不能走或者已经走过，就回溯
        path.remove(path.size() -1);
        visited[x][y] = 0;
        return false;
    }
}

3. 总结