自动搬运

查看原文

来自洛谷，原作者为

	lxzy_ 燊，我的燊 | 拾起的这回忆，无论喜或悲伤，都随光阴绵长

搬运于2025-08-24 21:30:44，当前版本为作者最后更新于2019-11-09 21:37:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道奇奇怪怪的搜索题

以我的感觉，这一道题除了传送门需要特判一下，并注意不要重复计算路径，其他地方都不算太难。

大约是$\color{orange}\text{普及组T2}$的难度。

好了废话不多说了，开始切题QwQ

求出Bessie需要移动到出口处的最短时间

显然地，这题的思路就是：

暴力BFS

关于BFS可以康康我写的另外一篇题解：

$\text{P1443马的遍历}$

广搜的主要思想便是将所有可行解（可到达的点）放入队列，然后再一个个遍历所有可行解（可到达的点），知道找到终点为止。

$C++$的优势再一次显现出来了——我们可以使用$C++STL$中的$queue$数据结构C++万岁！

如下：

struct point{//定义一个名为point的结构体
	int x;//当前可到达点的x坐标
	int y;//当前可到达点的y坐标
	int t;//到达当前点的最小步数
};
queue<point> que;//定义一个变量类型为point的队列

不过记得加上：

#include<queue>

关于广搜的部分：

与深搜相同，定义坐标偏移量，以便枚举当前所有可到达点。不同点在于，深搜是一个急性子：遇到可到达点就不管三七二十一直接走上去，直到走不通为止；而广搜则是将所有可到达点放入队列后，再一个个遍历。

$\text{裸广搜模板：}$

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};//定义坐标偏移量
int sx,sy;//起点x、y坐标
int vis[350][350];//vis数组用来防止同一个点访问多次，true表示已访问，false表示为访问

que.push((point){sx,sy,0});//将起点坐标放入队列，初始步数为0

while(!que.empty())//只要还有可到达点就继续访问，知道榨干它
{
    point f=que.front();//提取出队头
    que.pop();//切记！一定要记得将队头扔掉，否则会死循环

    if(a[f.x][f.y]=='=')//如果当前点就是终点
    {
        cout<<f.t;//输出它，结束~
        return 0;
    }

    for(int i=0;i<=3;i++)//遍历其上下左右相邻的点
    {
        //下面与深搜基本一样
        int nx=x+dx[i];//获取相邻点的x、y坐标
        int ny=y+dy[i]; 
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&!vis[nx][ny])//判断是否越界、是否撞墙、当前点是否已经被访问过
        {
            que.push((point){nx,ny,f.t+1});//可以走便将其放入队列
            vis[nx][ny]=true;//标记当前点已经走过
        }
    }
}

由于这道题加入了一个新的元素：传送门。因此我们需要在广搜中多增加一个特判：当前是否为传送门，是的话，我们就需要找到另一个传送门所在坐标，然后将那个传送门所在点的坐标储存进队列。

$\color{green}AC$ $\text{Code：}$

#include<iostream>
#include<queue>
using namespace std;
const int N=350;

struct point{
    int x;
    int y;
    int t;
};

queue<point> que;

char a[N][N];
bool vis[N][N];
int n,m;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int sx;
int sy;

void goto_another(int &nx,int &ny,int k)//goto_another函数用于寻找另一个传送门，nx、ny代表当前点的坐标，记得要加上取地址符'&'，因为每当贝西踏入一个传送门，它就会立即被传送至另一个传送门，不能在原地停留
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==a[nx][ny]&&(i!=nx||j!=ny))//如果a[i][j]这个点的是一个与a[nx][ny]相同的传送门，并且a[i][j]与a[nx][ny]不是同一个点
            {
                nx=i;//改变当前坐标，将贝西强行移动至另一个传送门处
                ny=j;
                return ;//告辞
            }
        }
    }
}
int main()
{
    
    cin>>n>>m;
    string s;
    for(int i=1;i<=n;i++)
    {
        cin>>s;//由于输入奇奇怪怪地没有空格，于是乎窝便使用字符串读入
        for(int j=1;j<=m;j++)
        {
            a[i][j]=s[j-1];
            if(a[i][j]=='@')//获取起点坐标
            {
                sx=i;
                sy=j;
            }
        }
    }
    que.push((point){sx,sy,0});

    while(!que.empty())
    {
        point f=que.front();
        que.pop();
        if(a[f.x][f.y]=='=')
        {
            cout<<f.t;
            return 0;
        }
        if(a[f.x][f.y]>='A'&&a[f.x][f.y]<='Z')//特判部分，如果当前点是一个传送门，那么就传送至另一个传送门
        {
            goto_another(f.x,f.y,f.t);
        }
        for(int i=0;i<=3;i++)
        {
            int nx=f.x+dx[i];
            int ny=f.y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&!vis[nx][ny])
            {
                vis[nx][ny]=true;
                que.push((point){nx,ny,f.t+1});
            }
        }
    }
    return 0;
}

以上就是我对这道假绿题的解法，蟹蟹观康$QwQ$