C++で行列を反スパイラル形式（逆渦巻き順）に出力する方法

はじめに

n×n の2次元配列が与えられたとき、その行列を「反スパイラル形式」で出力することが本記事の課題です。反スパイラル出力とは、通常のスパイラル（渦巻き）順とは逆の順序で要素を取り出すことを指します。

例として、以下の4×4の行列を考えてみましょう。

Input : arr[4][4]={1,2,3,4,
    5,6,7,8,
    9,10,11,12
    13,14,15,16}
Output: 10 11 7 6 5 9 13 14 15 16 12 8 4 3 2 1

この問題はスタックを使うことで効率的に解けます。仕組みはシンプルで、まず行列の要素をスパイラル順にスタックへプッシュしていき、その後すべての要素をポップすると、LIFO（後入れ先出し）の性質により自然と反スパイラル順の出力が得られます。

アルゴリズム

START
STEP 1 -> スタック stk を宣言し、変数 r=4, c=4, i, j, rs=0, cs=0 を用意する
Step 2 -> 行列の要素を2次元配列に格納する
Step 3 -> ループ: i=0 から i<4 まで i++
    内側ループ: j=0 から j<4 まで j++
       arr[i][j] を表示
    改行を表示
Step 4 -> rs<c かつ cs<r の間ループ
    ループ: i=rs から i<c まで i++
       arr[rs][i] をプッシュ
    cs++
    ループ: i=cs から i<r-1 まで ++i
       arr[i][c-1] をプッシュ
    c--
    IF(cs<r)
       ループ: i=r-1 から i>=rs まで --i
          arr[r-1][i] をプッシュ
       r--
    IF(rs<c)
       ループ: i=c-1 から i>=cs まで i--
          arr[i][rs] をプッシュ
       rs++
Step 5 -> スタックが空になるまでループ
    stk.top() を表示
    pop() を呼び出す
STOP

実装例

以下は上記のアルゴリズムをC++で実装したコードです。

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
    stack <int> stk;
    int R=4,C=4,i,j,RS=0,CS=0;
    int mat[R][C] = { {1,2,3, 4}, {5,6,7,8},{9,10,11,12},{13,14,15,16}};
    for(i=0;i<4;i++){
        for(j=0;j<4;j++)
            cout<<mat[i][j]<<" ";
        cout<<"\n";
    }
    while(RS<C&&CS<R) {
        for(i=RS;i<C;i++)
            stk.push(mat[RS][i]);
        CS++;
        for(i=CS;i<R-1;++i)
            stk.push(mat[i][C-1]);
        C--;
    if(CS<R){
        for(i=R-1;i>=RS;--i)
            stk.push(mat[R-1][i]);
        R--;
    }
    if(RS<C){
        for(i=C-1;i>=CS;i--)
            stk.push(mat[i][RS]);
        RS++;
    }
}
while(!stk.empty()){
    cout<<stk.top()<<" ";
    stk.pop();
}

出力結果

上記のプログラムを実行すると、次のような出力が得られます。

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

処理のポイント

このアルゴリズムでは、外側の行・右側の列・内側の行・左側の列という順番で境界を内側へ縮めながら（rs、cs を増やし、r、c を減らしながら）要素をスタックに積んでいきます。最後にスタックから全要素を取り出すことで、渦巻きの中心から外側へ向かう「反スパイラル」の順序が出力される仕組みです。