P1605 迷宫 题解


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

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

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

评论

  • 凤凰战士
    Orz
作者: skylee  更新时间: 2016-10-30 10:55  在Ta的博客查看 举报    1  

基本思路就是深搜啦~

将二位压缩为一维以及集合操作是这题解的亮点

注意特判终点是障碍的情况

var
    n,m,t,i,x,y,s,f,ans:longint;
    a,path:set of byte;
function getpos(x,y:longint):byte;inline;
    begin
        exit((x-1)*m+y)
    end;
function getup(p:byte):byte;inline;
    begin
        exit(p-m)
    end;
function getdown(p:byte):byte;inline;
    begin
        exit(p+m)
    end;
function getleft(p:byte):byte;inline;
    begin
        exit(p-1)
    end;
function getright(p:byte):byte;inline;
    begin
        exit(p+1)
    end;
function isup(p:byte):boolean;inline;
    begin
        exit(p<=m)
    end;
function isdown(p:byte):boolean;inline;
    begin
        exit(p>m*(n-1))
    end;
function isleft(p:byte):boolean;inline;
    begin
        exit(p mod m=1)
    end;
function isright(p:byte):boolean;inline;
    begin
        exit(p mod m=0)
    end;
procedure dfs(p:longint);
    begin
        if (p=f) and not (p in a) then begin
            inc(ans);
            exit
        end;
        if not (p in path+a) then begin
            path:=path+[p]
        end
        else begin
            exit
        end;
        if not isup(p) then begin
            dfs(getup(p))
        end;
        if not isdown(p) then begin
            dfs(getdown(p))
        end;
        if not isleft(p) then begin
            dfs(getleft(p))
        end;
        if not isright(p) then begin
            dfs(getright(p))
        end;
        path:=path-[p]
    end;
begin
    readln(n,m,t);
    read(x,y);
    s:=getpos(x,y);
    readln(x,y);
    f:=getpos(x,y);
    a:=[];
    for i:=1 to t do begin
        readln(x,y);
        a:=a+[getpos(x,y)]
    end;
    ans:=0;
    dfs(s);
    writeln(ans)
end.

评论

  • 还没有评论
作者: wangge 更新时间: 2020-01-09 20:59  在Ta的博客查看 举报    0  

C++搜索与回溯 --深搜 DFS

思想:搜索 >> 标记>> AC

重点和难点!

-->

1.;一共上下左右4种走法,可以用数组来完成

2.判断条件要弄清楚;

3.障碍物处理;

4.开始点要标走过;

5.2维数组行列变量弄清楚.

针对问题

一. 一共上下左右4种走法,可以用数组来完成.

上下左右4种走法,确实不太好弄,

仔细观察才能发现.

若所在点为a[n][m]

n,m-1
n-1,m n , m n+1,m
n,m+1

(1)上:a[n][m-1] (2)下:a[n][m+1] (3)左:a[n-1][m] (4)右:a[n+1][m]

所以 代码如下

-->

int dx[4]={0,0,1,-1};//打表
int dy[4]={-1,1,0,0};//打表

二. 判断条件要弄清楚

一共6条件

(1)是否超界; (2)是否为障碍物走过

所以 代码如下

-->

if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&zhang[nx][ny]==0&&use[nx][ny]==0)
{
    use[nx][ny]=1;//标记
    dfs(nx,ny);
    use[nx][ny]=0;//清标记或回溯
}

三. 障碍物处理

直接定义bool双重变量
0为不是障碍物
1 为是障碍物

所以 代码如下

-->

for(int i=1;i<=t;i++)
{
    int x,y;//障碍物坐标
    cin>>x>>y;
    zhang[x][y]=1;//标记
}

四. 开始点要标走过

在DFS中我没算起点的重复,所以我在主函数之中给他算了重复;

所以 代码如下

-->

use[sx][sy]=1;//起点算重复

【上AC代码】

#include<bits/stdc++.h>//万能头
using namespace std;
int n,m,t,sx,sy,fx,fy,sum;
bool zhang[10][10],use[10][10];//zhang为障碍物标记,ues为走过标记,俩数组可合二为一
int dx[4]={0,0,1,-1};//打表
int dy[4]={-1,1,0,0};//打表
void dfs (int x,int y)
{
    if(x==fx&&y==fy)
    {
        sum++;//可行方案+1
        return ;
    }
    for(int i=0;i<=3;i++)//数组下标为0,一共4个方向,所以0到3
    {
        int nx,ny;
        nx=x+dx[i];//nx=new x,新x
        ny=y+dy[i];//ny=new y,新y
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&zhang[nx][ny]==0&&use[nx][ny]==0)//6个条件,不能过范围,不为障碍物和不能走过
        {
            use[nx][ny]=1;//标记
            dfs(nx,ny);
            use[nx][ny]=0;//清标记
        }
    }
}
//深搜
int main()
{
    cin>>n>>m>>t;
    cin>>sx>>sy>>fx>>fy;//输入起点和终点
    for(int i=1;i<=t;i++)
    {
        int x,y;//障碍物坐标
        cin>>x>>y;
        zhang[x][y]=1;//标记
    }
    use[sx][sy]=1;//起点算重复
    dfs(sx,sy);
    cout<<sum;
    return 0;
}

吾为蒟蒻

如有优化建议可在讨论区发表

评论

  • 还没有评论
作者: breeze末影  更新时间: 2019-11-09 07:08  在Ta的博客查看 举报    0  

迷宫这系列的题算是dfs最经典的题了吧。

窝看到有一些dl用map标记,这里就给没学过map的提供一种做法。

我们用一个char数组记录障碍和起点。

char c[6][6];
if(c[sx][sy] == 'T'){
        cnt++;
        return;
}//标记终点
for(int i=0; i<t; i++){
        int zx,zy;
        cin >> zx >> zy;
        c[zx - 1][zy - 1] = '#';
}//标记障碍

最后是我可爱的代码君:

#include <iostream>
using namespace std;
char c[6][6];
int cnt;
int dir[4][2] = {
    {1,0},
    {0,1},
    {-1,0},
    {0,-1}
};//下一步
int n,m;
bool vis[6][6];//记录是否走过
bool in(int sx, int sy){//是否在地图内
    return sx >= 0 && sx < n && sy >= 0 && sy < m;
}
void dfs(int sx, int sy){//深搜
    vis[sx][sy] = true;
    if(c[sx][sy] == 'T'){
        cnt++;
        return;
    }//如果是终点,计数++,返回
    for(int i=0; i<4; i++){
        int tx = sx + dir[i][0];
        int ty = sy + dir[i][1];//记录下一步的坐标
        if(in(tx,ty) && !vis[tx][ty] && c[tx][ty] != '#'){//判断递归条件
            vis[tx][ty] = true;//标记
            dfs(tx,ty);//递归搜索
            vis[tx][ty] = false;//尝试回溯
        }
    }
    return;
}   
int main(){
    int t;
    cin >> n >> m >> t;
    int sx,sy,fx,fy;
    cin >> sx >> sy >> fx >> fy;
    c[fx - 1][fy - 1] = 'T';
    for(int i=0; i<t; i++){
        int zx,zy;
        cin >> zx >> zy;
        c[zx - 1][zy - 1] = '#';
    }
    dfs(sx - 1,sy - 1);//搜索,如果像我一样喜欢由0开头,需要-1
    cout << cnt;//输出
    return 0;
}完结撒花

希望能帮到大家,最后祝大家AC此题

评论

  • 还没有评论
作者: FirCoder 更新时间: 2019-10-18 09:43  在Ta的博客查看 举报    0  

迷宫都是经典DFS(BFS)题。我们需要模拟人走迷宫的一个过程,所以限制条件很好判断:

1:超出迷宫范围就要返回

2:碰到墙就返回

3:上下左右都走不通返回

4:不能走前面已经走过的路 那就死循环了


代码如下

#include <bits/stdc++.h>
using namespace std;
int n, m, t, sx, sy, ex, ey, times;
int mapp[10][10]; // 存迷宫
bool v[10][10]; // 判断有没有走过
int ne[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; // 四个方向,一定要看清写对,好多次这里-1,1,0写错但没有发现,很难受。
void dfs(int x, int y);
int main()
{
    cin >> n >> m >> t;
    cin >> sx >> sy >> ex >> ey;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            mapp[i][j] = 1;
    } // 初始化迷宫为1,迷宫以外的多余地方为0,这样判断mapp[x][y]是否为0就可以判断是否出界
    while (t--)
    {
        int x, y;
        cin >> x >> y;
        mapp[x][y] = 0; // 把有墙的地方变0
    }
    dfs(sx, sy);
    cout << times << endl;
    return 0;
}
void dfs(int x, int y)
{
    if (x == ex && y == ey) // 到达终点
    {
        times++;
        return ;
    }
    //if (v[x][y] || mapp[x][y] == 0) return ; // 不能在这里判断,要在for循环里面就判断,这样会出界
    for (int i = 0; i <= 3; ++i)
    {

        int xx = x + ne[i][0], yy = y + ne[i][1];
        if (!v[xx][yy] && mapp[xx][yy] == 1) // 在这里判断可以预防出界
        {
            v[x][y] = true; // 如果可以走(xx, xy)则在当前位置打标记,说明已经走过,避免死循环
            // cout << x << " " << y << endl;
            dfs(xx, yy);
            v[x][y] = false; // 返回后要去除标记
        }
    }
    return ;
}

评论

  • 还没有评论
作者: 小狼狗 更新时间: 2019-10-04 21:28  在Ta的博客查看 举报    0  

这是一道深度优先搜索的题,还是比较简单的,那本蒟蒻就来写一篇题解吧

(我可不会告诉别人我不会BFS的)逃~


先说说我的思路:

初始化:首先全部初始化为障碍(就是0),再把n行全部初始化为1,最后把障碍点变为0

接着来个大爆搜:先判断a == ex && b == ey,如果是就ans++;return;否则就判断上下左右,然后回溯

输出:输出ans就搞定了

深度优先搜索大家应该都懂吧,那就直接上代码了

#include<iostream>
#include<cstring>
using namespace std;
int mp[101][101];//迷宫
int ans = 0;//记录答案数量
int n,m,t,sx,sy,ex,ey,x,y;
void dfs(int a,int b)//搜索
{
    if (a==ex&&b==ey){ans++; return;}//判断是否到达终点
    mp[a][b] = 0;
    if(mp[a-1][b] != 0){dfs(a-1,b); mp[a-1][b] = 1;}
    if(mp[a][b-1] != 0){dfs(a,b-1); mp[a][b-1] = 1;}
    if(mp[a][b+1] != 0){dfs(a,b+1); mp[a][b+1] = 1;}
    if(mp[a+1][b] != 0){dfs(a+1,b); mp[a+1][b] = 1;}//这四句是判断上下左右
}
int main()
{
    memset(mp,0,sizeof(mp));//初始化为0
    cin>>n>>m>>t;
    cin>>sx>>sy>>ex>>ey;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp[i][j] = 1;//在初始化为1
    for(int i=1;i<=t;i++){cin>>x>>y; mp[x][y] = 0;}//标出障碍
    dfs(sx,sy);//调用
    cout<<ans<<endl;//输出

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



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