[蓝桥杯]上三角方阵

上三角方阵

题目描述

方阵的主对角线之上称为"上三角"。

请你设计一个用于填充 nn 阶方阵的上三角区域的程序。填充的规则是：使用 1，2，3.... 的自然数列，从左上角开始，按照顺时针方向螺旋填充。

例如：当 n=3n=3 时，输出：

1 2 3

6 4

5

当 n=4n=4 时，输出：

1 2 3 4

9 10 5

8 6

7

当 n=5n=5 时，输出：

1 2 3 4 5

12 13 14 6

11 15 7

10 8

9

输入描述

要求用户输入整数 n （3≤n≤20）n （3≤n≤20）。

输出描述

输出方阵的上三角部分。

要求每个数据宽度为 4，右对齐。

输入输出样例

示例

输入

9

输出

1 2 3 4 5 6 7 8 9
24 25 26 27 28 29 30 10
23 39 40 41 42 31 11
22 38 45 43 32 12
21 37 44 33 13
20 36 34 14
19 35 15
18 16
17

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 832  |  总提交次数: 900  |  通过率: 92.4%

难度: 中等   标签: 2011, 模拟, 省赛

问题分析

题目要求设计一个程序，用自然数1, 2, 3,... 按顺时针螺旋顺序填充n阶方阵的上三角区域。上三角区域定义为方阵主对角线（含）以上的部分。填充后需按特定格式输出：每行数据宽度为4，右对齐，且输出为锯齿状矩阵（第i行有n-i个元素）。

算法思路

1. ​​路径模拟​​：

   • 使用​​方向数组​​控制螺旋路径：右 (0,1) → 左下 (1,-1) → 上 (-1,0)
   • 从(0,0)开始，按优先级选择方向：先尝试当前方向，若无效则按右→左下→上顺序切换
   • 位置(r,c)有效条件：
     • 在矩阵范围内：0 ≤ r,c < n
     • 在上三角区域内：c ≤ n - r - 1
     • 目标位置未被填充

2. ​​填充过程​​：

   • 计算总元素数：T = n(n+1)/2
   • 初始化n×n矩阵，所有元素为0
   • 从k=1到T，依次填充数字：
     1. 将当前值k赋给矩阵位置(r,c)
     2. 尝试三种方向，找到第一个有效移动位置
     3. 更新坐标(r,c)和当前方向

3. ​​输出格式​​：

   • 按锯齿状输出：第i行输出前n-i个元素
   • 每个元素占4字符宽度，右对齐（C++中setw(4)）

     #include <iostream>
     #include <vector>
     #include <iomanip>
     using namespace std;
     
     int main() {
         int n;
         cin >> n;
         int T = n * (n + 1) / 2;  // 上三角区域总元素数
         vector<vector<int>> a(n, vector<int>(n, 0));  // 初始化n×n矩阵
     
         // 方向数组：右(0,1) -> 左下(1,-1) -> 上(-1,0)
         int dr[3] = {0, 1, -1};
         int dc[3] = {1, -1, 0};
         
         int r = 0, c = 0;          // 起始位置(0,0)
         int current_dir = 0;        // 初始方向：右
     
         for (int k = 1; k <= T; ++k) {
             a[r][c] = k;           // 填充当前值
             if (k == T) break;     // 填充完成
     
             bool found = false;
             for (int i = 0; i < 3; ++i) {
                 int nd = (current_dir + i) % 3;  // 尝试方向优先级：当前→下一→下下
                 int nr = r + dr[nd];
                 int nc = c + dc[nd];
                 
                 // 检查新位置是否有效
                 if (nr >= 0 && nr < n && nc >= 0 && nc < n && 
                     nc <= n - nr - 1 && a[nr][nc] == 0) {
                     r = nr;
                     c = nc;
                     current_dir = nd;  // 更新方向
                     found = true;
                     break;
                 }
             }
             if (!found) break;  // 无有效位置（理论上不会发生）
         }
     
         // 输出锯齿状上三角矩阵
         for (int i = 0; i < n; ++i) {
             for (int j = 0; j < n - i; ++j) {
                 cout << setw(4) << a[i][j];
             }
             cout << endl;
         }
         return 0;
     }

     关键步骤说明

   • ​​方向控制​​：

     • ​​右移​​：列坐标+1，用于填充当前行
     • ​​左下移​​：行坐标+1且列坐标-1，用于斜向填充
     • ​​上移​​：行坐标-1，用于填充左侧列
     • 方向切换确保路径始终顺时针螺旋

   • ​​边界检查​​：

     • 矩阵边界：0 ≤ r,c < n
     • 上三角边界：c ≤ n - r - 1（确保不越出上三角区域）
     • 已填充检查：目标位置值为0

   • ​​复杂度分析​​：

     • ​​时间复杂度​​：O(n²)，需填充n(n+1)/2个元素
     • ​​空间复杂度​​：O(n²)，存储n×n矩阵
     • 满足运行限制（n≤20时，计算量远低于1s）

   • 示例验证

     ​​输入n=3​​：

        1   2   3
        6   4
        5

     ​​路径轨迹​​：

   • (0,0)→(0,1)→(0,2) // 右移填充顶边
   • (1,1)→(2,0) // 左下移填充斜边
   • (1,0) // 上移填充左边

   • ​​输入n=4​​：

        1   2   3   4
        9  10   5
        8   6
        7

     路径轨迹​​：

   • (0,0)→(0,1)→(0,2)→(0,3) // 右移
   • (1,2)→(2,1)→(3,0) // 左下移
   • (2,0)→(1,0) // 上移
   • (1,1) // 右移