C言語で行列をジグザグ（波状）形式に出力する方法

行数と列数を持つ行列 mat[row][col] が与えられたとき、その行列を下の図のようにジグザグ（波状）形式で出力する必要があります。

期待される出力は以下のとおりです。

Output: 10 20 40 70 50 30 60 80 90

この問題に対しては、行列を対角線に沿って走査し、1本の対角線の要素を出力し終えるたびに走査方向を反転させるというシンプルなアプローチを採用しています。

アルゴリズム

開始
ステップ1：k = 3、l = 3 を宣言して設定する
ステップ2：行列 mat[][3] を宣言する
ステップ3：row = 0、col = 0、flag = false を宣言して設定する
ステップ4：mn = MINIMUM(k, l) を設定する
ステップ5：len = 1 から len <= mn まで ++len しながらループ
    i = 0 から i < len まで ++i しながらループ
        mat[row][col] を出力する
        i + 1 == len の場合はループを抜ける
        flag が true の場合
            row を1増やし、col を1減らす
        それ以外の場合
            row を1減らし、col を1増やす
    内側のループ終了
    len == mn の場合はループを抜ける
    flag が true の場合
        row を1増やし、flag = false に設定する
    それ以外の場合
        col を1増やし、flag = true に設定する
外側のループ終了
ステップ6：row == 0 の場合
    col == k - 1 なら row を1増やす
    それ以外なら col を1増やす
    flag = 1 に設定する
それ以外の場合
    row == l - 1 なら col を1増やす
    それ以外なら row を1増やす
    flag = 0 に設定する
ステップ7：MAX = MAXIMUM(k, l) - 1 を設定する
ステップ8：diag = MAX から diag > 0 まで --diag しながらループ
    diag > mn の場合は len = mn
    それ以外の場合は len = diag
    i = 0 から i < len まで ++i しながらループ
        mat[row][col] を出力する
        i + 1 == len の場合はループを抜ける
        flag が true の場合
            row を1増やし、col を1減らす
        それ以外の場合
            col を1増やし、row を1減らす
    内側のループ終了
    row == 0 または col == k - 1 の場合
        col == k - 1 なら row を1増やす
        それ以外なら col を1増やす
        flag = true に設定する
    col == 0 または row == l - 1 の場合
        row == l - 1 なら col を1増やす
        それ以外なら row を1増やす
        flag = false に設定する
終了

実装例（C言語）

#include <stdio.h>
#include <stdbool.h>
#define C 3
#define min(a, b) a>b?b:a
#define max(a, b) a>b?a:b
int main(){
    int k = 3, l = 3;
    int mat[][3] = {
        { 10, 20, 30 },
        { 40, 50, 60 },
        { 70, 80, 90 }
    };
    int row = 0, col = 0;
    bool flag = false;
    int i, j, len, diag;
    int MAX;
    int mn = min(k, l); // 最小値を求める
    for ( len = 1; len <= mn; ++len) {
        for ( i = 0; i < len; ++i) {
            printf("%d ", mat[row][col]); // 行列をジグザグ形式で出力
            if (i + 1 == len)
                break;
            if (flag)
                ++row, --col;
            else
                --row, ++col;
        }
        if (len == mn)
            break;
        if (flag)
            ++row, flag = false;
        else
            ++col, flag = true;
    }
    if (row == 0) {
        if (col == k - 1)
            ++row;
        else
            ++col;
        flag = 1;
    } else {
        if (row == l - 1)
            ++col;
        else
            ++row;
        flag = 0;
    }
    MAX = max(k, l) - 1; // 最大値を求める
    for ( len, diag = MAX; diag > 0; --diag) { // 対角線方向に走査するループ
        if (diag > mn)
            len = mn;
        else
            len = diag;
        for ( i = 0; i < len; ++i) {
            printf("%d ", mat[row][col]);
            if (i + 1 == len)
                break;
            if (flag)
                ++row, --col;
            else
                ++col, --row;
        }
        if (row == 0 || col == k - 1) {
            if (col == k - 1)
                ++row;
            else
                ++col;
            flag = true;
        }
        else if (col == 0 || row == l - 1) {
            if (row == l - 1)
                ++col;
            else
                ++row;
            flag = false;
        }
    }
    return 0;
}

出力

このプログラムを実行すると、以下の結果が出力されます。

10 20 40 70 50 30 60 80 90

プログラムの解説

このプログラムでは、左上の要素 mat[0][0] から出力を開始し、ブール型の変数 flag によって対角線上の移動方向（右上がり／左下がり）を管理しています。行列の上端・右端、あるいは左端・下端に到達したタイミングで flag を反転させ、次の対角線の始点へ移動することで、行列全体をジグザグに走査します。

前半のループでは対角線の長さが増えていく部分（左上から中央の対角線まで）を処理し、後半のループでは対角線の長さが減っていく部分（中央から右下まで）を処理しています。計算量は O(row × col) であり、行列の全要素を1度ずつ訪問するため非常に効率的です。