【AtCoder】ABC 335 D - Loong and Takahashi | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 431

問題概要

$N$ 行 $N$ 列のマスからなるグリッドがある。以下では、上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と書く。このグリッドに、以下の条件を満たすように高橋君と $1$ から $N^2 - 1$ の番号が付いたパーツからなる1匹の龍を配置したい。

高橋君はグリッドの中央であるマス $(\dfrac{N+1}{2}, \dfrac{N+1}{2})$ にTとして配置する。
高橋君がいるマス以外のマスには龍のパーツを1つ配置する。
$2 \leq x \leq N^2 - 1$ を満たす任意の $x$ について、パーツ $x$ はパーツ $x - 1$ があるマスと辺で隣接するマスに配置する。

条件を満たす配置方法を1つ出力せよ。なお、条件を満たす配置は必ず存在する。

制約

$N$ は奇数で、 $3 \leq N \leq 45$ を満たす。

考察

問題文だけだと何を言っているのかわかりにくいので、サンプルケースを見てみると、出力例1はこんな感じになる。

1 2 3 4 5
16 17 18 19 6
15 24 T 20 7
14 23 22 21 8
13 12 11 10 9

確かに、龍を外周から高橋君に向けて渦巻き状に配置すれば条件を満たす。ということで、このようなプログラムを書いていく。

方針としては、現在のグリッド上の座標と進んでいる向きを保持する変数を持って置き、以下の処理を行えばよい。

マス $(1, 1)$ から右向きでスタートする。
進行方向の次のマスがグリッドの範囲外またはすでに龍のパーツが配置されているマスならば向きを変える。
そうでなければ、龍のパーツを配置する。

実装に当たっては、向きに対応する移動量をコードのようなdx, dyの形で定義しておくとラク。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

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

int main()
{
    int N;
    cin >> N;

    vector<vector<int>> grid(N, vector<int>(N));
    int x = 0, y = 0;
    int cnt = 1;
    int dir = 0;
    while (cnt < N * N)
    {
        grid[y][x] = cnt;

        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (0 <= nx && nx < N && 0 <= ny && ny < N && grid[ny][nx] == 0)
        {
            x = nx;
            y = ny;
            cnt++;
        }
        else
        {
            dir = (dir + 1) % 4;
        }
    }

    rep(i, 0, N)
    {
        rep(j, 0, N)
        {
            if (i == (N - 1) / 2 && j == (N - 1) / 2)
                cout << 'T' << " ";
            else
                cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}