题目链接
洛谷 P3395 路障
思路分析
一道迷宫类问题，但不同的是它的障碍物的出现是在一既定时间往后。即对于位于 \(x_i,y_i\) 的障碍物 \(i\)，它会在第 \(i\) 秒末尾开始出现，即第 \(i+1\) 秒后的移动都需要考虑它。
我们就定义 \(mp_{i,j}\) 数组，一开始全部赋极大值 0x3f3f3f3f，对于障碍物 \(p\)，\(mp_{x_p,y_p}=p\)，即存储出现在哪一秒末尾。而对于移动来说，若第 \(q\) 秒到达，则 \(mp_{i,j}=-q\)，即到达时间倒数。
所以当可以在第 \(q\) 秒到达时，若 \(q\le mp_{x_p,y_p}\)，即还无需考虑这个障碍物，就按空格处理；否则则按障碍物处理。
代码如下，时间复杂度 \(O(Tn^2)\)，注意由于总共有 \(2n-2\) 秒，所以要开两倍的数组存储。
代码呈现
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;const int N=1010;
int t,n;
int x[N*2],y[N*2],mp[N][N],dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1};void bfs(){queue<pii> q;q.push({1,1}),mp[1][1]=0;while (!q.empty()){pii u=q.front();q.pop();for (int i=1;i<=4;++i){int nx=u.first+dx[i],ny=u.second+dy[i],ns=-mp[u.first][u.second]+1; // 原本 mp[u.first][u.second] 存的是负值if (nx>=1 && nx<=n && ny>=1 && ny<=n && ns<=mp[nx][ny])mp[nx][ny]=-ns,q.push({nx,ny});}}
}
int main(){scanf("%d",&t);while (t--){scanf("%d",&n);for (int i=1;i<=2*(n-1);++i) scanf("%d%d",x+i,y+i);memset(mp,0x3f,sizeof mp); // 多测不清空for (int i=1;i<=2*(n-1);++i) mp[x[i]][y[i]]=i;bfs();printf(mp[n][n]<=0?"Yes\n":"No\n"); // <=0 表示能到达}return 0;
}