問題概要

$H \times W$ のグリッドがあり、各マスには U, D, L, R のいずれかが書かれている。それぞれ、上、下、左、右へと進む指示を表している。

ただし、場外に移動するような指示があった場合はストップする。

今、マス (1, 1) にいる。マスの指示に従って動いたとき、最初にストップするマスを答えよ。ただし、無限に移動し続ける場合は -1 と出力せよ。

制約

$1 \le H, W \le 500$

考えたこと

まずは無限ループのことを考えずに、とにかく指示に従って移動する処理を実装しよう。

現在のマスを $(x, y)$ 、指示した通りに移動したときのマスを $(x_{2}, y_{2})$ としたとき、そのマスがグリッドの場外にあるかどうかは、

if (x2 < 0 || x2 >= H || y2 < 0 || y2 >= W)

という、いつもの構文で判定できる。

無限に移動するか

無限に移動し続ける場合、どこかのタイミングで、「新たに来たマスがすでに一度訪れたことのあるマスである」という状況が発生するはずである。

なぜならば、マスは $HW$ 個しかない (つまり有限個しかない) ので、移動を繰り返す限り、いつかはストップするか、一度来たマスを訪れるはずだからだ。

逆に、一度訪れたマスに来てしまった場合、同じ移動を繰り返すことになり無限ループに陥ることとなる。

よって、次の配列を用意しておくこととする。

already[x][y] ← マス $(x, y)$ が訪問済みかどうか

シミュレーション中に、すでに探索済みのマスへと移動する瞬間があれば、その時点で「-1」を出力して、処理を打ち切ればよい。

計算量

計算量を見積もる。

無限ループに陥らない場合は、高々 $HW$ 個のマスしか訪れないので、計算量は $O(HW)$ となる。

無限ループに陥る場合も、すでに探索済みのマスを訪れるまでに、高々 $HW$ 個のマスしか通らないので、計算量は $O(HW)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> G(H);
    for (int i = 0; i < H; ++i) cin >> G[i];
    
    // 各マスがすでに訪れたかどうか
    vector<vector<bool>> already(H, vector<bool>(W, false));
    
    // シミュレーション開始
    int x = 0, y = 0;
    while (true) {
        // 現在マス (x, y) -> 次のマス (x2, y2)
        int x2 = x, y2 = y;
        if (G[x][y] == 'U') --x2;
        else if (G[x][y] == 'D') ++x2;
        else if (G[x][y] == 'L') --y2;
        else ++y2;
        
        // 場外アウトの場合
        if (x2 < 0 || x2 >= H || y2 < 0 || y2 >= W) {
            cout << x+1 << " " << y+1 << endl;
            return 0;
        }
        
        // すでに来たマスの場合
        if (already[x2][y2]) {
            cout << -1 << endl;
            return 0;
        }
        
        // 現在マスを (x2, y2) に置き換える
        x = x2, y = y2;
        
        // 訪問済みにする
        already[x][y] = true;
    }
}