【洛谷p1605】迷宫

佚名 6年前 (2019-04-15) 随笔 1062人围观抢沙发百度已收录

（还记得我昨天大概没人看到的博客（我删辽）吗qwq，

那篇博客大致内容就是：我提交楼上这道题，交了好久好久好久好久

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

现在我告诉你，那次评测还N/A着呢qwq）

tqlqwq

回归正题qwq，今天是来写题解的：

传送门【】

算法标签嘤嘤嘤：

它幸好没出dfs，要不然我非要打死把这个题放在bfs（还是由简单到困难的第一个题的wz）小姐姐，伪装成后面没东西的样子qwq

行吧让我们宽广的搜索吧qwq：

其实这道题更像是个搜索回溯，每走一步可以退回原状态来看原状态是否还有符合的，但是我们练的是bfs嘛对不对，当然要写bfs了（不会写搜索回溯）

可不可以直接上代码qwq：

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,t,sx,sy,fx,fy,x,y,ans;
bool b[10][10];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
struct coder{//定义一个结构体coder（我也不知道为什么要叫这个名字） 
    int x,y;//结构体内包含横纵坐标 
    int gl[10][10];//和用来标记这个点是否走过的数组gl（我是不会告诉你我拿我初中同学的名字来命名变量的qwq）
};
coder hyh;//定义一个coder型变量hyh（我是不会告诉你我拿我初中同学的名字来命名变量的qwq） 
queue<coder> q;//定义一个coder型队列q 
void bfs(){//广搜 
    hyh.x=sx;//把起点的横纵坐标赋给hyh.x，hyh.y； 起点标记为已访问 
    hyh.y=sy;
    hyh.gl[sx][sy]=1;
    q.push(hyh);//入队 
    while(!q.empty()){
        coder h=q.front();//取出队首元素 
        q.pop();//把队首元素出队 
        for(int i=0;i<4;i++){
            int xx=h.x,yy=h.y;
                xx+=dx[i];
                yy+=dy[i];
                if(xx>n||xx<1||yy>m||yy<1||b[xx][yy]||h.gl[xx][yy]){//判断不满足条件的情况（不满足就进行下一次循环） 
                    continue;
                }
                if(xx==fx&&yy==fy){//到终点，ans+1； 
                ans++;
                continue;
                }
                hyh.x=xx;//没有到终点，把走一步后的元素给hyh（包括某一个位置走过否 
                hyh.y=yy;
                memcpy(hyh.gl,h.gl,sizeof(h.gl));
                hyh.gl[xx][yy]=1;//把走到这个点标为1 
                q.push(hyh);//入队 
            }
        }
    }
int main(){
    scanf("%d%d%d",&n,&m,&t);//输入惹 
    scanf("%d%d",&sx,&sy);
    scanf("%d%d",&fx,&fy);
    for(int i=1;i<=t;i++){
      scanf("%d%d",&x,&y);
      b[x][y]=1;//构造了一个矩阵，如同一个01地图，障碍物标记为1，通路标记为0； 
    }
    bfs();//广搜代码，与dfs（大法师）相对 
    cout<<ans<<endl;
}