针对CSP-J/S的冲刺练习：Day 4 提高题

一、审题

时间限制：1000ms ? ? ? ? ? ? ? ?内存限制：256MB ? ? ? ? ? ? ? ?平均AC率：7.89%

题目描述

输出一个n*n大小的螺旋矩阵。

螺旋矩阵的样子：

输入描述

共一行，一个正整数n，表示矩阵变长的长度

输出描述

共n行，每行n个正整数，表示n*n的螺旋矩阵

样例

输入

5

输出

?1 ? 2 ? 3 ? 4 ? 5

16 17 ?18 19 ?6

15 24 25 20 ?7

14 23 22 21 ?8

13 12 ?11 ?10 ?9

提示

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

28 29 30 31 32 33 34 ? 9

27 48 49 50 51 52 35 ?10

26 47 60 61 62?53 36 ?11

25 46 59?64?63 54 37 12

24 45 58 57 56 55 38?13

23 44 43 42 41 40 39 14

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。每填充一行或一列，对应的
边界值会进行相应的更新。

最后，输出填充好的螺旋矩阵。
*/

总算推导出来了！同志们，前面的伪代码有点问题哈～