【競技プログラミング】AtCoder Beginner Contest 383_C問題

# 問題
https://atcoder.jp/contests/abc383/tasks/abc383_c

## 要約
1. AtCoder社のオフィスは H行 W列のマス目で表されている。

2. 各マスの状態は以下の3種類で表される
   - '#': 壁
   - '.': 床
   - 'H': 加湿器が置かれた床

3. 加湿器からの加湿範囲
   - 加湿器から上下左右にD回以下の移動で到達できるマス
   - 壁を通過することはできない

4. 加湿されているマスの条件
   - 加湿器が置かれているマス自体
   - 加湿器からの加湿範囲内にあるマス

加湿されている床のマスの個数を求める

変数情報
- H: オフィスの行数
- W: オフィスの列数
- S[i,j]: マス(i,j)の状態を表す文字
- D: 加湿器からの最大移動回数


# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# アプローチ

幅優先探索（BFS）を用いて、各加湿器から加湿可能な範囲を効率的に特定し、加湿された床のマスの総数を求める。


# 解法手順

1. 入力を読み込み、オフィスの状態を2次元リストSとして保存する。

2. 加湿されたかどうかを記録する2次元リストhumidifiedを作成し、初期値をFalseで埋める。

3. 移動の方向ベクトル（上下左右）を定義する。

4. BFSに使用するキューを初期化する。

5. オフィス内をスキャンし、加湿器('H')の位置を見つけたら、そのマスをキューに追加し、humidifiedをTrueに設定する。

6. キューが空になるまで以下の処理を繰り返す：
   a. キューから要素（現在の位置と移動回数）を取り出す。
   b. 移動回数がDを超えている場合は、その要素の処理をスキップする。
   c. 現在の位置から上下左右の4方向に移動を試みる。
   d. 新しい位置が以下の条件を満たす場合、その位置を加湿済みとしてマークし、キューに追加する：
      - オフィスの範囲内である
      - 壁('#')ではない
      - まだ加湿されていない

7. humidifiedリスト内のTrueの数をカウントし、それが加湿された床のマスの総数となる。

8. 結果を出力する。


# ACコード
```python:ac.py
from collections import deque

def io_func():
    # 入力を読み込む
    H, W, D = map(int, input().split())  # オフィスの高さ、幅、加湿器の効果範囲
    S = [input().strip() for _ in range(H)]  # オフィスの状態
    return H, W, D, S

def solve(H, W, D, S):
    # 加湿されたかどうかを記録する2次元リスト
    humidified = [[False] * W for _ in range(H)]

    # 移動の方向ベクトル (上下左右)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # BFS用のキュー
    queue = deque()

    # 初期状態として、加湿器があるマスをキューに追加し、加湿済みとしてマーク
    for i in range(H):
        for j in range(W):
            if S[i][j] == 'H':
                queue.append((i, j, 0))  # (行, 列, 移動回数)
                humidified[i][j] = True

    # 幅優先探索 (BFS)
    while queue:
        x, y, dist = queue.popleft()
        
        # 移動回数がDを超えた場合は探索終了
        if dist >= D:
            continue
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # 範囲外チェック
            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue
            
            # 壁の場合はスキップ
            if S[nx][ny] == '#':
                continue
            
            # 既に加湿済みの場合はスキップ
            if humidified[nx][ny]:
                continue
            
            # 加湿済みにし、次の探索候補として追加
            humidified[nx][ny] = True
            queue.append((nx, ny, dist + 1))

    # 加湿された床のマスの数をカウント
    result = sum(row.count(True) for row in humidified)
    return result

# メイン処理
H, W, D, S = io_func()
result = solve(H, W, D, S)
print(result)

###
# - H: オフィスの高さ
# - W: オフィスの幅
# - D: 加湿器の効果範囲
# - S: オフィスの状態を表す2次元リスト
# - humidified: 各マスが加湿されたかどうかを記録する2次元リスト
# - directions: 移動の方向ベクトル（上下左右）
# - queue: BFSに使用するキュー
# - x, y: 現在の位置の座標
# - dist: 加湿器からの距離（移動回数）
# - nx, ny: 次の移動先の座標
# - result: 加湿された床のマスの総数

# 1. 入力処理（io_func関数）:
#    - オフィスの高さH、幅W、加湿器の効果範囲Dを読み込む
#    - オフィスの状態Sを2次元リストとして読み込む

# 2. メイン処理（solve関数）:
#    a. 初期化:
#       - 加湿状態を記録するhumidifiedリストを作成
#       - 移動方向を定義
#       - BFS用のキューを初期化
   
#    b. 加湿器の位置を特定:
#       - オフィス内をスキャンし、加湿器('H')の位置を見つける
#       - 加湿器の位置をキューに追加し、その位置を加湿済みとマーク

#    c. 幅優先探索（BFS）:
#       - キューが空になるまで以下の処理を繰り返す:
#         - キューから位置と距離を取り出す
#         - 距離がDを超えていたら、その要素の処理をスキップ
#         - 上下左右の4方向に移動を試みる
#         - 新しい位置が有効（範囲内、壁でない、未加湿）なら加湿済みとしてマークし、キューに追加

#    d. 結果の集計:
#       - humidifiedリスト内のTrueの数をカウントし、加湿された床のマスの総数を求める

# 3. 結果の出力:
#    - 加湿された床のマスの総数を出力する
```

# 思考過程

幅優先探索（BFS）を使用して加湿器の効果範囲を計算する。
BFSを選択した理由は、加湿器からの距離に基づいて段階的に探索を行うことができ、最短経路で各マスに到達できるため。


# 計算量の概算

O(H * W)

# その他周辺知識

## 入力関数の定義
```python
def io_func():
    H, W, D = map(int, input().split())
    S = [input().strip() for _ in range(H)]
    return H, W, D, S
```
- `map(int, input().split())`は、入力された文字列を空白で分割し、各要素を整数に変換する。
- リスト内包表記`[input().strip() for _ in range(H)]`を使用して、H行の入力を受け取り、各行の両端の空白を削除。
- 最後に、処理した入力値をタプルとして返す。


## 2次元配列

```python
S = [input().strip() for _ in range(H)]  # オフィスの状態
humidified = [[False] * W for _ in range(H)]
```

## ベクトル

```python
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
```

上下左右の移動を2次元ベクトルで表現する。
例えば、(-1, 0)は上への移動を、(1, 0)は下への移動を表す。


## 距離

```python
queue.append((i, j, 0))  # (行, 列, 移動回数)
if dist >= D:
    continue
```

加湿器からの距離をマンハッタン距離を加える。
移動回数がDを超えると探索を打ち切る。

## 加湿器の位置の特定と初期化
```python
    for i in range(H):
        for j in range(W):
            if S[i][j] == 'H':
                queue.append((i, j, 0))
                humidified[i][j] = True
```
二重ループでオフィス全体をスキャンし、加湿器('H')の位置を見つけたら、その位置をキューに追加し、humidifiedリストで加湿済みとマークする。

## 幅優先探索（BFS）の実装
```python
    while queue:
        x, y, dist = queue.popleft()
        
        if dist >= D:
            continue
```
キューが空になるまでループを続け、キューから要素を取り出す。
distがD以上の場合は、その要素の処理をスキップする。

## 論理演算と条件分岐

```python
if nx < 0 or nx >= H or ny < 0 or ny >= W:
    continue
if S[nx][ny] == '#':
    continue
if humidified[nx][ny]:
    continue
```

探索範囲の制限や既探索箇所のスキップ。

## 隣接マスの探索
```python
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue
            
            if S[nx][ny] == '#':
                continue
            
            if humidified[nx][ny]:
                continue
```
現在の位置から四方向に移動を試み、それぞれの新しい位置が有効かどうかをチェック。
範囲外、壁、既に加湿済みの場合は処理をスキップする。

## 集計

```python
result = sum(row.count(True) for row in humidified)
```

2次元配列内のTrue要素の数を数え上げる。
これは、加湿された床のマスの総数を求める操作に相当する。

## BFS箇所のみ抽出

```bfs_sample.py
from collections import deque

def bfs_grid(start_points, grid, max_distance=float('inf'), blocked_value='#'):
    """
    グリッド上で幅優先探索を行う関数

    :param start_points: 開始点のリスト。各要素は (row, col) のタプル
    :param grid: 2次元リストで表現されたグリッド
    :param max_distance: 探索する最大距離（デフォルトは無限大）
    :param blocked_value: 通過できないセルの値（デフォルトは '#'）
    :return: 各セルへの最短距離を格納した2次元リスト
    """
    height, width = len(grid), len(grid[0])
    distances = [[float('inf')] * width for _ in range(height)]
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右

    queue = deque()
    for start in start_points:
        queue.append((*start, 0))
        distances[start[0]][start[1]] = 0

    while queue:
        x, y, dist = queue.popleft()
        
        if dist >= max_distance:
            continue
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < height and 0 <= ny < width and grid[nx][ny] != blocked_value:
                new_dist = dist + 1
                if new_dist < distances[nx][ny]:
                    distances[nx][ny] = new_dist
                    queue.append((nx, ny, new_dist))

    return distances

# 使用例
H, W, D = 5, 5, 2
S = [
    ".....",
    ".H...",
    ".....",
    "...H.",
    "....."
]

start_points = [(i, j) for i in range(H) for j in range(W) if S[i][j] == 'H']
result = bfs_grid(start_points, S, max_distance=D)

# 結果の表示（加湿された床のマスの数をカウント）
humidified_count = sum(1 for row in result for cell in row if cell <= D)
print(f"加湿された床のマスの数: {humidified_count}")
```