算法随笔

2025-03-13 | 阅读：次

n阶螺旋矩阵

输入描述：输入包含多个测试用例，每个测试用例为一行，包含一个正整数n(1≤n≤50)，以输入0表示结束。

输出描述：每个测试用例输出n行，每行包括n个整数，整数之间用一个空格分隔。【注意：每行末尾的整数后没有空格】

输入样例： 4 0

输出样例： 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7

输出分析

输出了n行n列数字

如果考虑一行一行顺序来输出，就跟数字的排放逻辑冲突。

所以需要先把数据全部求出，再输出，也就是用一个二维的n x n数组将所有数据存储

n(1≤n≤50)

int a[52][52] = {0}

一共有n * n个数字，也就是说至少需要循环n * n次来完成数字的填入，第一次填的数字是1，第二次填的数字是2 ，第n次填入的数字就是n；

int i = 0, j = 0 ;
for(int k = 1; k <= n ; ++k ){
    a[i][j] = k;
    //处理i,j;
}

接下来就要考虑怎么处理索引了

第一行是从左到右 i+0 , j+1

接下来是从上到下 i+1 ,j+0

接下来是从右到左i+0 ，j-1

接下来是从下到上i-1 ，j+0

…

开始循环，也就是我们可以把这四个方向定义为索引的偏移量

(0,1);//RIGHT
(1,0);//DOWN
(0,-1);//LEFT
(-1,0);//UP

从头开始模拟情景

从(0 , 0)出发，一直向右，什么时候会改变方向？到达边界的时候，方向变为向下

一直向下，到达边界的时候改变方向为左，

一直向左，到达边界的时候改变方向为向上，

但是还没到达边界的时候就需要改变方向了，因为这个时候边界位置已经有数字了，所以需要提前改变方向

if(i j 越界 || next == 0 ) changedir();

假如n =4 ，当移动到第一行最后一个位置 i =3时j = 0，填入数字；

此时i + 1 > 3 说明下一个位置越界了，i+1 > n-1

if(i + 1> n-1 || j+1 > n-1 || i-1 < 0 || j-1 < 0 || next == 0) changdir();

next指的是下一个位置的数字，如果还没填入就是0，如果填入了就不是0

而下个位置的索引就是当前位置加上方向偏移量

next = a[i+DIR.x][j+DIR.y];

可以定义一个结构体来存储DIR,然后我们需要一个索引d 来确定我们当前使用哪个方向

struct Direction{
    int x;
    int y;
}DIR[4] = {{0,1},{1,0},{0,-1},{-1,0}}
int d = 0;

使用方式

next = a[i+DIR[d].x][j+DIR[d].y];

当changedir的时候只需要将索引d ++即可，注意方向会循环，也就是说当d = 3的时候下一个方向应该是d = 0 可以取模mod 4来完成循环

void ChangeDir(){
    d = (d+1) % 4;
}

回到最开始的地方。

#include<bits/stdc++.h>
using namespace std;
struct Direction{
    int x, y;
}DIR[4] = {{0, 1},
           {1, 0},
           {0, -1},
           {-1, 0}}; // 定义方向数组
int d = 0;// 定义当前方向
int x = 0, y = 0;//定义当前坐标
int n = 0;// 定义矩阵大小
int a[52][52] = {0};// 定义矩阵

bool IsNeededChangeDir(int i, int j){
    int ni = i + DIR[d].x;
    int nj = j + DIR[d].y;
    // 检查下一个位置是否越界或已被填充
    return ni < 0 || ni >= n || nj < 0 || nj >= n || a[ni][nj] != 0;
}

void ChangeDir(){
    // 直接修改全局变量d
    d = (d+1) % 4;
}

void move(int &i, int &j){
    i += DIR[d].x;
    j += DIR[d].y;
}

int main(){
    while(cin >> n && n!=0){
        // 循环n*n次，填充整个矩阵
        for(int k = 1; k <= n*n; ++k){
            //填入数字
            a[x][y] = k;

            // 先判断下一个位置是否需要改变方向
            if(IsNeededChangeDir(x,y)){
                ChangeDir();
            }

            // 移动到下一个位置
            move(x,y);
        }

        // 输出结果矩阵
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cout << a[i][j] << (j==n-1? "" : " ");
            }
			cout << endl;
        }
        // 重置矩阵
        memset(a, 0, sizeof(a));
		//重置方向
		d = 0 ;
		//重置坐标
		x = 0, y = 0;
    }
    return 0;
}

Wdream

算法随笔

目录

n阶螺旋矩阵

输出分析

Comments