【AtCoder】ABC 341 C - Takahashi Gets Lost | 茶コーダーが解くAtCoder

実行時間制限: 3 sec / メモリ制限: 1024 MB / Difficulty: 406

問題概要

$H$ 行 $W$ 列のグリッドがあり、各マスは陸か海のいずれかで、その情報は $H$ 個の長さ $W$ の文字列 $S_1, S_2, ..., S_H$ で与えられる。なお、.のとき陸で、#のとき海である。また、グリッドの外周のマスはすべて海であることが保証される。

ここで、あるマスからL, R, U, Dのみからなる長さ $N$ の文字列 $T$ で表される手順に沿って、高橋君がグリッド上を $N$ 回移動した。 $T$ の $i$ 文字目はそれぞれ以下の行動内容を表す。

Lのとき : 左に1マス移動した。
Rのとき : 右に1マス移動した。
Uのとき : 上に1マス移動した。
Dのとき : 下に1マス移動した。

高橋君の移動経路上のマス (スタートしたマスおよび現在いるマスを含む) はいずれも海でない。高橋君が現在いるマスとしてあり得るものの個数を出力せよ。

制約

$H, W, N$ はすべて整数
$3 \leq H, W \leq 500$
$1 \leq N \leq 500$
$1 \leq T_i \leq S_i \leq 10^9$

考察

移動の仕方が分かっているので、スタート地点が決まればゴール地点も決まる。したがって、スタート地点を全探索して「移動経路上に海のマスがない」という条件を満たすものをシュミレーションによって数えていけばよい。

実装においては、条件を満たさないことが分かった段階でcontinueするなりbreakするなりして、次のスタート地点の探索に移るようにした方が楽になる。

コード

#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;
    string T;
    cin >> H >> W >> N >> T;
    vector<string> S(H);
    rep(i, 0, H) cin >> S[i];

    int ans = 0;
    rep(y, 0, H) rep(x, 0, W)
    {
        int pos_x = x, pos_y = y;
        if (S[pos_y][pos_x] == '#')
            continue;

        bool flag = true;
        rep(i, 0, N)
        {
            if (T[i] == 'L')
                pos_x--;
            if (T[i] == 'R')
                pos_x++;
            if (T[i] == 'U')
                pos_y--;
            if (T[i] == 'D')
                pos_y++;

            if (S[pos_y][pos_x] == '#')
            {
                flag = false;
                break;
            }
        }

        if (flag)
            ans++;
    }

    cout << ans << endl;
}

atcoder.jp

実装時間: 15分

Yuulis.log

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

【AtCoder】ABC 341 C - Takahashi Gets Lost | 茶コーダーが解くAtCoder

問題概要

制約

考察

コード