概要

グリッド状の倉庫でロボットを命令に従って移動させ、通過したマスの荷物を回収した後に残る荷物の個数を求める問題です。

考察

問題の整理

この問題では、以下の流れでロボットが動作します： 1. マス \((1, 1)\)（0-indexed では \((0, 0)\)）からスタート 2. 各命令に従って移動（グリッド外への移動は無視） 3. 移動先に荷物があれば回収

素朴なアプローチで十分か？

この問題は、命令を1つずつシミュレーションする素朴なアプローチで解けます。

• 命令の数 \(N\) は最大 \(2 \times 10^5\)
• 各命令の処理は \(O(1)\)（位置の更新と荷物の確認のみ）

したがって、全体で \(O(N)\) 時間で処理でき、十分高速です。

重要な気づき

1. 荷物は一度回収されたら消える：同じマスを何度訪れても、2回目以降は何も起きません
2. 「残っている荷物」を求める：最初の荷物の総数から回収した数を引けばよい
3. グリッド外への移動は無視：境界チェックを忘れずに行う

アルゴリズム

1. 入力処理：倉庫のグリッドを読み込み、荷物の総数をカウント
2. 初期位置の処理：ロボットをマス \((0, 0)\) に配置し、荷物があれば回収
3. 命令の実行：各命令について以下を行う
   • 命令に応じた移動先座標を計算
   • 移動先がグリッド内なら移動し、荷物があれば回収（グリッドを更新）
   • 移動先がグリッド外なら何もしない
4. 結果の出力：（総荷物数）−（回収した荷物数）を出力

具体例

例えば、3×3 のグリッドで以下の状態を考えます：

#.#
...
#.#

命令が RRDD の場合： - 開始: \((0,0)\) → 荷物回収（残り3個） - R: \((0,1)\) → 荷物なし - R: \((0,2)\) → 荷物回収（残り2個） - D: \((1,2)\) → 荷物なし - D: \((2,2)\) → 荷物回収（残り1個）

最終的に残る荷物は1個です。

計算量

• 時間計算量: \(O(H \times W + N)\)
  • グリッドの読み込みに \(O(H \times W)\)
  • 命令の実行に \(O(N)\)（各命令は \(O(1)\)）
• 空間計算量: \(O(H \times W + N)\)
  • グリッドの保存に \(O(H \times W)\)
  • 命令文字列の保存に \(O(N)\)

実装のポイント

1. 0-indexed と 1-indexed の違い：問題文は 1-indexed ですが、実装では 0-indexed で扱うと配列アクセスが楽です

2. 境界チェック：移動先が 0 <= nr < H かつ 0 <= nc < W を満たすか確認してから移動

3. 荷物の回収処理：回収したマスは '.' に更新することで、同じマスで二重にカウントすることを防ぎます

4. 移動しない場合の処理：命令が無視された場合でも「荷物があれば回収」の処理が発生しますが、移動していないマスは既に訪問済みなので、実質的に何も起きません（今回の実装では移動した場合のみ回収チェックを行っています）

   ソースコード

def solve():
    H, W, N = map(int, input().split())
    
    # 倉庫の状態を読み込む
    grid = []
    total_cargo = 0
    for i in range(H):
        row = input().strip()
        grid.append(list(row))
        total_cargo += row.count('#')
    
    # 命令を読み込む
    T = input().strip()
    
    # ロボットの初期位置
    r, c = 0, 0
    
    # 回収した荷物の数
    collected = 0
    
    # 初期位置の荷物を回収
    if grid[r][c] == '#':
        grid[r][c] = '.'
        collected += 1
    
    # 命令を順番に実行
    for cmd in T:
        nr, nc = r, c
        if cmd == 'U':
            nr = r - 1
        elif cmd == 'D':
            nr = r + 1
        elif cmd == 'L':
            nc = c - 1
        elif cmd == 'R':
            nc = c + 1
        
        # グリッド内かチェック
        if 0 <= nr < H and 0 <= nc < W:
            r, c = nr, nc
            # 荷物があれば回収
            if grid[r][c] == '#':
                grid[r][c] = '.'
                collected += 1
    
    # 残っている荷物の数
    print(total_cargo - collected)

solve()

---

この解説は claude4.5opus によって生成されました。