#include "iostream"\n#include "vector"\n#include "queue"\nusing namespace std;\n\n// 定义一个格子的结构体\nstruct Cell {\n int x, y, time;\n Cell(int _x, int _y, int _time) : x(_x), y(_y), time(_time) {}\n}\n\nint main() {\n int n, m;\n cin >> n >> m;\n vector<vector> obstacle(n+1, vector(n+1, false)); // 初始化障碍矩阵\n for (int i = 0; i < m; i++) {\n int x, y;\n cin >> x >> y;\n obstacle[x][y] = true; // 标记障碍位置为true\n }\n \n vector<vector> visited(n+1, vector(n+1, false)); // 初始化访问矩阵\n queue| q;\n q.push(Cell(1, 1, 0)); // 将起点入队\n visited[1][1] = true; // 标记起点已访问\n int maxTime = 0; // 最大时间差\n while (!q.empty()) {\n Cell cur = q.front();\n q.pop();\n maxTime = max(maxTime, cur.time); // 更新最大时间差\n \n if (cur.x == n && cur.y == n) { // 到达终点\n break;\n }\n \n // 向上走一步\n if (cur.x > 1 && !obstacle[cur.x-1][cur.y] && !visited[cur.x-1][cur.y]) {\n q.push(Cell(cur.x-1, cur.y, cur.time+1));\n visited[cur.x-1][cur.y] = true;\n }\n \n // 向下走一步\n if (cur.x < n && !obstacle[cur.x+1][cur.y] && !visited[cur.x+1][cur.y]) {\n q.push(Cell(cur.x+1, cur.y, cur.time+1));\n visited[cur.x+1][cur.y] = true;\n }\n \n // 向左走一步\n if (cur.y > 1 && !obstacle[cur.x][cur.y-1] && !visited[cur.x][cur.y-1]) {\n q.push(Cell(cur.x, cur.y-1, cur.time+1));\n visited[cur.x][cur.y-1] = true;\n }\n \n // 向右走一步\n if (cur.y < n && !obstacle[cur.x][cur.y+1] && !visited[cur.x][cur.y+1]) {\n q.push(Cell(cur.x, cur.y+1, cur.time+1));\n visited[cur.x][cur.y+1] = true;\n }\n }\n \n cout << maxTime << endl;\n \n return 0;\n} |
