题解 | #旺仔哥哥走迷宫#

题目链接

题目描述

在一个由 $N$ 个房间和 $M$ 条双向通道组成的迷宫中，旺仔哥哥需要从房间 $1$ 找到通往房间 $N$ 的出口。部分房间设有陷阱，由一个数组 $A$ 标记，若 $A_i=1$ 则房间 $i$ 有陷阱，若 $A_i=0$ 则房间安全。旺仔哥哥只能在安全的房间内移动。判断是否存在一条仅经过安全房间的路径。

解题思路

本题可以抽象为一个图论问题：给定一个图，判断两个节点（房间 $1$ 和房间 $N$ ）之间是否存在一条路径，使得路径上的所有节点都满足特定条件（安全）。

这是一个典型的图遍历问题，可以使用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 来解决。这里我们选用 BFS，因为它可以找到最短路径，虽然本题只要求判断路径是否存在。

算法流程如下：

建图与初始化：
- 根据输入的 $M$ 条通道，构建一个邻接表来表示图的结构。
- 创建一个布尔数组 $\mathit{is\_safe}$ ，根据输入的数组 $A$ 来标记每个房间是否安全。
- 创建一个布尔数组 $\mathit{visited}$ ，用于记录在搜索过程中哪些房间已经被访问过，以避免无限循环。
- 创建一个队列 $\mathit{queue}$ ，用于实现 BFS。
特殊情况处理：
- 首先检查起点房间 $1$ 和终点房间 $N$ 是否安全。如果任意一个有陷阱，则不可能存在满足条件的路径，直接返回 No。
执行 BFS：
- 将起点房间 $1$ 加入队列，并标记为已访问 ( $\mathit{visited}[1] = \text{true}$ )。
- 进入循环，当队列不为空时：
  - 从队列头部取出一个房间 $u$ 。
  - 如果 $u$ 就是终点房间 $N$ ，说明已找到一条有效路径，直接返回 Yes 并结束算法。
  - 遍历 $u$ 的所有邻居房间 $v$ ：
    - 如果房间 $v$ 是安全的 ( $\mathit{is\_safe}[v] = \text{true}$ ) 并且尚未被访问过 ( $\mathit{visited}[v] = \text{false}$ )，则将其加入队列，并标记为已访问。
处理结果：
- 如果 BFS 循环结束（队列为空）后，仍未到达终点房间 $N$ ，则说明从起点无法到达终点，返回 No。

代码

c++
java
python

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

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<bool> is_safe(n + 1);
    for (int i = 1; i <= n; ++i) {
        int trap_status;
        cin >> trap_status;
        is_safe[i] = (trap_status == 0);
    }

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if (!is_safe[1] || !is_safe[n]) {
        cout << "No\n";
        return 0;
    }

    if (n == 1) {
        cout << "Yes\n";
        return 0;
    }

    queue<int> q;
    vector<bool> visited(n + 1, false);

    q.push(1);
    visited[1] = true;

    bool found = false;
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == n) {
            found = true;
            break;
        }

        for (int v : adj[u]) {
            if (is_safe[v] && !visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }

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

    return 0;
}

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

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

        boolean[] isSafe = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            isSafe[i] = (sc.nextInt() == 0);
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        if (!isSafe[1] || !isSafe[n]) {
            System.out.println("No");
            return;
        }

        if (n == 1) {
            System.out.println("Yes");
            return;
        }

        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];

        q.add(1);
        visited[1] = true;

        boolean found = false;
        while (!q.isEmpty()) {
            int u = q.poll();

            if (u == n) {
                found = true;
                break;
            }

            for (int v : adj.get(u)) {
                if (isSafe[v] && !visited[v]) {
                    visited[v] = true;
                    q.add(v);
                }
            }
        }

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

import sys
from collections import deque

def solve():
    line = sys.stdin.readline()
    if not line:
        return
    n, m = map(int, line.split())

    traps = list(map(int, sys.stdin.readline().split()))
    is_safe = [True] * (n + 1)
    for i in range(n):
        if traps[i] == 1:
            is_safe[i + 1] = False

    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        adj[v].append(u)
    
    if not is_safe[1] or not is_safe[n]:
        print("No")
        return
        
    if n == 1:
        print("Yes")
        return

    q = deque([1])
    visited = {1}
    
    found = False
    while q:
        u = q.popleft()
        if u == n:
            found = True
            break
        
        for v in adj[u]:
            if is_safe[v] and v not in visited:
                visited.add(v)
                q.append(v)

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

solve()

算法及复杂度

算法：广度优先搜索 (BFS)
时间复杂度： $\mathcal{O}(N+M)$ 。
- 构建邻接表需要 $\mathcal{O}(M)$ 的时间。
- BFS 过程中，每个节点和每条边最多被访问一次，因此时间复杂度为 $\mathcal{O}(N+M)$ 。
- 总体时间复杂度为 $\mathcal{O}(N+M)$ 。
空间复杂度： $\mathcal{O}(N+M)$ 。
- 存储邻接表需要 $\mathcal{O}(N+M)$ 的空间。
- $\mathit{is\_safe}$ 和 $\mathit{visited}$ 数组需要 $\mathcal{O}(N)$ 的空间。
- BFS 队列在最坏情况下可能存储所有节点，需要 $\mathcal{O}(N)$ 的空间。
- 总体空间复杂度为 $\mathcal{O}(N+M)$ 。