P1605 迷宫 题解


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

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

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

评论

  • ybb756032937
    天然的好orz
  • 性感的beauty女
    666
  • xhx0809
    好,十分详细
  • xhx0809
    你,值得使用
  • red_archer
    好久没有见到那么详细的题解了
  • dongjiajiedc
    刚学搜索,简单易懂
  • 和泉sagiri
    不会搜索。。。
  • Chevalier
    非常好的题解!但是只开一个map似乎不会对结果产生影响?
  • nanamomo
    注意:有些同学可能觉得就在地图map数组上打标记(自己走过的路)比较简单,走过的路和障碍可能引起混淆,如果只用map数组的话,可能只的得到80分;(贴主的惨痛经历) 能贴下这个80分的代码吗?
  • Fike_L
    %%%
作者: ybb756032937 更新时间: 2018-01-07 17:42  在Ta的博客查看 举报    152  

C++题解

基本思路:搜索 标记 打表 AC

代码呈上:

#include<iostream>//个人建议不使用万能头文件,如果要使用万能头文件,就不能定义数组map;
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int map[6][6];//地图;
bool temp[6][6];//走过的标记;
int dx[4]={0,0,1,-1};//打表;
int dy[4]={-1,1,0,0};//打表;
int total,fx,fy,sx,sy,T,n,m,l,r;//total计数器,fx,fy是终点坐标,sx,sy是起点坐标,T是障碍总数,n,m是地图的长和宽,l,r是障碍的横坐标和纵坐标;
void walk(int x,int y)//定义walk;
{
    if(x==fx&&y==fy)//fx表示结束x坐标,fy表示结束y坐标;
    {
        total++;//总数增加;
        return;//返回,继续搜索;
    }
    else
    {
        for(int i=0;i<=3;i++)//0——3是左,右,下,上四个方向;
        {
            if(temp[x+dx[i]][y+dy[i]]==0&&map[x+dx[i]][y+dy[i]]==1)//判断没有走过和没有障碍;
            {
                temp[x][y]=1;//走过的地方打上标记;
                walk(x+dx[i],y+dy[i]);
                temp[x][y]=0;//还原状态;
            }    
        } 
    }
}
int main()
{
    cin>>n>>m>>T;//n,m长度宽度,T障碍个数 
    for(int ix=1;ix<=n;ix++)
        for(int iy=1;iy<=m;iy++)
            map[ix][iy]=1;//把地图刷成1;
    cin>>sx>>sy;//起始x,y 
    cin>>fx>>fy;//结束x,y 
    for(int u=1;u<=T;u++)
    {
        cin>>l>>r;//l,r是障碍坐标;
        map[l][r]=0;
    }
    walk(sx,sy);
    cout<<total;//输出总数;
    return 0;
} 

题整体来说比较简单,使用深搜一个个查,使用一个数组map记录障碍的地方,再使用一个temp来标记自己所走过的路;

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

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

使用自动选择方向来代替4个if判断(使代码更加简洁长度变短);

如果没有障碍并且不是自己走过的,就进一步搜索,把自己走过的路打上标记,返回时,再将标记还原;

注意:有些同学可能觉得就在地图map数组上打标记(自己走过的路)比较简单,走过的路和障碍可能引起混淆,如果只用map数组的话,可能只的得到80分;(贴主的惨痛经历)

这里再给大家一个基本的深搜模板:

int search(int t)
{
    if(满足输出条件)
    {
        输出解;
    }
    else
    {
        for(int i=1;i<=尝试方法数;i++)
            if(满足进一步搜索条件)
            {
                为进一步搜索所需要的状态打上标记;
                search(t+1);
                恢复到打标记前的状态;//也就是说的{回溯一步}
            }
    }
}

整个模板有几个地方需要注意:

1.第一个if是符合输出解的条件,第二个if是符合进一步搜索的条件;

2.下一步搜索时,不是使用return search(t+1),直接search(t+1);(新手可能会注意不到这个关键的地方,以至于每次写完不知道为什么只得到一个答案就返回主程序了

3.for循环之后的if可以是多个;

4.for循环边界,例如:

1>方向是四个,那么边界肯定就是4;(帖主用3,是因为从0开始的)

2>素数环需要尝试1至20,那么边界就是20;

如果想要得到更多知识,请关注我博客:https://www.luogu.org/blog/AHacker/

此博客不定期更新内容!!!感谢大家!!!

评论

  • Keith_2006
    666
  • Sn_Eddy
    Oh good good boy
  • chenhaiquan
    万能头文件能用了
  • chenhaiquan
    万能头文件能用了?
  • Aonrbet
    别信他,万能头文件不可能能用
  • Aonrbet
    别被骗了
  • Double_Y
    可以用的
  • Lagerstoremia
    万能头能用?
  • 良辰、
    那个万能头文件最好不用吧(随缘了,有些评测机可以,有些就爆0 qaq
  • Eyjafjalla
    ...
作者: Sn_Eddy 更新时间: 2017-11-10 23:54  在Ta的博客查看 举报    46  

首先告诉大家一个好消息:bits/stdc++.h在复赛可以使用了。

其次看这道简单的题目,我的策略是不考虑边界,直接初始化,将边界当作障碍。

附上程序。

#include<bits/stdc++.h>
using namespace std;
int q[101][101];
int sum=0;
int i,j,n,m,t,sx,sy,x,y,ex,ey;
void dfs(int a,int b)
{
    if (a==ex&&b==ey)//终止条件
    {
        sum++;
        return;
    }
    else
    {
           q[a][b]=0;//保存结果
        if(q[a-1][b]!=0) {dfs(a-1,b);q[a-1][b]=1;}
        if(q[a][b-1]!=0) {dfs(a,b-1);q[a][b-1]=1;}
        if(q[a][b+1]!=0) {dfs(a,b+1);q[a][b+1]=1;}
        if(q[a+1][b]!=0) {dfs(a+1,b);q[a+1][b]=1;}//这四部是穷举所有可行的搜索,并且回溯
    }
}
int main()
{
    memset(q,0,sizeof(q));//边界当作障碍。
    cin>>n>>m>>t;
    cin>>sx>>sy>>ex>>ey;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            q[i][j]=1;//可以走
    for(i=1;i<=t;i++)
    {
        cin>>x>>y;
        q[x][y]=0;//障碍物初始化
    }
    dfs(sx,sy);
    cout<<sum<<endl;
    return 0;
}
完美!

评论

  • chenjh丶
    能让本蒟蒻看懂,是个好东西
  • 爆零蒟蒻2326
    我才是最弱的蒟蒻
  • djt366
    违规用户名BfmB*EV0 正解
  • k88887
    orz
  • lilinrui2005
    数组不需要那么大,看看范围
  • tgs9311
    70分怎么办
  • jy20051228
    G数组没有用途,完全可以把它合并到VIS里面。所有的障碍点和起点都在初始化的时候放到VIS里面(设为true)就好了。不必单独开一个G数组。
  • 李曦来
    哈,我也只有两个题解
  • hexiang
    70分就看看;/哭
  • 1710121058李博
    我就是没有标记起点。。。。wa了一发
作者: Billy●Herrington 更新时间: 2018-08-06 14:18  在Ta的博客查看 举报    14  

大扎好,我系世界第一蒟蒻czdh。介系我发布的第2篇题解

首先,这一题一看就知道一定要用dfs回溯。因为我们要枚举走的步数,以及走错路时抑制住自己的愤怒回来换下一条路。

看到有不少人在讨论版里发只有40分(我一开始也只有40分。),关于这个问题,我会在代码里解释。

以下是代码:

#include <iostream>
#include <cstdio>
using namespace std;
bool G[15][15],VIS[15][15];//G为总地图,VIS记录是否访问
int n,m,d[5]={-1,0,1,0,-1};//方向不解释 
int nx,ny,ex,ey,CNT;
//nx,ny起点坐标;ex,ey终点坐标,CNT路径条数
void dfs(int x,int y)
{
    if (x ==ex&&y ==ey)//如果到终点
    {
        CNT++;//路径加一
        return;//回去继续查找
    } 
    for (int k=0;k<4;k++)
    {
        int l=x+d[k];int r=y+d[k+1];
        if (l>=1&&r>=1&&l<=n&&r<=m&&!G [l][r]&&!VIS [l][r]) 
        {
            VIS [l][r]=true;//标记为已访问
            dfs (l,r);
            VIS [l][r]=false;//回溯
        }
    }
    return; 
}
int main ()
{
    int t,zx,zy;
    cin>>n>>m>>t>>nx>>ny>>ex>>ey;
    G[nx][ny]=true; //这就是许多人(我)40分的原因
    //因为dfs函数里并没有将起点设为已访问
    //所以在后面的访问里,可能访问起点许多次
    //所以你的答案可能比标准答案多
    while(t--)
    {
        cin>>zx>>zy;
        G[zx][zy]=true;//设为障碍
    } 
    dfs (nx,ny);//从起点开始寻找 
    cout<<CNT;
    return 0; 
} 

蒟蒻第二次发布题解,请大家指教qwq

蟹蟹大家qwq

评论

  • programmer
    很不错的深搜题目,初学深搜的小伙伴可以试试练练手
  • 止战之殇
    pascal太少了
  • _Wolverine
    dfs(电风扇)
  • QwQ自动机
    大法师?!不是depth first search 吗?
  • 征途者二号
    楼上认真就输了······【滑稽】
  • 巨型蚊子精
    +1
  • lx79378
    抓住楼上老实人
  • 拱大垲
    +1
  • Initial20070831
    不!应该是death fuck shit
作者: Dream_Runner 更新时间: 2017-08-17 14:08  在Ta的博客查看 举报    13  

dfs(大法师)pascal福利

此题是一道典型的深搜题目,将能通过的位置赋值为0,将不能通过的位置赋值为1,然后进行深度优先搜索就ok了。

千万别忘记原地回溯!!!不要将起点设为1,1!!!(如果一碰到障碍物或重点就返回(exit))

下附代码:

  var
  i,j,k,n,m,t,sx,sy,fx,fy,a,b:longint;
  ans:int64;
  z:array[0..10,0..10] of longint;
  flag:array[0..10,0..10] of boolean;

procedure dfs(x,y:longint);   //深搜开始
  begin
    if z[x,y]=1 then exit;   //判断是否遇到障碍物
    if (x=fx) and (y=fy)   //判断是否到达终点
      then
        begin
          inc(ans);   //更新答案
          exit;
        end;
    flag[x,y]:=true;  //将**flag[x,y]**设为已经走过
    if (x-1>0) and (not flag[x-1,y]) then dfs(x-1,y);   //递归开始(如果越出地图或那一个点一走过则不进行深搜)
    if (x+1<=n) and (not flag[x+1,y]) then dfs(x+1,y);
    if (y-1>0) and (not flag[x,y-1])then dfs(x,y-1);
    if (y+1<=m) and (not flag[x,y+1])then dfs(x,y+1);
    flag[x,y]:=false;   //原地回溯
  end;

begin
  readln(n,m,t);
  readln(sx,sy,fx,fy);
  fillchar(z,sizeof(z),0);
  for i:=1 to t do
    begin
      readln(a,b);
      z[a,b]:=1;
    end;
  dfs(sx,sy);   //调用子程序
  writeln(ans);   //输出(大功告成)
end.

z[x,y]表示此点是否可通行,flag[x,y]表示此点是否走过

评论

  • 咔咔
    小心MLE
  • 神之蒟蒻xyk
    当年noip因cin TLE掉了70分~~~
  • 李博睿
    ios::sync_with_stdio(false); 使cin,cout的时间和scanf,printf相差无几
  • hah_Gj
    你的标记是什么意思 ??
  • hah_Gj
    memcpy(sa.used,now.used,sizeof(now.used));
  • LJC001151
    本蒟蒻也是用bfs做的
  • LJC001151
  • LIFE_IS_FANTASTIC
    “ 如果这里是终点,那么结果数量加一”这一句忘了加“//”了
作者: legends·never·die 更新时间: 2018-07-05 07:21  在Ta的博客查看 举报    8  
    虽然迷宫这道题放在dfs的试练场里,但是bfs显然也是可以写出来的。现在大家看一下代码
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,m,k,x,y,a,b,ans;
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
bool vis[6][6];
struct oo{
    int x,y,used[6][6];
};

oo sa;

void bfs()
{
    queue<oo> q;      //定义结构体后,可以直接使用结构体名定义变量或者队列。
    sa.x = x;
    sa.y = y;         //横纵坐标替换,这样写起来方便。
    sa.used[x][y] = 1;//标记走过的路径
    q.push(sa);
    while(!q.empty())
    {
        oo now = q.front();     //一起拿出来
        q.pop();
        for(int i = 0;i < 4; i++)
        {
            int sx = now.x + dx[i];
            int sy = now.y + dy[i];
            if( now.used[sx][sy] 
                || vis[sx][sy] 
                || sx == 0 || sy == 0 
                || sx > n || sy > m)
                continue;    //如果这里走过,或者这里是障碍,或者这里是墙壁,那么这里就不能走。
            if(sx == a && sy == b)
            {
                ans++;           如果这里是终点,那么结果数量加一
                continue;
            }
            sa.x = sx;
            sa.y = sy;
            memcpy(sa.used,now.used,sizeof(now.used));
            sa.used[sx][sy] = 1;     //这里的操作都是为了标记路径
            q.push(sa);
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d%d%d",&x,&y,&a,&b);         //虽然这里可以合并成一个句子,但是由于我是从python转过来的,建议大家以后写代码都设置一个界限,代码不宜太长
    for(int i = 1,aa,bb;i <= k; i++)     //大家注意一下,我现在是直接把变量定义在循环里面。
    {
        scanf("%d%d",&aa,&bb);           //现在我们不能走障碍了。
        vis[aa][bb] = 1;
    }
    bfs();
    printf("%d",ans);
    return 0;
}
    输入输出为什么不用标准输入输出流而用格式化输入输出,嗯~..因为这样比较快吧,不这样写可能会T掉,不过大家可以试一试

    现在这个题就解出来了,本人是第一次写题解,如果有什么地方没有解释清楚可以再问我,多提意见,接下来将会改进的更好
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



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