1 条题解
-
0
#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
- 上传者