@[xiaorunrun520](/user/993122) 所以您为什么还要再广搜函数以外在添加一个函数?
by SCAR_L @ 2023-06-08 06:58:18
@[xiaorunrun520](/user/993122) 我不是太明白您代码中的chuan函数的作用。
by SCAR_L @ 2023-06-08 07:01:39
@[xiaorunrun520](/user/993122) w我的代码:
```cpp
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
struct Conveyor{int x1, y1, x2, y2;};
struct Point{int x, y, t;};
map<char, Conveyor> c;
int n, m;
int sx, sy;
bool flag[305][305];
char a[305][305];
void bfs()
{
queue<Point> q;
q.push({sx, sy, 0});
while(!q.empty())
{
int x = q.front().x, y = q.front().y, t = q.front().t; q.pop();
if(x < 1 || y < 1 || x > n || y > m || flag[x][y] || a[x][y] == '#') continue;
if(a[x][y] == '=')
{
cout << t << endl;
exit(0);
}
flag[x][y] = true;
if(a[x][y] >= 'A' && a[x][y] <= 'Z')
{
int xx = x, yy = y;
if(c[a[xx][yy]].x1 == x && c[a[xx][yy]].y1 == y)
x = c[a[xx][yy]].x2, y = c[a[xx][yy]].y2;
else
x = c[a[xx][yy]].x1, y = c[a[xx][yy]].y1;
}
q.push({x + 1, y, t + 1});
q.push({x, y + 1, t + 1});
q.push({x - 1, y, t + 1});
q.push({x, y - 1, t + 1});
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
if(a[i][j] == '@') sx = i, sy = j;
if(a[i][j] >= 'A' && a[i][j] <= 'Z')
if(c[a[i][j]].x1 == 0 && c[a[i][j]].y1 == 0)
c[a[i][j]].x1 = i, c[a[i][j]].y1 = j;
else c[a[i][j]].x2 = i, c[a[i][j]].y2 = j;
}/*
for(char i = 'A'; i <= 'Z'; i++)
if(c.count(i))printf("%c: x1 = %d, y1 = %d, x2 = %d, y2 = %d\n", i, c[i].x1, c[i].y1, c[i].x2, c[i].y2);
else printf("%c: Not find\n", i);*/
bfs();
return 0;
}
```
by SCAR_L @ 2023-06-08 07:04:04
@[xiaorunrun520](/user/993122) 而且您代码中chuan函数效率太慢了,每次都要扫一遍整张地图,太慢了
by SCAR_L @ 2023-06-08 07:08:45
所以建议您用一个数组(map也行),来代替chuan
函数。能在O(1)的时间内找到转送装置的另一端。
by SCAR_L @ 2023-06-08 07:12:13
具体方法:
先开一个结构体```struct Conveyor{int x1, y1, x2, y2;};```
1. 数组:```Conveyor chuan[30]```,$chuan_i$ 表示第 i 个字母的传送装置,其中$(x1, y1)$为传送装置大写字母的那一端的坐标,$(x2,y2)$为小写字母的坐标。
2. map:在我的代码中有,思想同数组,只不过把索引从第 i 个字母改成了字母 c。建议用数组,数组快。
by SCAR_L @ 2023-06-08 07:21:33
看我写的这么辛苦,给个关注呗
by SCAR_L @ 2023-06-08 07:27:37
@[SCAR_L](/user/608703) 您的代码有问题 比如说
##@#
##Z#
##=#
就出错了 你对只有一个字母时没有特判 如果map只有一个 而是原地传送
by 呆呆的她啊 @ 2023-11-02 10:54:07
@[SCAR_L](/user/608703)
by 呆呆的她啊 @ 2023-11-02 10:55:00