Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
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):
    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)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [input() for i in range(H)]
A = [[0 for j in range(W)] for i in range(H)]
pos = []
cnt = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      pos.append([i, j])
      A[i][j] = 1
      cnt += 1
ccnt = 0
pnt = 0
while pnt < cnt:
  n = cnt
  ccnt += 1
  for i in range(pnt, cnt):
    x, y = pos[i][0], pos[i][1]
    if x > 0:
      if A[x-1][y] == 0:
        A[x-1][y] = 1
        pos.append([x-1, y])
        cnt += 1
    if x < H-1:
      if A[x+1][y] == 0:
        A[x+1][y] = 1
        pos.append([x+1, y])
        cnt += 1
    if y > 0:
      if A[x][y-1] == 0:
        A[x][y-1] = 1
        pos.append([x, y-1])
        cnt += 1
    if y < W-1:
      if A[x][y+1] == 0:
        A[x][y+1] = 1
        pos.append([x, y+1])
        cnt += 1
  pnt = n
print(ccnt-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import pprint
h,w=map(int, input().split())
a=[list(input()) for i in range(h)]


#スタートをキューに格納

route=[[1,0],[0,1],[-1,0],[0,-1]]
cnt=0

q=[]
for i in range(h):
  for j in range(w):
    if a[i][j]=="#":
      q.append([i,j])
qDummy=q
for _ in range(h*w):
  q=qDummy
  while q:
    #print(len(q))
    qDummy=[]
    for _ in range(len(q)):
      x,y = q.pop(0)

      for i in range(4):
        nx, ny = x+route[i][0], y+route[i][1]
        #条件に合致すれば追加
        if 0<=nx<h and 0<=ny<w and a[nx][ny]!="#":
          a[nx][ny]="#"
          qDummy.append([nx,ny])
          #print("nx,ny", nx,ny)
  cnt+=1
  #pprint.pprint(a)
  if len(qDummy)==0:
    print(cnt-1)
    exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
h, w = map(int, input().split())
a = [[j for j in input()] for i in range(h)]
# print(a)

cnt = [[INF if a[i][j] == "." else 0 for j in range(w)] for i in range(h)]
# print(cnt)

for i in range(h):
    for j in range(w):
        if a[i][j] == ".":
            continue
        queue = deque([[i, j, 0]])
        visited = [[0 for _ in range(w)] for _ in range(h)]
        while queue:
            now_y, now_x, cnt2 = queue.popleft()
            if not (0 <= now_y < h and 0 <= now_x < w):
                continue
            if visited[now_y][now_x] == 1:
                continue
            visited[now_y][now_x] = 1
            if a[now_y][now_x] == ".": 
                if cnt[now_y][now_x] <= cnt2:
                    continue
                cnt[now_y][now_x] = min(cnt[now_y][now_x], cnt2)
            for k in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                queue.append([now_y + k[0], now_x + k[1], cnt2 + 1])

# print(cnt)
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
h, w = map(int, input().split())
a = [[j for j in input()] for i in range(h)]
# print(a)

cnt = [[INF if a[i][j] == "." else 0 for j in range(w)] for i in range(h)]
# print(cnt)

for i in range(h):
    for j in range(w):
        if a[i][j] == ".":
            continue
        queue = deque([[i, j, 0]])
        visited = [[0 for _ in range(w)] for _ in range(h)]
        while queue:
            now_y, now_x, cnt2 = queue.popleft()
            if not (0 <= now_y < h and 0 <= now_x < w):
                continue
            if visited[now_y][now_x] == 1:
                continue
            visited[now_y][now_x] = 1
            if a[now_y][now_x] == ".": 
                cnt[now_y][now_x] = min(cnt[now_y][now_x], cnt2)
            for k in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                queue.append([now_y + k[0], now_x + k[1], cnt2 + 1])

# print(cnt)
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def start_search(G):
    start=[]
    for i in range(H):
        for j in range(W):
            if G[i][j]=='#':
                start.append((i,j))
    return start
def bfs(G,visited,start):
    queue=deque(start)
    cnt=0
    for p,q in start:
        visited[p][q]=0
    while queue:
        tmp=len(queue)
        for _ in range(tmp):
            (y,x)=queue.popleft()
            for j,k in ([1,0],[0,1],[-1,0],[0,-1]):
                tmp_y,tmp_x = y+j,x+k
                if 0<=tmp_y<=H-1 and 0<=tmp_x<=W-1 and visited[tmp_y][tmp_x]==-1:
                    visited[tmp_y][tmp_x]=visited[y][x]+1
                    queue.append([tmp_y,tmp_x])
        cnt+=1
    return cnt-1
if __name__=="__main__":
    H,W = map(int,input().split())
    G=[input() for _ in range(H)]
    start=start_search(G)
    visited=[[-1]*W for _ in range(H)]
    print(bfs(G,visited,start))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def resolve():
    H, W = map(int, input().split())
    A, q = [], deque([])
    for i in range(H):
        A.append(list(input()))
        if '#' in A[i]:
            for j in range(W):
                if A[i][j] == '#':
                    q.append((i, j))

    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    cnt = -1

    # 1回目で各黒マスを拡張して，2回目以降は拡張した黒マスから拡張してく
    nq = deque([])
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.':
                nq.append((ny, nx))
                A[ny][nx] = '#'
        if q == deque([]):
            q = nq
            nq = deque([])
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
A, white = [], []
for i in range(H):
    A.append(list(input()))
    if '.' in A[i]:
        for j in range(W):
            if A[i][j] == '.':
                white.append([i, j])

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
cnt = 0

# 各白マスから黒マスまでの最短距離を探索し，その最大値を出力
for sy, sx in white:
    dis = [[float('inf')] * W for _ in range(H)]
    dis[sy][sx] = 0
    q = deque([(sy, sx)])
    update = False
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if (1
                    and 0 <= ny < H
                    and 0 <= nx < W
                    and dis[ny][nx] == float('inf')):
                dis[ny][nx] = dis[y][x] + 1
                q.append((ny, nx))
                if A[ny][nx] == '#':
                    cnt = max(dis[ny][nx], cnt)
                    update = True
        if update:
            break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def resolve():
    H, W = map(int, input().split())
    A, white = [], []
    for i in range(H):
        A.append(list(input()))
        if '.' in A[i]:
            for j in range(W):
                if A[i][j] == '.':
                    white.append([i, j])

    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    cnt = 0

    # 各白マスから黒マスまでの最短距離を探索し，その最大値を出力
    for sy, sx in white:
        dis = [[float('inf')] * W for _ in range(H)]
        dis[sy][sx] = 0
        q = deque([(sy, sx)])
        update = False
        while q:
            y, x = q.popleft()
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if (1
                        and 0 <= ny < H
                        and 0 <= nx < W
                        and dis[ny][nx] == float('inf')):
                    dis[ny][nx] = dis[y][x] + 1
                    q.append((ny, nx))
                    if A[ny][nx] == '#':
                        cnt = max(dis[ny][nx], cnt)
                        update = True
            if update:
                break
    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #queの定義
    que = deque([])
   
    for i in range(n):
        for j in range(m):
            # スタートとゴールの座標を探す
            if maze[i][j] == "#":
                sx = i
                sy = j
                que.append((sx, sy))
                d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    ans = 0
    for i in range(n):
        for j in range(m):
            ans = max(ans, d[i][j])
    
    return ans

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.buffer.readline
def readints():return list(map(int,readline().split()))
def readstr():return readline().rstrip().decode()

import queue

h,w = readints()
s = [list(readstr()) for i in range(h)]

q = queue.Queue()
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            q.put((i,j,0))

move = ((0,1),(0,-1),(1,0),(-1,0))

for i in range(10**6):
    y,x,d = q.get()
    for a,b in move:
        if 0<=y+a<h and 0<=x+b<w:
            if s[y+a][x+b]=='.':
                s[y+a][x+b]='#'
                q.put((y+a,x+b,d+1))
    if q.empty():
        break

print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

import queue

h,w = readints()
s = [[0]*w for i in range(h)]
for i in range(h):
    a = readstr()
    for j,x in enumerate(a):
        if x=='#':
            s[i][j]=1

q = queue.Queue()
for i in range(h):
    for j in range(w):
        if s[i][j]==1:
            q.put((i,j,0))

move = ((0,1),(0,-1),(1,0),(-1,0))

for i in range(10**6):
    y,x,d = q.get()
    for a,b in move:
        if 0<=y+a<h and 0<=x+b<w:
            if s[y+a][x+b]==0:
                s[y+a][x+b]=1
                q.put((y+a,x+b,d+1))
    if q.empty():
        break

print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]
q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            check[y][x] = 0
            q.append((y, x, 0))

dy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]

while q:
    y, x, cnt = q.popleft()
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < H and 0 <= nx < W:
            if check[ny][nx] == -1 or cnt+1 < check[ny][nx]:
                check[ny][nx] = cnt + 1
                q.append((ny, nx, cnt+1))


print(max([max(c) for c in check]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import queue

h,w = readints()
s = [[0]*w for i in range(h)]
for i in range(h):
    a = readstr()
    for j,x in enumerate(a):
        if x=='#':
            s[i][j]=1

q = queue.Queue()
for i in range(h):
    for j in range(w):
        if s[i][j]==1:
            q.put((i,j,0))

move = ((0,1),(0,-1),(1,0),(-1,0))

while not q.empty():
    y,x,d = q.get()
    for a,b in move:
        if 0<=y+a<h and 0<=x+b<w:
            if s[y+a][x+b]==0:
                s[y+a][x+b]=1
                q.put((y+a,x+b,d+1))

print(d)

Submission status: Time Limit Exceeded

Solution code:
import collections

h,w = map(int,input().split())
field = [list(input()) for i in range(h)]

ans = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]

def bfs(y,x):
    global ans
    c = tmp_field[y][x]
    for k in range(4):
        newy = y + dy[k]
        newx = x + dx[k]
        if 0<= newy < h and 0<= newx < w:
            if field[newy][newx] == "#":
                ans = max(ans,c+1)
                q.clear()
                break
            elif tmp_field[newy][newx] == 0:
                tmp_field[newy][newx] = c+1
                q.append((newy,newx))

for i in range(h):
    for j in range(w):
        if field[i][j] == ".":
            tmp_field = [[0]*w for _ in range(h)]
            q = collections.deque([])
            q.append((i,j))
            while q:
                s = q.popleft()
                y,x =  s[0],s[1]
                bfs(y,x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

h,w = map(int,input().split())
field = [list(input()) for i in range(h)]

ans = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for i in range(h):
    for j in range(w):
        if field[i][j] == ".":
            tmp_field = [[0]*w for _ in range(h)]
            q = collections.deque([])
            q.append((i,j))
            while q:
                s = q.popleft()
                y,x =  s[0],s[1]
                c = tmp_field[y][x]
                for k in range(4):
                    newy = y + dy[k]
                    newx = x + dx[k]
                    if 0<= newy < h and 0<= newx < w:
                        if field[newy][newx] == "#":
                            ans = max(ans,c+1)
                            break
                        elif tmp_field[newy][newx] == 0:
                            tmp_field[newy][newx] = c+1
                            q.append((newy,newx))
                else:
                    continue
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = list(list(input()) for _ in range(H))

    que = deque([])
    maze = [[f_inf] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if grid[h][w] == "#":
                que.append([h, w])
                maze[h][w] = 0

    while que:
        h, w = que.popleft()
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_h, next_w = h + dh, w + dw
            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            if maze[next_h][next_w] > maze[h][w] + 1:
                maze[next_h][next_w] = maze[h][w] + 1
                que.append([next_h, next_w])

    res = 0
    for h in range(H):
        for w in range(W):
            res = max(res, maze[h][w])
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = list(list(input()) for _ in range(H))

    res = 0
    while True:
        NEXT = set()
        cnt = 0
        for h in range(H):
            for w in range(W):
                if grid[h][w] == "#":
                    cnt += 1
                    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                        next_h, next_w = h + dh, w + dw
                        if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                            continue
                        if grid[next_h][next_w] == ".":
                            NEXT.add((next_h, next_w))
        if cnt == H * W:
            break

        for next_h, next_w in NEXT:
            grid[next_h][next_w] = "#"
        res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

dx = [0,1,0,-1]
dy = [1,0,-1,0]

H, W = map(int, input().split())

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

if len(black_deque) == H*W:
    print(0)
    exit(0)

for x,y in black_deque:
    A[x][y] = 0

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    if x+1 < H and A[x+1][y]=='.':
        black_deque.append((x+1, y))
        A[x+1][y] = depth+1
    if 0 <= x-1 and A[x-1][y]=='.':
        black_deque.append((x-1, y))
        A[x-1][y] = depth+1
    if y+1 < W and A[x][y+1]=='.':
        black_deque.append((x, y+1))
        A[x][y+1] = depth+1
    if 0 <= y-1 and A[x][y-1]=='.':
        black_deque.append((x, y-1))
        A[x][y-1] = depth+1

    tansaku = [(x+dx[k], y+dy[k]) for k in range(4)
        if 0 <= x+dx[k] < H and
           0 <= y+dy[k] < W and
           A[x+dx[k]][y+dy[k]] == '.'
    ]
    for new_x,new_y in tansaku:
        black_deque.append((new_x, new_y))
        A[new_x][new_y] = depth+1

print(depth)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

dx = [0,1,0,-1]
dy = [1,0,-1,0]

H, W = map(int, input().split())

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

if len(black_deque) == H*W:
    print(0)
    exit(0)

for x,y in black_deque:
    A[x][y] = 0

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    tansaku = [(x+dx[k], y+dy[k]) for k in range(4)
        if 0 <= x+dx[k] < H and
           0 <= y+dy[k] < W and
           A[x+dx[k]][y+dy[k]] == '.'
    ]
    for new_x,new_y in tansaku:
        black_deque.append((new_x, new_y))
        A[new_x][new_y] = depth+1

print(depth)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

dx = [0,1,0,-1]
dy = [1,0,-1,0]

H, W = map(int, input().split())

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

for x,y in black_deque:
    A[x][y] = 0

n_white = H*W-len(black_deque)
while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    tansaku = [(x+dx[k], y+dy[k]) for k in range(4)
        if 0 <= x+dx[k] < H and
           0 <= y+dy[k] < W and
           A[x+dx[k]][y+dy[k]] == '.'
    ]
    for new_x,new_y in tansaku:
        black_deque.append((new_x, new_y))
        n_white -= 1
        A[new_x][new_y] = depth+1
        if n_white == 0:
            print(depth+1)
            exit(0)

print(depth)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

dx = [0,1,0,-1]
dy = [1,0,-1,0]

H, W = map(int, input().split())

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

for x,y in black_deque:
    A[x][y] = 0

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    tansaku = [(x+dx[k], y+dy[k]) for k in range(4)
        if 0 <= x+dx[k] < H and
           0 <= y+dy[k] < W and
           A[x+dx[k]][y+dy[k]] == '.'
    ]
    for new_x,new_y in tansaku:
        black_deque.append((new_x, new_y))
        A[new_x][new_y] = depth+1

print(depth)