「Luogu P3395」路障 解题报告

题面

这D1T1给的很有面子！ 我居然做的来！

从左上角走到右上角

然后n<=1000

所以果断放弃DFS，选择BFS

思路还是一样的BFS

证明：

走到一个点的时间越早越好（因为时间越晚能走到的点越少，路障多了）

所以用BFS，走过的点不用再次走，用 vis数组记录已经是否遍历过

然后为了防止跑出棋盘去（B君看到了棋盘外美铝？！）

我们就给棋盘加一个 ‘1’的边框，这样就不会出去

然后还要记录一个时间t、x、y，可以用一个结构体

构造用

struct node{

​ int x,y,t;

​ node(int a,int b,int c):x(a),y(b),t(c) { }

​ node(){}

};

node(x,y,t)//直接构造

但是本菜还是比较喜欢用两个queue

一个存pair(x,t)，一个存y

贴上：

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
using namespace std;
int Cx[4]={1,0,0,-1};//四个方向，八个方向也一样
int Cy[4]={0,1,-1,0};//在下有强迫症，所以用两个数组
int n,T;
int x,y;
int b[1010][1010];
bool vis[1010][1010];
int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s;
}
bool BFS()
{
    int i,t;
    int Tx,Ty;
    queue<pair<int,int> >px;
    queue<int>py;
    while(!py.empty())
        px.pop(),py.pop();
    px.push(make_pair(1,1));
    py.push(1);
    vis[1][1]=1;
    while(!px.empty())
    {
        x=px.front().first;
        t=px.front().second;px.pop();
        y=py.front();py.pop();
        if(x==n&&y==n)//有了这句就不用特判n=1的情况了
            return 1;
        for(i=0;i<4;i++)
        {
            Tx=x+Cx[i];
            Ty=y+Cy[i];
            if(!vis[Tx][Ty]&&t<=b[Tx][Ty])
            {
                vis[Tx][Ty]=1;
                px.push(make_pair(Tx,t+1));
                py.push(Ty);
            }
        }
    }
    return 0;
}
int main()
{
    int i;
    T=read();
    while(T--)
    {
        n=read();
        memset(vis,0,sizeof(vis));
        memset(b,INF,sizeof(b));//一开始赋无穷大比较方便
        for(i=1;i<=n;i++)//裱框
            vis[i][0]=vis[0][i]=vis[n+1][i]=vis[i][n+1]=1;
        for(i=1;i<=2*n-2;i++)
        {
            x=read();y=read();
            b[x][y]=i;
        }
        if(BFS())//此处纪念ydk大佬把"Yes"打成"YES"，本蒟瑟瑟发抖
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}