D - Loong and Takahashi / AtCoder Beginner Contest 335（Sponsored by Mynavi）

問題

縦 行横 列のマスからなるグリッドがあり、上から 行目、左から 列目のマスをマス と表す。 また、 は 以下の奇数である。

このグリッドに、以下の条件を満たすように高橋君と から までの番号がついた 個のパーツからなる1匹の龍を配置する。

• 高橋君はグリッドの中央、すなわちマス に配置しなければならない。
• それ以外のマスには龍のパーツをちょうど1つ配置しなければならない。
• を満たすすべての整数 について、龍のパーツ はパーツ があるマスと辺で隣接するマスに配置しなければならない。
  • と が辺で隣接するとは、 であることを意味する。

このとき、条件を満たす配置方法を1つ出力せよ。

入力

1行に、整数 が与えられる。

条件

• 実行時間制限: 2s
• メモリ制限: 1024MB
• 
• は奇数である。

出力

行に渡り、 をマス に高橋君を配置するとき T、パーツ を配置するときに としたら、 行目に を空白区切りで出力すること。

解法

グリッドの中央のマスに高橋君が配置されるので、最終的には文字 T は以下の図のような位置に配置されます。

残りの空いているマスについては、以下のように龍のパーツを配置することで、条件を満たしながら龍を配置することができると言えます。

図のような渦巻き状に龍を配置するには、「下 → 右 → 上 → 左 → 下 → …」という順番で、「次のマスにパーツを配置していない限り、その方向に進み続ける」ということを繰り返して、中央のマスに辿り着くまで行うことによって達成できます。

具体的には、マス にパーツ を配置し、

• グリッドの境界か、既にパーツが配置されているマスに到達する直前まで下方向（ の方向）に動き、パーツを配置し続ける
• グリッドの境界か、既にパーツが配置されているマスに到達する直前まで右方向（ の方向）に動き、パーツを配置し続ける
• グリッドの境界か、既にパーツが配置されているマスに到達する直前まで上方向（ の方向）に動き、パーツを配置し続ける
• グリッドの境界か、既にパーツが配置されているマスに到達する直前まで左方向（ の方向）に動き、パーツを配置し続ける
• グリッドの境界か、既にパーツが配置されているマスに到達する直前まで下方向（ の方向）に動き、パーツを配置し続ける
• 

という手順で、最終的に のパーツを配置するまでこれを繰り返せば問題を解くことができます。

ソースコード

main() 関数の中に、答えを出力する部分を直接実装しました。

int n, ans[50][50]; // ans はどのパーツが配置されたかを記録する
bool visited[50][50]; // visited はマス (i, j) にパーツを配置したかどうかを表す
const int di[4] = {1, 0, -1, 0}, dj[4] = {0, 1, 0, -1}; // di, dj はそれぞれ下、右、上、左方向への i, j の値の変分を表す

int main() {
  cin >> n; // n の値の入力

  visited[(n + 1) / 2][(n + 1) / 2] = true; // グリッドの中央は既に訪問済として記録する

  int cnt = 1, i = 1, j = 1, k = 0; // cnt は次に置くパーツの番号、 i, j は現在のマスの座標、 k はどの方向を現在表しているのかを表す

  // パーツ n ^ 2 - 1 が配置されるまで、パーツの配置を繰り返す
  while (cnt <= n * n - 1) {
    visited[i][j] = true; // マス (i, j) を訪問済にする
    ans[i][j] = cnt; // マス (i, j) にパーツ cnt を配置する
    cnt++; // cnt の値を 1 増やす

    // 次のマスが (i + di[k], j + dj[k]) であることを利用して、マスの移動を行う
    if (1 <= i + di[k] && i + di[k] <= n && 1 <= j + dj[k] && j + dj[k] <= n &&
        !visited[i + di[k]][j + dj[k]]) {
      // 次のマスが未訪問でグリッド内に収まっていれば、そのまま次のマスに移動する
      i += di[k];
      j += dj[k];
    } else {
      // 次のマスが上記の条件を満たしていない場合は、方向を変える
      k = (k + 1) % 4; // k の値を 1 増やすことにより、次の方向に切り替えられる
      i += di[k];
      j += dj[k];
    }
  }

  // 答えの出力
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (ans[i][j] == 0) {
        // 中央のマスのみは ans[i][j] = 0 となっているため、 T を出力する
        cout << "T";
      } else {
        // そうでないマスは ans[i][j] をそのまま出力する
        cout << ans[i][j];
      }

      if (j == n) {
        cout << endl;
      } else {
        cout << " ";
      }
    }
  }

  return 0;
}

• 提出したコード: https://atcoder.jp/contests/abc335/submissions/49349255
• GitHub