用广搜解决一切~~~

· · 题解

首先的一点是：

由于数据有T组，所以每次计算完后要重置所有用过的数据。

用结构体手写队列，加上广搜，每秒广搜完所有可能走过的地方后，再放路障。

以下的代码是定义数据的代码。

int T,n,x,y,nx,ny,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
struct q{
    int x,y;
}que[10000010],no[1001];
bool pd[1001][1001];

在上面的代码里，T是要处理的T组数据，n是棋盘大小，x，y是输入路障的坐标，nx，ny是待会广搜要用到的下一步走到的坐标，dx与dy是方向数组。 在结构体里面，que数组是用来广搜的，no数组是来存放路障的，no[i]代表第i秒结束时放路障的坐标。

下面的代码是主函数。

int main(){
    scanf("%d",&T);
    for(int e=1;e<=T;e++){
        scanf("%d",&n);
        for(int i=1;i<=2*n-2;i++){
            scanf("%d %d",&x,&y);
            no[i].x=x,no[i].y=y;
        }
        bfs();
        reset();
    }
    return 0;
}

bfs是广搜，输出此组数据能否到达。reset是重置函数。

以下是重置函数。

void reset(){
    memset(que,0,sizeof(que));
    memset(pd,0,sizeof(pd));
    memset(no,0,sizeof(no));
}

接下来重头戏，精华！！！！！广搜怎摸写？

void bfs(){
    int t=1,head=1,tail=2;
    que[head].x=1,que[head].y=1,pd[1][1]=1;
    do{
        for(int i=0;i<4;i++){
            nx=que[head].x+dx[i];
            ny=que[head].y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&pd[nx][ny]==0){
                que[tail].x=nx;
                que[tail].y=ny;
                tail++;
                pd[nx][ny]=1;
            }
        }
        pd[no[t].x][no[t].y]=1;
        t++;
        head++;
    }while(head<tail);
    for(int i=tail;i>=1;i--){
        if(que[i].x==n&&que[i].y==n){
            printf("Yes\n");
            return;
        }
    }
    printf("No\n");
    return;
}

在这里t是记录第t秒的，配合no数组，head是头指针，tail是尾指针。 先把que[head].x与.y标记为（1，1），pd[1][1]=1为（1，1）走过了。 do while循环里，for循环为4个方向，nx，ny为下一个走向，如果符合条件那么把他存到尾指针，tail++，把他标记为走过。 当这个head四个方向都判断完后，也就是这一秒走过后，用pd[no[t].x][no[i].y]=1来放路障，标记为1相当于不能走了。 do while 外的for循环为在que数组中找有没有到达（n，n）的点，如果有，输出Yes换行return，循环完毕说明没有到达，就输出No换行return。

所以完整代码如下：

#include<bits/stdc++.h>
using namespace std;
int T,n,x,y,nx,ny,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
struct q{
    int x,y;
}que[10000010],no[1001];
bool pd[1001][1001];
void bfs(){
    int t=1,head=1,tail=2;
    que[head].x=1,que[head].y=1,pd[1][1]=1;
    do{
        for(int i=0;i<4;i++){
            nx=que[head].x+dx[i];
            ny=que[head].y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&pd[nx][ny]==0){
                que[tail].x=nx;
                que[tail].y=ny;
                tail++;
                pd[nx][ny]=1;
            }
        }
        pd[no[t].x][no[t].y]=1;
        t++;
        head++;
    }while(head<tail);
    for(int i=tail;i>=1;i--){
        if(que[i].x==n&&que[i].y==n){
            printf("Yes\n");
            return;
        }
    }
    printf("No\n");
    return;
}
void reset(){
    memset(que,0,sizeof(que));
    memset(pd,0,sizeof(pd));
    memset(no,0,sizeof(no));
}
int main(){
    scanf("%d",&T);
    for(int e=1;e<=T;e++){
        scanf("%d",&n);
        for(int i=1;i<=2*n-2;i++){
            scanf("%d %d",&x,&y);
            no[i].x=x,no[i].y=y;
        }
        bfs();
        reset();
    }
    return 0;
}

禁止抄袭！！！看我写题解这么辛苦的份上给个赞吧~~~