C++矩阵例题分析(3):螺旋矩阵

发布时间:2024年01月05日

一、审题

时间限制:1000ms ? ? ? ? ? ? ? ?内存限制:256MB ? ? ? ? ? ? ? ?各平台平均AC率:14.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为例)

次数方向个数
14
24
34
44
52
62
72
82
91

初步猜测:每次个数都-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?

次数方向个数
17
27
37
47
55
65
75
85
93
103
113
123
131
141
151

二次猜测:初步猜测是正确的

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

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

总算推导出来了!同志们,前面的伪代码有点问题哈~

文章来源:https://blog.csdn.net/joe_g12345/article/details/135417799
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。