P3395 路障 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • AsianGiao
    有什么问题可以提出,期待大佬纠错!
  • AsianGiao
    我先说一下, bfs(1,1,0);//广搜 vis[1][1]=1;//起点肯定被访问了 这两句写反了 ,不过并不影响AC!!
作者: AsianGiao 更新时间: 2019-04-18 21:02  在Ta的博客查看 举报    6  

其实这个题完全是一个BFS的简单题。

我使用了队列+BFS的做法,我觉得十分好理解。有一点要说明,STL的queue虽然好打,但是它比手写的队列运行速度要慢的(我才不考诉你我不会呢!),差别应该也不是很大吧。

大家先注意这个点:

每秒结束的时刻,大家注意,是在每一秒之后,而并不是在一开始就有路障,这就是一个坑,C君会在(x,y)上摆一个路障。B君不能走在路障上(**C君有点坏~**)。

这个题先可以用数组存储一下路障的坐标,然后在每一秒结束后,将路障放置,然后B君就不可以走。

我觉得大家(不包括大佬)如果不会的话,应该是在摆路障的问题上浪费了时间,其实,真的很简单!!!

详细解释在代码中~~~~

code:


#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
int n,zx[2000],zy[2000],k,xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};//n是矩阵的大小,zx,zy是障碍的坐标,k是数据组数,xx,yy是四个移动方向 
bool map[1001][1001],vis[1001][1001],flag;//map是地图,vis看是否被访问,flag看是否可以到达 
struct node
{
    int x,y,t;//记录坐标和现在的时间 
};
void bfs(int x,int y,int t)
{
    queue<node>q;//我喜欢用STL的队列,不喜欢手动模拟的,因为我懒啊 
    node now,net;
    now.x=x;now.y=y;now.t=t;
    q.push(now);
    while(!q.empty()) {
        now=q.front();//取出队头元素 
        q.pop();//出队 
        int a=now.x;int b=now.y;int c=now.t;//便于后面码代码 
        if(a==n && b==n) {//到了终点 
            flag=1;//改变标志 
            break;//直接退出循环 
        }
        map[zx[now.t-1]][zy[now.t-1]]=1;//要点,障碍降落,因为t是从0开始,所以要减1 
        for(int i=0;i<4;i++) {//枚举四个方向 
            int dx=a+xx[i];int dy=b+yy[i];
            if(dx>=1 && dx<=n && dy>=1 && dy<=n && map[dx][dy]==0 && vis[dx][dy]==0) {//在矩阵中,无障碍,无访问 
                net.x=dx;net.y=dy;net.t=c+1;//时间加加 
                vis[dx][dy]=1;
                q.push(net);//进入队列 
            }
        }
    }
}
int main()
{
    scanf("%d",&k);
    while(k--) {//一般是到0就结束
        scanf("%d",&n);
        memset(map,0,sizeof(map));//初始化!! 
        memset(vis,0,sizeof(vis));
        flag=0;//看是否可以到达终点的标志 
        for(int i=1;i<=2*n-2;i++)//输入障碍 
            scanf("%d%d",&zx[i],&zy[i]);
        bfs(1,1,0);//广搜 
        vis[1][1]=1;//起点肯定被访问了 
        if(flag==1)//判断 
            printf("Yes\n");
        else
            printf("No\n");
    }
}

求过!谢谢观看!

评论

  • KGV7
    请问能否证明不会出现以下情况: 一个很早放下的路障把后来B君的回头路堵了,如果按照您的算法,这个很早的路障不会起作用
作者: lowww666 更新时间: 2016-10-12 20:15  在Ta的博客查看 举报    6  

简单灌水法

由于从a0,b0到a1,b1的最短路径长为|a1-a0|+|b1-b0|-1,所以在这个时间之后的路障都可以忽略。边读入边处理,之后灌水法bfs推一遍,看看能不能达到终点。代码:

#include<cstdio>
using namespace std;
int f[1001][1001],n,t,x,y;
int main()
{
    scanf("%d",&t);
    for(int q=1;q<=t;q++)
    {
        scanf("%d",&n);
        for(int i=1;i<=2*n-2;i++)
        {
            scanf("%d%d",&x,&y);
            if(x==n&&y==n&&x+y-2<i)
            {
                printf("No\n");
                break;
            }
            if(x+y-2>i)
                f[x][y]=-1;
        }
        f[1][1]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if((f[i-1][j]==1||f[i][j-1]==1)&&f[i][j]!=-1)
                    f[i][j]=1;
        if(f[n][n]==1)
            printf("Yes\n");
        else
            printf("No\n");
        if(q!=t)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=0;
    }
}

评论

  • 魔法时间
    厉害
作者: 喝烘箱 更新时间: 2019-01-12 16:08  在Ta的博客查看 举报    3  

这么简单的题居然是D1T1!!!!

我都惊到了!!!

咳咳,不皮了,先说一下思路。

广搜从起点开始搜索太慢了!而且没有必要!虽然要过这道题的数据是轻轻松松

我们可以直接广搜路障!!!

然后时间复杂度就会直接缩小到天的另一边去!!!

首先!这是一个矩阵!

所以在无障碍的情况下这个熊孩子跑到每一个点的时间可以用数组下标直接算出来
因为我们到的每一个点的最短距离就是这两个点的横坐标之差与纵坐标之差的和

1 2 3 4 5 6 7 8 9
2 起点 -- -- -- -- -- -- --
3
4
5 o
6 o
7
8 o
9 o

很容易就能发现,以任意一个点为终点都可以与起点连成一个矩形
然后又因为只能向上下左右四个方向移动。。。
所以步数最短的走法就是一直想终点方向走,即只向下或向右走。。。
之后后就不用我说了吧
这其实是小学奥数

其次!如果在某一时刻落下路障时这个熊孩子已经走过了这个点,那这个路障就和没放完全没有区别,因为最短距离一定是一直向下或向右走,所以只要过了那个位置就再也不会走到那个位置了!

所以那个路障就可以当做没有出现过!

还有一件有意思的事,就是当所有的路障都落下来的时候,如果这些路障之间有空隙,那么他们就不能拦住这个熊孩子!

举个栗子,我们用X来代表路障,具体来看一下

1 2 3 4 5 6
2
3 X X
4 X
5
6 X end

这样就拦不住

1 2 3 4 5 6
2
3 X X
4 X
5 X
6 X end

这样就拦住了

所以不难发现,要想拦住这个娃必须要满足以下几点条件:
$1.$必须与一边相连。
$2.$每一个路标必须在另一个路标的旁边相邻位置,如斜对角线上一格,或相邻格。
$3.$这一连串相邻的路障必须将起点与终点之间的路径截断,否则不能。

然后我们就只需要从边上的路障找起,每一次寻找他的相邻的路障,只要找到了一次能够切断起点和终点的情况,就说明这个孩子走不到终点,如果把边上所有的路障都搜索过了,还没有切断,就说明这个孩子可以走到终点!

那这不就非常美滋滋了,搜索的总量已经缩小的没个人样了。。。

先在还有一个问题就是如何说明这个路障切断了起点和终点
那就分类讨论就行了

可以切断的情况一:(终点所在的一条边与终点所在的另一条边相连)

1 2 3 4 5 6
2 start
3 X X
4 X
5 X
6 X end

可以切断的情况二:(一条边和与其相对的另一条边相连)

1 2 3 4 5 6
2 start X
3 X
4 X
5 X
6 X end

1 2 3 4 5 6
2 start
3 X
4 X X X
5 X
6 end

可以切断的情况三:(起点点所在的一条边与起点点所在的另一条边相连)

1 2 3 4 5 6
2 start X
3 X
4 X X
5 X
6 end

这就是所有的情况了,只有以上的三种条件之中的任意一种,才能切断起点和终点!

所以我们可以选择两条边,每一次只要发现有在这两条边上的有效路障,就让他入队。 然后就和一般的广搜思路一模一样了,只要有哪一个路障连到了选择的两条边之外的另外两条边,就走不到终点。(选择的两条边必须相邻)

有一个小技巧,就是我们可以定义两个数组$dx , dy$,来表示这个路障下一次搜索的方向

    int dx[8]={-1,1,0,0,1,-1,-1,1};
    int dy[8]={0,0,-1,1,-1,1,-1,1};

这之后寻找路障(位置 $x$,$y$)就只需要在$x+dx[i] , y+dy[i]$这八个位置就行了

具体操作请见代码:

#include<cstdio>
#include<algorithm>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
int a[1010][1010],T,n,x,y;

queue<int> nx;
queue<int> ny;

int dx[8]={-1,1,0,0,1,-1,-1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};

bool judge( int xx,int yy )
{
    if(xx>=1&&yy>=1&&xx<=n&&yy<=n)
    {
        if(a[xx][yy]>=1)
        {
            return true;
        }
    }
    return false;
}

void bfs()
{
    while(!nx.empty())
    {
        int nowx=nx.front();
        int nowy=ny.front();
        nx.pop();
        ny.pop();

        if( nowx==n||nowy==1 )          
        {
            printf("No\n");
            return ;
        }

        for(int i=0;i<=7;i++)
        {
            int nexx=nowx+dx[i];
            int nexy=nowy+dy[i];
            {
                if(judge(nexx,nexy))
                {
                    nx.push(nexx);
                    ny.push(nexy);
                    a[nexx][nexy]=0;
                }
            }
        }   
    }

    printf("Yes\n");
    return;
}

int main()
{
    scanf("%d",&T);
    for(int s=1;s<=T;s++)
    {
        scanf("%d",&n);
        int o=2*n-2;
        for(int i=1;i<=o;i++)
        {
            scanf("%d %d",&x,&y);
            if( x+y-2 > i )
            {
                a[x][y]=1;
                if(x==1||y==n)
                {
                    nx.push(x);
                    ny.push(y);
                }
            }
        }
        bfs();
        memset(a,0,sizeof(a));
    }
    return 0;
}

评论

  • xsl666
    time是头文件<ctime>中的标准名字吧
  • Aehnuwx
    vis数组难道不会MLE嘛?计算一下,其需要的空间为10005*10005*1=100.100025MB,再加上其他各种数组和循环变量,早超空间了
  • cuichenxi
    不会爆
  • cuichenxi
    虽然vis没什么用
作者: luoyue123 更新时间: 2017-10-25 12:55  在Ta的博客查看 举报    2  

发现题解里没有人贴STL队列的代码0.0就是一个简单的bfs,注意路障的处理,注意数组别开小了和判断入队的合法性。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=10005;
struct point{
    int x,y,time;//x,y是点的坐标,time是时间。
};
point a,z[MAXN];//z数组要开的足够大啊。(大于2*n-2)之前开小RE了好几次。。
queue<point>q; //STL队列
bool vis[MAXN][MAXN];
int ax[]={0,0,1,-1},ay[]={1,-1,0,0},n,g;//ax ay是四个方向判断
void bfs(){
    bool flag=0;
    while(!q.empty()){
        point u=q.front();
        q.pop();
        if(u.x==n&&u.y==n){
            printf("Yes\n");
            flag=1;
            break;
        }
        vis[z[u.time-1].x][z[u.time-1].y]=1;//因为是BFS,时间和入队顺序是按时间层层递进的。
        for(int i=0;i<=3;i++){
            if(!vis[u.x+ax[i]][u.y+ay[i]]&&u.x+ax[i]>=1&&u.x+ax[i]<=n&&u.y+ay[i]>=1&&u.y+ay[i]<=n){//判断合法性
                vis[u.x+ax[i]][u.y+ay[i]]=1;//直接标记为走过以免重复入队
                q.push((point){u.x+ax[i],u.y+ay[i],u.time+1});//入队
            }
        }
    }
    if(flag==0)printf("No\n");
}
int main(){
//    freopen("3395.in","r",stdin);
//    freopen("3395.out","w",stdout);
    scanf("%d",&g);
    for(int l=1;l<=g;l++){
        memset(vis,0,sizeof(vis));
        memset(z,0,sizeof(z));
        scanf("%d",&n);
        for(int i=1;i<=2*n-2;i++){
            scanf("%d%d",&z[i].x,&z[i].y);
        }
        while(!q.empty()){
            q.pop();//清空数组
        }
        q.push((point){1,1,1});
        vis[1][1]=1;//避免走回起点
        bfs();
    }
    return 0;
}

评论

  • Aehnuwx
    orz hhx
作者: huanghaox1212 更新时间: 2019-01-13 17:18  在Ta的博客查看 举报    0  

其实这题不需要BFS,只需要一个简单的二维DP!

首先,如很多题解所述,我们要明确什么时候障碍物是对这个熊孩子有用的。

其实这里要认识到,最短路径一定是向右或者向下走的。这是因为熊孩子不可能折回到他以前早已走过的点。如果仍不理解,参考一下BFS的搜索规则会给您一些帮助。

因为地图是一个矩阵,按照上述的规则,从点$(a,b)$到$(c,d)$的最短时间就是他们之间的曼哈顿距离减去1:$c-a+d-b-1$。

故第$i$秒,代入上式,只有满足$x+y-2>i$的障碍物才有作用(这样就不会落到已经走过的点上)。

按照此规则,一个点$(i,j)$可以从$(i-1,j)$和$(i,j-1)$走来,并且该点不可以有障碍物。这样这题就演变为一个求联通块的题目,可以使用二维DP。状态转移方程如下:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f_{i,j}=(f_{i-1,j}|f_{i,j-1})\&dag_{i,j}$

其中dag记录该点是否有有效的障碍物。有效的条件已经讨论过了。

那么代码奉上:

#include<cstdio>
#include<cstring>
using namespace std;
#define reg register
static int n,t,x,y;
static char dp[1001][1001],dag[1001][1001];
int main(){
    scanf("%d",&t);
    while(t--){
        memset(dp,0,sizeof(dp)),
        memset(dag,0,sizeof(dag));//这里很重要!因为有多组数据,每次必须初始化。
        scanf("%d",&n);
        for(reg int i=1;i<=2*n-2;++i){
            scanf("%d%d",&x,&y);
            if(x==n&&y==n&&x+y-2<i){
                puts("No");
                break;
            }
            if(x+y-2>i)dag[x][y]=1;//标记有效的障碍物。
        }
        dp[1][1]=1;
        for(reg int i=1;i<=n;++i)
            for(reg int j=1;j<=n;++j)
                dp[i][j]|=(dp[i-1][j]||dp[i][j-1])&&!dag[i][j];//DP方程
        if(dp[n][n])puts("Yes");
        else puts("No");
    }
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。