题解 P3395 路障

前言

没想到这是\(\sf {tgD1T1}\)难度……

题目大意

有一个\(n\times n\) 的棋盘，有\(2n-2\) 个路障，在第\(i\) 秒会在\((x_i,y_i)\) 放置路障。求B君是否能从\((1,1)\) 走到\((n,n)\) 。

\(\sf Solution\)

模拟+bfs。

从起点开始，边走边放置路障。碰到路障就不继续走，找到一条路径就标记并break 。若搜完整个棋盘仍未找到路径，输出No，否则Yes。

\(\sf {P.S.}\)

注意放置路障后该位置永久无法通行。如果只是单纯的判断，是会WA+MLE的……

\(\sf {Code}\)

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

int t,n,a[2001],b[2001],xx,yy,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

bool vis[1001][1001],flag;

struct node

{

    int x,y,k;

} o;

queue<node>q;

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        while(!q.empty())

            q.pop();

        memset(vis,0,sizeof(vis));

        memset(a,0,sizeof(a));

        memset(b,0,sizeof(b));

        vis[1][1]=true;flag=false;//初始化

        scanf("%d",&n);

        for(int i=1;i<=2*n-2;++i)

            scanf("%d%d",&a[i],&b[i]);//读入

        q.push((node){1,1,0});//入队

        while(!q.empty())//bfs

        {

            o=q.front(),q.pop();

            if(o.x==n&&o.y==n)//找到路径

            {

                printf("Yes\n");

                flag=true;//标记

                break;

            }

            vis[a[o.k-1]][b[o.k-1]]=1;//放置路障

            for(int i=0;i<4;++i)

            {

                xx=o.x+dx[i],yy=o.y+dy[i];

                if(xx<=0||yy<=0||xx>n||yy>n||vis[xx][yy]||a[o.k]==o.x&&b[o.k]==o.y)

                    continue;//判断不合法情况

                vis[xx][yy]=true;q.push((node){xx,yy,o.k+1});//标记为已走并入队

            }

        }

        if(flag==false)

            printf("No\n");//未找到路径，输出No

    }

    return 0;

}

题解 P3395 路障的相关教程结束。