评论区翻了很久,说不需要对传送门标记。但是我标记传送起点的话(传送终点没有被标记),依然可以从传送终点回到传送起点。真的想不到反例了,求助大佬58分
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
char mp[105][105];
int cnt[305][305];
int ans,n,m,nx,ny;
bool vis[305][305];
pair<int,int>node;
deque<pair<int,int> >dq;
void getAnother(char ch)
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
if(mp[i][j] == ch && !(i == nx && j == ny))
{
nx = i;
ny = j;
return;
}
}
}
void bfs(int sx,int sy)
{
vis[sx][sy] = true;
pair<int,int> start; start.first = sx,start.second = sy;
dq.push_back(start);
while(!dq.empty())
{
int x = dq.front().first,y = dq.front().second;
if(mp[x][y] == '@')
{
ans = cnt[x][y];
return;
}
for(int i = 0 ; i < 4; i++)
{
nx = x + dx[i],ny = y + dy[i];
if(nx >= 1 && nx <= 300 && ny >= 1 && ny <= 300 && !vis[nx][ny] && mp[nx][ny] != '#')
{
vis[nx][ny] = true; //如果是传送门,则标记的是传送起点的点,不影响传送后从当前的传送终点再回到传送起点,因为传送终点仍然是false
if(mp[nx][ny] >= 'A' && mp[nx][ny] <= 'Z') getAnother(mp[nx][ny]);//强行传送至下一传送门
cnt[nx][ny] = cnt[x][y] + 1; //如果是传送后,则传送后的门cnt为传送前的位置+1
dq.push_back({nx,ny}); //果是传送后,则加入队列的点是传送后的点
}
}
dq.pop_front();
}
}
int main()
{
cin>>n>>m;
int x,y;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
cin>>mp[i][j];
if(mp[i][j] == '=')
{
x = i;
y = j;
}
}
bfs(x,y);
cout<<ans;
// 打印cnt数组
// cout<<endl;
// for(int i = 1; i <= n; i++)
// {
// for(int j = 1; j <= m; j++) cout<<cnt[i][j];
// cout<<endl;
// }
return 0;
}