(C卷,100分)- 螺旋数字矩阵（Java & JS & Python & C）

题目描述

疫情期间，小明隔离在家，百无聊赖，在纸上写数字玩。他发明了一种写法：

给出数字个数 n （0 < n ≤ 999）和行数 m（0 < m ≤ 999），从左上角的 1 开始，按照顺时针螺旋向内写方式，依次写出2,3,….,n，最终形成一个 m 行矩阵。

小明对这个矩阵有些要求：

1. 每行数字的个数一样多
2. 列的数量尽可能少
3. 填充数字时优先填充外部
4. 数字不够时，使用单个 * 号占位

输入描述

两个整数，空格隔开，依次表示 n、m

输出描述

符合要求的唯一矩阵

用例

题目解析

本题需要我们将1~n数字按照螺旋顺序填入矩阵。

本题只给出了矩阵的行数m，没有给列数，需要我们求解一个最少的列数来满足矩阵能够填入n个数字，因此列数 k = ceil(n / m)，这里的除法不是整除，并且要对除法的结果向上取整。

将数字1~n按照螺旋顺序，从矩阵matrix左上角开始填入，比较考察思维能力，具体实现如下：

• 定义变量step，初始step=1，表示当前要填入的数字，因此step ≤ n
• 定义变量x，y，初始x=0, y=0，表示要填值得矩阵位置，即初始时从矩阵左上角开始填入

然后按照顺序循环进行下面四个填值操作：

1. 正序填入第X行
2. 正序填入第Y列
3. 倒序填入第X行
4. 倒序填入第Y列

具体行为如下：

正序填入第x行

初始时，X,Y处于下面位置

按照螺旋顺序，我们应该正序填第X行，即此时行号X不变，列号Y++，具体操作是：

matrix[x][y++] = step++

当列号 Y >= k 时停止填值。如下图所示：此时 X = 0，Y = k

正序填入第y列

按照螺旋顺序，下一步我们应该做一次X++, Y–，让填值位置移动到（X,Y）位置

开始正序填第Y列，即此时列号Y保持不变，行号X++，具体操作是：

matrix[x++][y] = step++

当行号X >= m 时停止填值。如下图所示：此时X=n，Y = k – 1

倒序填入第x行

按照螺旋顺序，下一步我们应该做一次X–, Y–，让填值位置移动到（X,Y）位置

开始倒序填第X行，即此时行号X保持不变，列号Y–，具体操作是：

matrix[x][y–] = step++

当行号Y < 0 时停止填值。如下图所示：此时 X=n-1，Y = -1

倒序填入第y列

按照螺旋顺序，下一步我们应该做一次X–, Y++，让填值位置移动到（X,Y）位置

开始倒序填第Y列，即此时行号X–，列号Y保持不变，具体操作是：

matrix[x–][y] = step++

当行号X < 0 时停止填值。如下图所示：此时 X=-1，Y = 0

但是，此时不符合用例1要求，因为step只需要填到n即可，而用例1的n=9，因此填值过程中，我们需要增加一个判断，即step > n时彻底停止添值，即到下面状态时停止。

假设用例1修改为：

11 4

那么下面状态也是不对的

因为11覆盖掉了该位置添的值1，

因此填值过程如果发现，要添值位置已经有值了，比如下图X–后，发现(X,Y)位置已经填过值了，此时我们应该结束当前方向的添值

按照螺旋顺序，下一个添值位置应该如下图所示：

此时应该基于前一个状态进行X++，Y++，到达上图黄色位置后，此时又回到螺旋顺序的第一步，从第X行开始正序填入。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // n 表示需要在螺旋矩阵中填入 1 ~ n 数字
  // m 是螺旋矩阵行数
  const [n, m] = (await readline()).split(" ").map(Number);

  // k 是螺旋矩阵列数
  const k = Math.ceil(n / m);

  // 螺旋矩阵，未填值位置默认值"*"
  const matrix = new Array(m).fill(0).map(() => new Array(k).fill("*"));

  // 当前要填入的值
  let step = 1;

  // 当前要填入的值的位置
  let x = 0;
  let y = 0;

  // 如果填入的值 > n，则停止填值，否则继续填
  while (step <= n) {
    // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
    while (y < k && matrix[x][y] == "*" && step <= n) matrix[x][y++] = step++;
    // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步
    y -= 1;
    // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列
    x += 1;

    // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
    while (x < m && matrix[x][y] == "*" && step <= n) matrix[x++][y] = step++;
    x -= 1;
    y -= 1;

    // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
    while (y >= 0 && matrix[x][y] == "*" && step <= n) matrix[x][y--] = step++;
    y += 1;
    x -= 1;

    // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
    while (x >= 0 && matrix[x][y] == "*" && step <= n) matrix[x--][y] = step++;
    x += 1;
    y += 1;
  }

  // 打印螺旋矩阵字符串
  for (let i = 0; i < m; i++) {
    console.log(matrix[i].join(" "));
  }
})();

Java算法源码

import java.util.Scanner;
import java.util.StringJoiner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // 需要在螺旋矩阵中填入 1 ~ n 数字
    int n = sc.nextInt();

    // 螺旋矩阵行数
    int m = sc.nextInt();

    // 螺旋矩阵列数
    int k = (int) Math.ceil(n * 1.0 / m);

    // 螺旋矩阵
    int[][] matrix = new int[m][k]; // 由于需要填入1~n数字，因此这里未填值的位置值默认初始化为0

    // 当前要填入的值
    int step = 1;

    // 当前要填入的值的位置
    int x = 0;
    int y = 0;

    // 如果填入的值 > n，则停止填值，否则继续填
    while (step <= n) {
      // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
      while (y < k && matrix[x][y] == 0 && step <= n) matrix[x][y++] = step++;
      // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步
      y -= 1;
      // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列
      x += 1;

      // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
      while (x < m && matrix[x][y] == 0 && step <= n) matrix[x++][y] = step++;
      x -= 1;
      y -= 1;

      // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
      while (y >= 0 && matrix[x][y] == 0 && step <= n) matrix[x][y--] = step++;
      y += 1;
      x -= 1;

      // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
      while (x >= 0 && matrix[x][y] == 0 && step <= n) matrix[x--][y] = step++;
      x += 1;
      y += 1;
    }

    // 打印螺旋矩阵字符串
    for (int i = 0; i < m; i++) {
      StringJoiner row = new StringJoiner(" ");
      for (int j = 0; j < k; j++) {
        if (matrix[i][j] == 0) {
          row.add("*");
        } else {
          row.add(matrix[i][j] + "");
        }
      }
      System.out.println(row);
    }
  }
}

Python算法源码

import math

# 输入获取
# n 表示需要在螺旋矩阵中填入 1 ~ n 数字
# m 表示螺旋矩阵行数
n, m = map(int, input().split())


# 算法入口
def getResult():
    # k是螺旋矩阵列数
    k = int(math.ceil(n / m))

    # 螺旋矩阵
    matrix = [['*'] * k for _ in range(m)]  # 未填值位置默认初始化为*

    # 当前要填入的值
    step = 1

    # 当前要填入的值的位置
    x = 0
    y = 0

    # 如果填入的值 > n，则停止填值，否则继续填
    while step <= n:
        # 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
        while y < k and matrix[x][y] == '*' and step <= n:
            matrix[x][y] = str(step)
            step += 1
            y += 1

        # 正序填完第x行后，y处于末尾越界位置，因此y需要退一步
        y -= 1
        # 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列
        x += 1

        # 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
        while x < m and matrix[x][y] == '*' and step <= n:
            matrix[x][y] = str(step)
            step += 1
            x += 1

        x -= 1
        y -= 1

        # 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
        while y >= 0 and matrix[x][y] == '*' and step <= n:
            matrix[x][y] = str(step)
            step += 1
            y -= 1

        y += 1
        x -= 1

        # 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
        while x >= 0 and matrix[x][y] == '*' and step <= n:
            matrix[x][y] = str(step)
            step += 1
            x -= 1

        x += 1
        y += 1

    # 打印螺旋矩阵字符串
    for i in range(m):
        print(" ".join(matrix[i]))


# 算法调用
getResult()

C算法源码

#include <stdio.h>
#include <math.h>

int main() {
    // n 表示需要在螺旋矩阵中填入 1 ~ n 数字
    // m 表示螺旋矩阵行数
    int n, m;
    scanf("%d %d", &n, &m);

    // k 表示螺旋矩阵列数
    int k = (int) ceil(n * 1.0 / m);

    // 螺旋矩阵
    int matrix[m][k];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < k; j++) {
            matrix[i][j] = 0; // 由于需要填入1~n数字，因此这里未填值的位置值默认初始化为0
        }
    }

    // 当前要填入的值
    int step = 1;

    // 当前要填入的值的位置
    int x = 0;
    int y = 0;

    // 如果填入的值 > n，则停止填值，否则继续填
    while (step <= n) {
        // 正序填入第x行，即：行号不变，列号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
        while (y < k && matrix[x][y] == 0 && step <= n) matrix[x][y++] = step++;
        // 正序填完第x行后，y处于末尾越界位置，因此y需要退一步
        y -= 1;
        // 正序填完第x行来到第x行的末尾，即第y列，按照螺旋矩阵顺序，应该从第x+1行开始正序填值第y列
        x += 1;

        // 正序填入第y列，即：列号不变，行号增加，注意：添值过程不能发生覆盖，也不能填入超过n的值
        while (x < m && matrix[x][y] == 0 && step <= n) matrix[x++][y] = step++;
        x -= 1;
        y -= 1;

        // 倒序填入第x行，即：行号不变，列号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
        while (y >= 0 && matrix[x][y] == 0 && step <= n) matrix[x][y--] = step++;
        y += 1;
        x -= 1;

        // 倒序填入第y列，即：列号不变，行号减少，注意：添值过程不能发生覆盖，也不能填入超过n的值
        while (x >= 0 && matrix[x][y] == 0 && step <= n) matrix[x--][y] = step++;
        x += 1;
        y += 1;
    }

    // 打印螺旋矩阵字符串
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < k; j++) {
            if (matrix[i][j] == 0) {
                printf("*");
            } else {
                printf("%d", matrix[i][j]);
            }

            if (j < k - 1) {
                printf(" ");
            }
        }
        puts("");
    }

    return 0;
}