麦当劳游戏：最聪明和最不聪明的小朋友，时间差最大是多少？

话说我们铭铭小朋友成功的回答了爸爸的问题，自然少不了要去索要些奖励，抠门的爸爸一看报纸，嘿，门口的麦当劳在搞活动，还有免费午餐哦，不过前提条件：得正确回答麦当劳叔叔的问题。\n\n问题是这样描述的：\n\n“我面前有很多个小朋友，我希望你帮我找到一个最聪明的小朋友。我心目中最聪明的就是第一个跑进麦当劳大门的，我希望你帮我找出最聪明和最不聪明的小朋友，可能的最大的到达时间差。但是，小朋友只能按照一个特殊的规则前进。小朋友面前有一个 n\u00d7nn\u00d7n 的格子矩阵，左下角的格子是起点，右上角的格子是大门。每个孩子每秒可以走向 上、下、左、右 前进一个格子，每个格子只能经过一次。但矩阵中间有一些障碍区，不能通过，只能绕过。”\n\n例如，4\u00d744\u00d74 的矩阵，格子 (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\n我们可以使用广度优先搜索（BFS）来解决这个问题。从起点开始，逐层向外扩展，直到达到终点或者无法继续扩展为止。在扩展的过程中，我们需要记录每个格子的到达时间。\n\n具体步骤如下：\n\n1. 创建一个 n\u00d7n 的矩阵，用来记录每个格子的到达时间。初始值设为一个很大的数，表示该格子还未被访问过。\n\n2. 将起点的到达时间设为0，并将起点加入队列。\n\n3. 从队列中取出一个格子，检查其上下左右四个邻居格子。如果邻居格子未被障碍物占据且未被访问过，则更新邻居格子的到达时间，并将邻居格子加入队列。\n\n4. 重复步骤3，直到队列为空或者找到终点。\n\n5. 最后，我们得到了每个格子的到达时间。最聪明的小朋友的到达时间就是终点的到达时间，最不聪明的小朋友的到达时间就是起点的到达时间。\n\n6. 计算最大的时间差，并输出。\n\n下面是Python代码的实现：\n\npython\nimport sys\nfrom collections import deque\n\n# 读取输入\nn, m = map(int, sys.stdin.readline().split())\n\n# 初始化矩阵\nmatrix = [[sys.maxsize] * n for _ in range(n)]\n\n# 设置起点和终点\nstart = (0, 0)\nend = (n-1, n-1)\n\n# 将起点的到达时间设为0\nmatrix[start[0]][start[1]] = 0\n\n# 障碍物的坐标\nobstacles = []\nfor _ in range(m):\n x, y = map(int, sys.stdin.readline().split())\n obstacles.append((x-1, y-1))\n\n# 定义上下左右四个方向的坐标变换\ndx = [0, 0, -1, 1]\ndy = [1, -1, 0, 0]\n\n# 广度优先搜索\nqueue = deque([start])\nwhile queue:\n x, y = queue.popleft()\n\n # 检查上下左右四个邻居格子\n for k in range(4):\n nx = x + dx[k]\n ny = y + dy[k]\n\n # 检查邻居格子是否越界或被障碍物占据\n if nx < 0 or nx >= n or ny < 0 or ny >= n or (nx, ny) in obstacles:\n continue\n\n # 更新邻居格子的到达时间，并将邻居格子加入队列\n if matrix[nx][ny] == sys.maxsize:\n matrix[nx][ny] = matrix[x][y] + 1\n queue.append((nx, ny))\n\n# 计算最大的时间差\nmax_time_diff = matrix[end[0]][end[1]] - matrix[start[0]][start[1]]\n\n# 输出结果\nprint(max_time_diff)\n\n\n这样，我们就可以得到最大的时间差，并输出。