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())
a = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]  # 黒ならdist[i][j]は0、白なら-1

black_cells = deque()

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

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h_black, w_black = black_cells.popleft()
        d=dist[h_black][w_black]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h_black+dy
            new_w = w_black+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 max(sum(dist,[]))

d = bfs(black_cells, dist)
print(d)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
L=[]
for h in range(H):
    l=list(input())
    L.append(l)
D=[(1,0),(0,1),(-1,0),(0,-1)]
ans=[[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if L[h][w]==".":
            que=[(h,w)]
            done=[]
            flag=False
            while len(que)>0:
                nowh,noww=que.pop(0)
                for d in D:
                    dh,dw=d
                    newh=nowh+dh
                    neww=noww+dw
                    if 0<=newh<H and 0<=neww<W:
                        if L[newh][neww]=="#":
                            ans[h][w]=abs(newh-h)+abs(neww-w)
                            flag=True
                            break
                        elif ((newh,neww) not in done):
                            que.append((newh,neww))
                            done.append((newh,neww))
                if flag:
                    break
A=0
for h in range(H):
    for w in range(W):
        a=ans[h][w]
        if a!="#":
            A=max(A, a)
print(A)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
L=[]
for h in range(H):
    l=list(input())
    L.append(l)
D=[(1,0),(0,1),(-1,0),(0,-1)]
ans=[[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if L[h][w]==".":
            que=[(h,w)]
            done=[]
            flag=False
            while len(que)>0:
                nowh,noww=que.pop(0)
                for d in D:
                    dh,dw=d
                    newh=nowh+dh
                    neww=noww+dw
                    if 0<=newh<H and 0<=neww<W:
                        if L[newh][neww]=="#":
                            ans[h][w]=abs(newh-h)+abs(neww-w)
                            flag=True
                            break
                        elif ((newh,neww) not in done):
                            que.append((newh,neww))
                            done.append((newh,neww))
                if flag:
                    break
import numpy as np
ans=np.array(ans)
print(ans.max())

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
L=[]
for h in range(H):
    l=list(input())
    L.append(l)
D=[(1,0),(0,1),(-1,0),(0,-1)]
ans=L.copy()
for h in range(H):
    for w in range(W):
        if L[h][w]==".":
            que=[(h,w)]
            done=[]
            flag=False
            while len(que)>0:
                nowh,noww=que.pop(0)
                for d in D:
                    dh,dw=d
                    newh=nowh+dh
                    neww=noww+dw
                    if 0<=newh<H and 0<=neww<W:
                        if L[newh][neww]=="#":
                            ans[h][w]=abs(newh-h)+abs(neww-w)
                            flag=True
                            break
                        elif ((newh,neww) not in done):
                            que.append((newh,neww))
                            done.append((newh,neww))
                if flag:
                    break
a=0
for h in range(H):
    for w in range(W):
        if ans[h][w]!="#":
            a=max(a, ans[h][w])
print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
a,b=map(int,input().split())
List=[]
q=deque([[0,0]])
for i in range(a):
  l=list(input())
  for _ in range(b):
    if l[_]=="#":
      q.append([i,_])
      l[_]=0
  List.append(l)
q.popleft()
aaa=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
while q:
  h,w=q.popleft()
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
        if List[h+x][w+y]>ans:
          ans=List[h+x][w+y]
print(ans)

Submission status: Time Limit Exceeded

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

H,W = list(map(int, input().split()))
matrix = [ list(readline()) for _ in range(H) ]
black = deque([])
seen = [ [False]*W for _ in range(H)]
for ri,m in enumerate(matrix):
  for ci,j in enumerate(matrix[ri]):
    if j == "#":
      black.append((ri,ci))
      seen[ri][ci] = True

cnt = 0
while black:
  cnt += 1

  new_black = deque([])
  for i in range(len(black)):
    r,c = black[i]
    seen[r][c] = True

    for y,x in [(1,0),(-1,0),(0,1),(0,-1)]:
      nr,nc = r+y,c+x
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if seen[nr][nc] or seen[nr][nc] == "#" or (nr,nc) in new_black: continue
      matrix[nr][nc] = "#"
      seen[r][c] = True
      new_black.append((nr,nc))

  black = new_black

print(cnt-1)

Submission status: Time Limit Exceeded

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

H,W = list(map(int, input().split()))
matrix = [ list(readline()) for _ in range(H) ]
black = deque([])
seen = [ [False]*W for _ in range(H)]
for ri,m in enumerate(matrix):
  for ci,j in enumerate(matrix[ri]):
    if j == "#":
      black.append((ri,ci))
      seen[ri][ci] = True

cnt = 0
while black:
  cnt += 1

  new_black = deque([])
  for i in range(len(black)):
    r,c = black.popleft()
    seen[r][c] = True

    for y,x in [(1,0),(-1,0),(0,1),(0,-1)]:
      nr,nc = r+y,c+x
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if seen[nr][nc] or seen[nr][nc] == "#" or (nr,nc) in new_black: continue
      matrix[nr][nc] = "#"
      seen[r][c] = True
      new_black.append((nr,nc))

  black = new_black

print(cnt-1)

Submission status: Time Limit Exceeded

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

H,W = list(map(int, input().split()))
matrix = []
black = deque([])
white = 0
for i in range(H):
  row = list(readline().rstrip())
  matrix.append(row)

  for j in range(W):
    if row[j] == "#":
      black.append((i,j))
    else:
      white += 1

cnt = 0
seen = [ [False]*W for _ in range(H)]
while black:
  cnt += 1
  if white == 0: break
  for i in range(len(black)):
    r,c = black.popleft()
    seen[r][c] = True
    if white == 0: break

    for y,x in [(1,0),(-1,0),(0,1),(0,-1)]:
      nr,nc = r+y,c+x
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if seen[nr][nc] or seen[nr][nc] == "#" or (nr,nc) in black: continue
      matrix[nr][nc] = "#"
      seen[r][c] = True
      white -= 1
      black.append((nr,nc))
      if white == 0: break

print(cnt-1)

Submission status: Time Limit Exceeded

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

H,W = list(map(int, input().split()))
matrix = []
black = deque([])
white = 0
for i in range(H):
  row = list(readline().rstrip())
  matrix.append(row)

  for j in range(W):
    if row[j] == "#":
      black.append((i,j))
    else:
      white += 1

cnt = 0
seen = [ [False]*W for _ in range(H)]
while black:
  cnt += 1
  if white == 0: break
  for i in range(len(black)):
    r,c = black.popleft()
    seen[r][c] = True
    if white == 0: break

    for y,x in [(1,0),(-1,0),(0,1),(0,-1)]:
      nr,nc = r+y,c+x
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if seen[nr][nc] or seen[nr][nc] == "#" or (nr,nc) in black: continue
      matrix[nr][nc] = "#"
      white -= 1
      black.append((nr,nc))
      if white == 0: break

print(cnt-1)

Submission status: Time Limit Exceeded

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

H,W = list(map(int, input().split()))
matrix = []
black = deque()
white = 0
for i in range(H):
  row = list(readline().rstrip())
  matrix.append(row)

  for j in range(W):
    if row[j] == "#":
      black.append((i,j))
    else:
      white += 1

cnt = 0
seen = [ [False]*W for _ in range(H)]
while black:
  cnt += 1  
  for i in range(len(black)):
    r,c = black.popleft()
    seen[r][c] = True

    for y,x in [(1,0),(-1,0),(0,1),(0,-1)]:
      nr,nc = r+y,c+x
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if seen[nr][nc] or seen[nr][nc] == "#" or (nr,nc) in black: continue
      matrix[nr][nc] = "#"
      black.append((nr,nc))

print(cnt-1)

Submission status: Time Limit Exceeded

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

H,W = list(map(int, input().rstrip().split()))
A_list = [list(input().rstrip()) for i in range(H)]
#-----

def check(matrix):
    for i in range(len(matrix)):
        matrix[i] = ["#"] + matrix[i][:] + ["#"]
    
    matrix = [["#"]*(W+2)] + matrix[:] + [["#"]*(W+2)]
    
    
    # queue = [ (row, column) ]
    # deque = [ (int, int   ) ]
    queue = deque()
    
    for i in range(1,H+1):
        for j in range(1, W+1):
            if matrix[i][j] == "#":
                queue.append( (i, j) )
    
    
    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    step = -1
    
    while queue:
        step += 1
        
        for _ in range(len(queue)):
            r,c = queue.popleft()
            
            for d in delta:
                next_r = r + d[0]
                next_c = c + d[1]
                
                if matrix[next_r][next_c] == ".":
                    matrix[next_r][next_c] = "#"
                    queue.append( (next_r, next_c) )


    return step

#-----

ans = check(A_list)
print(ans)

Submission status: Time Limit Exceeded

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

H,W = list(map(int, input().rstrip().split()))
A_list = [list(input().rstrip()) for i in range(H)]
#-----

def check(matrix):
    # queue = [ ( (row, column),step ) ]
    # deque = [ ( (int, int   ),int ) ]
    queue = deque()
    
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == "#":
                queue.append(  ( (i, j), 0 )  )
    
    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    max_step = 0
    
    while queue:
        (r,c),step = queue.popleft()
        
        for d in delta:
            next_r = r + d[0]
            next_c = c + d[1]
            
            if (0 <= next_r < H) and (0 <= next_c < W) and \
               matrix[next_r][next_c] == ".":
            
                matrix[next_r][next_c] = "#"
                queue.append( ( (next_r, next_c), step+1 ) )
                max_step = max(max_step, step+1)


    return max_step
#-----

ans = check(A_list)
print(ans)

Submission status: Time Limit Exceeded

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

H,W = list(map(int, input().rstrip().split()))
A_list = [list(input().rstrip()) for i in range(H)]
#-----

def check(matrix):
    # queue = [ ( (row, column),step ) ]
    # deque = [ ( (int, int   ),int ) ]
    queue = deque()
    
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == "#":
                queue.append(  ( (i, j), 0 )  )
    
    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    visited = set()
    max_step = 0
    
    while queue:
        (r,c),step = queue.popleft()
        
        for d in delta:
            next_r = r + d[0]
            next_c = c + d[1]
            
            if (0 <= next_r < H) and (0 <= next_c < W) and \
               (next_r, next_c) not in visited  and \
               matrix[next_r][next_c] == ".":
            
                matrix[next_r][next_c] = "#"
                queue.append( ( (next_r, next_c), step+1 ) )
                visited.add( (next_r, next_c) )
                max_step = max(max_step, step+1)


    return max_step
#-----

ans = check(A_list)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
    
h,w = (int(x) for x in input().split())
ab = []
step = []
count = 0
for i in range(h):
    a = list(input())
    ab.append(a+['#'])
    for j in range(w):
        if a[j] == '#':
            step.append([i,j])

ab.append(list('#'*w))           

dp = [[0 for a in range(w)] for b in range(h)]
 
while len(step) > 0:
    y, x = step.pop(0)
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1

mx = max(list(itertools.chain.from_iterable(dp)))
 
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
    
h,w = (int(x) for x in input().split())
ab = []
step = []
count = 0
for i in range(h):
    a = list(input())
    ab.append(a+['#'])
    for j in range(w):
        if a[j] == '#':
            step.append([i,j])

ab.append(list('#'*w))           
memo_step = copy.deepcopy(step)

dp = [[0 for a in range(w)] for b in range(h)]
 
while len(step) > 0:
    y, x = step.pop(0)
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1

for i,j in memo_step:
    dp[i][j] = 0

mx = max(list(itertools.chain.from_iterable(dp)))
 
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
    
h,w = (int(x) for x in input().split())
ab = []
step = []
count = 0
for i in range(h):
    a = list(input())
    ab.append(a+['#'])
    for j in range(w):
        if a[j] == '#':
            step.append([i,j])

ab.append(list('#'*w))           
memo_step = copy.deepcopy(step)

dp = [[0 for a in range(w)] for b in range(h)]
 
while len(step) > 0:
    y, x = step.pop(0)
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 and -1 < x < w and -1 < y < h :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 and -1 < x < w and -1 < y < h :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 and -1 < x < w and -1 < y < h :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 and -1 < x < w and -1 < y < h :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1

for i,j in memo_step:
    dp[i][j] = 0

mx = max(list(itertools.chain.from_iterable(dp)))
 
print(mx)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            A[i][j] = 0
        else:
            A[i][j] = -1


def chg(i, j, c):
    if i < 0 or j < 0 or H <= i or W <= j: return False
    if A[i][j] >= 0:
        return False

    A[i][j] = c
    return True


def f(c):
    edit = 0
    for i in range(H):
        for j in range(W):
            if 0 <= A[i][j] < c:
                A[i][j] = c
                edit |= chg(i - 1, j, c)
                edit |= chg(i + 1, j, c)
                edit |= chg(i, j - 1, c)
                edit |= chg(i, j + 1, c)
    return edit


ans = 0
while 1:
    if f(ans + 1):
        ans += 1
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            A[i][j] = 0
        else:
            A[i][j] = -1


def chg(i, j, c):
    if i < 0 or j < 0 or H <= i or W <= j: return
    A[i][j] = A[i][j] if A[i][j] >= 0 else c


def f(c):
    for i in range(H):
        for j in range(W):
            if 0 <= A[i][j] < c:
                A[i][j] = c
                chg(i - 1, j, c)
                chg(i + 1, j, c)
                chg(i, j - 1, c)
                chg(i, j + 1, c)


def chk():
    for i in range(H):
        for j in range(W):
            if A[i][j] == -1: return False
    return True


ans = 0
while 1:
    if chk():
        break
    ans += 1
    f(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

INF = 10 ** 9

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

s = []
d = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            s.append((i, j))
        else:
            d.append((i, j))

ans = 0
for di in d:
    m = INF
    for si in s:
        m = min(m, abs(di[0] - si[0]) + abs(di[1] - si[1]))
    ans = max(ans, m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]


def f():
    B = [['.'] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                B[i][j] = '#'
                if i > 0:
                    B[i - 1][j] = '#'
                if j > 0:
                    B[i][j - 1] = '#'
                if i < H - 1:
                    B[i + 1][j] = '#'
                if j < W - 1:
                    B[i][j + 1] = '#'
    return B


def c():
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.': return False
    return True


ans = 0
while 1:
    if c():
        break
    ans += 1
    A = f()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int, input().split())
dydx = [[0,1], [1,0], [0,-1],[-1,0]]

qu = deque()
q=[]
grid=[]
for i in range(h):
    s=list(input().rstrip())
    for j in range(w):
        if s[j]=="#":
            q.append([j,i])
    grid.append(s)
qu.append(q)
ans=0
def ok(x, y):
    if x>-1 and y>-1 and x<w and y<h and grid[y][x]!="#":
        return 1
    else:
        return 0
while q:
    b = qu.pop()
    q=[]
    for xy in b:
        for d in dydx:
            if ok(xy[1]+d[1], xy[0]+d[0]):
                q.append([xy[0]+d[0],xy[1]+d[1]])
                grid[xy[0]+d[0]][xy[1]+d[1]]="#"
    if len(q)==0:
        break
    qu.append(q)
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for i in range(h)]
search = deque([(i, j) for i in range(h) for j in range(w) if a[i][j] == '#'])
d = [[0 if a[i][j] == '#' else -1 for j in range(w)] for i in range(h)]

def bfs(search):
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and d[ni][nj] < 0:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

print(bfs(search))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for i in range(h)]
search = deque([(i, j) for i in range(h) for j in range(w) if a[i][j] == '#'])
d = [[-1] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            d[i][j] = 0

def bfs(search):
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and d[ni][nj] < 0:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

print(bfs(search))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for i in range(h)]
search = deque()
d = [[-1] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            search.append((i, j))
            d[i][j] = 0

def bfs(search):
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and d[ni][nj] < 0:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

print(bfs(search))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for i in range(h)]
search = deque()
d = [[-1] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            search.append((i, j))
            d[i][j] = 0

def bfs(search):
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and a[ni][nj] == '.' and d[ni][nj] < 0:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

print(bfs(search))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for i in range(h)]
black = deque()
INF = -1
d = [[-1] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black.append((i, j))
            d[i][j] = 0

def bfs(black):
    search = black
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and a[ni][nj] == '.' and d[ni][nj] < 0:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

print(bfs(black))

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)]
black = deque()
INF = -1
d = [[-1] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black.append((i, j))
            d[i][j] = 0

def bfs(black):
    search = black
    while search:
        i, j = search.popleft()
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < h and 0 <= nj < w and a[ni][nj] == '.' and d[ni][nj] < 0:
                search.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

print(bfs(black))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
  h,w=map(int,input().split())
  a=[input() for _ in range(h)]
  seen=[[-1]*w for _ in range(h)]
  from collections import deque
  todo=deque([])
  for hi,ai in enumerate(a):
    for wj,aij in enumerate(ai):
      if aij=='#':
        seen[hi][wj]=0
        todo.append((hi,wj,0))
  while len(todo)>0:
    hi,wi,i=todo.popleft()
    if hi>0 and seen[hi-1][wi]==-1:
      todo.append((hi-1,wi,i+1))
      seen[hi-1][wi]=i+1
    if hi<h-1 and seen[hi+1][wi]==-1:
      todo.append((hi+1,wi,i+1))
      seen[hi+1][wi]=i+1
    if wi>0 and seen[hi][wi-1]==-1:
      todo.append((hi,wi-1,i+1))
      seen[hi][wi-1]=i+1
    if wi<w-1 and seen[hi][wi+1]==-1:
      todo.append((hi,wi+1,i+1))
      seen[hi][wi+1]=i+1
  print(i)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(dist, black, H, W):
    q = deque(black)

    res = 0
    while q:
        h, w = q.pop()

        for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if dist[nh][nw] == -1:
                    dist[nh][nw] = dist[h][w] + 1
                    if res < dist[nh][nw]:
                        res = dist[nh][nw]
                    q.appendleft((nh, nw))

    return res


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    black = []
    dist = [[-1] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                black.append((h, w))
                dist[h][w] = 0

    ans = bfs(dist, black, H, W)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[input() for _ in range(h)]

seen=[[-1]*w for _ in range(h)]
from collections import deque
todo=deque([])
for hi in range(h):
  for wi in range(w):
    if a[hi][wi]=='#':
      seen[hi][wi]=0
      todo.append((hi,wi,0))
while len(todo)>0:
  hi,wi,i=todo.popleft()
  if hi>0 and seen[hi-1][wi]==-1:
    todo.append((hi-1,wi,i+1))
    seen[hi-1][wi]=i+1
  if hi<h-1 and seen[hi+1][wi]==-1:
    todo.append((hi+1,wi,i+1))
    seen[hi+1][wi]=i+1
  if wi>0 and seen[hi][wi-1]==-1:
    todo.append((hi,wi-1,i+1))
    seen[hi][wi-1]=i+1
  if wi<w-1 and seen[hi][wi+1]==-1:
    todo.append((hi,wi+1,i+1))
    seen[hi][wi+1]=i+1
print(max([max(seeni) for seeni in seen]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
H,W=map(int,input().split())
A=[]
for i in range(H):
    a=list(input())
    A.append(a)
#多点スタートな最短路問題
q=deque()
dist=[[-1 for _ in range(W)]for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            dist[i][j]=0
            q.append([i,j])

dx=[1,0,-1,0]
dy=[0,1,0,-1]
while(len(q)):
    h,w=q.popleft()
    #print(h,w)
    #print(q)
    for i in range(4):
        y=h+dy[i]
        x=w+dx[i]
        if (y<0)or(y>=H)or(x<0)or(x>=W):
            continue
        if dist[y][x]==-1:
            dist[y][x]=dist[h][w]+1
            q.append([y,x])
ans=0
#print(dist)
for i in range(len(dist)):
    ans=max(ans,max(dist[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
H,W=map(int,input().split())
A=[]
for i in range(H):
    a=list(input())
    A.append(a)
#多点スタートな最短路問題
q=deque()
dist=[[-1 for _ in range(W)]for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            dist[i][j]=0
            q.append([i,j])

dx=[1,0,-1,0]
dy=[0,1,0,-1]
while(len(q)):
    h,w=q.popleft()
    #print(h,w)
    #print(q)
    for i in range(4):
        y=h+dy[i]
        x=w+dx[i]
        if (y<0)or(y>=H)or(x<0)or(x>=W):
            continue
        if dist[y][x]==-1:
            dist[y][x]=dist[h][w]+1
            q.append([y,x])
ans=0
#print(dist)
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:
H,W=map(int,input().split())
A=[]
for i in range(H):
    a=list(input())
    A.append(a)

white=[]
black=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            cnt=0
            if (i+1)<H:
                if A[i+1][j]=="#":
                    cnt+=1
            if (i-1)>=0:
                if A[i-1][j]=="#":
                    cnt+=1
            if (j+1)<W:
                if A[i][j+1]=="#":
                    cnt+=1
            if (j-1)>=0:
                if A[i][j-1]=="#":
                    cnt+=1
            if cnt==4:
                pass
            else:
                black.append([i,j])
        else:
            white.append([i,j])
ans=0
for h,w in white:
    val=10**10
    for i,j in black:
        val1=abs(h-i)+abs(w-j)
        val=min(val,val1)
    ans=max(ans,val)

print(ans)

Submission status: Time Limit Exceeded

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

b_y = deque()
b_x = deque()
for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      b_y.append(i)
      b_x.append(j)
      a[i][j] = 0

d = [[1,0], [-1, 0], [0,-1], [0,1]]
while b_y:
  for y,x in d:
    if 0 <= b_y[0]+y <= h-1 and 0 <= b_x[0]+x <= w-1 and a[b_y[0]+y][b_x[0]+x] == ".":
      a[b_y[0]+y][b_x[0]+x] = a[b_y[0]][b_x[0]]+1
      b_y.append(b_y[0]+y)
      b_x.append(b_x[0]+x)
  b_y.popleft()
  b_x.popleft()

ans = 0
for v in a:
  if max(v) > ans: ans = max(v)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[input() for _ in range(h)]

ans = [ [ 12345678 for _ in range(w) ] for d in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            ans[i][j] = 0

for i in range(h):
    for j in range(1,w):
        ans[i][j] = min(ans[i][j], ans[i][j-1]+1)
    for j in range(w-1-1,-1,-1):
        ans[i][j] = min(ans[i][j],ans[i][j+1]+1)

for j in range(w):
    for i in range(1,h):
        ans[i][j] = min(ans[i][j], ans[i-1][j]+1)
    for i in range(h-1-1,-1,-1):
        ans[i][j] = min(ans[i][j], ans[i+1][j]+1)

ma =-4
for x in ans:
    for y in x:
        ma = max(ma,y)
print(ma)

Submission status: Time Limit Exceeded

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
H,W = inputlist()
graph = [0]*H
for i in range(H):
    graph[i] = list(input())
from collections import deque
que = deque()
seen = [[False]*W for _ in range(H)]
li = []
for x in range(H):
    for y in range(W):
        if graph[x][y] == '#':
            tp = (x,y)
            li.append(tp)
que.append(li)
dx = [1,0,-1,0]
dy = [0,1,0,-1]
count = 0
while len(que) != 0:
    l = que.popleft()
    lis = []
    for tup in l:
        xa = tup[0]
        ya = tup[1]
        for i in range(4):
            nx = xa + dx[i]
            ny = ya + dy[i]
            if nx >= H or ny >= W or nx < 0 or ny < 0:
                continue
            if graph[nx][ny] == '#':
                continue
            graph[nx][ny] = '#'
            lis.append((nx,ny))
    count+=1
    if len(lis) == 0:
        print(count-1)
        exit()
    que.append(lis)