概要

\(H \times W\) のグリッド上を、与えられた \(N\) 個の命令に従って移動するロボットの動きをシミュレーションし、最終的に回収されずに残った荷物の個数を求める問題です。

考察

この問題は、ロボットの現在位置を管理しながら、命令を一つずつ実行していくシミュレーションによって解くことができます。

重要なポイントは以下の通りです： - 初期位置の処理: 命令を実行する前に、まずスタート地点であるマス \((1, 1)\) の荷物を回収する必要があります。 - 移動の判定: 命令によってグリッドの外（行が \(1\) 未満や \(H\) より大きい、列が \(1\) 未満や \(W\) より大きい）に出る場合は、その命令を無視して移動しません。 - 荷物の回収: 荷物があるマスを訪れたら、そのマスの状態を「荷物なし」に変更します。これにより、同じマスを二度訪れた際に重複して数えることを防げます。 - 最終的なカウント: すべての命令が終わった後、グリッド全体を走査して # がいくつ残っているかを数えます。

制約を確認すると、\(H, W \leq 500\)、\(N \leq 2 \times 10^5\) です。命令のシミュレーションに \(O(N)\)、最後のカウントに \(O(HW)\) かかりますが、これらは十分に実行時間制限内に収まります。

アルゴリズム

1. 倉庫の状態を2次元配列（リストのリストなど）として読み込みます。
2. ロボットの現在位置を \((r, c) = (0, 0)\) とします（0-indexedで管理）。
3. マス \((r, c)\) が荷物 (#) であれば、それを空 (.) に書き換えます。
4. 文字列 \(T\) の各文字（命令）について、以下の処理を繰り返します。
   • 命令が U, D, L, R のどれかに応じて、移動先の候補 \((nr, nc)\) を計算します。
   • \((nr, nc)\) がグリッドの範囲内（\(0 \leq nr < H\) かつ \(0 \leq nc < W\)）であれば、現在位置を \((nr, nc)\) に更新します。
   • 更新後のマス \((r, c)\) が荷物 (#) であれば、それを空 (.) に書き換えます。
5. 全ての命令終了後、2次元配列内の # の個数を合計して出力します。

計算量

• 時間計算量: \(O(N + HW)\)
  • 命令のシミュレーションに \(O(N)\) かかります。
  • 最後に残った荷物を数えるためにグリッドの全マスを確認するのに \(O(HW)\) かかります。
• 空間計算量: \(O(HW + N)\)
  • グリッドの状態を保持するのに \(O(HW)\)、命令文字列を保持するのに \(O(N)\) のメモリを使用します。

実装のポイント

• 0-indexed への変換: 問題文ではマスが \((1, 1)\) から始まりますが、プログラム上（配列のインデックスなど）では \((0, 0)\) から始まるものとして扱うと処理がスムーズです。

• 荷物の更新: Python の文字列は不変（immutable）であるため、grid[r][c] = '.' のように書き換えるには、各行を文字のリストに変換しておく必要があります。

• 境界チェック: 移動先の座標が 0 未満になったり、H や W 以上になったりしないかを、移動のたびに正しく判定する必要があります。

  ソースコード

import sys

def solve():
    # 全ての入力を読み込み、空白文字で分割します。
    # これにより、H, W, N、グリッドの各行、および命令文字列 T を取得します。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # グリッドの高さ H、幅 W、命令の数 N を取得
    H = int(data[0])
    W = int(data[1])
    N = int(data[2])
    
    # グリッドの状態を 2次元リストとして読み込みます。
    # 荷物の回収（'#' から '.' への変更）を行うため、リストのリストにします。
    # data[3] から data[H+2] までが各行 S_i に対応します。
    grid = [list(data[i]) for i in range(3, 3 + H)]
    
    # 命令文字列 T を取得します。
    # 万が一命令が複数行に分かれていた場合を考慮して join します。
    T = "".join(data[3 + H:])
    
    # ロボットの初期位置 (0-indexed)
    # 問題文の (1, 1) は 0-indexed では (0, 0) になります。
    r, c = 0, 0
    
    # 最初に配置されたマスの荷物を回収します。
    if grid[r][c] == '#':
        grid[r][c] = '.'
        
    # 各命令を順番に実行します。
    for cmd in T:
        nr, nc = r, c
        if cmd == 'U':
            nr -= 1
        elif cmd == 'D':
            nr += 1
        elif cmd == 'L':
            nc -= 1
        elif cmd == 'R':
            nc += 1
        
        # 移動後のマスがグリッドの範囲内にあるか判定します。
        if 0 <= nr < H and 0 <= nc < W:
            # 範囲内であれば移動し、そのマスの荷物を回収します。
            r, c = nr, nc
            if grid[r][c] == '#':
                grid[r][c] = '.'
        # 範囲外に出る命令の場合は無視され、ロボットはその場に留まります。
    
    # すべての命令終了後、残っている荷物 ('#') の個数を数えます。
    remaining_cargo = 0
    for row in grid:
        remaining_cargo += row.count('#')
        
    # 結果を出力します。
    print(remaining_cargo)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。