我把走过的'.'以及单个出现的字母标记为'#',成对的传送门不标记,第二个测试用例没有走到出口,找不到问题。。。
#include <iostream>
#include <queue>
using namespace std;
const int N = 310;
char maze[N][N];
int step[N][N];
int n,m;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
pair<int,int> My_find(int x, int y)
{
for(int i=1 ; i<=n ; i++)
for(int j=1 ; j<=m ; j++)
if(maze[i][j] == maze[x][y] && i!=x)
return {i,j};
cout<<maze[x][y]<<endl;
return {0,0};
}
int bfs(int x, int y)
{
queue<pair<int,int>> q;
q.push({x,y});
maze[x][y] = '#';
step[x][y] = 0;
while(!q.empty())
{
int xx = q.front().first;
int yy = q.front().second;
q.pop();
for(int i=0 ; i<4 ; i++)
{
int row = xx + dx[i];
int col = yy + dy[i];
if(row>=1&&row<=n && col>=1&&col<=m
&& maze[row][col]!='#')
{
step[row][col] = step[xx][yy]+1;
if(maze[row][col] == '.')
maze[row][col] = '#'; //走过地路标记为墙
else if(maze[row][col] == '=')
{
return step[row][col];
}
else
{
pair<int,int> p = My_find(row,col); //找到传送点坐标
if(p.first == 0) maze[row][col] = '#'; //无法传送,标记为走过
else
{ //传送
row = p.first;
col = p.second;
step[row][col] = step[xx][yy]+1;
}
}
q.push({row,col});
}
}
}
for(int i=1 ; i<=n ; i++)
{
for(int j=1 ; j<=m ; j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
return -1;
}
int main()
{
int st_x,st_y;
cin>>n>>m;
for(int i=1 ; i<=n ; i++)
for(int j=1 ; j<=m ; j++)
{
cin>>maze[i][j];
if(maze[i][j] == '@')
{
st_x=i; st_y=j;
}
}
cout<<bfs(st_x,st_y)<<endl;
return 0;
}