运行超时，优化一下。BFS

Question

希望能看懂修改的代码，大一下学到BFS，感谢

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <stdio.h>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <string.h>
using namespace std;

using ll = long long;
typedef pair<int, int> PII;

const int inf = 0x3f3f3f3f;
const int N = 20;

char mpp[205][205];
int mark[205][205];
int x[4] = { -1,0,1,0 }, y[4] = { 0,1,0,-1 };
int n, m;

int bfs(int nn, int mm, char sreach) {
    queue<PII> q;
    memset(mark, -1, sizeof mark);

    q.push(make_pair(nn, mm));
    mark[nn][mm] = 0;

    int ans = 0, sum = 0;
    while (!q.empty()) {
        PII top = q.front();
        q.pop();
        int i = top.first, j = top.second;

        if (mpp[i][j] == sreach)
            return mark[i][j];

        for (int k = 0; k < 4; k++) {
            int xx = i + x[k], yy = j + y[k];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && mark[xx][yy] == -1 && mpp[xx][yy] != '#') {
                mark[xx][yy] = mark[i][j] + 1;
                q.push(make_pair(xx, yy));
            }
        }
    }
    return  inf;
}


int main() {
    while (cin >> n >> m && (n != 0 && m != 0)) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cin >> mpp[i][j];

        int tmp = inf;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mpp[i][j] == '@') {
                    int Y = bfs(i, j, 'Y');
                    int M = bfs(i, j, 'M');
                    if (Y < inf && M < inf) {
                        int sum = Y + M;
                        if (sum < tmp)
                            tmp = sum;
                    }
                }
            }
        }
        cout << tmp * 11 << "\n";
    }
    return 0;
}

题目
在杭州学习了一年后，一分飞终于回到了家乡宁波。离开宁波一年，一分飞有很多人要见。尤其是好朋友Merceki。
一分飞的家在农村，而Merceki的家在市中心。所以一分飞和Merceki约好在肯德基见面。宁波有很多家肯德基，他们想选择一家让两人到达的总时间最短。
现在给你一份宁波地图，一分飞和Merceki都可以向上、下、左、右移动到相邻的道路，每次移动花费11分钟。
输入
输入包含多个测试用例。
每个测试用例包括，首先两个整数n，m。(2≤n，m≤200)。
接下来n行，每行包含m个字符。
‘Y’ 表示一分飞的初始位置。
‘M’ 表示Merceki的初始位置。
‘#’ 禁止通行的道路；
‘.’ 可通行的道路。
‘@’ 肯德基。
输出
对于每个测试用例，输出使一分飞和Merceki到达某家肯德基的最小总时间。你可以确定总有一家肯德基可以让他们见面。
输入样例

4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#

输出样例
66
88
66

Answer 1

引自免费微信小程序：皆我百晓生

根据您提供的代码和描述，这是一个基于BFS（宽度优先搜索）算法来解决的问题。程序的目标是从两个人各自的位置开始搜索，并计算他们分别到达任意一个肯德基的最短距离，然后将这两个距离相加得到总时间。

为了优化这段代码并减少运行时间超时的可能性，可以从以下方面入手：

1. 减少冗余搜索：对于每个点，只进行一次BFS搜索以找到最近的肯德基。在搜索过程中记录下每个点到最近肯德基的距离，而不是为每个'Y'或'M'都重新进行全局搜索。

2. 使用unordered_map替换二维数组mark存储每个位置到最近肯德基的距离，因为这可以更快地查找和更新距离信息。

3. 仅对'@'（肯德基）进行BFS搜索，这样只需遍历地图一次。

以下是修改后的代码：

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

typedef pair<int, int> PII;

const int inf = 0x3f3f3f3f;
const int N = 205;

char mpp[N][N];
int x[4] = { -1, 0, 1, 0 }, y[4] = { 0, 1, 0, -1 };
int n, m;

// 记录每个位置到最近肯德基的距离
unordered_map<PII, int> distToKFC;

void bfs(int nn, int mm) {
    queue<PII> q;
    distToKFC[{nn, mm}] = 0;
    q.push({ nn, mm });

    while (!q.empty()) {
        PII top = q.front();
        q.pop();
        int i = top.first, j = top.second;

        for (int k = 0; k < 4; k++) {
            int xx = i + x[k], yy = j + y[k];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && mpp[xx][yy] != '#' && distToKFC.find({ xx, yy }) == distToKFC.end()) {
                distToKFC[{xx, yy}] = distToKFC[{i, j}] + 1;
                q.push({ xx, yy });
            }
        }
    }
}

int main() {
    while (cin >> n >> m && (n != 0 && m != 0)) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                cin >> mpp[i][j];

        // 找到所有肯德基并进行BFS
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mpp[i][j] == '@') {
                    bfs(i, j);
                }
            }
        }

        int minYDist = inf, minXDist = inf;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mpp[i][j] == 'Y')
                    minYDist = min(minYDist, distToKFC[{i, j}]);
                else if (mpp[i][j] == 'M')
                    minXDist = min(minXDist, distToKFC[{i, j}]);
            }
        }

        cout << (minYDist + minXDist) * 11 << "\n";
    }
    
    return 0;
}

这段代码首先通过遍历地图找出所有的肯德基，对每个肯德基执行一次BFS以计算出每个可通行点到最近肯德基的距离。之后再遍历地图一次，找到'Y'和'M'的位置并获取它们到最近肯德基的距离，最后将这两个距离相加乘以11得到答案。这样的优化有助于降低搜索复杂度，从而可能避免运行超时问题。