C++で行列を逆波形（リバースウェーブ）形式で出力する方法

この問題では、行列が与えられ、その行列を逆波形（リバースウェーブ）の順序で1行に出力することが求められます。

問題の概要

具体例を使って問題を確認してみましょう。

入力:
    1 4 6 11
    2 5 8 54
    7 9 3 43
    1 7 4 34
出力: 11 54 43 34 4 3 8 6 4 5 9 7 1 7 2 1

この問題を解くには、行列を逆波形の順序で走査する必要があります。具体的には、まず最後の列の要素を上から下へ出力し、次に後ろから2番目の列の要素を下から上へ出力します。この上下交互の走査を、行列の最初の列に到達するまで繰り返していきます。

アルゴリズムのポイント

• 列を右から左へ走査します（j = n-1 から 0 まで）。
• 1つ目の列では、行を上から下へ（i = 0 から m-1 まで）出力します。
• 2つ目の列では、行を下から上へ（i = m-1 から 0 まで）出力します。
• フラグ変数 wave を使って、出力方向を交互に切り替えます。

実装例

上記の解法を実装したC++プログラムは以下の通りです。

#include<iostream>
using namespace std;
#define R 4
#define C 4
void printReverseWaveForm(int m, int n, int arr[R][C]) {
    int i, j = n - 1, wave = 1;
    while (j >= 0) {
        if (wave == 1) {
            for (i = 0; i < m; i++)
                cout<<arr[i][j]<<" ";
            wave = 0;
            j--;
        } else {
            for (i = m - 1; i >= 0; i--)
                cout<<arr[i][j]<<" ";
            wave = 1;
            j--;
        }
    }
}
int main() {
    int arr[R][C] = {
        { 1, 5, 7, 98 },
        { 15, 22, 45, 12 },
        { 5, 10, 21, 34 },
        { 31, 24, 45, 60 }
    };
    cout<<"Reverse Wave Form of the given matrix :\n";
    printReverseWaveForm(R, C, arr);
    return 0;
}

出力結果

上記プログラムを実行すると、与えられた行列の逆波形が以下のように出力されます。

98 12 34 60 45 21 45 7 5 22 10 24 31 5 15 1

計算量

このアルゴリズムは行列のすべての要素をちょうど1回ずつ訪問するため、時間計算量は O(m × n) です。また、出力用の補助配列を必要としないため、空間計算量は O(1) で非常に効率的です。