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:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===

def main():
    h, w = ns()
    table = [list(input()) for _ in range(h)]
    not_visited = [[True for _ in range(w)] for __ in range(h)]
    dist = [[INF for _ in range(w)] for __ in range(h)]

    que = collections.deque()
    for hi in range(h):
        for wi in range(w):
            if table[hi][wi] == "#":
                not_visited[hi][wi] = False
                dist[hi][wi] = 0
                que.append([hi, wi])

    nxt = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    cnt = -1
    ans = 0
    while len(que):
        cnt += 1
        for i in range(len(que)):
            hi, wi = que.popleft()
            for yi, xi in nxt:
                th = hi + yi
                tw = wi + xi
                if -1 < th < h and -1 < tw < w:
                    if not_visited[th][tw]:
                        not_visited[th][tw] = False
                        dist[th][tw] = min(dist[th][tw], dist[hi][wi] + 1)
                        que.append([th, tw])

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
H, W = map(int, input().split())

matrix = []

visited = set()

for i in range(H):
    matrix.append(list(input()))

que = deque([])

for i in range(H):
    for j in range(W):
        if matrix[i][j] == '#' and (i, j) not in visited:
            visited.add((i, j))
            for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#' or (i+ud, j+lr) in visited:
                    continue
                que.append((i+ud, j+lr))

res = 0

while que:
    res += 1
    for k in range(len(que)):
        i, j = que.popleft()
        visited.add((i, j))
        for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#' or (i+ud, j+lr) in visited:
                continue
            que.append((i+ud, j+lr))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
H, W = map(int, input().split())

matrix = []

visited = set()

for i in range(H):
    matrix.append(list(input()))

que = deque([])

for i in range(H):
    for j in range(W):
        if matrix[i][j] == '#' and (i, j) not in visited:
            visited.add((i, j))
            for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#':
                    continue
                que.append((i+ud, j+lr))

res = 0

while que:
    for k in range(len(que)):
        i, j = que.popleft()
        if (i, j) in visited:
            continue
        visited.add((i, j))
        for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#':
                continue
            que.append((i+ud, j+lr))
    if que:
        res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())

matrix = []

visited = set()

for i in range(H):
    matrix.append(list(input()))

visited = set()

for i in range(H):
    for j in range(W):
        if matrix[i][j] == '#' and (i, j) not in visited:
            for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#':
                    continue
                visited.add((i+ud, j+lr))
                matrix[i+ud][j+lr] = '#'

res = 0

while visited:
    res += 1
    buf = set()
    for i, j in visited:
        if matrix[i][j] == '#' and (i, j) not in buf:
            for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#':
                    continue
                buf.add((i+ud, j+lr))
                matrix[i+ud][j+lr] = '#'
    if not buf:
        break
    visited = buf

print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())

matrix = []

res = 0

visited = set()

for i in range(H):
    matrix.append(list(input()))

while True:
    visited = set()
    count = 0
    for i in range(H):
        for j in range(W):
            if matrix[i][j] == '#' and (i, j) not in visited:
                for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '#':
                        continue
                    visited.add((i+ud, j+lr))
                    matrix[i+ud][j+lr] = '#'
                    count += 1
    if count == 0:
        break
    res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w=map(int, input().split())
a = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
black = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black.append((i,j))
            visited[i][j] = 0

queue = deque(black)


while queue:
    y,x = queue.popleft()
    dydx = [[1,0],[-1,0],[0,1],[0,-1]]
    for j,k in dydx:
        newy,newx = y+j,x+k 
        if newy < 0 or newy >= h:continue 
        if newx < 0 or newx >= w:continue 
        if visited[newy][newx] == -1:
            visited[newy][newx] = visited[y][x] + 1
            queue.append((newy,newx))

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
# 壁あり
A = [['#'] * (w + 2)] +  [['#'] + list(input()) + ['#'] for _ in range(h)] + [['#'] * (w + 2)]

from copy import deepcopy

dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
cnt = 0
while True:
    cnt_white = sum([e.count('.') for e in A])
    if cnt_white == 0:
        break
    B = deepcopy(A)
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if A[i][j] == '#':
                for x, y in dxdy:
                    B[i + x][j + y] = '#'
    A = deepcopy(B)
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
A = [list(input()) for _ in range(h)]
V = [[-1]*w for _ in range(h)]
que = deque([])
for i,a in enumerate(A):
    for j,_a in enumerate(a):
        if _a == '#':
            que.append([i,j])
            V[i][j] = 0
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
while que:
    nwh,nww = que.popleft()
    for dh, dw in dhdw:
        if not (0<=nwh+dh<h and 0<=nww+dw<w): continue
        if V[nwh+dh][nww+dw] != -1: continue
        V[nwh+dh][nww+dw] = V[nwh][nww]+1
        que.append([nwh+dh, nww+dw])
print(max(map(max, V)))

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import deque

H, W = (int(x) for x in input().split())

MAP = []
for i in range(H):
    MAP.append([0 if x == "#" else -1 for x in input()])

que = deque()
for i in range(H):
    for j in range(W):
        if MAP[i][j] == 0:
            que.append((i, j))

ret = -1
while(len(que) > 0):
    i, j = que.popleft()
    curVal = MAP[i][j]
    ret = max(ret, curVal)
    for di, dj in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        next_i = i + di
        next_j = j + dj
        if next_i < 0 or next_j < 0 or next_i >= H or next_j >= W:
            continue

        next_val = MAP[next_i][next_j] 
        if next_val != -1 and next_val <= curVal + 1:
            continue

        MAP[next_i][next_j] = curVal + 1
        que.append((next_i, next_j))

print(ret)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import deque

H, W = (int(x) for x in input().split())


MAP = []
for i in range(H):
    MAP.append([0 if x == "#" else -1 for x in input()])

que = deque()
for i in range(H):
    for j in range(W):
        if MAP[i][j] == 0:
            que.append((i, j))

ret = -1
while(len(que) > 0):
    i, j = que.popleft()
    ret = max(ret, MAP[i][j])
    for di, dj in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        next_i = i + di
        next_j = j + dj
        if next_i < 0 or next_j < 0 or next_i >= H or next_j >= W:
            continue

        next_val = MAP[next_i][next_j] 
        if next_val != -1 and next_val <= MAP[i][j] + 1:
            continue

        MAP[next_i][next_j] = MAP[i][j] + 1
        que.append((next_i, next_j))

print(ret)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8

H, W = (int(x) for x in input().split())


MAP = []
for i in range(H):
    MAP.append([0 if x == "#" else -1 for x in input()])

que = []
for i in range(H):
    for j in range(W):
        if MAP[i][j] == 0:
            que.append((i, j))
ret = -1
while(len(que) > 0):
    i, j = que.pop(0)
    ret = max(ret, MAP[i][j])
    for di, dj in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        next_i = i + di
        next_j = j + dj
        if next_i < 0 or next_j < 0 or next_i >= H or next_j >= W:
            continue

        next_val = MAP[next_i][next_j] 
        if next_val != -1 and next_val <= MAP[i][j] + 1:
            continue

        MAP[next_i][next_j] = MAP[i][j] + 1
        que.append((next_i, next_j))

print(ret)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append((i,j))
            dist[i][j] = 0
while d:
    x,y = d.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                ans = max(ans,dist[nx][ny])
                d.append((nx,ny))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                ans = max(ans,dist[nx][ny])
                d.append([nx,ny])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,dist[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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


def neighbors(ih, iw):
    for ih1, iw1 in (
        (ih + 1, iw),
        (ih - 1, iw),
        (ih, iw - 1),
        (ih, iw + 1),
    ):
        if 0 <= ih1 < h and 0 <= iw1 < w:
            yield (ih1, iw1)


queue = []  # black cells
for ih, iw in product(range(h), range(w)):
    if grid[ih][iw] == "#":
        queue.append((ih, iw))


filled = [[False] * w for _ in range(h)]  # h * w
n_step = -1

while queue:
    n_step += 1
    queue_next = []
    while queue:
        ih0, iw0 = queue.pop()
        grid[ih0][iw0] = "#"
        for ih1, iw1 in neighbors(ih0, iw0):
            if grid[ih1][iw1] == ".":
                queue_next.append((ih1, iw1))
    queue = queue_next


print(n_step)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt, pi
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
maze = [input() for i in range(H)]

black = []
dp = [[float('inf')] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            black.append((i, j))
            dp[i][j] = 0

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

def blacker(sy, sx):
    pos = deque([[sy, sx]])
    while len(pos) > 0:
        y, x = pos.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < W and 0 <= ny < H and dp[ny][nx] > dp[y][x] + 1:
                dp[ny][nx] = dp[y][x] + 1
                pos.append([ny, nx])

for a, b in black:
    blacker(a, b)

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
used = [[False] * (w+2) for _ in range(h+2)]
for r in range(h+2):
    used[r][0] = True
    used[r][-1] = True
for c in range(w+2):
    used[0][c] = True
    used[-1][c] = True
que = deque([])
for r in range(h):
    line = input()
    for c in range(w):
        if line[c] == "#":
            que.append((r+1, c+1, 0))
            used[r+1][c+1] = 0
neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
while que:
    r, c, k = que.popleft()
    for dr, dc in neighbors:
        nr, nc = r+dr, c+dc
        if not used[nr][nc]:
            que.append((nr, nc, k+1))
            used[nr][nc] = True
print(k)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
used = [[False] * (w+2) for _ in range(h+2)]
for r in range(h+2):
    used[r][0] = True
    used[r][-1] = True
for c in range(w+2):
    used[0][c] = True
    used[-1][c] = True
que = deque([])
for r in range(h):
    line = input()
    for c in range(w):
        if line[c] == "#":
            que.append((r+1, c+1, 0))
            used[r+1][c+1] = 0
neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
while que:
    r, c, k = que.popleft()
    for dr, dc in neighbors:
        nr, nc = r+dr, c+dc
        if not used[nr][nc]:
            que.append((nr, nc, k+1))
            used[nr][nc] = True
print(k)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def solve(h, w, a):
    used = [[False] * (w+2) for _ in range(h+2)]
    for r in range(h+2):
        used[r][0] = True
        used[r][-1] = True
    for c in range(w+2):
        used[0][c] = True
        used[-1][c] = True
    que = deque([])
    for r in range(h):
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
                used[r+1][c+1] = 0
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k

h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def solve(h, w, a):
    used = [[False] * (w+2) for _ in range(h+2)]
    for r in range(h+2):
        used[r][0] = True
        used[r][-1] = True
    for c in range(w+2):
        used[0][c] = True
        used[-1][c] = True
    que = deque([])
    for r in range(h):
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
                used[r+1][c+1] = 0
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k

h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

def solve(h, w, a): 
    dist = np.full((h, w), -1, dtype=int)
    que = deque([])
    for r in range(h):
        for c in range(w):
            if a[r][c] == "#":
                que.append((r, c, 0)) 
                dist[r, c] = 0 
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if (0 <= nr < h) and (0 <= nc < w) and (dist[nr, nc] == -1):
                que.append((nr, nc, k+1))
                dist[nr, nc] = k+1 
    return np.max(dist)

h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))

Submission status: Time Limit Exceeded

Solution code:
import copy

h,w = map(int,input().split())
#a = [input() for _ in range(h)]
a = [list(input()) for _ in range(h)]
b = [[False]*w for _ in range(h)]
c = []
d = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = True
            c.append((i,j))

while True:
    tmp = []
    cnt = 0
    for i,j in c:
        for d1,d2 in d:
            if 0 <= i + d1 < h and 0 <= j + d2 < w:
                if not b[i+d1][j+d2]:
                    tmp.append((i+d1, j+d2))
                    b[i+d1][j+d2] = True
                    cnt += 1
    if cnt > 0:
        c = copy.deepcopy(tmp)
        ans += 1
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

h,w = map(int,input().split())
#a = [input() for _ in range(h)]
a = [list(input()) for _ in range(h)]
#b = [[False]*w for _ in range(h)]
c = []
d = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0

"""
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = True
            c.append((i,j))
"""

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            c.append((i,j))

while True:
    tmp = []
    cnt = 0
    for i,j in c:
        for d1,d2 in d:
            if 0 <= i + d1 < h and 0 <= j + d2 < w:
                #if not b[i+d1][j+d2]:
                if a[i+d1][j+d2] == '.':
                    tmp.append((i+d1, j+d2))
                    #b[i+d1][j+d2] = True
                    a[i+d1][j+d2] = '#'
                    cnt += 1
    if cnt > 0:
        c = copy.deepcopy(tmp)
        ans += 1
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

h,w = map(int,input().split())
a = [input() for _ in range(h)]
b = [[False]*w for _ in range(h)]
c = []
d = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = True
            c.append((i,j))

while True:
    tmp = []
    cnt = 0
    for i,j in c:
        for d1,d2 in d:
            if 0 <= i + d1 < h and 0 <= j + d2 < w:
                if not b[i+d1][j+d2]:
                    tmp.append((i+d1, j+d2))
                    b[i+d1][j+d2] = True
                    cnt += 1
    if cnt > 0:
        c = copy.deepcopy(tmp)
        ans += 1
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import copy

    h,w = map(int,input().split())
    a = [input() for _ in range(h)]
    b = [[False]*w for _ in range(h)]
    c = []
    d = [(-1,0), (1,0), (0,-1), (0,1)]
    ans = 0

    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                b[i][j] = True
                c.append((i,j))

    while True:
        tmp = []
        for i,j in c:
            for d1,d2 in d:
                if 0 <= i + d1 < h and 0 <= j + d2 < w:
                    if not b[i+d1][j+d2]:
                        tmp.append((i+d1, j+d2))
                        b[i+d1][j+d2] = True
        if tmp:
            c = copy.deepcopy(tmp)
            ans += 1
        else:
            break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

h,w = map(int,input().split())
a = [input() for _ in range(h)]
b = [[False]*w for _ in range(h)]
c = []
d = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = True
            c.append((i,j))

while True:
    tmp = []
    for i,j in c:
        for d1,d2 in d:
            if 0 <= i + d1 < h and 0 <= j + d2 < w:
                if not b[i+d1][j+d2]:
                    tmp.append((i+d1, j+d2))
                    b[i+d1][j+d2] = True
    if tmp:
        c = copy.deepcopy(tmp)
        ans += 1
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

import numpy as np

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h, w in zip(*np.where(A == "#")):
        dist[h, w] = 0
        queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if not (0 <= next_h < H and 0 <= next_w < W):
                continue
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))

    return dist.max()


def main():
    H, W = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=str)
    for i in range(H):
        A[i] = list(input().rstrip())

    dist = np.full(shape=(H, W), fill_value=-1, dtype=np.int32)
    ans = bfs(H, W, A, dist)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                dist[h][w] = 0
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if not (0 <= next_h < H and 0 <= next_w < W):
                continue
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))


def main():
    H, W = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = input().rstrip()

    dist = [[-1] * W for _ in range(H)]
    bfs(H, W, A, dist)

    ans = max(map(max, dist))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def check(MAP):
	white = 0
	H = len(MAP)
	for i in range(H):
		white += MAP[i].count('.')
		if white != 0:
			break

	if white != 0:
		return 0
	else:
		return 1


def conv(S,index,c):
	lstS = list(S)
	lstS[index] = c
	S = ''.join(lstS)

	return S


def DFS(stack,MAP,size,count):
	if check(MAP) == 1:
		return count
	else:
		newstack = []
		for p in stack:
			y = p[0]
			x = p[1]
			Y = size[0]
			X = size[1]
			if y != 0:
				if MAP[y-1][x] == '.':
					MAP[y-1] = conv(MAP[y-1],x,'#')
					newstack.append([y-1,x])
			if y != Y-1:
				if MAP[y+1][x] == '.':
					MAP[y+1] = conv(MAP[y+1],x,'#')
					newstack.append([y+1,x])
			if x != 0:
				if MAP[y][x-1] == '.':
					MAP[y] = conv(MAP[y],x-1,'#')
					newstack.append([y,x-1])
			if x != X-1:
				if MAP[y][x+1] == '.':
					MAP[y] = conv(MAP[y],x+1,'#')
					newstack.append([y,x+1])

		return DFS(newstack,MAP,size,count+1)


if __name__ == '__main__':
	H, W = map(int, input().split())

	MAP = []
	stack = []

	for y in range(H):
		IN = input() 
		MAP.append(IN)

	for y in range(H):
		for x in range(W):
			c = 0
			if MAP[y][x] == '#':
				if y != 0:
					if MAP[y-1][x] == '.':
						c = 1
				if y != H-1:
					if MAP[y+1][x] == '.':
						c = 1
				if x != 0:
					if MAP[y][x-1] == '.':
						c = 1
				if x != W-1:
					if MAP[y][x+1] == '.':
						c = 1

				if c == 1:
					stack.append([y,x])

	step = DFS(stack,MAP,[H,W],0)

	print(step)

Submission status: Time Limit Exceeded

Solution code:
def check(MAP):
	white = 0
	H = len(MAP)
	for i in range(H):
		white += MAP[i].count('.')
		if white != 0:
			break

	if white != 0:
		return 0
	else:
		return 1


def conv(S,index,c):
	lstS = list(S)
	lstS[index] = c
	S = ''.join(lstS)

	return S
	

def DFS(stack,MAP,size,count):
	if check(MAP) == 1:
		return count
	else:
		newstack = []
		for p in stack:
			y = p[0]
			x = p[1]
			Y = size[0]-1
			X = size[1]-1
			if y != 0:
				if MAP[y-1][x] == '.':
					MAP[y-1] = conv(MAP[y-1],x,'#')
					newstack.append([y-1,x])
			if y != Y:
				if MAP[y+1][x] == '.':
					MAP[y+1] = conv(MAP[y+1],x,'#')
					newstack.append([y+1,x])
			if x != 0:
				if MAP[y][x-1] == '.':
					MAP[y] = conv(MAP[y],x-1,'#')
					newstack.append([y,x-1])
			if x != X:
				if MAP[y][x+1] == '.':
					MAP[y] = conv(MAP[y],x+1,'#')
					newstack.append([y,x+1])

		return DFS(newstack,MAP,size,count+1)


if __name__ == '__main__':
	H, W = map(int, input().split())

	MAP = []
	stack = []

	for y in range(H):
		IN = input() 
		MAP.append(IN)

	for y in range(H):
		for x in range(W):
			if MAP[y][x] == '#':
				stack.append([y,x])

	step = DFS(stack,MAP,[H,W],0)

	print(step)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
from collections import *
h,w=map(int,input().split())
a=[]
l=[(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    t=list(input())
    a.append(t)
ans=[[float("inf")]*w for i in range(h)]
v=[[False for j in range(w)] for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            ans[i][j]=0
            q.append((i,j))
aa=0
while q:
    x,y=q.popleft()
    for xx,yy in l:
        nx,ny=x+xx,y+yy
        if 0<=nx<h and 0<=ny<w:
            if v[nx][ny]:
                continue
            v[nx][ny]=True
            if ans[nx][ny]>ans[x][y]+1:
                ans[nx][ny]=ans[x][y]+1
                if ans[nx][ny]>aa:
                    aa=ans[nx][ny]
                if (nx,ny) not in q:
                    q.append((nx,ny))
print(aa)