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

問題概要

$H \times W$ のマス目があり、上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と表す。マス $(i,j)$ は $S_{i,j} =$ #のとき通行不可能、. のとき通行可能であり家が建っていない、@のとき通行可能であり家が建っていることを表す。

最初、マス $(X,Y)$ にサンタクロースがおり、文字列 $T$ に従って以下の行動を行う。

現在サンタクロースがいるマスをとする。について、
- $T_i =$ Uかつマス $(x-1,y)$ が通行可能ならマス $(x-1,y)$ に移動する。
- $T_i =$ Dかつマス $(x+1,y)$ が通行可能ならマス $(x+1,y)$ に移動する。
- $T_i =$ Lかつマス $(x,y-1)$ が通行可能ならマス $(x,y-1)$ に移動する。
- $T_i =$ Rかつマス $(x,y+1)$ が通行可能ならマス $(x,y+1)$ に移動する。
- それ以外の場合、マス $(x,y)$ に留まる。

行動を終えたあとにサンタクロースがいるマスと、行動により通過または到達した家の数を求めよ。ただし、同じ家を複数回通過または到達してもそれらは重複して数えない。

制約

与えられる数値は全て整数。
$3 \leq H,W \leq 100$
$1 \leq X \leq H$
$1 \leq Y \leq W$
全ての $1 \leq i \leq H$ について $S_{i,1},S_{i,W} =$ #
全ての $1 \leq j \leq W$ について $S_{1,j},S_{H,j} =$ #
$S_{X,Y}=$ .
$T$ はU, D, L, Rのいずれかからなる長さ $1$ 以上 $10^4$ 以下の文字列。

考察

基本的には、サンタクロースの動きをシミュレーションしていき、各行動毎に到着したマスが家かどうかを判定してカウントしていけばよい。

ただし、「同じ家を複数回通過または到達してもそれらは重複して数えない」とあるので、一度訪れた家のマスは@から.に置き換えるなどの処理が必要。家を破壊する物騒なサンタ...

コード

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

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

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

int main()
{
    int H, W, X, Y;
    cin >> H >> W >> X >> Y;
    X--, Y--;
    vector<string> S(H);
    rep(i, 0, H) cin >> S[i];
    string T;
    cin >> T;

    int cnt = 0;
    rep(i, 0, T.size())
    {
        if (T[i] == 'U')
        {
            if (X == 0 || S[X - 1][Y] == '#')
                continue;
            X--;
        }
        else if (T[i] == 'D')
        {
            if (X == H - 1 || S[X + 1][Y] == '#')
                continue;
            X++;
        }
        else if (T[i] == 'L')
        {
            if (Y == 0 || S[X][Y - 1] == '#')
                continue;
            Y--;
        }
        else if (T[i] == 'R')
        {
            if (Y == W - 1 || S[X][Y + 1] == '#')
                continue;
            Y++;
        }

        if (S[X][Y] == '@')
        {
            cnt++;
            S[X][Y] = '.';
        }
    }

    cout << X + 1 << " " << Y + 1 << " " << cnt << endl;
}