蛇形矩陣問題

題目描述

小明玩一個數字遊戲，取個n行n列數字矩陣（其中n為不超過100的奇數），數字的填補方法為：在矩陣中心從1開始以逆時針方向繞行，逐圈擴大，直到n行n列填滿數字，請輸出該n行n列正方形矩陣以及其的對角線數字之和.

解答

使用分治算法, 如果給出蛇形矩陣 n * n 的前 m - 1層填充結果, 按照定義很容易填充第 m 層, 進而可以得到整個蛇形矩陣的填充圖.

代碼:

#include <iostream>
using namespace std;

void arrInsert(int **arr, int n, int m);
int main() {
    int n;
    cin >> n;
    /*動态生成二維數組*/
    int **arr;
    arr = new int *[n];
    for(int i = ; i < n; ++i) {
        arr[i] = new int[n];
    }
    for (int i = ; i < n; ++i) {
        for (int j = ; j < n; ++j) {
            arr[i][j] = ;
        }
    }

    /*填充矩陣*/
    if(n % ) { //奇數
        arrInsert(arr, n, n / ); //填充 n * n矩陣的 n / 2層
    }
    /*顯示結果*/
    int sum = ; //儲存對角線的和
    for (int i = ; i < n; ++i) {
        for (int j = ; j < n; ++j) {
            cout << arr[i][j] << " ";
            if (i == j ) { //對角線
                sum += arr[i][j];
            }
            else if(j - n /  == n /  - i) { //反對角線
                sum += arr[i][j];
            }
        }
        cout << endl;  
    }
    cout << sum << endl;

    /*釋放記憶體*/
    for(int i = ; i < n; ++i) {
        delete[] arr[i];
    }
    delete[] arr;
    return ;
}

void arrInsert(int **arr, int n, int m) {
    int mid = n / ;
    if(m == ) {
        arr[mid][mid] = ;
    }
    else {
        arrInsert(arr, n, m - ); //填充裡面的 m - 1層
        arr[mid + m - ][mid + m] = arr[mid + m - ][mid + m - ] + ;
        for (int i = mid + m - ; i >= mid - m; --i) {
            arr[i][mid + m] = arr[i + ][mid + m] + ;
        }
        for (int j = mid + m - ; j >= mid - m; --j) {
            arr[mid - m][j] = arr[mid - m][j + ] + ;
        }
        for (int i = mid - m + ; i <= mid + m; ++i) {
            arr[i][mid - m] = arr[i - ][mid - m] + ;
        }
        for (int j = mid - m + ; j <= mid + m; ++j) {
            arr[mid + m][j] = arr[mid + m][j - ] + ;
        }
    }
}