ac了,问题就是传送门没有被标记,然而从a传送到b,需要把传送起点a标记。具体为什么我也不是很理解....
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 310, M = 1e6;
char g[N][N];
int n, m, d[N][N];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
bool vis[N][N];
PII q[M], st, ed;
PII trans(int x, int y)
{
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
{
if(g[i][j] == g[x][y] && (i != x || j != y))
return {i, j};
}
}
void bfs()
{
memset(d, -1, sizeof d);
int hh = 0, tt = 0;
q[0] = st;
d[st.first][st.second] = 0;
vis[st.first][st.second] = true;
while(hh <= tt)
{
auto t = q[hh++];
int x = t.first, y =t.second;
if(g[x][y] == '=')
{
cout<<d[x][y]<<endl;
return;
}
for(int i = 0; i < 4; i ++)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < m && g[nx][ny] != '#' && !vis[nx][ny])
{
if(g[nx][ny] == '.' || g[nx][ny] == '=')
{
d[nx][ny] = d[x][y] + 1;
vis[nx][ny] = true;
q[++tt] = {nx, ny};
}
else
{
PII res = trans(nx, ny);
d[res.first][res.second] = d[x][y] + 1;
vis[nx][ny] = true; //标记传送起点,和上面的代码相比就多加了这一行
q[++tt] = res;
}
}
}
}
}
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] == '@')
st = {i, j};
if(g[i][j] == '=')
ed = {i, j};
}
bfs();
return 0;
}
```
by virstaring @ 2023-03-25 15:25:48
玄学 我也是一样 把搜索顺序上下左右调整一下就能过其中三个的某个测试点,但是我想不明白为什么从a传送到b点要标记a
by 程序小大白 @ 2023-04-25 23:16:45
@[程序小大白](/user/419073) 感觉是因为要防止走过去走回来又走过去的情况?
by tzlnb666 @ 2023-06-16 21:01:15