刷题笔记合集🔗

螺旋数字矩阵

问题描述

LYA 小姐最近在家无聊时发明了一种填数游戏。给定一个矩阵的行数 和需要填入的数字个数 ,从矩阵的左上角开始,按顺时针螺旋的方式依次填入从 开始的连续正整数。矩阵需要满足以下要求:

1. 每行数字的个数相同。
2. 列数尽可能少。
3. 优先填充矩阵的外圈。
4. 如果数字不够填充完整个矩阵,则使用单个星号 * 占位。

输入格式

输入为一行,包含两个用空格分隔的正整数 和 ,分别表示需要填入的数字个数和矩阵的行数。

输出格式

输出为一个矩阵,每行元素之间用单个空格分隔,最后一行无多余空格。

样例输入 1

9 4

样例输出 1

1 2 3 
* * 4
9 * 5
8 7 6

样例解释 1

给定 个数字和 行,按要求填充矩阵。

样例输入 2

3 5

样例输出 2

1
2 
3
*
*

数据范围

题解

模拟

我们可以使用一个二维数组来模拟矩阵,初始时将所有元素填充为 *。然后从左上角开始,按顺时针螺旋的方式依次填入数字。当遇到边界或已填充的元素时,改变方向继续填充。填充完成后,输出矩阵即可。

参考代码

• Python

def soln(n, m):
    # 计算矩阵的列数，至少为1
    cols = max((n - 1) // m + 1, 1)
    # 创建一个 m x cols 的矩阵，初始化为 '*'
    matrix = [['*' for _ in range(cols)] for _ in range(m)]
    
    # 定义四个方向：右、下、左、上
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    x, y, d = 0, 0, 0  # 初始位置和方向
    
    # 填充数字
    for i in range(1, n + 1):
        matrix[x][y] = str(i)  # 填入当前数字
        # 计算下一个位置
        nx, ny = x + dx[d], y + dy[d]
        # 如果下一个位置越界或已被填充，则改变方向
        if nx < 0 or nx >= m or ny < 0 or ny >= cols or matrix[nx][ny] != '*':
            d = (d + 1) % 4  # 顺时针旋转方向
            nx, ny = x + dx[d], y + dy[d]
        x, y = nx, ny  # 移动到下一个位置
    
    # 将矩阵转换为字符串列表
    return [' '.join(row) for row in matrix]

# 读取输入
n, m = map(int, input().split())
# 计算并打印结果
print('\n'.join(soln(n, m)))

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000

void soln(int n, int m) {
    // 计算矩阵的列数，至少为1
    int cols = (n - 1) / m + 1;
    if (cols < 1) cols = 1;

    // 创建矩阵并初始化为 '*'
    char matrix[MAX_SIZE][MAX_SIZE];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < cols; j++) {
            matrix[i][j] = '*';
        }
    }

    // 定义四个方向：右、下、左、上
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};
    int x = 0, y = 0, d = 0;  // 初始位置和方向

    // 填充数字
    for (int i = 1; i <= n; i++) {
        char num[5];
        sprintf(num, "%d", i);
        strcpy(&matrix[x][y], num);  // 填入当前数字

        // 计算下一个位置
        int nx = x + dx[d], ny = y + dy[d];
        // 如果下一个位置越界或已被填充，则改变方向
        if (nx < 0 || nx >= m || ny < 0 || ny >= cols || matrix[nx][ny] != '*') {
            d = (d + 1) % 4;  // 顺时针旋转方向
            nx = x + dx[d];
            ny = y + dy[d];
        }
        x = nx;
        y = ny;  // 移动到下一个位置
    }

    // 打印矩阵
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < cols; j++) {
            printf("%s", &matrix[i][j]);
            if (j < cols - 1) printf(" ");
        }
        printf("\n");
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    soln(n, m);
    return 0;
}

• Ja