题解 P1825 【[USACO11OPEN]玉米田迷宫Corn Maze】

· · 题解

一道奇奇怪怪的搜索题

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

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

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

\color{red}\text{思路}

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

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

暴力BFS

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

\text{P1443马的遍历}

\color{green}\text{写法}

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

如下： ```cpp struct point{//定义一个名为point的结构体 int x;//当前可到达点的x坐标 int y;//当前可到达点的y坐标 int t;//到达当前点的最小步数 }; queue<point> que;//定义一个变量类型为point的队列 ``` 不过记得加上： ```cpp #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