Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

トップ > AtCoder > 【AtCoder】ABC 339 B - Langton's Takahash | 茶コーダーが解くAtCoder

【AtCoder】ABC 339 B - Langton's Takahash | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: 100~299 grid シュミレーション プログラミング

atcoder.jp


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

問題概要

H 行 W 列のトーラス状のグリッドがあり、初めは全てのマスが白で塗られている。今、マス (1, 1) において上を向いている。以下の操作を N 回繰り返した後、グリッドの各マスがどの色で塗られているかを出力せよ。ただし、白のマスは.、黒のマスは#で表せ。

  • 操作 : 現在いるマスが白で塗られている場合は、現在いるマスを黒に塗り替え、時計回りに 90^\circ 回転し、向いている方向に1マス進む。そうでない場合は、現在いるマスを白に塗り替え、反時計回りに 90^\circ 回転し、向いている方向に1マス進む。

制約

  • 入力はすべて整数。
  • 1 \leq H, W \leq 100
  • 1 \leq N \leq 1000

考察

グリッド上を移動する問題は、グリッドの情報を2次元配列で保持しておき、現在の位置の行インデックスと列インデックスをそれぞれ変数としてそれを更新していくのが一般的だ。本問では向きの概念があるため、現在の向きを変数としておき、その向きで移動する距離を管理する配列 (ここではdx, dyとした) を作っておくと実装が楽になる。

また、このグリッドはトーラス状になっているので、例えばマス (1, 1) から上に移動するとマス (H, 1) になる。これは、上下方向は H 、左右方向は W の剰余をとることで解決できる。このあたりは有名な「ライフゲーム」あたりを実装したことがあれば容易に思いつくのではないだろうか。ただし、 C++ の負の数に対する剰余の挙動に注意。

あとは問題文の通りにシュミレーションをして、結果を出力すればよい。

コード

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

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

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

int main()
{
    int H, W, N;
    cin >> H >> W >> N;

    vector<vector<char>> v(H, vector<char>(W, '.'));
    int pos_x = 0, pos_y = 0, dir = 0;
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {-1, 0, 1, 0};

    rep(i, 0, N)
    {
        if (v[pos_y][pos_x] == '.')
        {
            v[pos_y][pos_x] = '#';
            dir++;
        }
        else
        {
            v[pos_y][pos_x] = '.';
            dir--;
        }

        dir = ((dir % 4) + 4) % 4;

        pos_x += dx[dir];
        pos_y += dy[dir];

        pos_x = ((pos_x % W) + W) % W;
        pos_y = ((pos_y % H) + H) % H;
    }

    for (auto &&h : v)
    {
        for (auto &&w : h)
        {
            cout << w;
        }
        cout << endl;
    }

atcoder.jp

実装時間: 10分