🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1084
🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁~
🍓OJ题目截图
文章目录
- 📎在线评测链接
- 🍓OJ题目截图
- ⏰ 螺旋矩阵填数
- 问题描述
- 输入格式
- 输出格式
- 样例输入 1
- 样例输出 1
- 样例解释 1
- 样例输入 2
- 样例输出 2
- 数据范围
- 题解
- 参考代码
⏰ 螺旋矩阵填数
问题描述
LYA 小姐最近在家无聊时发明了一种填数游戏。给定一个矩阵的行数 m m m 和需要填入的数字个数 n n n,从矩阵的左上角开始,按顺时针螺旋的方式依次填入从 1 1 1 开始的连续正整数。矩阵需要满足以下要求:
- 每行数字的个数相同。
- 列数尽可能少。
- 优先填充矩阵的外圈。
- 如果数字不够填充完整个矩阵,则使用单个星号
*
占位。
输入格式
输入为一行,包含两个用空格分隔的正整数 n n n 和 m m m,分别表示需要填入的数字个数和矩阵的行数。
输出格式
输出为一个矩阵,每行元素之间用单个空格分隔,最后一行无多余空格。
样例输入 1
9 4
样例输出 1
1 2 3
* * 4
9 * 5
8 7 6
样例解释 1
给定 9 9 9 个数字和 4 4 4 行,按要求填充矩阵。
样例输入 2
3 5
样例输出 2
1
2
3
*
*
数据范围
- 1 ≤ n , m ≤ 999 1 \le n, m \le 999 1≤n,m≤999
题解
我们可以使用一个二维数组来模拟矩阵,初始时将所有元素填充为 *
。然后从左上角开始,按顺时针螺旋的方式依次填入数字。当遇到边界或已填充的元素时,改变方向继续填充。填充完成后,输出矩阵即可。
参考代码
- Python
def soln(n, m):matrix = [['*' for _ in range(max((n - 1) // m + 1, 1))] for _ in range(m)]dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]x, y, d = 0, 0, 0for 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 >= len(matrix[0]) or matrix[nx][ny] != '*':d = (d + 1) % 4nx, ny = x + dx[d], y + dy[d]x, y = nx, nyreturn [' '.join(row) for row in matrix]n, m = map(int, input().split())
print('\n'.join(soln(n, m)))
- Java
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int cols = Math.max((n - 1) / m + 1, 1);String[][] matrix = new String[m][cols];for (String[] row : matrix) {Arrays.fill(row, "*");}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++) {matrix[x][y] = Integer.toString(i);int nx = x + dx[d], ny = y + dy[d];if (nx < 0 || nx >= m || ny < 0 || ny >= cols || !"*".equals(matrix[nx][ny])) {d = (d + 1) % 4;nx = x + dx[d];ny = y + dy[d];}x = nx;y = ny;}for (String[] row : matrix) {System.out.println(String.join(" ", row));}}
}
- Cpp
#include <iostream>
#include <vector>
#include <string>using namespace std;vector<string> soln(int n, int m) {vector<vector<string>> matrix(m, vector<string>(max((n - 1) / m + 1, 1), "*"));int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};int x = 0, y = 0, d = 0;for (int i = 1; i <= n; i++) {matrix[x][y] = to_string(i);int nx = x + dx[d], ny = y + dy[d];if (nx < 0 || nx >= m || ny < 0 || ny >= matrix[0].size() || matrix[nx][ny] != "*") {d = (d + 1) % 4;nx = x + dx[d];ny = y + dy[d];}x = nx;y = ny;}vector<string> result;for (const auto& row : matrix) {string line;for (const auto& elem : row) {line += elem + " ";}line.pop_back();result.push_back(line);}return result;
}int main() {int n, m;cin >> n >> m;vector<string> result = soln(n, m);for (const auto& line : result) {cout << line << endl;}return 0;
}