学习总结2.17

将每个路障录入地图中，同时每个路障以落下的时间命名，当到达路障点的时候，步数小于路障落下时间，即算作可以通过

#include <stdio.h>
#include<stdlib.h>
#define max 1005
int n;
int block[max][max];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};//上左下右
int row,line;
int vis;
int b;
typedef struct{
    int x,y,step;
}Node;
Node node[max][max];
void bfs(){
    Node que[max*max];//数组模拟队列
    int head=0,tail=0;
    node[1][1]=(Node){1,1,0};//起点入队
    que[tail++]=node[1][1];
    while(head<tail){//队列不为空
        Node t=que[head++];//队列中取出一个节点
        int s=t.step;
        for(int i=0;i<4;i++){
            row=t.x+dx[i];
            line=t.y+dy[i];
            vis=node[row][line].step;//是否被遍历
            b=block[row][line];
            if(row>=1&&row<=n&&line>=1&&line<=n&&vis==0&&(b==0||s+1<=b)){
                node[row][line]=(Node){row,line,s+1};
                que[tail++]=node[row][line];
            }
        }
    }
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--){
        memset(block,0,sizeof(block));
        memset(node,0,sizeof(node));
        scanf("%d",&n);
        if(n==1){//1*1地图大小
            printf("Yes\n");
            continue;
        }
        for(int i=1;i<=2*n-2;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            block[a][b]=i;//以路障落下的时间命名
        }
        bfs();
        if(node[n][n].step>0) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}