Ural 319：矩陣填數輸出格式處理

題目大意

給定 n，構造 n×n 矩陣，按特定對角線順序填入 1~n²，輸出矩陣。具體規律：從右上角向左下、從左下向右上交替填充。

構造算法

1. 先處理右上半部（含主對角線）：對每條從 (1, k) 到 (k, 1) 的對角線（k = n..1），按行遞增填入遞增數字。
2. 再處理左下半部（不含主對角線）：對每條從 (n, k) 到 (k, n) 的對角線（k = 1..n-1），按行遞減填入遞減數字（從 n² 往下）。

代碼實現

#include <bits/stdc++.h>
using namespace std;

int g[101][101];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while (cin >> n) {
        int key = 1;
        // 右上半部：從右上向左下
        for (int k = n; k >= 1; --k) {
            int i = 1, j = k;
            g[i][j] = key++;
            while (i + 1 <= n && j + 1 <= n) {
                ++i; ++j;
                g[i][j] = key++;
            }
        }
        // 左下半部：從左下向右上
        key = n * n;
        for (int k = 1; k <= n - 1; ++k) {
            int i = n, j = k;
            g[i][j] = key--;
            while (i - 1 >= 1 && j - 1 >= 1) {
                --i; --j;
                g[i][j] = key--;
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j > 1) cout << ' ';
                cout << g[i][j];
            }
            cout << '\n';
        }
    }
    return 0;
}

輸出範例（n=4）

1  2  6  7
3  5  8 13
4  9 12 14
10 11 15 16

複雜度

• 時間：O(n²)
• 空間：O(n²)

本題重點在於觀察填數規律並正確實現雙向對角線遍歷，輸出格式需注意行末無多餘空格。