1 条题解

  • 0
    @ 2026-2-17 22:13:16
    #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
    上传者