方阵填充自然数

女爷i 2023-03-12 12:29 23阅读 0赞

### 1004: 方阵填充自然数 ###

时间限制: 1 Sec  内存限制: 125 MB  
提交次数: 537  解决: 64

附加描述

> 在一个N\*N的方阵中，填入1，2，……N\*N个数，并要求构成如下的格式：  
> 例如：  
> N=5  
> 13 14 15 16  1  
> 12 23 24 17  2  
> 11 22 25 18  3  
> 10 21 20 19  4  
>  9  8  7  6  5  
>   
>   
> N=6  
> 16 17 18 19 20  1  
> 15 30 31 32 21  2  
> 14 29 36 33 22  3  
> 13 28 35 34 23  4  
> 12 27 26 25 24  5  
> 11 10  9  8  7  6

> 输入
> 
> 每个测试文件只包含一组测试数据，每组输入一个N。

> 输出
> 
> 输出构成的方阵。

> 样例输入 
> 
>     5

> 样例输出 
> 
>     13 14 15 16 1
>     12 23 24 17 2
>     11 22 25 18 3
>     10 21 20 19 4
>     9 8 7 6 5

> 提示
> 
> N阶方阵范围 1～100  
> 使用二维数组保存方阵数据。  
> 注意N<=3时候的数据打印间隔。

其原理如图所示一圈圈的填充，

![Center][]

#include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    ///1004
    #define DOWN    0
    #define LEFT    1
    #define UP      2
    #define RIGHT   3
    #define MAXNUM 100
    
    void FillMatrix(int matrix[MAXNUM][MAXNUM], int size, int num, int offset)
    {
        //matrix为总矩阵，size为剩余矩阵的大小，num为要填的第一个数，offset为剩余矩阵在总矩阵中的位置
        //递归终止条件
        if (size == 0)
            return;
        //递归终止条件
        if (size == 1)
        {
            matrix[offset][offset] = num;
            return;
        }
        //先填充外围
        int i;
        int begin = offset;
        int end = offset + size -1;
        for (i = 0;i < size - 1;i++)
        {
            matrix[begin + i][end] = num + i + (size - 1) * DOWN;
            matrix[end ][end- i] = num + i + (size-1) * LEFT;
            matrix[end - i][begin ] = num + i + (size - 1) * UP;
            matrix[begin][begin+i] = num + i + (size - 1) * RIGHT;
        }
        //再递归填充内核(小了一圈的子矩阵)
        FillMatrix(matrix, size - 2, num +4*(size-1), offset + 1);
    }
    
    void NxNfill_nNum(int N) 
    {
        int flag = 0;
        int i =N, j = N;
        int nNUM[MAXNUM][MAXNUM] = {0};
        //memset(nNUM, 0, sizeof(nNUM));
        FillMatrix(nNUM, N, 1, 0);
        cout.setf(std::ios::left);
        for (size_t i = 0; i < N; i++)
        {
           for (size_t j = 0; j < N; j++)
            {
              cout << nNUM[i][j] << "  ";
            }cout << endl;
         }
    }
    
    
    int main()
    {
        int i = 0;
        //cout << "please enter a num to start:" << endl;
        while (cin >> i)
        {
            NxNfill_nNum(i);
        }
       
    }

## 测试结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODY4MTA4_size_16_color_FFFFFF_t_70][]

[Center]: /images/20230312/7428d01c99ca44d697b9d8c1fa1275cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODY4MTA4_size_16_color_FFFFFF_t_70]: /images/20230312/fcdf559ea1fa4441814e4bd7215e2596.png