1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 常量与全局变量定义 const int MAXN = 1005; // 适配题目最大地图规模 // 四个移动方向:上、下、左、右 int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; int mp[MAXN][MAXN]; // 地图数组:1=陆地,0=海洋 int dist[MAXN][MAXN]; // 距离数组:记录每个点到起点的最短步数 int n; // 地图的大小n×n int main() { // 关闭cin同步,加速输入 ios::sync_with_stdio(false); cin.tie(nullptr); // [2] 读取地图大小n cin >> n; // [3] 读取n×n的地图矩阵 for(int i = 1; i <= n; i++) { string s; cin >> s; // 地图坐标为1-based,字符串为0-based,做索引转换 for(int j = 1; j <= n; j++) { mp[i][j] = s[j-1] - '0'; } } // [4] 读取起点(辽宁号)和终点(故障巨轮)的坐标(1-based) int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; // [5] 初始化距离数组,-1表示该位置未被访问 memset(dist, -1, sizeof(dist)); queue<pair<int, int>> q; // BFS队列,存储待遍历的坐标 // [6] 起点初始化:起点步数为0,入队启动BFS dist[sx][sy] = 0; q.push({sx, sy}); // [7] BFS核心循环,层级遍历所有可达的海洋格子 while(!q.empty()) { // 取出队首的当前坐标 auto cur = q.front(); q.pop(); int x = cur.first; int y = cur.second; // 到达终点,直接输出最短距离并结束程序 if(x == ex && y == ey) { cout << dist[x][y] << endl; return 0; } // 遍历四个移动方向 for(int i = 0; i < 4; i++) { // 计算移动后的新坐标 int nx = x + dx[i]; int ny = y + dy[i]; // 合法性校验: // 1. 坐标在1~n范围内,不越界 // 2. 目标位置是海洋(0),不可走陆地 // 3. 目标位置未被访问过 if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && mp[nx][ny] == 0 && dist[nx][ny] == -1) { // 更新步数,标记已访问 dist[nx][ny] = dist[x][y] + 1; // 新坐标入队,等待后续遍历 q.push({nx, ny}); } } } // 题目保证一定有解,此处不会执行 return 0; }
- 1
信息
- ID
- 1307
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者