自动搬运

查看原文

来自洛谷，原作者为

	_yjh 我感觉我是活不明白了。

搬运于2025-08-24 21:36:05，当前版本为作者最后更新于2019-10-03 20:13:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题解是STL加广搜

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

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

1.队列

使用 queue(队列) 的步骤

• 引入头文件

#include

- 定义一个 **任何类型的队列** (如int)
  ```cpp 
queue <类型名> 变量名;

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

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

 ___2.广度优先搜索___
  
  ```cpp
广度优先搜索算法（英语：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好奇怪的游戏