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

题目链接

题目描述

给定一个包含 $n$ 个房间、 $m$ 条双向通道的迷宫，房间编号为 $1\sim n$ 。第二行给出数组 $t$ ，当 $t_i=1$ 表示房间 $i$ 有陷阱、 $t_i=0$ 表示安全。只能经过安全房间。判断是否存在一条仅经过安全房间的路径，从房间 $1$ 到房间 $n$ 。

输入：

第一行两个整数 $n$ 、 $m$
第二行 $n$ 个整数 $t_1,\dots,t_n$ （ $0$ 表示安全， $1$ 表示陷阱）
接下来 $m$ 行，每行两个整数 $u$ 、 $v$ ，表示 $u$ 与 $v$ 之间有双向通道

输出：

若存在路径，输出 Yes；否则输出 No

解题思路

建图（邻接表）。若起点或终点为陷阱，直接输出 No。
在只访问安全房间的前提下，对图做 BFS/DFS 可达性判定：从 $1$ 出发扩展到所有安全邻居，检查能否到达 $n$ 。
时间复杂度 $\mathcal{O}(n+m)$ ，空间复杂度 $\mathcal{O}(n+m)$ 。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    vector<int> vis(n + 1, 0);
    queue<int> q;
    q.push(1); vis[1] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == n) { cout << "Yes\n"; return 0; }
        for (int v : g[u]) {
            if (!vis[v] && trap[v] == 0) {
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    cout << "No\n";
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] trap = new int[n + 1];
        for (int i = 1; i <= n; i++) trap[i] = sc.nextInt();
        List<Integer>[] g = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            g[u].add(v);
            g[v].add(u);
        }
        if (trap[1] == 1 || trap[n] == 1) {
            System.out.println("No");
            return;
        }
        boolean[] vis = new boolean[n + 1];
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(1); vis[1] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            if (u == n) { System.out.println("Yes"); return; }
            for (int v : g[u]) {
                if (!vis[v] && trap[v] == 0) {
                    vis[v] = true;
                    q.add(v);
                }
            }
        }
        System.out.println("No");
    }
}

from collections import deque

n, m = map(int, input().split())
trap = [0] + list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

if trap[1] == 1 or trap[n] == 1:
    print('No')
else:
    vis = [False] * (n + 1)
    q = deque([1])
    vis[1] = True
    ok = False
    while q:
        u = q.popleft()
        if u == n:
            ok = True
            break
        for v in g[u]:
            if not vis[v] and trap[v] == 0:
                vis[v] = True
                q.append(v)
    print('Yes' if ok else 'No')

算法及复杂度

算法：图上 BFS/DFS 可达性（仅扩展安全房间）
时间复杂度： $\mathcal{O}(n+m)$
空间复杂度： $\mathcal{O}(n+m)$