@[HDawn](/user/226030) 正常
你的代码是第一次找到终点就结束程序
不是最优
这样的话方向顺序当然对结果有影响
by 吴勉之 @ 2020-07-14 19:27:52
@[吴勉之](/user/143925) 广度优先第一次找到肯定是最优的啊
by HDawn @ 2020-07-14 19:43:39
@[HDawn](/user/226030) 那只能说明您的bfs有问题
by 吴勉之 @ 2020-07-14 19:48:50
或者是有些~~玄学~~东西没考虑全
~~反正我看不出来~~
by 吴勉之 @ 2020-07-14 19:49:34
AC了 下了四个点终于AC了
```cpp
//
// Created by HDawn on 2020/7/11.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
string str[310];
int a[310][310];
queue<pair<int, int> > que;
map<char, pair<int, pair<int, int> > > map1;
map<pair<int, int>, pair<int, int> > map2;
void check(int x, int y, int num) {
if (a[x][y] == 0 && str[x][y] == '.') {
que.push(make_pair(x, y));
a[x][y] = num + 1;
} else if (str[x][y] == '=') {
cout << num + 1 << endl;
exit(0);
} else if (str[x][y] >= 'A' && str[x][y] <= 'Z') {
que.push(make_pair(map2[make_pair(x, y)].first, map2[make_pair(x, y)].second));
if (a[map2[make_pair(x, y)].first][map2[make_pair(x, y)].second] != 0)
a[map2[make_pair(x, y)].first][map2[make_pair(x, y)].second] = min(
a[map2[make_pair(x, y)].first][map2[make_pair(x, y)].second], num + 1);
else a[map2[make_pair(x, y)].first][map2[make_pair(x, y)].second] = num + 1;
}
}
int main() {
cin >> n >> m;
int x, y;
for (int i = 0; i < n; ++i) {
cin >> str[i];
for (int j = 0; j < m; ++j) {
if (str[i][j] >= 'A' && str[i][j] <= 'Z') {
char c = str[i][j];
if (map1[c].first == 0) {
map1[c].first = 1;
map1[c].second.first = i;
map1[c].second.second = j;
} else {
map2[map1[c].second] = make_pair(i, j);
map2[make_pair(i, j)] = map1[c].second;
}
} else if (str[i][j] == '@') {
x = i, y = j;
}
}
}
map1.clear();
que.push(make_pair(x, y));
while (!que.empty()) {
x = que.front().first;
y = que.front().second;
que.pop();
if (x + 1 < n && str[x + 1][y] != '#')
check(x + 1, y, a[x][y]);
if (x - 1 >= 0 && str[x - 1][y] != '#')
check(x - 1, y, a[x][y]);
if (y + 1 < m && str[x][y + 1] != '#')
check(x, y + 1, a[x][y]);
if (y - 1 >= 0 && str[x][y - 1] != '#')
check(x, y - 1, a[x][y]);
}
return 0;
}
```
by HDawn @ 2020-07-14 20:58:34