麦当劳寻宝游戏：破解时间差谜题 | C++ 代码实现

"话说我们铭铭小朋友成功的回答了爸爸的问题，自然少不了要去索要些奖励，抠门的爸爸一看报纸，嘿，门口的麦当劳在搞活动，还有免费午餐哦，不过前提条件：得正确回答麦当劳叔叔的问题。\n\n问题是这样描述的：\n\n"我面前有很多个小朋友，我希望你帮我找到一个最聪明的小朋友。我心目中最聪明的就是第一个跑进麦当劳大门的，我希望你帮我找出最聪明和最不聪明的小朋友，可能的最大的到达时间差。但是，小朋友只能按照一个特殊的规则前进。小朋友面前有一个 n\times nn\times n 的格子矩阵，左下角的格子是起点，右上角的格子是大门。每个孩子每秒可以走向 上、下、左、右 前进一个格子，每个格子只能经过一次。但矩阵中间有一些障碍区，不能通过，只能绕过。"\n\n例如，4\times 44\times 4 的矩阵，格子 (1, 1),(2, 3),(4, 2)(1,1),(2,3),(4,2) 为障碍区，黑格子就是一条可行的路线。时间为 77。\n\n输入格式\n第一行为两个整数 n, mn,m。\n\n第二至第 m+1m+1 行里，每行描述一个障碍区。用两个整数表示 x, yx,y。\n\n输出格式\n仅一行，那个最大的时间差。\n\n用c++解答内容：我们可以使用广度优先搜索(BFS)来解决这个问题。\n\n首先，我们需要定义一个结构体来表示每个格子的坐标。\n\ncpp\nstruct Point {\n int x;\n int y;\n};\n\n\n然后，我们可以定义一个函数来判断一个格子是否在矩阵内并且不是障碍区。\n\ncpp\nbool isValid(int x, int y, int n, vector<Point>& obstacles) {\n if (x < 1 || x > n || y < 1 || y > n) {\n return false;\n }\n for (int i = 0; i < obstacles.size(); i++) {\n if (obstacles[i].x == x && obstacles[i].y == y) {\n return false;\n }\n }\n return true;\n}\n\n\n接下来，我们可以定义一个函数来计算从起点到大门的最大时间差。\n\ncpp\nint calculateMaxTimeDiff(int n, vector<Point>& obstacles) {\n // 定义四个方向的偏移量\n int dx[] = {0, 1, 0, -1};\n int dy[] = {1, 0, -1, 0};\n \n // 定义一个二维数组来保存每个格子的到达时间\n vector<vector<int>> time(n + 1, vector<int>(n + 1, -1));\n \n // 定义一个队列来进行广度优先搜索\n queue<Point> q;\n \n // 起点的到达时间为0\n time[1][1] = 0;\n q.push({1, 1});\n \n while (!q.empty()) {\n Point p = q.front();\n q.pop();\n \n int x = p.x;\n int y = p.y;\n \n // 遍历四个方向\n for (int i = 0; i < 4; i++) {\n int nx = x + dx[i];\n int ny = y + dy[i];\n \n // 如果下一个格子是有效的，并且还没有到达过\n if (isValid(nx, ny, n, obstacles) && time[nx][ny] == -1) {\n // 到达时间为上一个格子的到达时间加1\n time[nx][ny] = time[x][y] + 1;\n q.push({nx, ny});\n }\n }\n }\n \n // 最大时间差为到达大门的时间减去到达起点的时间\n return time[n][n] - time[1][1];\n}\n\n\n最后，我们可以读取输入并调用上述函数来计算最大时间差。\n\ncpp\nint main() {\n int n, m;\n cin >> n >> m;\n \n vector<Point> obstacles(m);\n for (int i = 0; i < m; i++) {\n cin >> obstacles[i].x >> obstacles[i].y;\n }\n \n int maxTimeDiff = calculateMaxTimeDiff(n, obstacles);\n cout << maxTimeDiff << endl;\n \n return 0;\n}\n\n\n这样，我们就可以得到最大时间差并输出结果了。