题解 P2298 【Mzc和男家丁的游戏】

_yjh · 2019-10-03 20:13:30 · 题解

本题解是STL加广搜

阅读本题解大于需要 3-5min ，\color{lightgreen}{\text{My blog }} 阅读效果更佳。

介绍一下萌新难以理解的知识点

1.队列

使用 queue(队列) 的步骤

• 引入头文件 <queue>

  #include<queue>

• 定义一个 任何类型的队列 (如int)

  queue <类型名> 变量名;

• 使用 库中的函数 对其进行操作

  //基本操作
  /*定义一个队列变量q*/
  #1 q.push(变量); 将变量插入队尾
  #2 q.pop(); 弹出队首的元素
  #3 q.front(); 访问队首元素
  #4 q.back(); 访问队尾元素
  #5 q.empty(); 判断队列是否为空,是则返回true
  #6 q.size(); 返回队中元素的个数

  2.广度优先搜索

  广度优先搜索算法（英语：Breadth-First-Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。 
                                                                                   ---By搜狗百科

  思路

  一道迷宫最短路的模板题。
  我这是一种标准的 STL队列+广搜 的做法。
  

Code(杜绝抄袭，共建和谐洛谷)

#include<iostream>
#include<queue>
using namespace std;
struct Pos
{
    int x,y;
}; //坐标点定义
queue <Pos> q;
int n,m,x,y,tx,ty,dis[1001][1001],s_a,s_b,t_a,t_b;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
char mp[1001][1001];
bool vis[1001][1001]; //方向等变量的定义
int bfs(int sx,int sy)
{
    q.push((Pos){sx,sy});
    vis[sx][sy]=true;
    while(!q.empty())
    {
        x=q.front().x;
        y=q.front().y; 
        q.pop();  //弹出队列
        if(mp[x][y]=='m') return dis[x][y];
        for(int i=0;i<4;i++)
        {
            tx=x+dx[i];
            ty=y+dy[i];
            if(tx<=0||tx>n||ty<=0||ty>m) continue;
            if(mp[tx][ty]=='#'||vis[tx][ty]==true) continue; //不符合条件，跳过
            dis[tx][ty]=dis[x][y]+1;
            vis[tx][ty]=true;
            q.push((Pos){tx,ty});
        }
    }
    return -1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>mp[i][j];
            if(mp[i][j]=='d')
            {
                s_a=i;
                s_b=j; //获取起点坐标
            }
        }
    int c;
    c=bfs(s_a,s_b);
    if(c==-1)cout<<"No Way!"<<endl;
    else cout<<c<<endl; //这里可以压缩一下 
    return 0;
}

运行时间 969ms，空间20.64mb

附赠给大家一个广搜模板：

int bfs(int sx,int sy)
{
    q.push((Pos){sx,sy}); //起点加入队列
    vis[sx][sy]=true; //标记
    while(!q.empty()) 
    {
        x=q.front().x;
        y=q.front().y; //获取起始坐标
        q.pop(); //弹出队列
        if(符合条件) return ans(答案); 
        for(int i=0;i<走法;i++)
        {
            tx=x+dx[i];
            ty=y+dy[i];
            if(符合条件) continue;
            if(符合条件) continue; //符合条件跳过循环
            /*
                           可行,执行该部分语句
                                                      */
            q.push((Pos){tx,ty}); //加入队列
        }
    }
}

最后给大家推荐几道搜索的题

P1443 马的遍历

P1746离开中山路

P1747好奇怪的游戏