题解 P3395 【路障】
lowww666
2016-10-12 20:15:50
简单灌水法
由于从a0,b0到a1,b1的最短路径长为|a1-a0|+|b1-b0|-1，所以在这个时间之后的路障都可以忽略。边读入边处理，之后灌水法bfs推一遍，看看能不能达到终点。代码：
```cpp
#include<cstdio>
using namespace std;
int f[1001][1001],n,t,x,y;
int main()
{
scanf("%d",&t);
for(int q=1;q<=t;q++)
{
scanf("%d",&n);
for(int i=1;i<=2*n-2;i++)
{
scanf("%d%d",&x,&y);
if(x==n&&y==n&&x+y-2<i)
{
printf("No\n");
break;
}
if(x+y-2>i)
f[x][y]=-1;
}
f[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((f[i-1][j]==1||f[i][j-1]==1)&&f[i][j]!=-1)
f[i][j]=1;
if(f[n][n]==1)
printf("Yes\n");
else
printf("No\n");
if(q!=t)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=0;
}
}
```