配列をぐるぐる回しながら、周回したい

競技プログラミングなどで、よく使用する気がする配列を周りからぐるぐると回しながら進んでいくような周回方法を忘れないように備忘録として残す

イメージ

[
[1,2,3,4],
[5,6,7,8],
[9,10,11,12]
]

上のようなイメージがあるとき、1→2→3→4→8→12→11→10→9→5→6→7のように配列を参照したい。

処理方法

４つの境界を定義しておき、配列を順番に周回することで実装できる
配列の要素数をHとする

top = 0;
bottom = H - 1;
left = 0;
right = W - 1;

次に以下のような順番で配列を周回する

1. 左 → 右（top 行）
2. 上 → 下（right 列）
3. 右 → 左（bottom 行）
4. 下 → 上（left 列）

一周回った際に各変数を以下のように処理して境界を縮小させる

top++
bottom--
left++
right--

また再度、以下のような順で周回をしていく

1. 左 → 右（top 行）
2. 上 → 下（right 列）
3. 右 → 左（bottom 行）
4. 下 → 上（left 列）

最終的に

簡易だが、以下のように実装をすることで配列をぐるぐる回しながら周回をすることができた

import java.util.*;

public class SpiralTraverse {
    public static List<Integer> spiral(int[][] a) {
        int h = a.length;
        int w = a[0].length;

        List<Integer> res = new ArrayList<>();

        int top = 0, bottom = h - 1;
        int left = 0, right = w - 1;

        while (top <= bottom && left <= right) {

            // 1. 左 → 右
            for (int j = left; j <= right; j++) {
                res.add(a[top][j]);
            }
            top++;

            // 2. 上 → 下
            for (int i = top; i <= bottom; i++) {
                res.add(a[i][right]);
            }
            right--;

            if (top > bottom || left > right) break;

            // 3. 右 → 左
            for (int j = right; j >= left; j--) {
                res.add(a[bottom][j]);
            }
            bottom--;

            // 4. 下 → 上
            for (int i = bottom; i >= top; i--) {
                res.add(a[i][left]);
            }
            left++;
        }

        return res;
    }

    public static void main(String[] args) {
        int[][] data = {
            {1,2,3,4},
            {5,6,7,8},
            {9,10,11,12}
        };

        System.out.println(spiral(data));
    }
}