题解 | #迷宫问题#

题目链接

题目描述

在一个 $N \cdot M$ 的网格迷宫中，0 代表通路，1 代表墙壁。起点固定为左上角的 $(0, 0)$ ，终点固定为右下角的 $(N-1, M-1)$ 。你需要找到一条从起点到终点的可行路径，并按顺序输出路径上每个格子的坐标。题目保证路径存在且唯一。

解题思路

本题是一个典型的迷宫寻路问题。我们需要在给定的网格中，找到一条从起点 $(0, 0)$ 到终点 $(N-1, M-1)$ 的可行路径。由于题目保证路径存在且唯一，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。这里我们采用深度优先搜索（DFS）的方法。

DFS 的核心思想是“一条路走到黑”，即从起点开始，沿着一个方向不断探索，直到到达终点或遇到死路（墙壁或已访问过的格子）。如果遇到死路，就回溯到上一个路口，尝试其他方向。

为了能够输出最终的路径，我们不能只判断是否能到达终点，还需要记录下路径的轨迹。一个经典的方法是使用一个 $parent$ 数组（或哈希表），在搜索过程中， $parent[r][c]$ 记录我们是从哪个格子到达 $(r, c)$ 的。

算法步骤如下：

初始化：创建一个二维的 $visited$ 数组来标记访问过的格子，避免重复搜索和陷入死循环。创建一个二维的 $parent$ 数组来存储每个格子的前驱节点。
递归搜索：从起点 $(0, 0)$ 开始进行 DFS。定义递归函数 $dfs(r, c)$ :

a. 将当前格子 $(r, c)$ 标记为已访问。

b. 如果 $(r, c)$ 是终点，说明已找到路径，返回 $true$ 。

c. 遍历当前格子的四个邻居 $(nr, nc)$ 。如果邻居是有效的（在边界内、不是墙、且未被访问过）：
$\ \ \ \$ i. 记录 $parent[nr][nc] = (r, c)$ 。
$\ \ \ \$ ii. 递归调用 $dfs(nr, nc)$ 。如果返回 $true$ ，说明通过这个邻居找到了通往终点的路径，立刻将 $true$ 向上层返回，停止搜索其他分支。

d. 如果所有邻居都无法通向终点，返回 $false$ 。
路径回溯：在主函数中调用 $dfs(0, 0)$ 后，如果返回 $true$ ，我们就可以从终点 $(N-1, M-1)$ 开始，利用 $parent$ 数组一步步回溯到起点。
输出：将回溯得到的路径反转，即为从起点到终点的正确路径。按题目要求格式输出每个点的坐标。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<vector<int>> grid;
vector<vector<bool>> visited;
vector<vector<pair<int, int>>> parent;
int dr[] = {-1, 1, 0, 0}; // 方向数组，上下左右
int dc[] = {0, 0, -1, 1};

// 深度优先搜索函数
bool dfs(int r, int c) {
    visited[r][c] = true;
    if (r == n - 1 && c == m - 1) {
        return true; // 到达终点
    }

    for (int i = 0; i < 4; ++i) {
        int nr = r + dr[i];
        int nc = c + dc[i];

        // 检查邻居是否合法
        if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 0 && !visited[nr][nc]) {
            parent[nr][nc] = {r, c}; // 记录父节点
            if (dfs(nr, nc)) {
                return true; // 找到了路径
            }
        }
    }
    return false; // 未找到路径
}

int main() {
    cin >> n >> m;
    grid.assign(n, vector<int>(m));
    visited.assign(n, vector<bool>(m, false));
    parent.assign(n, vector<pair<int, int>>(m, {-1, -1}));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    if (dfs(0, 0)) {
        vector<pair<int, int>> path;
        int r = n - 1, c = m - 1;
        // 从终点开始回溯
        while (r != -1 && c != -1) {
            path.push_back({r, c});
            pair<int, int> p = parent[r][c];
            r = p.first;
            c = p.second;
        }
        reverse(path.begin(), path.end()); // 反转路径

        for (const auto& p : path) {
            cout << "(" << p.first << "," << p.second << ")" << endl;
        }
    }

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static int n, m;
    static int[][] grid;
    static boolean[][] visited;
    static Point[][] parent;
    static int[] dr = {-1, 1, 0, 0}; // 方向数组
    static int[] dc = {0, 0, -1, 1};

    // 用于存储坐标点
    static class Point {
        int r, c;
        Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    // 深度优先搜索函数
    static boolean dfs(int r, int c) {
        visited[r][c] = true;
        if (r == n - 1 && c == m - 1) {
            return true; // 到达终点
        }

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            // 检查邻居是否合法
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 0 && !visited[nr][nc]) {
                parent[nr][nc] = new Point(r, c); // 记录父节点
                if (dfs(nr, nc)) {
                    return true; // 找到了路径
                }
            }
        }
        return false; // 未找到路径
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        grid = new int[n][m];
        visited = new boolean[n][m];
        parent = new Point[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        if (dfs(0, 0)) {
            List<Point> path = new ArrayList<>();
            int r = n - 1, c = m - 1;
            // 从终点回溯
            while (r != -1) { // 初始parent为null，其r,c默认为0，所以不能用r,c判断
                path.add(new Point(r, c));
                if (r == 0 && c == 0) break;
                Point p = parent[r][c];
                r = p.r;
                c = p.c;
            }
            Collections.reverse(path); // 反转路径

            for (Point p : path) {
                System.out.println("(" + p.r + "," + p.c + ")");
            }
        }
    }
}

import sys

# 增加递归深度限制以防迷宫过深
sys.setrecursionlimit(10000)

def main():
    n, m = map(int, sys.stdin.readline().split())
    grid = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    
    visited = [[False] * m for _ in range(n)]
    parent = {}  # 使用字典记录父节点
    
    dr = [-1, 1, 0, 0] # 方向数组
    dc = [0, 0, -1, 1]

    # 深度优先搜索函数
    def dfs(r, c):
        visited[r][c] = True
        if r == n - 1 and c == m - 1:
            return True # 到达终点

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            # 检查邻居是否合法
            if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 0 and not visited[nr][nc]:
                parent[(nr, nc)] = (r, c) # 记录父节点
                if dfs(nr, nc):
                    return True # 找到了路径
        return False # 未找到路径

    if dfs(0, 0):
        path = []
        curr = (n - 1, m - 1)
        # 从终点回溯
        while curr in parent:
            path.append(curr)
            curr = parent[curr]
        path.append((0, 0))  # 添加起点
        path.reverse() # 反转路径
        
        for r, c in path:
            print(f"({r},{c})")

if __name__ == "__main__":
    main()

算法及复杂度

算法：深度优先搜索 (DFS)
时间复杂度：我们需要访问迷宫中的每个格子最多一次。对于每个格子，我们检查其四个方向的邻居。因此，总时间复杂度为 $\mathcal{O}(N \cdot M)$ ，其中 $N$ 和 $M$ 分别是迷宫的行数和列数。
空间复杂度：
- $grid$ , $visited$ , $parent$ 数组都需要 $\mathcal{O}(N \cdot M)$ 的空间。
- DFS 的递归调用栈在最坏情况下（例如一条覆盖所有格子的蜿蜒路径）深度可能达到 $\mathcal{O}(N \cdot M)$ 。
- 因此，总空间复杂度为 $\mathcal{O}(N \cdot M)$ 。