概要

ロボットが与えられた命令に従ってグリッド上を移動し、訪れたマスの荷物を回収するシミュレーションを行い、最後に残った荷物の個数を求めます。

考察

この問題は、ロボットの動きをシミュレートしながら、訪れたマスにある荷物を効率的に管理する必要があります。

重要な観察

• ロボットは命令通りに順番に移動し、訪れたマスの荷物をその場で回収します。
• 各マスの荷物は一度回収されると再び出現しないため、「すでに回収されたか」を管理する必要があります。
• 移動先がグリッド外に出る場合は、その命令は無視されます。

素朴なアプローチの問題点

• 各命令ごとに現在地を更新し、そのマスが # かどうかを直接確認しても、問題ありませんが、もし毎回マスの状態を文字列で確認していたら、文字列操作が重くなり、TLEの原因になります。
• また、荷物の存在を毎回文字列から読み込むのは非効率です。

改善策

• グリッド全体の状態（どこに荷物があるか）を二次元配列で前処理して持っておくことで、高速にアクセスできます。
• 回収済みかどうかをフラグで管理し、ロボットがそのマスに来たときにフラグを更新します。
• あらかじめ荷物の総数を数えておけば、回収のたびに減算することで、最終的な残り個数を簡単に求められます。

アルゴリズム

1. 入力から倉庫の状態を受け取り、# の個数を数えつつ、二次元配列 warehouse に記録します（1: 荷物あり、0: なし）。
2. ロボットの初期位置 \((0, 0)\) に置いて、そのマスに荷物があれば回収します。
3. 命令文字列 \(T\) を先頭から順に処理します：
   • 各命令に従って次の座標を計算。
   • 次の座標がグリッド内であれば移動し、そのマスに荷物があれば回収（warehouse を更新し、カウントを減らす）。
4. 全命令を処理した後の残りの荷物の個数を出力します。

計算量

• 時間計算量: \(O(H \cdot W + N)\)
  （初期荷物カウントに \(O(H \cdot W)\)、命令処理に \(O(N)\)）
• 空間計算量: \(O(H \cdot W)\)
  （倉庫の状態を保持する二次元配列）

実装のポイント

• 座標系が1-indexedで与えられるが、プログラム内部では0-indexedとして扱うのが一般的です。

• 移動先が範囲外かどうかのチェックは必ず行い、範囲外なら移動しないようにします。

• 荷物の有無は二次元リストで管理し、回収済みのマスは再度回収されないように注意します。

  ソースコード

H, W, N = map(int, input().split())
S = [input() for _ in range(H)]
T = input()

# 荷物の初期位置を記録
warehouse = [[0] * W for _ in range(H)]
initial_count = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            warehouse[i][j] = 1
            initial_count += 1

# ロボットの初期位置 (0-indexed)
x, y = 0, 0

# 最初のマスの荷物を回収
if warehouse[x][y] == 1:
    warehouse[x][y] = 0
    initial_count -= 1

# 命令を順に処理
for move in T:
    nx, ny = x, y
    if move == 'U':
        nx -= 1
    elif move == 'D':
        nx += 1
    elif move == 'L':
        ny -= 1
    elif move == 'R':
        ny += 1
    
    # グリッド内かどうかチェック
    if 0 <= nx < H and 0 <= ny < W:
        x, y = nx, ny
        # 荷物があれば回収
        if warehouse[x][y] == 1:
            warehouse[x][y] = 0
            initial_count -= 1

print(initial_count)

この解説は qwen3-coder-480b によって生成されました。