C言語でO(1)の追加メモリ領域のみを使ってn×nのスパイラル行列を出力する方法

正の整数 n が与えられたとき、追加の作業用メモリを O(1) しか使用せずに、時計回り方向の n×n スパイラル行列を生成して出力する方法を解説します。

スパイラル行列とは、円の原点から出発し、時計回りに渦を描くように値を埋めていく行列のことです。ここでは、2 → 4 → 6 → 8 → 10 → 12 → 14 → 16 → 18 というように偶数を渦状に配置した行列を、O(1) の空間計算量で出力することを目標とします。

以下にスパイラル行列の例を示します。

実行例

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

メモリを無制限に使えばこの問題は簡単に解けますが、それは効率的とは言えません。優れたプログラムとは、メモリと時間の両面で効率的なものだからです。一般的には、行列の上・右・下・左の4つの境界に対応する4つのループを使ってスパイラル順序を維持しますが、行列を「右上部分」と「左下部分」の2つに分割して考えれば、数式から各要素の値を直接求めることができます。

右上部分の要素を求める式

mat[i][j] = (n-2*x)*(n-2*x)-(i-x)-(j-x)

左下部分の要素を求める式

mat[i][j] = (n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)

注意 − ここで扱うプログラムは、2の倍数（偶数）を配置した行列を出力するものです。

アルゴリズム

int spiralmatrix(int n)
START
STEP 1: DECLARE i, j, a, b, x
STEP 2: LOOP FOR i = 0 AND i < n AND i++
    LOOP FOR j = 0 AND j < n AND j++
        (i<j) の最小値を求めて a に代入
        (n-1-i) と (n-1-j) の最小値を求めて b に代入
        a と b のうち小さい方を x に代入
        IF i <= j THEN,
            2 * ((n-2*x)*(n-2*x) - (i-x) - (j-x)) の値を出力
        ELSE
            2 * ((n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)) の値を出力
    END LOOP
    改行を出力
END LOOP
STOP

C言語による実装例

#include <stdio.h>
// n x n のスパイラル行列を出力
int spiralmatrix(int n){
    int i, j, a, b, x; // x は (i, j) 番目の要素が属する層（渦）を表す
    for ( i = 0; i < n; i++){
        for ( j = 0; j < n; j++){
            // 4つの候補値の最小値を求める
            a = ((i<j ? i : j));
            b = ((n-1-i) < (n-1-j) ? (n-1-i) : (n-1-j));
            x = a < b ? a : b;
            // 右上部分の場合
            if (i <= j)
                printf("%d\t ", 2 * ((n-2*x)*(n-2*x) - (i-x) - (j-x)));
            // 左下部分の場合
            else
                printf("%d\t ", 2*((n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)));
        }
        printf("\n");
    }
}
int main(int argc, char const *argv[]){
    int n = 3;
    spiralmatrix(n);
    return 0;
}

出力結果

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

18 16 14
4 2 12
6 8 10

このプログラムのポイントは、行列をメモリ上に実際に構築せず、各座標 (i, j) に対して数式から直接値を計算している点です。変数 x は、その要素が行列の外周から何番目の渦（層）に属するかを表しており、要素が右上側にあるか左下側にあるかで適用する式を切り替えることで、追加メモリ O(1) のまま時計回りのスパイラル順序を正確に再現できます。