题意

一个玉米园,有草地,玉米,起点,终点,传送装置

不踩玉米地从起点到终点的最短路(用BFS)

• 起点 "@"
• 终点 "="
• 玉米 "#"
• 草地 "." 可以通过四联通行走,每步耗费1单位时间
• 传送装置 "A"~"Z" ,每个字母只能出现一对,可以互传位置不耗费单位时间,但不代表走到传送装置面前不用耗费

思路

BFS

其他不难,这道题主要难在传送装置(对于我这种蒟蒻来说,还好)

传送装置使用结构体

传送装置的数组要用字符的ascii来代替下标

如遇到字母就判断是第一个还是第二个

代码

#include<iostream>
#include<queue>
using namespace std;
int n,m;
char a[114*3][514];//图
int vis[114*3][514]={0};//标记探索
int xl[4]={0,0,1,-1};//相对坐标
int yl[4]={1,-1,0,0};//相对坐标
int sx,sy,ex,ey;//起点与终点坐标
struct xy
{
    int x,y,c;
};//用于BFS
queue<xy >q;
struct csxy
{
    int x1=-1,y1=-1,x2=-1,y2=-1;//注意初始值
}cs[114];//用于传送装置
int main()
{
    cin>>n>>m;//输入
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];//输入
            if(a[i][j]=='@')sx=i,sy=j;//标记起点
            if(a[i][j]=='=')ex=i,ey=j;//标记终点
            if(a[i][j]>='A' && a[i][j]<='Z')//传送装置
            {
                if(cs[a[i][j]].x1==-1)//是第一个时(因为初始值为-1)
                {
                    cs[a[i][j]].x1=i,cs[a[i][j]].y1=j;//标记
                }
                else//是第二个时
                {
                    cs[a[i][j]].x2=i,cs[a[i][j]].y2=j;//标记
                }
            }
        }
    }
    q.push({sx,sy,0});//初始为0
    while(q.size())//BFS
    {
        xy e=q.front();//方便获取
        q.pop();
        if(e.x==ex && e.y==ey)//为终点时
        {
            cout<<e.c;//输出步数
            return 0;//记住要结束
        }
        if(vis[e.x][e.y])//标记过时
        {
            continue;//不再探索
        }
        vis[e.x][e.y]=1;//标记
        for(int i=0;i<4;i++)//四联通
        {
            int x=e.x+xl[i];//获取坐标
			int y=e.y+yl[i];//获取坐标
            if(x<0 && x>=n && y<0 && y>=m)//超出范围
            {
                continue;//不再探索
            }
            if(a[x][y]=='#')//为玉米时
            {
            	continue;//不再探索
			}
            if(cs[a[x][y]].x1!=-1)//是个传送装置
            {
                if(cs[a[x][y]].x1==x && cs[a[x][y]].y1==y)//为第一个,这里要加1的原因是,你也要走到传送装置面前
                {
                    q.push({cs[a[x][y]].x2,cs[a[x][y]].y2,e.c+1});//push
                }
                else//为第二个,这里要加1的原因是,你也要走到传送装置面前
                {
                    q.push({cs[a[x][y]].x1,cs[a[x][y]].y1,e.c+1});//push
                }
            }
            else
            {
                q.push({x,y,e.c+1});//正常的草地
            }
        }
    }
    return 0;//完结散花
}