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 copy

H, W = map(int, input().split())
A = [[0 for i in range(W)]for j in range(H)]
white_num = 0
for i in range(H):
    S = input()
    for j in range(W):
        A[i][j] = S[j]
        if A[i][j] == '.':
            white_num += 1

ans = 0
while white_num > 0:
    A_ = copy.deepcopy(A)
    ans += 1
    for y in range(H):
        for x in range(W):
            if A[y][x] == ".":
                continue
            if A[y][x] == "#":
                for k in range(4):
                    nx = x + [1, 0, -1, 0][k]
                    ny = y + [0, 1, 0, -1][k]
                    if nx < 0 or ny < 0 or nx >= W or ny >= W:
                        continue
                    if A[ny][nx] == "#":
                        continue
                    if A[ny][nx] == "." and A_[ny][nx] == ".":
                        A_[ny][nx] = "#"
                        white_num -= 1
    A = A_
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
m = [['#'] * (w+2)]
for j in range(h):
    m.append(['#'])
    m[j+1].extend([i for i in input()]) #スペース区切りならinput().split()
    m[j+1].append('#')
m.append(['#'] * (w+2))

todo = []
for i in range(1, h+1):
    for j in range(1, w+1):
        if m[i][j] == '#':
            todo.append([i, j])
            m[i][j] = 0
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

while(todo != []):
    a = todo.pop(0) #First Out
    for i in range(4):
        if m[a[0]+dx[i]][a[1]+dy[i]] == '.':
            todo.append([a[0]+dx[i], a[1]+dy[i]])
            m[a[0]+dx[i]][a[1]+dy[i]] = m[a[0]][a[1]] + 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
l = ''
part = []
for i in range(h):
    part.append(input())
    l += part[i]

def stror(l, m, n, o, p):
    q = ''
    for i in range(h*w):
        if any([l[i]=='#', m[i]=='#', n[i]=='#', o[i]=='#', p[i]=='#']):
            q += '#'
        else:
            q += '.'
    return q

ans = 0
while(l != '#' * h * w):
    left = ''
    right = ''
    for i in part:
        left += i[1:] + '.'
        right += '.' + i[:-1]
    up = l[w:] + '.' * w
    down = '.' * w + l[:-w]
    l = stror(l, left, right, up, down)
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]

directions = [[-1,0],[1,0],[0,-1],[0,1]]

D = [[-1]*W for i in range(H)]

B = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            B.append([i,j])
            D[i][j] = 0

q = deque(B)

while q:
    nh,nw= q.pop()
    for dh,dw in directions:
        if not (0<= nh+dh < H and 0 <= nw+dw < W):
            continue
        elif D[nh+dh][nw+dw] != -1:
            continue
        elif A[nh+dh][nw+dw] == '#':
            D[nh+dh][nw+dw] = D[nh][nw]
            q.append([nh+dh,nw+dw])
        elif A[nh+dh][nw+dw] == '.':
            D[nh+dh][nw+dw] = D[nh][nw]+1
            q.appendleft([nh+dh,nw+dw])

print(max(max(D[i]) for i in range(H)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs():
    global ans
    while q:
        p = q.popleft()
        for u in v:
            x, y = p[0] + u[0], p[1] + u[1]
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] == -1:
                    s[x][y] = s[p[0]][p[1]] + 1
                    q.append([x, y])
                    ans = max(ans, s[x][y])
    return

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
s = [[-1] * w for _ in range(h)]
v = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            s[i][j] = 0
            q.append([i, j])
bfs()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
inf = 10 ** 7

def bfs(sx, sy):
    d = [[inf for _ in range(w)] for _ in range(h)]
    d[sx][sy] = 0
    que = deque()
    que.append((sx, sy))

    while que:
        px, py = que.popleft()
        if a[px][py] == '#':
            return d[px][py]
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            qx, qy = px + dx, py + dy
            if 0 <= qx < h and 0 <= qy < w:
                if d[qx][qy] > d[px][py] + 1:
                    d[qx][qy] = d[px][py] + 1
                    que.append((qx, qy))

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            ans = max(ans, bfs(i, j))

print(ans)

Submission status: Time Limit Exceeded

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

q=deque()
dist=[[-1]*(W+1) for a in range(H+1)]
G=[['#']*(W+1) for _ in range(H+1)]
for i in range(1,H+1):
    G_comp=list(str(input()))
    for j in range(1,W+1):
        if G_comp[j-1]=='#':
            q.append((i,j))
            dist[i][j]=0
        G[i][j]=G_comp[j-1]

def sur(v):  #v is tuple
    vx=v[0]
    vy=v[1]
    preE=[(vx-1,vy),(vx+1,vy),(vx,vy-1),(vx,vy+1)]
    E=[]
    for nv in preE:
        if 1<=nv[0]<=H and 1<=nv[1]<=W:
            if G[nv[0]][nv[1]]=='.':
                E.append(nv)
    return E

while q:
    now=q.popleft()
    for next in sur(now):
        if dist[next[0]][next[1]]!=-1:
            continue
        q.append(next)
        dist[next[0]][next[1]]=dist[now[0]][now[1]]+1

M=[]
for k in range(1,H+1):
    M.append(max(dist[k]))

print(max(M))

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=['' for i in range(0,H)]
for i in range(0,H):
    s=input()
    A[i]=[s[j] for j in range(0,W)]

ans=0
q=set([])
for i in range(0,H):
    for j in range(0,W):
        if A[i][j]=='#':
            q.add((i,j))

sub=set([])
while q:
    while q:
        i,j=q.pop()
        if i!=H-1 and A[i+1][j]=='.':
            A[i+1][j]="#"
            sub.add((i+1,j))
        if i!=0 and A[i-1][j]=='.':
            A[i-1][j]="#"
            sub.add((i-1,j))
        if j!=W-1 and A[i][j+1]=='.':
            A[i][j+1]="#"
            sub.add((i,j+1))
        if j!=0 and A[i][j-1]=='.':
            A[i][j-1]="#"
            sub.add((i,j-1))

        if (not q) and sub:
            q=sub
            sub=set([])
            ans+=1
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def mbfs(S,H,W,d):
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        x=d[0][2]
        d.popleft()
        for di in range(4):
            nh=h+dx[di]
            nw=w+dy[di]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(S[nh][nw]=='#'):
                continue
            S[nh][nw]='#'
            d.append([nh,nw,x+1])
    return x
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
d=deque()
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            d.append([i,j,0])
print(mbfs(A,H,W,d))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def mbfs(S,H,W,sh,sw):
    dist[sh][sw]=0
    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for di in range(4):
            nh=h+dx[di]
            nw=w+dy[di]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if((dist[nh][nw]!=-1 and dist[nh][nw]<dist[h][w]+1) or S[nh][nw]=='#'):
                continue
            dist[nh][nw]=dist[h][w]+1
            d.append([nh,nw])
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
dist=[[-1]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            mbfs(A,H,W,i,j)
print(max(max(dist[i]) for i in range(H)))

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(input())

import queue
todo = queue.Queue()
seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            todo.put((x, y))
            seen[y][x] = True


seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
last = 0
while not todo.empty():
    x, y = todo.get()
    #print(x, y)
    for i in range(4):
        if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
            if seen[y + dy[i]][x + dx[i]] == False:
                route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                last = route[y + dy[i]][x + dx[i]]
                seen[y + dy[i]][x + dx[i]] = True
                todo.put((x + dx[i], y + dy[i]))

#print(seen)
#print(route)
print(last)
# M = 0
# for y in range(W):
#     for x in range(H):
#         M = max(M, route[y][x])
# print(M)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(input())

import queue
todo = queue.Queue()
seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            todo.put((x, y))
            seen[y][x] = True


seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
last = 0
def bfs(el):
    global last
    x, y = el
    #print(x, y)
    for i in range(4):
        if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
            if seen[y + dy[i]][x + dx[i]] == False:
                route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                last = route[y + dy[i]][x + dx[i]]
                seen[y + dy[i]][x + dx[i]] = True
                todo.put((x + dx[i], y + dy[i]))
    if not todo.empty():
        bfs(todo.get())
    else:
        return None
bfs(todo.get())
#print(seen)
#print(route)
print(last)
# M = 0
# for y in range(W):
#     for x in range(H):
#         M = max(M, route[y][x])
# print(M)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(input())

import queue
todo = queue.Queue()
seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            todo.put((x, y))
            seen[y][x] = True


seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def bfs(el):
    x, y = el
    #print(x, y)
    for i in range(4):
        if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
            if seen[y + dy[i]][x + dx[i]] == False:
                route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                seen[y + dy[i]][x + dx[i]] = True
                todo.put((x + dx[i], y + dy[i]))
    if not todo.empty():
        bfs(todo.get())
    else:
        return None
bfs(todo.get())
#print(seen)
#print(route)

M = 0
for y in range(W):
    for x in range(H):
        M = max(M, route[y][x])
print(M)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(input())
import queue
todo = queue.Queue()
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            exist = True
            todo.put((x, y))

seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def bfs(el):
    x, y = el
    #print(x, y)
    seen[y][x] = True
    for i in range(4):
        if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
            if seen[y + dy[i]][x + dx[i]] == False and A[y + dy[i]][x + dx[i]] == '.':
                route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                seen[y + dy[i]][x + dx[i]] = True
                todo.put((x + dx[i], y + dy[i]))
    if not todo.empty():
        bfs(todo.get())
    else:
        return None
bfs(todo.get())
#print(seen)
#print(route)

M = 0
for y in range(W):
    for x in range(H):
        M = max(M, route[y][x])
print(M)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H,W=map(int,input().split())
A=[[c for c in l.strip()] for l in sys.stdin]
maze=[[3000]*W for i in range(H)]
q=deque([])
start=[]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    if(A[i][j]=="#"):
      q.append((i,j))
#print(start)
x=0
y=maze[:]

for i in q:
  maze[i[0]][i[1]]=0
while(q):
  c=q.popleft()
  for j in range(4):
    if(c[0]+dy[j]>=0 and c[0]+dy[j]<H and c[1]+dx[j]>=0 and c[1]+dx[j]<W):
      if(maze[c[0]+dy[j]][c[1]+dx[j]]==3000 and A[c[0]+dy[j]][c[1]+dx[j]]=="."):
        q.append((c[0]+dy[j],c[1]+dx[j]))
        maze[c[0]+dy[j]][c[1]+dx[j]]=maze[c[0]][c[1]]+1
        
        x=max(x,maze[c[0]+dy[j]][c[1]+dx[j]])
print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H,W=map(int,input().split())
A=[[c for c in l.strip()] for l in sys.stdin]
maze=[[3000]*W for i in range(H)]
q=deque([])
start=[]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    if(A[i][j]=="#"):
      start.append((i,j))
#print(start)
x=0
y=maze[:]
for i in start:
  maze=[[3000]*W for i in range(H)]
  q.append(i)
  maze[i[0]][i[1]]=0
  while(q):
    c=q.popleft()
    y[c[0]][c[1]]=min(y[c[0]][c[1]],maze[c[0]][c[1]])
    for j in range(4):
      if(c[0]+dy[j]>=0 and c[0]+dy[j]<H and c[1]+dx[j]>=0 and c[1]+dx[j]<W):
        if(maze[c[0]+dy[j]][c[1]+dx[j]]==3000 and A[c[0]+dy[j]][c[1]+dx[j]]=="."):
          q.append((c[0]+dy[j],c[1]+dx[j]))
          maze[c[0]+dy[j]][c[1]+dx[j]]=maze[c[0]][c[1]]+1
          
          #y=max(y,maze[c[0]+dy[j]][c[1]+dx[j]])

for i in range(H):
  x=max(x,max(y[i]))
print(x)

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
a = []
for i in range(h):
    a.append(list(ins()))
q = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
cnt = 0
#ddprint(a)
#ddprint(q)
while len(q)>0:
    qq = []
    while len(q)>0:
        i,j = q.pop()
        for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            x = i+dx
            y = j+dy
            if 0<=x<h and 0<=y<w and a[x][y]=='.':
                a[x][y] = '#'
                qq.append((x,y))
    q = qq
    if len(q)>0:
        cnt += 1
    #ddprint(a)
    #ddprint(q)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# 長い間考えて分からなかったけど、ようやく方針が分かった。
# 始点を複数にした幅優先探索
# 距離1の点をキューに入れる、
# 距離1の点を出しながら距離2の点をキューに入れる、
# 以下略。でできるじゃん。

h, w = list(map(int, input().split()))

masu = [input() for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

distance = [[-1 for _ in range(w)] for _ in range(h)]

from collections import deque

queue = deque([])
for i in range(h):
    for j in range(w):
        if masu[i][j] == '#':
            distance[i][j] = 0
            queue.append((i, j))

ans = 0
while True:
    if len(queue) == 0:
        break
    now = queue.popleft()
    now_h = now[0]
    now_w = now[1]
    now_distance = distance[now_h][now_w]
    # print(now_h, now_w)

    for i in range(4):
        next_h = now_h + dx[i]
        next_w = now_w + dy[i]
        if not (0 <= next_h <= h-1 and 0 <= next_w <= w-1):
            continue
        if distance[next_h][next_w] == -1:
            distance[next_h][next_w] = now_distance + 1
            queue.append((next_h, next_w))
            ans = now_distance + 1
            # print("appended {} {}".format(next_h, next_w))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
visited=[[-1]*w for _ in range(h)]
queue=deque()
for i in range(h):
  for j in range(w):
    if a[i][j]=='#':
      visited[i][j]=0
      queue.append([i,j])
while queue:
  y,x=queue.popleft()
  for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
    n_y,n_x=y+j,x+k
    if 0<=n_y<h and 0<=n_x<w and a[n_y][n_x]=='.' and visited[n_y][n_x]<0:
      visited[n_y][n_x]=visited[y][x]+1
      queue.append([n_y,n_x])
ans=0
for l in visited:
  ans=max([ans]+l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def penetrate(x, y, count):
    global max_idx
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = count + 1
            q.append((nx, ny, d[nx][ny]))
            max_idx = max(max_idx, d[nx][ny])


h, w = map(int, input().split())
d = [[-1] * w for _ in range(h)]

A = [[] for i in range(h)]
q = deque()

for i in range(h):
    A[i] = list(input())
    for j in range(w):
        if A[i][j] == "#":
            d[i][j] = 0
            q.append((i, j, d[i][j]))

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

while len(q) > 0:
    idx = q.popleft()
    penetrate(idx[0], idx[1], idx[2])

print(max_idx)

Submission status: Time Limit Exceeded

Solution code:
import queue

def penetrate(x, y, count):
    global max_idx
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = count + 1
            q.put((nx, ny, d[nx][ny]))
            max_idx = max(max_idx, d[nx][ny])


h, w = map(int, input().split())
d = [[-1] * w for _ in range(h)]

A = [[] for i in range(h)]
q = queue.Queue()

for i in range(h):
    A[i] = list(input())
    for j in range(w):
        if A[i][j] == "#":
            d[i][j] = 0
            q.put((i, j, d[i][j]))

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

while q.empty() == False:
    idx = q.get()
    penetrate(idx[0], idx[1], idx[2])

print(max_idx)

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy as np

def penetrate(x, y, count):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = count + 1
            q.put((nx, ny, d[nx][ny]))


h, w = map(int, input().split())
d = [[-1] * w for _ in range(h)]

A = [[] for i in range(h)]
q = queue.Queue()

for i in range(h):
    A[i] = list(input())
    for j in range(w):
        if A[i][j] == "#":
            d[i][j] = 0
            q.put((i, j, d[i][j]))

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

while q.empty() == False:
    idx = q.get()
    penetrate(idx[0], idx[1], idx[2])

print(np.max(d))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def penetrate(x, y, idx):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = idx + 1


h, w = map(int, input().split())
d = [[-1] * w for _ in range(h)]

A = [[] for i in range(h)]

for i in range(h):
    A[i] = list(input())
    for j in range(w):
        if A[i][j] == "#":
            d[i][j] = 0

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

idx = 0
while True:
    count = 0
    for i in range(h):
        for j in range(w):
            if d[i][j] == idx:
                penetrate(i, j, idx)
            if d[i][j] == -1:
                count += 1
    idx += 1
    if count == 0:
        break

print(np.max(d))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]

Q = deque()
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            A[h][w]="."
            Q.append((0,h,w))
ans = 0
while Q:
    cnt,h,w = Q.popleft()
    if min(h,w)<0 or h>=H or w>=W:continue
    if A[h][w]=="#":continue
    A[h][w] = "#"
    ans = max(cnt,ans)
    for i in [-1,1]:
        Q.append((cnt+1,h+i,w))
        Q.append((cnt+1,h,w+i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque 
import sys
input = sys.stdin.readline
def main():
    q = deque([])
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    x=[[-1,0],[1,0],[0,-1],[0,1]]
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                for k in x:
                    if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                        a[i+k[0]][j+k[1]]="0"
                        q.append([i+k[0],j+k[1],1])
    ans=0
    while q:
        v=q.popleft()
        for k in x:
            if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
                a[v[0]+k[0]][v[1]+k[1]]="0"
                q.append([v[0]+k[0],v[1]+k[1],v[2]+1])
                ans=v[2]+1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A=[list('X'+input()+'X') for i in range(H)]
A.append('X'*(W+2))
A.insert(0,'X'*(W+2))
d=[[0,1],[0,-1],[1,0],[-1,0]]
wnum=0
blis=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]=='.':
            wnum+=1
        if A[i][j]=='#':
            blis.append([i,j])

if wnum==0:
    print(0)
    exit()

ans=0
wtob=0
while len(blis):
    ans+=1
    nblis=[]
    for p in blis:
        for v in d:
            ny=p[0]+v[0]
            nx=p[1]+v[1]
            if A[ny][nx]=='.':
                A[ny][nx]='#'
                nblis.append([ny,nx])
                wtob+=1
    if wtob==wnum:
        print(ans)
        exit()
    blis=[]
    for i in nblis:
        blis.append(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]
min_step_map = [[10**6]*Width for _ in range(Height)]
research_point = deque()

# Find the minimum number of steps from all blacks.
# The maximum number of the obtained minimum steps is the answer.
def search_min_step():
    while len(research_point) > 0:
        y_now, x_now = research_point.popleft()
        
        for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
            y_next, x_next = y_now+dy, x_now+dx
            if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
                continue
            
            if Map[y_next][x_next] == '#' or \
               min_step_map[y_next][x_next] <= min_step_map[y_now][x_now]:
                continue
            else:
                min_step_map[y_next][x_next] = min_step_map[y_now][x_now] + 1
                research_point.append([y_next, x_next])

for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '#':
            min_step_map[y][x] = 0
            research_point.append([y, x])

search_min_step()

max_step = 0
for y in range(Height):
    max_step = max(max_step, max(min_step_map[y]))

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]
min_step_map = [[10**6]*Width for _ in range(Height)]

# Find the minimum number of steps from all blacks.
# The maximum number of the obtained minimum steps is the answer.
def search_min_step(y_start, x_start):
    compare_step_map = [[0]*Width for _ in range(Height)]
    compare_step_map[y_start][x_start] = 0
    min_step_map[y_start][x_start] = 0

    research_point = deque()
    research_point.append([y_start, x_start])
    while len(research_point) > 0:
        y_now, x_now = research_point.popleft()
        
        for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
            y_next, x_next = y_now+dy, x_now+dx
            if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
                continue

            compare_step_map[y_next][x_next] = compare_step_map[y_now][x_now]+1
            if Map[y_next][x_next] == '#' or \
               min_step_map[y_next][x_next] <= compare_step_map[y_next][x_next]:
                continue
            else:
                min_step_map[y_next][x_next] = compare_step_map[y_next][x_next]
                research_point.append([y_next, x_next])

for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '#':
            search_min_step(y, x)

max_step = 0
for y in range(Height):
    max_step = max(max_step, max(min_step_map[y]))

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]
min_step_map = [[10**6]*Width for _ in range(Height)]

# Find the minimum number of steps from all blacks.
# The maximum number of the obtained minimum steps is the answer.
def search_min_step(y_start, x_start):
    compare_step_map = [[0]*Width for _ in range(Height)]
    compare_step_map[y_start][x_start] = 0
    min_step_map[y_start][x_start] = 0

    research_point = deque()
    research_point.append([y_start, x_start])
    while len(research_point) > 0:
        y_now, x_now = research_point.popleft()
        
        for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
            y_next, x_next = y_now+dy, x_now+dx
            if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
                continue

            compare_step_map[y_next][x_next] = compare_step_map[y_now][x_now]+1
            if min_step_map[y_next][x_next] <= compare_step_map[y_next][x_next]:
                continue
            else:
                min_step_map[y_next][x_next] = compare_step_map[y_next][x_next]
                research_point.append([y_next, x_next])

for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '#':
            search_min_step(y, x)

max_step = 0
for y in range(Height):
    max_step = max(max_step, max(min_step_map[y]))

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = list(map(int,input().split()))
s = [[x for x in input()] for _ in range(h)]
b = deque([])
for i in range(h):
  for j in range(w):
    if s[i][j] == '#':
      s[i][j] = 0
      b.append([i,j])
    if s[i][j] == '.':
      s[i][j] = 1

dh = [1,0,-1,0]
dw = [0,1,0,-1]

def rev(b):
  cnt = 0
  nb = deque([])
  for p in b:
    for i in range(4):
      nh = p[0] + dh[i]
      nw = p[1] + dw[i]
      
      if nh >=0 and nh < h and nw >=0 and nw < w and s[nh][nw]==1:
        s[nh][nw] = 0
        nb.append([nh,nw])
  return nb
cnt = 0
while sum([sum(x) for x in s]) > 0:
  b = rev(b)
  cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = list(map(int,input().split()))
s = [[x for x in input()] for _ in range(h)]

def find_w():
  for i in range(h):
    for j in range(w):
      if s[i][j] == '.':
        return True

def find_b():
  b = deque([])
  for i in range(h):
    for j in range(w):
      if s[i][j] == '#':
        b.append([i,j])
  return b

dh = [1,0,-1,0]
dw = [0,1,0,-1]

def rev():
  que = find_b()
  for b in que:
    for i in range(4):
      nh = b[0] + dh[i]
      nw = b[1] + dw[i]
      if nh >=0 and nh < h and nw >=0 and nw < w:
        s[nh][nw] = '#'

cnt = 0
while  find_w():
  rev()
  cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = list(map(int,input().split()))
s = [[x for x in input()] for _ in range(h)]

def find_w():
  for i in range(h):
    for j in range(w):
      if s[i][j] == '.':
        return True

def find_b():
  b = deque([])
  for i in range(h):
    for j in range(w):
      if s[i][j] == '#':
        b.append([i,j])
  return b

d = [[float('inf') for _ in range(w)] for _ in range(h)]
def bfs():
  que = deque([])
  que.extend(find_b())
  dh = [1,0,-1,0]
  dw = [0,1,0,-1]
  while que:
    p = que.pop()
    for i in range(4):
      nh = p[0] + dh[i]
      nw = p[1] + dw[i]
      
      if nh >= 0 and nh < h and nw >= 0 and nw < w and \
          s[nh][nw] == '.' and d[nh][nw] == float('inf'):
        s[nh][nw] = '#'

cnt = 0
while find_w():
  bfs()
  cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = list(map(int,input().split()))
s = [[x for x in input()] for _ in range(h)]

def find_w():
  for i in range(h):
    for j in range(w):
      if s[i][j] == '.':
        return True

def find_b():
  b = deque([])
  for i in range(h):
    for j in range(w):
      if s[i][j] == '#':
        b.append([i,j])
  return b

d = [[float('inf') for _ in range(w)] for _ in range(h)]
def bfs():
  que = deque([])
  que.extend(find_b())
  dh = [1,0,-1,0]
  dw = [0,1,0,-1]
  while que:
    p = que.popleft()
    for i in range(4):
      nh = p[0] + dh[i]
      nw = p[1] + dw[i]
      
      if nh >= 0 and nh < h and nw >= 0 and nw < w and \
          s[nh][nw] == '.' and d[nh][nw] == float('inf'):
        s[nh][nw] = '#'

cnt = 0
while find_w():
  bfs()
  cnt += 1

print(cnt)