C++で与えられた2次元行列を逆スパイラル形式で出力する方法

この記事では、2次元行列が与えられたときに、そのすべての要素を逆スパイラル形式で出力する方法を解説します。C++での実装例とともに、アルゴリズムの考え方をわかりやすく説明していきます。

問題の例

まず、具体的な入力と出力の例を見てみましょう。

入力:
    12 23 54 67
    76 90 01 51
    43 18 49 5
    31 91 75 9
出力: 18 49 1 90 76 43 31 91 75 9 5 51 67 54 23 12

アルゴリズムの考え方

逆スパイラル形式とは、行列の中心からスタートして、渦巻きの逆順に沿って要素を外側へ向かって出力していく形式です。

実装の流れは以下の通りです。まず、通常のスパイラル順（左→右、上→下、右→左、下→上）で行列を一周ずつ走査し、訪れた要素を補助配列に順番に格納します。このとき、4つのループを組み合わせて各層（外周）を処理し、走査範囲を徐々に内側へ狭めていきます。最後に、補助配列を末尾から先頭へ向かって出力することで、結果として中心から始まる逆スパイラル順の出力が得られます。

C++による実装例

以下は、このアルゴリズムを実装したC++プログラムです。

#include <iostream>
#define R 3
#define C 6
using namespace std;
void printReverseSpiral(int m, int n, int a[R][C]) {
    long int b[100];
    int i, k = 0, l = 0;
    int z = 0;
    int size = m*n;
    while (k < m && l < n) {
        int val;
        for (i = l; i < n; ++i){
            val = a[k][i];
            b[z] = val;
            ++z;
        }
        k++;
        for (i = k; i < m; ++i){
            val = a[i][n-1];
            b[z] = val;
            ++z;
        }
        n--;
        if (k < m){
            for (i = n-1; i >= l; --i){
                val = a[m-1][i];
                b[z] = val;
                ++z;
            }
            m--;
        }
        if (l < n){
            for (i = m-1; i >= k; --i){
                val = a[i][l];
                b[z] = val;
                ++z;
            }
            l++;
        }
    }
    for (int i = size-1; i >= 0; --i){
        cout<<b[i]<<" ";
    }
}
int main() {
    int mat[R][C] = {
        {34, 5, 6, 98, 12, 23},
        {9, 12, 56, 87, 99, 1},
        {13, 91, 50, 8, 21, 2}
    };
    cout<<"Printing reverse Spiral of the matrix :\n";
    printReverseSpiral(R, C, mat);
    return 0;
}

実行結果

Printing reverse Spiral of the matrix :
99 87 56 12 9 13 91 50 8 21 2 1 23 12 98 6 5 34

計算量について

このアルゴリズムは行列の全要素を一度ずつ走査するため、時間計算量は O(m×n) となります。また、要素を一時的に保存するための補助配列が必要なため、空間計算量も O(m×n) です。行列のサイズが大きくなっても線形時間で処理できる、効率的なアプローチと言えます。