题解 | #迷宫寻路#

题目链接

迷宫寻路

题目描述

给定一个 $R \times C$ 的矩形迷宫，每个格子要么是空地（用符号 . 表示），要么是墙（用符号 # 表示）。旺仔哥哥只能从一个空地移动到其上下左右四个相邻的空地。

已知起点为左上角 $(1, 1)$ ，终点为右下角 $(R, C)$ 。请判断他是否能够从起点到达终点。

解题思路

这是一个典型的图搜索问题，目标是判断图（迷宫）中两个节点（起点和终点）是否连通。我们可以将迷宫的每个空地格子看作图中的一个节点，相邻的空地格子之间存在一条边。

解决此类问题的常用算法是广度优先搜索 (BFS) 或深度优先搜索 (DFS)。这里我们采用广度优先搜索 (BFS)，因为它在寻找路径问题中非常直观且能保证找到最短路径（尽管本题不要求）。

广度优先搜索 (BFS) 算法流程

初始化：
- 创建一个队列，用于存放待访问的格子坐标。
- 创建一个与迷宫同样大小的二维布尔数组 visited，用于记录访问过的格子，防止重复访问和死循环。
- 将起点 (0, 0)（代码中通常使用 0-based 索引）加入队列，并将其在 visited 数组中对应的位置标记为 true。
循环搜索：
- 当队列不为空时，从队列头部取出一个格子 (r, c)。
- 如果 (r, c) 就是终点 (R-1, C-1)，说明已经找到一条路径，搜索结束。
- 否则，考察 (r, c) 的上、下、左、右四个相邻格子。对于每一个相邻格子 (nr, nc)，如果它满足以下所有条件，就将其加入队列，并标记为已访问：
  - 未越出迷宫边界。
  - 不是墙壁 (#)。
  - 尚未被访问过 (visited[nr][nc] 为 false)。
判断结果：
- 如果在搜索过程中成功到达终点，则输出 "Yes"。
- 如果队列为空后，搜索结束仍未到达终点，说明从起点无法到达终点，输出 "No"。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int r, c;
    cin >> r >> c;

    vector<string> maze(r);
    for (int i = 0; i < r; ++i) {
        cin >> maze[i];
    }

    queue<pair<int, int>> q;
    vector<vector<bool>> visited(r, vector<bool>(c, false));

    // 从起点 (0,0) 开始
    q.push({0, 0});
    visited[0][0] = true;

    // 定义四个方向的移动
    int dr[] = {-1, 1, 0, 0}; // 上, 下
    int dc[] = {0, 0, -1, 1}; // 左, 右

    bool found = false;
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        int curr_r = curr.first;
        int curr_c = curr.second;

        // 到达终点
        if (curr_r == r - 1 && curr_c == c - 1) {
            found = true;
            break;
        }

        // 探索四个方向
        for (int i = 0; i < 4; ++i) {
            int next_r = curr_r + dr[i];
            int next_c = curr_c + dc[i];

            // 检查边界、是否为墙、是否已访问
            if (next_r >= 0 && next_r < r && next_c >= 0 && next_c < c &&
                maze[next_r][next_c] == '.' && !visited[next_r][next_c]) {
                
                visited[next_r][next_c] = true;
                q.push({next_r, next_c});
            }
        }
    }

    if (found) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        sc.nextLine(); // 消耗换行符

        char[][] maze = new char[r][c];
        for (int i = 0; i < r; i++) {
            maze[i] = sc.nextLine().toCharArray();
        }

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[r][c];

        // 从起点 (0,0) 开始
        queue.add(new int[]{0, 0});
        visited[0][0] = true;

        // 定义四个方向的移动
        int[] dr = {-1, 1, 0, 0}; // 上, 下
        int[] dc = {0, 0, -1, 1}; // 左, 右

        boolean found = false;
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int currR = curr[0];
            int currC = curr[1];

            // 到达终点
            if (currR == r - 1 && currC == c - 1) {
                found = true;
                break;
            }

            // 探索四个方向
            for (int i = 0; i < 4; i++) {
                int nextR = currR + dr[i];
                int nextC = currC + dc[i];

                // 检查边界、是否为墙、是否已访问
                if (nextR >= 0 && nextR < r && nextC >= 0 && nextC < c &&
                    maze[nextR][nextC] == '.' && !visited[nextR][nextC]) {
                    
                    visited[nextR][nextC] = true;
                    queue.add(new int[]{nextR, nextC});
                }
            }
        }

        if (found) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

import collections

r, c = map(int, input().split())
maze = [input() for _ in range(r)]

# 创建队列和 visited 集合
queue = collections.deque([(0, 0)])
visited = [[False for _ in range(c)] for _ in range(r)]
visited[0][0] = True

# 定义四个方向的移动
dr = [-1, 1, 0, 0] # 上, 下
dc = [0, 0, -1, 1] # 左, 右

found = False
while queue:
    curr_r, curr_c = queue.popleft()

    # 到达终点
    if curr_r == r - 1 and curr_c == c - 1:
        found = True
        break

    # 探索四个方向
    for i in range(4):
        next_r, next_c = curr_r + dr[i], curr_c + dc[i]

        # 检查边界、是否为墙、是否已访问
        if 0 <= next_r < r and 0 <= next_c < c and \
           maze[next_r][next_c] == '.' and not visited[next_r][next_c]:
            
            visited[next_r][next_c] = True
            queue.append((next_r, next_c))

if found:
    print("Yes")
else:
    print("No")

算法及复杂度

算法：广度优先搜索 (BFS)
时间复杂度：在 BFS 中，每个格子最多被访问（入队和出队）一次。对于每个格子，我们会进行常数次操作来检查它的邻居。因此，总时间复杂度与格子总数成正比，为 $\mathcal{O}(R \cdot C)$ 。
空间复杂度：空间开销主要来自 visited 数组和队列。visited 数组需要 $\mathcal{O}(R \cdot C)$ 的空间。在最坏情况下，队列可能需要存储接近所有格子的坐标，所以空间复杂度也是 $\mathcal{O}(R \cdot C)$ 。