マトリックスを螺旋状（スパイラル）に出力するアルゴリズム

このアルゴリズムは、2次元配列（マトリックス）の要素を螺旋状（スパイラル形式）に出力するために用いられます。処理の流れは以下の通りです。

まず最初の行を左から右へすべて出力し、続いて最後の列を上から下へ、次に最後の行を右から左へ、さらに最初の列を下から上へと出力します。この一連の操作を内側に向かって繰り返すことで、要素が渦巻き状に順番に出力されます。

このアルゴリズムの時間計算量は O(MN) です。ここで M は行数、N は列数を表します。

入力と出力

Input:
The matrix:
 1   2   3   4   5   6
 7   8   9  10  11  12
13  14  15  16  17  18

Output:
Contents of an array as the spiral form
1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 15 16

アルゴリズム

dispSpiral(mat, m, n)

入力：マトリックス mat、行数 m、列数 n。

出力：マトリックスの全要素を螺旋状の順序で出力する。

Begin
    currRow := 0 かつ currCol := 0
    while currRow と currCol がマトリックスの範囲内である間、繰り返す
        for i を currCol から n-1 まで、繰り返す
            display mat[currRow, i]
        done

        currRow を 1 増やす
        for i を currRow から m-1 まで、繰り返す
            display mat[i, n-1]
        done

        n を 1 減らす
        if currRow < m ならば
            for i := n-1 から currCol まで減少させながら、繰り返す
                display mat[m-1, i]
            done
            m を 1 減らす
        if currCol < n ならば
            for i := m-1 から currRow まで減少させながら、繰り返す
                display mat[i, currCol]
            done
            currCol を 1 増やす
    done
End

アルゴリズムのポイント

• currRow / currCol：現在の出力対象となっている外周の開始位置（行・列）を管理します。
• m / n の更新：各行・各列を出力し終えるたびに範囲を狭めていくことで、すでに出力済みの外側の要素を二度と参照しないようにしています。
• 範囲チェック：最後の行や最初の列を出力する前に条件判定を行うことで、1行のみ・1列のみの残りマトリックスでも重複出力を防ぎます。

C++による実装例

#include <iostream>
#define ROW 3
#define COL 6
using namespace std;

int array[ROW][COL] = {
    {1, 2, 3, 4, 5, 6},
    {7, 8, 9, 10, 11, 12},
    {13, 14, 15, 16, 17, 18}
};

void dispSpiral(int m, int n) {
    int i, currRow = 0, currCol = 0;
    while (currRow < ROW && currCol < COL) {
        for (i = currCol; i < n; i++) {          //最初の行をそのまま出力
            cout << array[currRow][i] << " ";
        }
        currRow++;                                //次の行へ移動

        for (i = currRow; i < m; ++i) {           //最後の列を出力
            cout << array[i][n-1] << " ";
        }

        n--;                                      //n-1列目を新たな最終列として設定

        if (currRow < m) {                        //currRowが範囲内なら最後の行を出力
            for (i = n-1; i >= currCol; --i) {
                cout << array[m-1][i] << " ";
            }
            m--;                                  //行の範囲を縮小
        }

        if (currCol < n) {                        //currColが範囲内なら最初の列を出力
            for (i = m-1; i >= currRow; --i) {
                cout << array[i][currCol] << " ";
            }
            currCol++;                            //列の開始位置を進める
        }
    }
}

int main() {
    dispSpiral(ROW, COL);
}

実行結果

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

このように、3×6 のマトリックスの要素が、外周から内側へ向かって螺旋状に正しく出力されていることが確認できます。