题解 | #迷宫#

迷宫

https://www.nowcoder.com/practice/7387750c12e0401abe2ad6e9b45258f5

题目链接

迷宫

题目描述

给定一个 $n \times m$ 的迷宫，由 # 与 . 两种字符组成。其中 # 代表障碍物，. 表示空地。迷宫中还有一个起点 S 和一个终点 E，它们都可以视为空地。

由于近期迷宫发生了塌方，导致起点和终点之间可能并不连通。幸运的是，你拥有一种超能力——在迷宫中移动时（移动方向为上、下、左、右四个方向之一），可以在当前位置朝任一方向（上、下、左、右四个方向之一）释放激光。激光能够清除该方向上所有的障碍物，并且这种超能力至多只能使用一次。

现在，你需要判断是否能利用这种超能力成功从起点到达终点。

解题思路

本题是一个带有特殊规则的图上寻路问题。问题的关键在于“激光至多使用一次”这个条件。我们可以将任何一条从起点 $S$ 到终点 $E$ 的有效路径分为两种情况：

不使用激光，直接通过空地从 $S$ 到达 $E$ 。
使用一次激光。路径可以被分解为三个阶段： a. 从 $S$ 不使用激光走到某个点 $P$ 。 b. 在点 $P$ 朝某个方向发射激光，这条激光路径上的某个点为 $Q$ 。 c. 从点 $Q$ 不使用激光走到终点 $E$ 。

这个分解启发我们，可以预先计算出所有不使用激光可以到达的区域，然后检查是否存在一个可以通过激光连接的“桥梁”。

算法步骤如下：

从起点进行 BFS：从起点 $S$ 开始，进行一次标准的广度优先搜索（BFS），找出所有不使用激光就能到达的格子。我们将这些格子的可达性记录在一个二维布尔数组 $visited_s$ 中。

在这次 BFS 结束后，如果 $visited_s$ 标记终点 $E$ 为可达，说明无需激光即可到达，可以直接返回 YES。
从终点进行 BFS：

从终点 $E$ 开始，进行第二次标准的 BFS。这次搜索可以找到所有能够不使用激光就到达 $E$ 的格子（可以理解为从 $E$ 能反向走到的所有格子）。我们将结果保存在 $visited_e$ 数组中。
标记激光发射源：

为了高效地判断是否存在连接，我们预处理出哪些行和列可以作为激光的发射区域。

创建两个布尔数组， $row\_has\_s$ 和 $col\_has\_s$ 。遍历 $visited_s$ 数组，如果 $visited_s[i][j]$ 为真，则说明第 $i$ 行和第 $j$ 列存在一个 $S$ 的可达点。因此，我们将 $row\_has\_s[i]$ 和 $col\_has\_s[j]$ 标记为真。这表示我们可以从第 $i$ 行的某个位置发射横向激光，或从第 $j$ 列的某个位置发射纵向激光。
寻找连接点：

遍历整个迷宫的每一个格子 $(i, j)$ ，判断它是否能成为连接起点区域和终点区域的“桥梁”。一个格子 $(i, j)$ 要成为桥梁，必须同时满足两个条件：

a. 它能被来自起点的激光击中：这意味着，存在一个从 $S$ 可达的区域发射的激光，能够让你到达点 $(i,j)$ 或其邻近位置，从而可以移动到 $(i,j)$ 。根据给定的正确逻辑，这等价于：点 $(i, j)$ 的行号 $i$ 、或其相邻行号 $i-1, i+1$ 中，至少有一个行号上存在 $S$ 的可达点；或者，点 $(i, j)$ 的列号 $j$ 、或其相邻列号 $j-1, j+1$ 中，至少有一个列号上存在 $S$ 的可达点。

b. 从它出发可以不使用激光走到终点：这等价于 $visited_e[i][j]$ 为真。

只要我们找到任何一个满足上述两个条件的格子 $(i, j)$ ，就说明存在一条路径，答案就是 YES。
最终结果：

如果遍历完所有格子，都没有找到满足条件的“桥梁”格子，那么就说明即使有一次激光机会，也无法从起点到达终点。此时返回 NO。

这个算法将问题分解为两次独立的 BFS 和一次检查，时间复杂度为 $\mathcal{O}(n \cdot m)$ ，可以高效地解决问题。

代码

cpp
java
python

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

using namespace std;

int n, m;
vector<string> grid;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

// 标准BFS函数，返回一个标记所有可达点的二维布尔数组
vector<vector<bool>> bfs(int start_r, int start_c) {
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    if (start_r == -1) {
        return visited;
    }

    queue<pair<int, int>> q;
    q.push({start_r, start_c});
    visited[start_r][start_c] = true;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        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] != '#' && !visited[nr][nc]) {
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }
    return visited;
}

int main() {
    cin >> n >> m;
    grid.resize(n);
    int start_r = -1, start_c = -1, end_r = -1, end_c = -1;

    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 'S') {
                start_r = i;
                start_c = j;
            } else if (grid[i][j] == 'E') {
                end_r = i;
                end_c = j;
            }
        }
    }

    auto visited_s = bfs(start_r, start_c);
    if (visited_s[end_r][end_c]) {
        cout << "YES" << endl;
        return 0;
    }

    auto visited_e = bfs(end_r, end_c);

    vector<bool> row_has_s(n, false);
    vector<bool> col_has_s(m, false);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (visited_s[i][j]) {
                row_has_s[i] = true;
                col_has_s[j] = true;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // 如果这个点可以走到终点
            if (visited_e[i][j]) {
                // 检查其自身及相邻行/列是否能被S区域的激光覆盖
                bool can_be_reached = false;
                for (int dr = -1; dr <= 1; ++dr) {
                    if (i + dr >= 0 && i + dr < n && row_has_s[i + dr]) {
                        can_be_reached = true;
                        break;
                    }
                }
                if (can_be_reached) {
                    cout << "YES" << endl;
                    return 0;
                }
                for (int dc = -1; dc <= 1; ++dc) {
                    if (j + dc >= 0 && j + dc < m && col_has_s[j + dc]) {
                        can_be_reached = true;
                        break;
                    }
                }
                if (can_be_reached) {
                    cout << "YES" << endl;
                    return 0;
                }
            }
        }
    }

    cout << "NO" << endl;
    return 0;
}

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

public class Main {
    static int n, m;
    static char[][] grid;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    // 标准BFS，返回visited数组
    static boolean[][] bfs(int startR, int startC) {
        boolean[][] visited = new boolean[n][m];
        if (startR == -1) {
            return visited;
        }

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startR, startC});
        visited[startR][startC] = true;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1];
            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] != '#' && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        return visited;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        grid = new char[n][m];
        int startR = -1, startC = -1, endR = -1, endC = -1;

        for (int i = 0; i < n; i++) {
            grid[i] = sc.next().toCharArray();
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'S') {
                    startR = i;
                    startC = j;
                } else if (grid[i][j] == 'E') {
                    endR = i;
                    endC = j;
                }
            }
        }

        boolean[][] visitedS = bfs(startR, startC);
        if (visitedS[endR][endC]) {
            System.out.println("YES");
            return;
        }

        boolean[][] visitedE = bfs(endR, endC);

        boolean[] rowHasS = new boolean[n];
        boolean[] colHasS = new boolean[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visitedS[i][j]) {
                    rowHasS[i] = true;
                    colHasS[j] = true;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                 // 如果这个点可以走到终点
                if (visitedE[i][j]) {
                    // 检查其自身及相邻行/列是否能被S区域的激光覆盖
                    boolean canBeReached = false;
                    for (int dr = -1; dr <= 1; dr++) {
                        if (i + dr >= 0 && i + dr < n && rowHasS[i + dr]) {
                            canBeReached = true;
                            break;
                        }
                    }
                    if (canBeReached) {
                        System.out.println("YES");
                        return;
                    }
                    for (int dc = -1; dc <= 1; dc++) {
                        if (j + dc >= 0 && j + dc < m && colHasS[j + dc]) {
                            canBeReached = true;
                            break;
                        }
                    }
                    if (canBeReached) {
                        System.out.println("YES");
                        return;
                    }
                }
            }
        }

        System.out.println("NO");
    }
}

import sys
from collections import deque

def main():
    # 读取输入
    line = sys.stdin.readline()
    if not line: return
    n, m = map(int, line.split())
    grid = [sys.stdin.readline().strip() for _ in range(n)]

    start_pos, end_pos = None, None
    for r in range(n):
        for c in range(m):
            if grid[r][c] == 'S':
                start_pos = (r, c)
            elif grid[r][c] == 'E':
                end_pos = (r, c)

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    # 标准BFS函数
    def bfs(start_node):
        if not start_node:
            return [[False] * m for _ in range(n)]
        q = deque([start_node])
        visited = [[False] * m for _ in range(n)]
        visited[start_node[0]][start_node[1]] = True
        
        while q:
            r, c = q.popleft()
            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] != '#' and not visited[nr][nc]:
                    visited[nr][nc] = True
                    q.append((nr, nc))
        return visited

    # 从起点S开始BFS
    visited_s = bfs(start_pos)
    if end_pos and visited_s[end_pos[0]][end_pos[1]]:
        print("YES")
        return

    # 从终点E开始BFS
    visited_e = bfs(end_pos)

    # 标记可以发射激光的行和列
    row_has_s = [False] * n
    col_has_s = [False] * m
    for r in range(n):
        for c in range(m):
            if visited_s[r][c]:
                row_has_s[r] = True
                col_has_s[c] = True

    # 寻找连接点
    for r in range(n):
        for c in range(m):
            # 如果这个点可以走到终点
            if visited_e[r][c]:
                # 检查其自身及相邻行/列是否能被S区域的激光覆盖
                can_be_reached = False
                for dr_offset in [-1, 0, 1]:
                    if 0 <= r + dr_offset < n and row_has_s[r + dr_offset]:
                        can_be_reached = True
                        break
                if can_be_reached:
                    print("YES")
                    return
                
                for dc_offset in [-1, 0, 1]:
                    if 0 <= c + dc_offset < m and col_has_s[c + dc_offset]:
                        can_be_reached = True
                        break
                if can_be_reached:
                    print("YES")
                    return

    print("NO")

if __name__ == "__main__":
    main()

算法及复杂度

算法：广度优先搜索 (BFS)
时间复杂度：我们执行了两次独立的 BFS，每次遍历整个网格一次，复杂度为 $\mathcal{O}(n \cdot m)$ 。之后，我们遍历所有行和列来标记激光源，以及再次遍历所有格子寻找连接点，这些部分的复杂度也都是 $\mathcal{O}(n \cdot m)$ 。因此，总的时间复杂度为 $\mathcal{O}(n \cdot m)$ 。
空间复杂度：两次 BFS 都需要一个 visited 数组和一个队列，空间开销都是 $\mathcal{O}(n \cdot m)$ 。此外还需要辅助数组来标记激光源。因此，总空间复杂度为 $\mathcal{O}(n \cdot m)$ 。