はじめに
最近[いつ？]，グリッド状の盤面の上で方向転換したくなる問題がしばしば出題されています*1*2．方向転換に限らず，グリッド上で
- 4 近傍に移動する
- ある方向を向いている状態から方向転換する
- より複雑な移動（後述で例示）をする
などはしばしば見るわけですが，これらのコードはあるひとつのアイデアを知っていれば格段に簡略化できるので，そのことについて書いてみます．
設定と動機
「グリッド状の盤面の上で何かをしろ」といった設定の問題を想定します．セル $( y, x )$ *3にいる状態から 4 近傍*4への移動を考えると遷移先の座標は（存在すれば）
- $( y - 1, x )$
- $( y, x + 1 )$
- $( y + 1, x )$
- $( y, x - 1 )$
の 4 つとなりますが，これを素朴にコーディングしようとすると 4 つの方向それぞれについて別のコードを書くことになってしまったりします．それは少々アレなので，これを簡略化したいです．
Key Insight
超重要なアイデアとして，まずは次のような 2 つの列
\begin{align*}
\mathit{ dy } &= \langle -1, 0, 1, 0 \rangle \\
\mathit{ dx } &= \langle 0, 1, 0, -1 \rangle
\end{align*}
を用意します．こうすると，先程例示した 4 近傍の座標はいずれも整数 $d \in \{ 0, 1, 2, 3 \}$ を用いて*5，
\begin{equation*}
( y + dy_d, x + dx_d )
\end{equation*}
という形で書くことができます．以降，整数 $d$ と方向を同一視します．
4 近傍への操作
上記のアイデアを用いると，例えば 4 近傍のそれぞれに対して何かをしたい場合は
for ( int d = 0; d < 4; ++d ) { const int ny = y + dy[d]; const int nx = x + dx[d]; // Your codes follow }
という風にループを回せばコードを纏められます．
方向転換
ある方向 $d$ を向いている状態から，$\frac \pi 2$ 右に方向転換したいとします．実は先程例示した $\mathit{ dy }, \mathit{ dx }$ の要素の順序には意味があって，方向 $d$ から右方向は方向 $d + 1 \bmod 4$ となるようになっています．よって，方向 $d$ を右に向ける処理は
( ++d ) %= 4;
と書くことができ，逆に左を向く処理は
( d += 3 ) %= 4;
その他の移動
たまに見かける設定として，チェスのナイトの移動を扱う問題が（わたしの記憶の中には）あります．この場合は，先程の $\mathit{ dy }, \mathit{ dx }$ の代わりに
\begin{align*}
\mathit{ dy } &= \langle -2, -1, 1, 2, 2, 1, -1, -2 \rangle \\
\mathit{ dx } &= \langle 1, 2, 2, 1, -1, -2, -2, -1 \rangle
\end{align*}
とすることで，整数 $d \in \{ 0, 1, \dots, 7 \}$ を使ってそれぞれの移動を表すことができます．
おわりに
ということで，グリッド上の移動・方向転換及びその応用に関してでした．しばしば使うテクニックで，現にわたしはスニペットにしているので，都度書かなくてよいように独立した記事にしてみました．
*1:https://atcoder.jp/contests/abc339/tasks/abc339_b
*2:https://atcoder.jp/contests/abc335/tasks/abc335_d
*3:プログラミング的な事情から $y$ を第 1 要素に置いています．というか，「$y$ 行目の第 $x$ 要素を $( y, x )$ と書く」としている問題は多いですが．
*5:プログラミング的な慣習から列の添字を $0$-origin にしています
*6:インクリメントと加算代入が操作先の参照になることを利用しています．
*7:$-1$ と $3$ が $4$ を法として合同なことを利用しています．
