# HDU-2612 双BFS
## [HDU-2612](http://acm.hdu.edu.cn/showproblem.php?pid=2612)
## 分析
老暴力了, 就是**从M和Y分别出发BFS顺便记录步数, 然后遍历步数矩阵, 找相加时的最小值**.
需要注意的地方是记录步数时必须将默认步数设为无穷值(INF), 并且INF必须在**机器最大值的1/2**(比如0x7fffffff的1/2, 如果使用有符号int的话)和**最大可能步数**之间, 而**不能为0**.
这是因为题目并不保证所有KFC(@)都能走到, 这样最后会产生INF+INF, 不管是初始值为0还是超过了整型最大值的1/2, 最终结果都会出现非预期的错误. 在这里坑了很久.
> **0x3f3f3f3f**是INF的惯用取值, 正好满足上述特性. 详情参见[这篇博客](https://blog.csdn.net/mlm5678/article/details/82729974?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-3.nonecase)
## 心得
原来还想过同步双向BFS(把第一次访问到另一个人来过的KFC时的情况作为最优解), 后来发现想错了. 目前看来只能两遍完整BFS.
比如出现这种情况, 同步双向BFS就会出问题:
| # | Y | # | ... |
|:---:|:---:|:---:|:---:|
| | | | ... |
| | # | 3 | ... |
| | 5 | ! | ... |
| ... | ... | ... | ... |
3 5代表Y到两个KFC的距离, !代表假设M遍历到的位置. 这时如果M优先走左侧, 就WA了.
## 代码
原型来自HDU讨论区
```cpp
// -------------- GLOBAL ----------------
char map1[250][250]; // YM.#@!
int booky[250][250], bookm[250][250];
int n, m;
int y1, y2, m1, m2;
// -------------- FUNC ----------------
void bfs(int x, int y, int book[250][250]) {
queue<pair<int, int>> que;
que.push({x, y});
book[x][y] = 0;
while (!que.empty()) {
auto p = que.front();
F0(i, 4) {
int tx = p.fs + dir[i][0];
int ty = p.se + dir[i][1];
if (tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if (book[tx][ty] != INF)
continue;
if (map1[tx][ty] == '.' || map1[tx][ty] == '@') {
que.push({tx, ty});
book[tx][ty] = book[p.fs][p.se] + 1;
}
}
que.pop();
}
}
// -------------- MAIN ----------------
int main() {
//ios_base::sync_with_stdio(false);
while (~scanf("%d%d", &n, &m)) {
memset(booky, 0x3F, sizeof(booky));
memset(bookm, 0x3F, sizeof(bookm));
fill0(map1);
F0(i, n) {
getchar();
F0(j, m) {
scanf("%c", &(map1[i][j]));
switch (map1[i][j]) {
case 'Y':
y1 = i, y2 = j;
break;
case 'M':
m1 = i, m2 = j;
break;
}
}
}
bfs(y1, y2, booky);
bfs(m1, m2, bookm);
int res = INF;
F0(i, n) {
F0(j, m) {
if (map1[i][j] == '@') {
res = min(res, booky[i][j] + bookm[i][j]);
}
}
}
printf("%d\n", res * 11);
}
return 0;
}
```
![]()