AtCoder Beginner Contest 335, D : Loong and Takahashi

問題文

　https://atcoder.jp/contests/abc335/tasks/abc335_d

問題概要

　奇数であるような正整数 $n$ が与えられる．以下の条件を満たす $n \times n$ グリッドを構成せよ．

• グリッドの各セルには文字列が書かれる．
• セル $\left( \frac { n + 1 } 2, \frac { n + 1 } 2 \right)$ に書かれる文字列は "T" ．
• その他のセルに書かれるのは数字列．
  • 数字列を整数として解釈した値を $x$ とすると，$1 \leq x < n^2$ ．
  • 数字列たちは相異なる．
  • 有効な $x$ について，$x$ と読める数字列と $x + 1$ と読める数字列が書かれたセルは辺を共有する．

　条件を満たすグリッドが少なくともひとつ存在する．

制約

• $3 \leq n \leq 45$
• $n \bmod 2 = 1$

解法

　サンプル 1 から察せられるように，螺旋状に巻くという戦略がひとつ考えられますが，実はこれで正解です．なのであとは実装の問題となります．
　セル $( 1, 1 )$ に $1$ を書き，時計回りに回りながら内側へ巻き込んでいく螺旋に沿って数を昇順に配置するアルゴリズムについて詳しく考えます．処理をバラすと，

1. 次に書く数，現在位置，進行方向を管理する変数をそれぞれ用意する．
2. 書くべき数を全て書き終わるまで，次の処理を繰り返す．
   • 現在位置から見て進行方向の向きにひとつ進んだ位置がグリッドの範囲内で，かつそのセルにまだ数を書き込んでいないとき，以下を行う．
     1. そのセルに次の数を書く．
     2. 現在位置をそのセルで更新する．
     3. 「次に書く数」をインクリメントする．
   • そうでないとき，以下を行う．
     1. 進行方向を時計回りに $\frac \pi 2$ 回転させる．

となります．
　実装するにあたって問題になりそうなのがひとつ先のセルの座標の計算と進行方向の管理で，何も考えないと if 文を 4 つ書くことになって面倒です．なので次のような工夫をします．まず，2 つの列
\begin{align*}
\mathit{ dy } &:= \langle 0, 1, 0, -1 \rangle \\
\mathit{ dx } &:= \langle 1, 0, -1, 0 \rangle
\end{align*}
を用意します．4 方向を $0 \leq d < 4$ なる整数 $d$ に対応付けて表すことにすると，位置 $( y, x )$ からひとつ進めたセルの座標は $( y + \mathit{ dy }_d, x + \mathit{ dx }_d )$ と求まります．また，$d$ を時計回りに $\frac \pi 2$ 回転させる処理は，$$d \leftarrow ( d + 1 ) \bmod 4$$ でできます．以上の工夫により，問題だった部分を簡潔に実装することができます．

コード

constexpr int dy[] = { 0, 1, 0, -1 };
constexpr int dx[] = { 1, 0, -1, 0 };

int main()
{
	IN( int, N );

	auto board = make_vector< string >( N, N, "" );
	board[ N / 2 ][ N / 2 ] = "T";
	
	const auto inside = [&]( const int y, const int x )
	{
		return 0 <= y && y < N && 0 <= x && x < N;
	};

	int current = 1, y = 0, x = 0, d = 0;
	board[0][0] = toString( current );

	while ( current + 1 < N * N )
	{
		const int ny = y + dy[d];
		const int nx = x + dx[d];

		if ( inside( ny, nx ) && board[ ny ][ nx ] == "" )
		{
			++current;
			y = ny;
			x = nx;

			board[y][x] = toString( current );
		}
		else
		{
			( ++d ) %= 4;
		}
	}

	FOR( row, board )
	{
		cout << row << endl;
	}

	return 0;
}