問題
要約
-
AtCoder社のオフィスは H行 W列のマス目で表されている。
-
各マスの状態は以下の3種類で表される
- '#': 壁
- '.': 床
- 'H': 加湿器が置かれた床
-
加湿器からの加湿範囲
- 加湿器から上下左右にD回以下の移動で到達できるマス
- 壁を通過することはできない
-
加湿されているマスの条件
- 加湿器が置かれているマス自体
- 加湿器からの加湿範囲内にあるマス
加湿されている床のマスの個数を求める
変数情報
- H: オフィスの行数
- W: オフィスの列数
- S[i,j]: マス(i,j)の状態を表す文字
- D: 加湿器からの最大移動回数
既存投稿一覧ページへのリンク
アプローチ
幅優先探索（BFS）を用いて、各加湿器から加湿可能な範囲を効率的に特定し、加湿された床のマスの総数を求める。
解法手順
-
入力を読み込み、オフィスの状態を2次元リストSとして保存する。
-
加湿されたかどうかを記録する2次元リストhumidifiedを作成し、初期値をFalseで埋める。
-
移動の方向ベクトル（上下左右）を定義する。
-
BFSに使用するキューを初期化する。
-
オフィス内をスキャンし、加湿器('H')の位置を見つけたら、そのマスをキューに追加し、humidifiedをTrueに設定する。
-
キューが空になるまで以下の処理を繰り返す：
a. キューから要素（現在の位置と移動回数）を取り出す。
b. 移動回数がDを超えている場合は、その要素の処理をスキップする。
c. 現在の位置から上下左右の4方向に移動を試みる。
d. 新しい位置が以下の条件を満たす場合、その位置を加湿済みとしてマークし、キューに追加する：- オフィスの範囲内である
- 壁('#')ではない
- まだ加湿されていない
-
humidifiedリスト内のTrueの数をカウントし、それが加湿された床のマスの総数となる。
-
結果を出力する。
ACコード
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)
その他周辺知識
入力関数の定義
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次元配列
S = [input().strip() for _ in range(H)] # オフィスの状態
humidified = [[False] * W for _ in range(H)]
ベクトル
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
上下左右の移動を2次元ベクトルで表現する。
例えば、(-1, 0)は上への移動を、(1, 0)は下への移動を表す。
距離
queue.append((i, j, 0)) # (行, 列, 移動回数)
if dist >= D:
continue
加湿器からの距離をマンハッタン距離を加える。
移動回数がDを超えると探索を打ち切る。
加湿器の位置の特定と初期化
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）の実装
while queue:
x, y, dist = queue.popleft()
if dist >= D:
continue
キューが空になるまでループを続け、キューから要素を取り出す。
distがD以上の場合は、その要素の処理をスキップする。
論理演算と条件分岐
if nx < 0 or nx >= H or ny < 0 or ny >= W:
continue
if S[nx][ny] == '#':
continue
if humidified[nx][ny]:
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
現在の位置から四方向に移動を試み、それぞれの新しい位置が有効かどうかをチェック。
範囲外、壁、既に加湿済みの場合は処理をスキップする。
集計
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}")