C++で指定した点から始まる螺旋形式の行列出力アルゴリズム

問題概要

この問題では、2次元行列と1つの点 P(c, r) が与えられます。求められているのは、指定された点 P を起点として、行列のすべての要素を反時計回りの螺旋(スパイラル)形式で出力することです。

問題の例

具体例を見ながら、問題を理解しましょう。

入力:
matrix[][] = {{1, 4, 7},
              {2, 5, 8},
              {3, 6, 9}}
開始点: P(2, 0) ※(列, 行)

出力:
7 8 5 4 9 6 3 2 1

開始点の要素「7」から始まり、反時計回りに「8 → 5 → 4 → 9 → 6 → 3 → 2 → 1」の順ですべての要素をたどります。

解決アプローチ

この問題は、4つのループを使うことで解決できます。各ループがそれぞれ担当する方向(右・下・左・上)の要素を出力し、開始点から螺旋を描くように範囲を広げていきます。

アルゴリズムの手順は以下の通りです。

• 開始点を基準に、螺旋の上下左右の境界(行と列の上限・下限)を初期化する
• ループ1:上の行を左から右へ出力
• ループ2:右の列を上から下へ出力
• ループ3:下の行を右から左へ出力
• ループ4:左の列を下から上へ出力
• 1周出力するごとに境界を外側へ拡張し、すべての要素を出力し終えるまで繰り返す

実装例

上記の解決策をC++で実装したプログラムを以下に示します。

#include <iostream>
using namespace std;
const int MAX = 100;

void printSpiralMatrix(int mat[][MAX], int r, int c) {
    int i, a = 0, b = 2;
    int low_row = (0 > a) ? 0 : a;
    int low_column = (0 > b) ? 0 : b - 1;
    int high_row = ((a + 1) >= r) ? r - 1 : a + 1;
    int high_column = ((b + 1) >= c) ? c - 1 : b + 1;
    while ((low_row > 0 - r && low_column > 0 - c)) {
        for (i = low_column + 1; i <= high_column && i < c && low_row >= 0; ++i)
            cout << mat[low_row][i] << " ";
        low_row -= 1;
        for (i = low_row + 2; i <= high_row && i < r && high_column < c; ++i)
            cout << mat[i][high_column] << " ";
        high_column += 1;
        for (i = high_column - 2; i >= low_column && i >= 0 && high_row < r; --i)
            cout << mat[high_row][i] << " ";
        high_row += 1;
        for (i = high_row - 2; i > low_row && i >= 0 && low_column >= 0; --i)
            cout << mat[i][low_column] << " ";
        low_column -= 1;
    }
    cout << endl;
}

int main() {
    int mat[][MAX] = {
        { 1, 4, 7 },
        { 2, 5, 8 },
        { 3, 6, 9 }
    };
    int r = 3, c = 3;
    cout << "Spiral traversal of matrix starting from point " << r << ", " << c << " is :\n";
    printSpiralMatrix(mat, r, c);
}

出力結果

Spiral traversal of matrix starting from point 3, 3 is :
7 8 5 4 9 6 3 2 1

コードの解説

このプログラムでは、変数 a と b が螺旋の開始位置(行・列のインデックス)を表しています。また、low_row、low_column、high_row、high_column の4つの変数が、現在の螺旋の境界範囲を管理します。

while ループ内の4つの for ループが、それぞれ右方向・下方向・左方向・上方向の要素を順に出力します。1周の出力が完了するたびに境界を外側へ1つずつ拡張していくことで、行列全体を螺旋状にたどることができます。

さらに、各ループには i < c や low_row >= 0 のような範囲チェックが組み込まれているため、開始点が行列の端や角にある場合、また行列が正方形以外の長方形である場合でも、範囲外アクセスを避けながら正しく動作するようになっています。