P1605 迷宫 题解


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

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

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

评论

  • gjh303987897
    想问一下,if里面的return会直接结束dfs函数的运行吗,那如果是这样的话答案最多是1啊
  • 苏子林
    扬皓大佬太强了
  • 苏子林
    日膜一波扬皓大佬
  • 苏子林
    sto%%%orz
  • 苏子林
    顺便再来一个赞
  • 扬皓2006
    return ;是结束这一层的递归,也就是回溯(相当于迷宫走不通往回走一样)
  • 一经多少年
    你好请问那个nex【x】【y】=0,为什么要回溯一步
  • 一经多少年
    你好还有就是那个主函数里标记空地用=1,遇到障碍用=0;那让标记空地=0,遇到障碍=1为什么不可以呢,我试了一下运行不出来哎
  • lsz0625
    萌新不懂欸,这样求出来的mi似乎并不是最小步数而是最后一个走通的路的步数啊。。求教
作者: 扬皓2006 更新时间: 2019-08-08 23:51  在Ta的博客查看 举报    8  

在进入正题之前,我们先来看一个题目

迷宫由n行m列的单元格组成(n,m都小于等于100),每个单元格要么是空地(1),要么是障碍物(0)你的任务是帮助小哼找到一条从迷宫的起点通往小哈所在位置的最少步数。

输入:第一行,n,m

第2~n+1行 每行m个数(0或1)

第n+2行:sx(起点横坐标),sy(起点纵坐标),fx(终点横坐标),fy(终点纵坐标)

输出:1个数,为最少步数(保证有解)

代码:


#include<bits/stdc++.h>//万能头
using namespace std;
int n,mi=0,m;
int dx[4]={0,0,1,-1};//4方向
int dy[4]={1,-1,0,0};
int nex[101][101];//判断是否走过数组
int tem[101][101];//地图数组
int fx,fy,sx,sy;
void dfs(int x,int y,int ste)
{
    if(x==fx&&y==fy)
    {
        mi=ste;//换成全局变量输出
        return ;
    }
    for(int i=0;i<=3;i++)
    {
        if(nex[x+dx[i]][y+dy[i]]==0&&tem[x+dx[i]][y+dy[i]]==1)//如果没有走过且没障碍
        {
            nex[x][y]=1;//标记过已走过
            dfs(x+dx[i],y+dy[i],ste+1);//继续搜索
            nex[x][y]=0;//回溯一步
        }
    } 
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>tem[i][j];
            nex[i][j]=0;//全标记为没走过
        }
    }
    cin>>sx>>sy>>fx>>fy;
    dfs(sx,sy,0);
    cout<<mi;
    return 0;
}

好 如果你上面这题会写 那么本题(P1605)你也会写了

只需要在代码上做点修改,如下:
#include<bits/stdc++.h>//万能头
using namespace std;
int n,m,coun=0,t;
int sx,sy,fx,fy;
int ma[6][6];
int a[6][6]={0};//全为没走过
int dx[4]={0,0,1,-1};//地图数组
int dy[4]={1,-1,0,0};
int b,c;//障碍坐标
void dfs(int x,int y)
{
    if(x==fx&&y==fy)//如果到达
    {
        coun++;return ;//方案+1并回溯
    }
    else{
        for(int i=0;i<=3;i++)
    {
        if(ma[x+dx[i]][y+dy[i]]==1&&a[x+dx[i]][y+dy[i]]==0)//如果没有障碍且没有走过
        {
            a[x][y]=1;//标记为已走过
            dfs(x+dx[i],y+dy[i]);//继续搜索
            a[x][y]=0;//回溯一步
         } 
    } 
    } 
}
int main()
{
    cin>>n>>m>>t;
    cin>>sx>>sy>>fx>>fy;
    a[sx][sy]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ma[i][j]=1;//全标记为空地
        }
    }
    for(int i=1;i<=t;i++)
    {
        cin>>b>>c;
        ma[b][c]=0;//标记障碍
    }
    dfs(sx,sy);//开始搜索
    printf("%d",coun);
    return 0;
}
做完这道题后,大家也可以做一下P1451 P1506 P1596 都是DFS求联通块的题目

最后,希望大家能学会DFS,也希望管理大大能通过此篇题解!

评论

  • Error_Eric
    希望通过!
  • 刘远超
    太妙了!
  • zxc2579738746
    思路清晰
作者: Error_Eric 更新时间: 2019-08-01 11:33  在Ta的博客查看 举报    5  

这是标准的搜索题目,我用的是深度优先,然而bfs似乎也可以用

深搜起点(sx,sy)

深搜拓展——举目四望上下左右 废话

深搜返回条件1:到达终点

深搜返回条件2:越界或进入不该进入的区域

深搜返回条件3:三面楚歌(即所有拓展已经return)

然后就可以愉快地码代码咯!

代码:

#include<iostream>
#include<algorithm>
using namespace std;
int vis[7][7];//是否允许行人通行
int n,m,t,total=0;
//total==方案总数
//其他如题
int sx,sy,fx,fy;
bool judge(int xxx,int yyy){//判断是否能走
    if(vis[xxx][yyy]>=1) return 0; //这里的地面被踩过了
    if(xxx>n || xxx<1) return 0;//光荣地掉下了悬崖
    if(yyy>m || yyy<1) return 0;//光荣地掉下了悬崖
    return 1; //似乎很安全
}
void dfs(int x,int y){ //我在那,我在(x,y)
    if(x==fx&&y==fy){//到达了终点
    //走上人生巅峰
        total++;//次数++
        return ;
    }
    int xx,yy;//下一步走哪儿?
    xx=x+1;yy=y;//举目四望之1(右方)
    if(judge(xx,yy)){
        vis[x][y]=1;
        dfs(xx,yy);
        vis[x][y]=0;//时光倒流——回溯
    }
    xx=x-1;yy=y;//举目四望之2(左方)
    if(judge(xx,yy)){
        vis[x][y]=1;
        dfs(xx,yy);
        vis[x][y]=0;//时光倒流——回溯
    }
    xx=x;yy=y+1;
    if(judge(xx,yy)){//举目四望之3(上方)
        vis[x][y]=1;
        dfs(xx,yy);
        vis[x][y]=0;//时光倒流——回溯
    }
    xx=x;yy=y-1;
    if(judge(xx,yy)){//举目四望之4(下方)
        vis[x][y]=1;
        dfs(xx,yy);
        vis[x][y]=0;//时光倒流——回溯
    }
    //四面楚歌
    return; 
} 
int main(){
    //输入
    cin>>n>>m>>t;//如题
    cin>>sx>>sy>>fx>>fy;
       //起点    终点
    int la,lb;
    for(int i=1;i<=t;i++){//输入障碍
        cin>>la>>lb;
        vis[la][lb]=9;//插翅难飞
    }
    dfs(sx,sy);//勇敢的迈出第一步!
    cout<<total;//输出
    return 0;//程序的结束
             //迷宫的终结
}

评论

  • Axev
    还没有评论
  • Axev
    写下你的评论
作者: Code渐行渐远 更新时间: 2019-07-14 10:37  在Ta的博客查看 举报    5  

整体来说这道题目比较的简单,是比较基础的搜索题


思路就是从起点开始采用dfs的思想,一直向下搜索,一旦遇到目标点就记为+1次


代码如下:


#include<iostream>
using namespace std;

int a[6][6];//用来储存地图和标记作用
int next[4][2]={{1, 0}, {-1, 0},{0, 1},{0, -1}};//方向数组
int sx, sy, fx, fy;//代表了起点和终点的坐标
int m, n, t;//m代表行,n代表列,t代表障碍数
int ans = 0;//总的条数
void dfs(int sx, int sy){
    int nx, ny;
    if(sx == fx && sy == fy){//终点的判定条件
        ans++;
        return;
    }
    a[sx][sy] = 1;//走过的要进行标记
    for(int i = 0; i < 4; ++i){//枚举上下左右四个方向
        nx = sx + next[i][0];
        ny = sy + next[i][1];
        if(nx < 1 || nx > m || ny < 1 || ny > n)//边界的判定条件
            continue;
        if(a[nx][ny] == 0){
            a[nx][ny] = 1;
            dfs(nx,ny);
            a[nx][ny] = 0;
        }
    }
}
int main(){
    cin >> m >> n >> t;
    cin >> sx >> sy >> fx >> fy;
    int x, y;
    for(int i = 0; i < t; ++i){
        cin >> x >> y;
        a[x][y]=1;//标记障碍的位置
    }
    dfs(sx,sy);

    cout << ans << endl;
    return 0;
}

第一次发题解,望管理员通过^_^

评论

  • 还没有评论
作者: 「QQ红包」  发红包了 更新时间: 2015-11-04 20:49  在Ta的博客查看 举报    5  

深度搜索。

要注意一个地方:棋盘内每一个点都可以走。只要该点在棋盘内就可以走。


var n,m,t,x1,y1,x2,y2,sum,xx,yy,i:longint;
    a,b:array[-10..100,-10..100] of longint;
procedure try(x,y:longint);
begin
    if (x=x2)and(y=y2) then inc(sum) else
    begin
        if (x>=1)and(y>=1)and(x+1<=n)and(y<=m)and(a[x+1,y]=0)
        and(b[x+1,y]=0) then begin b[x+1,y]:=1;try(x+1,y);b[x+1,y]:=0; end;
        if (x>=1)and(y>=1)and(x<=n)and(y+1<=m)and(a[x,y+1]=0)
        and(b[x,y+1]=0) then begin b[x,y+1]:=1;try(x,y+1);b[x,y+1]:=0; end;
        if (x-1>=1)and(y>=1)and(x<=n)and(y<=m)and(a[x-1,y]=0)
        and(b[x-1,y]=0) then begin b[x-1,y]:=1;try(x-1,y);b[x-1,y]:=0; end;
        if (x>=1)and(y-1>=1)and(x<=n)and(y<=m)and(a[x,y-1]=0)
        and(b[x,y-1]=0) then begin b[x,y-1]:=1;try(x,y-1);b[x,y-1]:=0; end;
    end;
end;
begin
    fillchar(a,sizeof(a),0);
    fillchar(b,sizeof(b),0);
    read(n,m,t,x1,y1,x2,y2);//a[x2,y2]:=100;
    for i:=1 to t do
    begin
        read(xx,yy);
        a[xx,yy]:=1;
    end;
    b[x1,y1]:=1;
    try(x1,y1);
    write(sum);
end.

评论

  • 还没有评论
作者: 煮酒论英雄 更新时间: 2019-08-17 19:21  在Ta的博客查看 举报    3  

在下刚刚学完深搜,就做了一题AC,都不好意思说自己是蒟蒻了(好吧,我本就是蒟蒻)

反正,这题除了深搜,还是深搜。

深搜,一句话来总结一下,就是:

不撞南墙不回头

而在这题里,“南墙”有三个:

第一个是真墙:迷宫的围墙

也就是俗话所说的越界。越界了你还不回头,你是想去哪儿?

第二个是山墙:障碍物T(姑且认为是山)

如果一座山横在你面前,你还是绕路吧!

第三个是人造墙:题目说了每个方格最多只能走一次

这是真没办法

所以深搜的返回条件就出来了——就是以上那三堵墙

我们每次可以从上下左右四个方向进行深搜,一旦遇上南墙就返回,如果走到了重点,s++。

记住了,题目里说保证起点没有障碍,并没有保证重点也没有啊

好了,上代码吧

#include<bits/stdc++.h>
using namespace std;
int a[6][6];
int tx,ty,sx,sy,fx,fy,t;
int n,m,s;
void dfs(int x,int y)//用x来表示x坐标,y来表示y坐标 
{
    if(x<1||x>n)//x坐标越界 
        return;
    if(y<1||y>m)//y坐标越界 
        return;
    if(x==fx&&y==fy)
    {
        s++;//终点站到了 
        return;
    }   
    if(a[x][y]==1||a[x][y]==2)//1代表走过了,2代表障碍 
        return;
    a[x][y]=1;
    dfs(x+1,y);//下 
    dfs(x,y+1);//右 
    dfs(x-1,y);//上 
    dfs(x,y-1);//左 
    a[x][y]=0;//清零 
}
int main()
{
    cin>>n>>m>>t;
    cin>>sx>>sy>>fx>>fy;
    for(int i=0;i<t;i++)
    {
        cin>>tx>>ty;
        a[tx][ty]=2;//标记障碍 
    }
    if(a[fx][fy]==2)//如果终点有障碍 
    {
        cout<<"0";//就没必要搜了 
        return 0;//肯定搜不到 
    }
    dfs(sx,sy);//从起点开始 
    cout<<s;
    return 0;
}

嗯,我看到标签里有枚举和暴力,这题能用枚举?(怀疑智商)

还有递推,有谁找到这题的递推关系式了?请评论区留个言,谢谢

 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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