このサイト(AtCoder 版！蟻本 (初級編))を参考に、AtCoderの問題を解いてアルゴリズムの基礎固めしています。今回解くのは、AtCoderのA - Darker and Darker。全探索の一種である幅優先探索(BFS)の教育的かつ典型的な問題です（だそうです）。
（参考：けんちょんさんのブログ）
問題
縦H行、横W列の白黒に塗られたマス目が与えられます。
一回の操作で、全ての黒のマスの上下左右を黒く塗るとき、何回の操作で全体を黒く塗りつぶせますか？という問題です。
1 ≦ H ,W ≦ 1000
解法
今回の問題の場合、
・「全白マスにおける、黒マスからの最短距離」の最大値を求める問題
と言えます。
つまり、最短経路問題とみなせて、BFSで解くことができます。
DFSでなくBFSで解くんだというイメージがわきやすい、良い問題ですね。
スタートの位置が複数ありますが、構わずキューに追加してしまい、BFSを用いることで「同時進行」させるのがポイントです。
※このような問題を、「多点スタートな最短路問題」と言うらしいです。
また、「開始時点の黒マス」からの距離を記録するリストを用意しておくのもポイントです。
（全スタート地点を0に初期化する）
【メモ】
ちなみにキューに追加するのをリストからタプルに変えたら、実行時間が短くなり、メモリ消費も減りました。
from collections import deque
H, W = map(int, input().split())
grid = [input() for i in range(H)]
# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]
# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
for w in range(W):
if grid[h][w] == '#':
black_cells.append((h, w))
dist[h][w] = 0
def bfs(black_cells, dist):
"""
BFSを用いて、全マス目を黒くする回数を求める
Args:
black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
dist: 「開始時の黒マス」からの距離の入ったリスト [[-1, -1, 0], ...]
（白マスの初期値は0）
Returns:
g: 操作を繰り返した数
"""
d = 0
while black_cells:
# キューとして使うのでpop()ではなくpopleft()
h, w = black_cells.popleft()
d = dist[h][w]
for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
new_h = h + dy
new_w = w + dx
if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
continue
if dist[new_h][new_w] == -1: # セルが白('.')であるのと同義
dist[new_h][new_w] = d+1
black_cells.append((new_h, new_w))
return d
d = bfs(black_cells, dist)
print(d)