被这个传送门传来传去搞糊涂了,于是想到,传送不耗费时间,传送之后也是要往四个方向走,于是不记录传送门那个点,每次踏进传送门之后,下一步是另外一个门的上下左右就好了。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 310;
char g[N][N];
int n,m,sx,sy;
int dist[N][N];
bool st[N][N];
unordered_map<char,vector<PII>> mp; // 记录传送门位置
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
vector<PII> get_states(int x,int y)
{
vector<PII> tmp;
int flag = 0;
if(g[x][y]>='A'&&g[x][y]<='Z')
{
vector<PII> t = mp[g[x][y]];
int x1 = t[0].first,y1 = t[0].second;
int x2 = t[1].first,y2 = t[1].second;
if(x1 == x && y1 ==y)
{
x = x2,y = y2;
}
else
{
x = x1,y=y1;
}
}
for(int i=0;i<4;i++)
{
int nx = x+dx[i],ny = y+dy[i];
tmp.push_back({nx,ny});
}
return tmp;
}
int bfs(int sx,int sy)
{
queue<PII> q;
st[sx][sy] = true;
q.push({sx,sy});
dist[sx][sy] = 0;
while(!q.empty())
{
auto t = q.front();
q.pop();
int tx = t.first,ty = t.second;
if(g[tx][ty] == '=') return dist[tx][ty];
vector<PII> tmp = get_states(tx,ty);
//cout<<"当前节点: "<<tx<<" "<<ty<<endl;
for(auto nt : tmp)
{
int nx = nt.first,ny = nt.second;
if(nx < 0 || nx >= n || ny < 0 || ny >= m ) continue;
if(st[nx][ny] || g[nx][ny] == '#') continue;
dist[nx][ny] = dist[tx][ty]+1;
st[nx][ny] = true;
q.push({nx,ny});
}
}
return -1;
}
int main()
{
cin>>n>>m;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
cin>>g[i][j];
if(g[i][j] == '@') sx = i,sy = j;
if(g[i][j] >= 'A' && g[i][j] <= 'Z')
{
mp[g[i][j]].push_back({i,j});
}
}
}
int ans = bfs(sx,sy);
cout<<ans<<endl;
return 0;
}