```cpp
#include <stdio.h>
#include <string.h>
int dx[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int que[5000001][3],b[1001][1001],a1[1001],a2[1001],v;
void BFS(int sum,int n)
{
memset(que,0,sizeof(que));
memset(b,0,sizeof(b));
int tail=1,head=0,p=1;
que[tail][0]=1;
que[tail][1]=1;
que[tail][2]=0;
b[1][1]=1;
do
{
head++;
b[a1[que[head][2]]][a2[que[head][2]]]=1;
for (int i=0;i<4;i++)
{
int x1=que[head][0]+dx[i][0];
int y1=que[head][1]+dx[i][1];
if (x1==n && y1==n)
{
v=1;
return ;
}
if (x1>=1 && x1<=n && y1>=1 && y1<=n && b[x1][y1]==0)
{
tail++;
que[tail][0]=x1;
que[tail][1]=y1;
b[x1][y1]=1;
que[tail][2]=que[head][2]+1;
}
}
}while (head<tail);
}
int main()
{
int t,n;
scanf("%d",&t);
while (t>=1)
{
t--;
scanf("%d",&n);
int k=2*n-2;
for (int i=1;i<=k;i++)
scanf("%d %d",&a1[i],&a2[i]);
v=0;
BFS(k,n);
if (v)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
现在40分了
```
by Sakura_Peng @ 2017-10-23 21:40:14
```cpp
#include <stdio.h>
#include <string.h>
int dx[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int que[5000001][3],b[1001][1001],a1[1001],a2[1001],v;
void BFS(int sum,int n)
{
memset(que,0,sizeof(que));
memset(b,0,sizeof(b));
int tail=1,head=0,p=1;
que[tail][0]=1;
que[tail][1]=1;
que[tail][2]=1;
b[1][1]=1;
do
{
head++;
b[a1[que[head][2]]][a2[que[head][2]]]=1;
for (int i=0;i<4;i++)
{
int x1=que[head][0]+dx[i][0];
int y1=que[head][1]+dx[i][1];
if (x1>=1 && x1<=n && y1>=1 && y1<=n && b[x1][y1]==0)
{
if (x1==n && y1==n)
{
v=1;
return ;
}
tail++;
que[tail][0]=x1;
que[tail][1]=y1;
b[x1][y1]=1;
que[tail][2]=que[head][2]+1;
}
}
}while (head<tail);
}
int main()
{
int t,n;
scanf("%d",&t);
while (t>=1)
{
t--;
scanf("%d",&n);
int k=2*n-2;
for (int i=1;i<=k;i++)
scanf("%d %d",&a1[i],&a2[i]);
v=0;
BFS(k,n);
if (n==1)
v=1;
if (v)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
60分了，这就比较GG了
```
by Sakura_Peng @ 2017-10-23 21:57:15
过了，发现是因为数组开小了
```cpp
#include <stdio.h>
#include <string.h>
int dx[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int que[5000001][3],b[1001][1001],a1[3001],a2[3001],v;
void BFS(int n)
{
memset(que,0,sizeof(que));
memset(b,0,sizeof(b));
int tail=1,head=0;
que[tail][0]=1;
que[tail][1]=1;
que[tail][2]=1;
b[1][1]=1;
do
{
head++;
// b[a1[que[head][2]]][a2[que[head][2]]]=1;
for (int i=0;i<4;i++)
{
//b[a1[que[head][2]]][a2[que[head][2]]]=1;
int x1=que[head][0]+dx[i][0];
int y1=que[head][1]+dx[i][1];
if (x1>=1 && x1<=n && y1>=1 && y1<=n && b[x1][y1]==0)
{
if (x1==n && y1==n)
{
v=1;
return ;
}
tail++;
que[tail][0]=x1;
que[tail][1]=y1;
b[x1][y1]=1;
que[tail][2]=que[head][2]+1;
}
/*if (que[tail][0]==n && que[tail][1]==n)
{
v=1;
return ;
}
```
\*/
```cpp
//b[a1[que[head][2]]][a2[que[head][2]]]=1;
}
b[a1[que[head][2]]][a2[que[head][2]]]=1;
}while (head<tail);
}
int main()
{
int t,n;
scanf("%d",&t);
while (t>=1)
{
t--;
scanf("%d",&n);
int k=2*n-2;
for (int i=1;i<=k;i++)
scanf("%d%d",&a1[i],&a2[i]);
v=0;
BFS(n);
if (n==1 )
v=1;
memset(a1,0,sizeof(a1));
memset(a2,0,sizeof(a2));
if (v)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
```
by Sakura_Peng @ 2017-10-24 22:46:03