时间限制:1000ms ? ? ? ? ? ? ? ?内存限制:256MB ? ? ? ? ? ? ? ?平均AC率:7.89%
题目描述
输出一个n*n大小的螺旋矩阵。
螺旋矩阵的样子:
输入描述
共一行,一个正整数n,表示矩阵变长的长度
输出描述
共n行,每行n个正整数,表示n*n的螺旋矩阵
样例
输入
5
输出
?1 ? 2 ? 3 ? 4 ? 5
提示
1 <= n <= 100
1. 初步观察填充方式(5*5为例)
次数 方向 个数 1 右 4 2 下 4 3 左 4 4 上 4 5 右 2 6 下 2 7 左 2 8 上 2 9 右 1 初步猜测:每次个数都-2,2之后是1
2. 二次观察填充方式(8*8为例)
?1 ? ?2 ? 3 ? 4 ? 5 ? ?6 ? 7 ? ?8
22 21 ?20 19 ?18 17 ?16 15?
次数 方向 个数 1 右 7 2 下 7 3 左 7 4 上 7 5 右 5 6 下 5 7 左 5 8 上 5 9 右 3 10 下 3 11 左 3 12 上 3 13 右 1 14 下 1 15 左 1 二次猜测:初步猜测是正确的
3. 观察填充次数
推导过程省略……
次数 = 2n - 1
?4. 伪代码
int Q = 2 * n - 1; // 次数 int times = n - 1; // 填充个数 for (int i = 1 ~ Q) for (int i = 1 ~ times) // 填充
? ? ? ? 最重要的是如何填充。嗯……还是硬着来吧。
int x = 1, y = 1; int temp_x = 1, temp_y = 1; int fill = 1; int direction = 0; /* x: 填充的x坐标 y: 填充的y坐标 temp_x: 临时存储x坐标 temp_y: 临时存储y坐标 fill: 填充的数字 direction: 填充时面向的方向 0: 右 1: 下 2: 左 3: 上 */
for (int i = 1 ~ Q) for (int i = 1 ~ times) matrix[x][y] = fill; // 填充数字 if (direction == 0) y++; // 向右一列 if (direction == 1) x++; // 向下一行 if (direction == 2) y--; // 向左一列 if (direction == 3) x--; // 向上一行 fill++; // 填充数字自增 if (times == 2) times--; else times -= 2; temp_x++; temp_y++; x = temp_x; y = temp_y;
嗯哼……打乱,重来一下。
5. 参考答案
#include <iostream> using namespace std; int main() { // 数据初始化 int n; int matrix[105][105] = {}; int x, y; int fill = 1; int direction = 0; // 输入 cin >> n; // 存储螺旋矩阵 int left = 1, right = n, top = 1, bottom = n; while (left <= right && top <= bottom) { // 从左到右 for (int i = left; i <= right; i++) { matrix[top][i] = fill++; } top++; // 从上到下 for (int i = top; i <= bottom; i++) { matrix[i][right] = fill++; } right--; // 从右到左 for (int i = right; i >= left; i--) { matrix[bottom][i] = fill++; } bottom--; // 从下到上 for (int i = bottom; i >= top; i--) { matrix[i][left] = fill++; } left++; } // 输出 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << matrix[i][j] << " "; } cout << endl; } return 0; } /* 这段代码的思路是通过四个边界值left、 right、top、bottom来确定当前填充范 围的边界,然后使用四个循环依次填充螺旋 矩阵的四个方向上的元素。 具体来说,首先将top行从左到右填充为1 到n,然后将right列从上到下填充为n+1 到2n-1,接着将bottom行从右到左填充为 2n到3n-2,最后将left列从下到上填充为 3n-1到4n-3。每填充一行或一列,对应的 边界值会进行相应的更新。 最后,输出填充好的螺旋矩阵。 */
总算推导出来了!同志们,前面的伪代码有点问题哈~