/*
我的思路是:考虑从当前点出发能到达的4个点,有以下几种情况:
(1)可能下一步踩在草地上,正常将其加入队列即可,并修改下一步踩上的点的ans为当前点的ans+1,并把这块草地标记为$(已经走过);
(2)可能下一步踩在假的传送门上,和正常草地一样处理;
(3)可能下一步踩在真的传送门上,那么修改下一步踩上的点的ans为当前点的ans+1,并修改对应传送门的ans为当前点的ans+1,将传送门的另一端加入队列。
以上做法对应的几个坑点:
(1)传送门可能多次经过,所以走过传送门不将其标记为$;
(2)传送门一旦踩上必定会触发,所以门的两头时间相同,且要将门的另一头加入队列;
(3)传送门如果只是中转站的话,不能传过去马上传回来,必须在门的另一头先踩一下草地再上传送门传回来。比如门的另一端被墙包围着,那么传过去就回不来了。
由于我考虑的是当前点能到达的四个点的情况,所以不会出现传过去立刻传回来的情况。
*/
#include <stdio.h>
#include <iostream>
#include <queue>
#define maxn 305
using namespace std;
char p[maxn][maxn]; //p用来存放地图
int n,m,ans[maxn][maxn]={};//n,m未地图大小,ans是到地图每个点的最短时间
int q[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//上下左右偏移量
int door[26][4]={};//用两组坐标来记录26个可能存在的传送装置,初始化未0
struct coord{
int x,y;
};
queue <coord> Q;//bfs用到的队列
int main(){
//freopen("P1825_6.in","r",stdin);
int start_x,start_y,end_x,end_y;//起点和终点的坐标
scanf("%d%d",&n,&m);
getchar();
for(int i=1;i<=n;++i) //读入图并进行预处理
for(int j=1;j<=m+1;++j){
scanf("%c",&p[i][j]);
if('A'<=p[i][j] && p[i][j]<='Z'){ //记录传送装置
if(door[p[i][j]-'A'][0]==0){
door[p[i][j]-'A'][0]=i;
door[p[i][j]-'A'][1]=j;
}else{
door[p[i][j]-'A'][2]=i;
door[p[i][j]-'A'][3]=j;
}
}else if(p[i][j]=='@'){ //记录起点
start_x=i; start_y=j;
}else if(p[i][j]=='='){ //记录终点
end_x=i; end_y=j;
}
}
Q.push(coord{start_x,start_y});//开始bfs,将起点加入队列
p[start_x][start_y]='$'; //并将其标记为$,表示已经走过
while(!Q.empty()){
coord now=Q.front();
Q.pop();
//printf("%d %d %d\n",now.x,now.y,ans[now.x][now.y]);
if(now.x==end_x && now.y==end_y){ //如果到达终点就输出终点的答案
printf("%d",ans[now.x][now.y]);
return 0;
}
for(int i=0;i<4;++i){ //依次遍历4个点
int xx=now.x+q[i][0],yy=now.y+q[i][1];//下一步的坐标
if(xx>=1 && yy>=1 && xx<=n && yy<=m && p[xx][yy]!='#' && p[xx][yy]!='$'){//如果下一步没出界且不是墙且没经过,就考虑加入队列
char temp=p[xx][yy];//先统一标记为$
p[xx][yy]='$';
ans[xx][yy]=ans[now.x][now.y]+1;//下一步的时间为当前位置时间+1
if('A'<=temp && temp<='Z' && door[temp-'A'][0]*door[temp-'A'][1]*door[temp-'A'][2]*door[temp-'A'][3] !=0){
//如果是传送门且是真传送门(地图坐标均为正整数,如果乘积为0必然是假门)
if(door[temp-'A'][0]==xx && door[temp-'A'][1]==yy){ //先判断是门的哪一头
Q.push(coord{door[temp-'A'][2],door[temp-'A'][3]});//将传送门的另一端加入队列。
ans[door[temp-'A'][2]][door[temp-'A'][3]]=ans[xx][yy];//修改对应的时间为这一头的时间(这一头的门的时间前面统一改过了)
}else{
Q.push(coord{door[temp-'A'][0],door[temp-'A'][1]});
ans[door[temp-'A'][0]][door[temp-'A'][1]]=ans[xx][yy];
}
p[xx][yy]=temp; //由于传送门可以经过多次,所以还原
}else{
Q.push(coord{xx,yy});//如果不是门就加入队列继续搜即可,时间已经改过了,也已经标记为$了
}
}
}
}
}