C++で解くスパイラル行列 III：時計回りに全マスを訪問するアルゴリズム

本記事では、R行C列の2次元グリッドを時計回りの渦巻き（スパイラル）状に巡回し、すべてのマスを訪問した順に座標を求める問題「スパイラル行列 III」をC++で解く方法を解説します。

問題の概要

R行C列の2次元グリッドを考えます。スタート地点は (r0, c0) で、最初は東向きに面しています。グリッドの北西の角は第1行・第1列に位置し、南東の角は最終行・最終列にあります。

私たちは時計回りの渦巻き状に歩きながら、グリッド内のすべてのマスを訪問します。途中でグリッドの境界外に出た場合でも、そのまま外側を歩き続け、後で再びグリッド内に戻ることがあります。

求めるのは、訪問した順番に並べたグリッド上の座標のリストです。例えば、以下のようなグリッドの場合、矢印が示す経路が答えとなります。

解法のアプローチ

この問題は、移動方向を管理しながら渦巻き状に一歩ずつ進むことで解けます。手順は以下の通りです。

• 方向ベクトル dirr := [[0,1],[1,0],[0,-1],[-1,0]] を用意します（東・南・西・北の順）。

• 結果格納用の配列 ret、現在の移動距離 len := 0、方向インデックス dir := 0 を初期化します。

• スタート地点 (r0, c0) を ret に追加します。

• ret のサイズが R×C に達するまで、以下を繰り返します。

  • dir が 0（東）または 2（西）のとき、len を1増やします。これは渦巻きの一周ごとに水平方向の移動距離が伸びるためです。

  • i を 0 から len−1 まで繰り返します。

    • r0 := r0 + dirr[dir][0]、c0 := c0 + dirr[dir][1] として1マス進みます。

    • 新しい座標がグリッドの範囲外（r0 または c0 が負、あるいは R・C 以上）であれば、そのマスは結果に加えずスキップします。

    • 範囲内であれば、座標 (r0, c0) を ret に追加します。

  • dir := (dir + 1) mod 4 として方向を時計回りに切り替えます。

• 最後に ret を返します。

それでは、理解を深めるために実際の実装を見てみましょう。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << "[";
       for(int j = 0; j <v[i].size(); j++){
          cout << v[i][j] << ", ";
       }
       cout << "],";
    }
    cout << "]"<<endl;
}
int dirr[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
class Solution {
    public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
       vector < vector <int> > ret;
       int len = 0;
       int dir = 0;
       ret.push_back({r0, c0});
       while(ret.size() < R * C){
          if(dir == 0 || dir == 2) len++;
          for(int i = 0; i < len; i++){
             r0 = r0 + dirr[dir][0];
            c0 = c0 + dirr[dir][1];
            if(r0 < 0 || c0 < 0 || c0 >= C || r0 >= R) continue;
            ret.push_back({r0, c0});
          }
          dir = (dir + 1) % 4;
       }
       return ret;
    }
};
main(){
    Solution ob;
    print_vector(ob.spiralMatrixIII(5,5,1,3));
}

入力

5
5
1
3

出力

[[1,3],[1,4],[2,4],[2,3],[2,2],[1,2],[0,2],[0,3],[0,4],[3,4],[3,3],[3,2],[3,1],[2,1],[1,1],[0,1],[4,4],[4,3],[4,2],[4,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

まとめ

このアルゴリズムは、方向を4つで管理し、東西方向に進むたびに移動距離を1つずつ伸ばすというシンプルな発想で、グリッド外を通過するケースにも柔軟に対応できます。計算量は O(max(R,C)²) 程度となり、すべてのマスを確実に訪問できる点がポイントです。