旺仔哥哥走迷宫【牛客tracker 每日一题】

旺仔哥哥走迷宫时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述迷宫由n nn个房间和m mm条双向通道组成房间编号1 ∼ n 1∼n1∼n。已知存在m mm对整数a i , b i a_i,b_iai​,bi​表示房间a i a_iai​与b i b_ibi​之间有通道。旺仔哥哥起始位于房间1 11迷宫出口在房间n nn。部分房间被设置了致命陷阱。设数组t tt当t i 1 t_i1ti​1时表示房间i ii有陷阱t i 0 t_i0ti​0表示安全。旺仔哥哥只能经过安全房间。请判断他是否能够从1 11号房间仅经过安全房间到达房间n nn。【名词解释】双向通道给出一对a i , b i a_i,b_iai​,bi​即可双向通行。输入描述第一行输入两个整数n , m ( 1 ≦ n , m ≦ 10 5 ) n,m(1≦n,m≦10^5)n,m(1≦n,m≦105)——房间数与通道数。第二行输入n nn个整数t 1 , … , t n ( t i ∈ { 0 , 1 } ) t_1,…,t_n(t_i∈\{0,1\})t1​,…,tn​(ti​∈{0,1})表示各房间是否存在陷阱。接下来m mm行每行输入两个整数a i , b i ( 1 ≦ a i , b i ≦ n ) a_i,b_i(1≦a_i,b_i≦n)ai​,bi​(1≦ai​,bi​≦n)表示房间a i a_iai​​ 与b i b_ibi​​ 之间有一条双向通道。输出描述若存在一条仅经过安全房间的路径从房间1 11到房间n nn输出单词Y e s YesYes首字母大写否则输出N o NoNo。示例1输入3 3 0 1 0 1 2 2 3 1 3输出Yes说明路径1 → 3 1→31→3仅经过安全房间可成功逃离。解题思路本题是无向图连通性判断问题核心采用广度优先搜索(BFS)高效求解。迷宫由n个房间和m条双向通道构成仅允许经过无陷阱t0的房间。首先做合法性预判若起点1或终点n存在陷阱直接输出No。用邻接表存储图的结构从起点1启动BFS遍历遍历过程中仅访问未被访问且无陷阱的节点一旦遍历到终点n立即输出Yes并终止程序若BFS完成仍未到达终点则输出No。算法时间复杂度O ( n m ) O(nm)O(nm)完美适配n 、 m ≤ 10 5 n、m≤10^5n、m≤105的大数据约束。总结核心逻辑BFS遍历无向图过滤陷阱节点判断起点与终点是否连通。关键操作邻接表建图、提前预判起点终点合法性、遍历中过滤陷阱节点。效率保障线性时间复杂度快速处理大规模图数据无超时风险。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;if(!(cinnm))return0;vectorllt(n1);for(ll i1;in;i)cint[i];vectorvectorlladj(n1);for(ll i0;im;i){ll u,v;cinuv;adj[u].push_back(v);adj[v].push_back(u);}if(t[1]1||t[n]1){coutNo\n;return0;}vectorllvis(n1,0);queuellq;q.push(1);vis[1]1;while(!q.empty()){ll uq.front();q.pop();if(un){coutYes\n;return0;}for(ll v:adj[u])if(!vis[v]t[v]0){vis[v]1;q.push(v);}}coutNo\n;return0;}