P3395 路障
题目背景
此题约为NOIP提高组Day1T1难度。
题目描述
B君站在一个n*n的棋盘上。最开始，B君站在(1,1)这个点，他要走到(n,n)这个点。
B君每秒可以向上下左右的某个方向移动一格，但是很不妙，C君打算阻止B君的计划。
每秒结束的时刻，C君会在(x,y)上摆一个路障。B君不能走在路障上。
B君拿到了C君准备在哪些点放置路障。所以现在你需要判断，B君能否成功走到(n,n)。
保证不会走到某处，然后被一个路障砸死。
输入输出格式
输入格式：
首先是一个正整数T，表示数据组数。
对于每一组数据：
第一行，一个正整数n。
接下来2n-2行，每行两个正整数x和y，意义是在那一秒结束后，(x,y)将被摆上路障。
输出格式：
对于每一组数据，输出Yes或No，回答B君能否走到(n,n)。
输入输出样例
输入样例#1：
2 2
1 1
2 2 5
3 3
3 2
3 1
1 2
1 3
1 4
1 5
2 2
输出样例#1：
Yes
Yes
说明
样例解释：
以下0表示能走，x表示不能走，B表示B君现在的位置。从左往右表示时间。
Case 1:
0 0 0 0 0 B (已经走到了)
B 0 x B x 0 Case 2:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 x 0 0 0 0 x 0 0 0 0 x 0 0
0 0 0 0 0 0 0 0 0 0 0 0 x 0 0 0 0 x 0 0
B 0 0 0 0 0 B 0 0 0 0 0 B 0 0 0 0 x B 0 ......(B君可以走到终点)数据规模：
防止骗分，数据保证全部手造。
对于20%的数据，有n<=3。
对于60%的数据，有n<=500。
对于100%的数据，有n<=1000。
对于100%的数据，有T<=10。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int T,n;
int f[],k[];
bool a[][],b[][];
void bfs(int x,int y,int t)
{
if (t<=*n-)
b[f[t]][k[t]]=;
if (x+<=n && b[x+][y]== && a[x+][y]==)
{ a[x+][y]=;
bfs(x+,y,t+);
}
if (x->=&&b[x-][y]==&&a[x-][y]==)
{
a[x-][y]=;
bfs(x-,y,t+);
}
if (y+<=n&&b[x][y+]==&&a[x][y+]==)
{
a[x][y+]=;
bfs(x,y+,t+);
}
if (y->=&&b[x][y-]==&&a[x][y-]==)
{
a[x][y-]=;
bfs(x,y-,t+);
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
cin>>n;
memset(a,,sizeof(a));
memset(b,,sizeof(b));
memset(f,,sizeof(f));
memset(k,,sizeof(k));
for (int i=;i<=*n-;i++)
scanf("%d%d",&f[i],&k[i]);
a[][]=;
bfs(,,);
if (a[n][n])
printf("YES\n");
else
printf("NO\n");
}
}