1 条题解

  • 0
    @ 2026-1-27 22:13:59
    #include <bits/stdc++.h>
    using namespace std;
    
    // [1] n-矩阵的行数;m-矩阵的列数;arr数组-存储矩阵每个单元格的标记值,0表示未标记
    int n, m, arr[110][110] = {};
    // [2] 四个方向的偏移量(严格按题目要求:右、下、左、上)
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    
    int main() {
        // 问题分析:矩阵按层标记问题,从左上角(0,0)开始标记为1,按右、下、左、上顺序扩展
        //          要求先处理完所有数字k的单元格,再处理数字k+1的单元格,最终输出全矩阵标记结果
        // 解题步骤:1.读取矩阵行列数,初始化BFS队列并标记起点(0,0)为1;2.层次式BFS核心循环,按层处理单元格;
        //          3.处理当前层所有单元格时,扩展四方向未标记单元格并赋值递增数字;4.逐行输出标记后的矩阵
    
        cin >> n >> m;  // [3] 读取矩阵的行数n和列数m
        queue<pair<int, int>> q;  // [4] BFS队列,存储待处理单元格的坐标对(横坐标,纵坐标)
        q.push({0, 0});  // [5] 起点(0,0)入队,作为BFS的第一层
        arr[0][0] = 1;  // [6] 初始化起点标记值为1,符合题目第一个标记要求
        int sum = 2;  // [7] 下一个要标记的数字,初始为2(起点后第一个标记值)
    
        // 层次式BFS核心循环:按层扩展,确保先处理完当前层再处理下一层
        while (!q.empty()) {
            int size = q.size();  // [8] 记录当前队列大小,即「当前层的单元格总数」(核心:分层依据)
            // 遍历处理当前层的所有单元格,处理完后再处理下一层
            for (int i = 0; i < size; ++i) {
                auto [x, y] = q.front();  // [9] 取出队首的当前层单元格坐标(x-行, y-列)
                q.pop();  // [10] 队首元素出队,避免重复处理
    
                // 遍历四个方向,扩展当前单元格的相邻单元格
                for (int d = 0; d < 4; ++d) {
                    int tx = x + dx[d];  // [11] 计算相邻单元格的横坐标
                    int ty = y + dy[d];  // [12] 计算相邻单元格的纵坐标
                    // 合法性判断:1.坐标在矩阵范围内;2.单元格未被标记(arr值为0)
                    if (tx >= 0 && tx < n && ty >= 0 && ty < m && arr[tx][ty] == 0) {
                        arr[tx][ty] = sum++;  // [13] 为未标记单元格赋值,赋值后sum自增准备下一个标记
                        q.push({tx, ty});  // [14] 新标记的单元格入队,作为下一层的待处理节点
                    }
                }
            }
        }
    
        // 逐行输出标记后的矩阵,每个数字后加空格分隔
        for (int i = 0; i < n; ++i) {  // [15] 遍历矩阵的每一行
            for (int j = 0; j < m; ++j) {  // [16] 遍历当前行的每一列
                cout << arr[i][j] << " ";  // [17] 输出当前单元格的标记值,后跟空格
            }
            cout << endl;  // [18] 一行遍历完毕,换行输出下一行
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1309
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    1
    已通过
    1
    上传者