ABC341 C - Takahashi Gets Lost

atcoder.jp

問題

• 高橋くんがH行W列のグリッド上のどこかのマスに不時着したよ
• 高橋くんは、LRUDの文字列に沿って移動したよ
• 高橋くんは移動中に海を通ってないよ
• 高橋くんが不時着した可能性のあるマスの個数を数えてね

成約

• $3 \leq H,W \leq 500$
• $1 \leq N \leq 500$

思考

• $500\times500$マスに落ちた可能性があって、
• 移動手順の長さが500なので、
• $O(HWN)$…？$500^{3}$通る…？
  • 3秒だったので安心してポイ

コード

H,W,N = map(int,input().split())
T = input()
grid_L = []
for i in range(H):
    grid_L.append(input())
ans = 0
for sr in range(H):
    for sc in range(W):
        if grid_L[sr][sc] == "#":
            continue
        now_r = sr
        now_c = sc

        for c in T:
            if c == "U":now_r -= 1
            elif c == "D":now_r += 1
            elif c == "L":now_c -= 1
            elif c == "R":now_c += 1

            if grid_L[now_r][now_c] == "#":
                break
        else:
            ans += 1
print(ans)