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:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
cost_map = [[None]*W for i in range(H)]
starts = list()
for x in range(H):
    for y in range(W):
        if map[x][y]=="#":
            for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
                if 0<=nx<H and 0<=ny<W:
                    if map[nx][ny]==".":
                        break
            else:
                continue
            starts.append([x, y])
for sx, sy in starts:
    queue = [[sx, sy]]
    cost_map[sx][sy] = 0
    while queue:
        x, y = queue.pop(0)
        current = cost_map[x][y]
        for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
            if 0<=nx<H and 0<=ny<W:
                if cost_map[nx][ny] is None:
                    cost_map[nx][ny] = current + 1
                    queue.append([nx, ny])
                elif current+1 < cost_map[nx][ny]:
                    cost_map[nx][ny] = current + 1
                    queue.append([nx, ny])
if cost_map[0][0] is None:
    print(0)
    exit()
result = 0
for i in range(H):
    for j in range(W):
        if cost_map[i][j]>result:
            result = cost_map[i][j]
print(result)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
cost_map = [[None]*W for i in range(H)]
# 迷路を最初のマス目の数だけ解く
starts = list()
for x in range(H):
    for y in range(W):
        if map[x][y]=="#":
            starts.append([x, y])
for sx, sy in starts:
    queue = [[sx, sy]]
    cost_map[sx][sy] = 0
    while queue:
        x, y = queue.pop(0)
        current = cost_map[x][y]
        for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
            if 0<=nx<H and 0<=ny<W:
                if cost_map[nx][ny] is None:
                    cost_map[nx][ny] = current + 1
                    queue.append([nx, ny])
                elif current+1 < cost_map[nx][ny]:
                    cost_map[nx][ny] = current + 1
                    queue.append([nx, ny])
result = 0
for i in range(H):
    for j in range(W):
        if cost_map[i][j]>result:
            result = cost_map[i][j]
print(result)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
queue = list()
for x in range(H):
    for y in range(W):
        if map[x][y]=="#":
            queue.append([x, y])
count = -1
while queue:
    next_queue = list()
    for x, y in queue:
        for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
            if 0<=nx<H and 0<=ny<W:
                if map[nx][ny]==".":
                    map[nx][ny] = "#"
                    next_queue.append([nx, ny])
    queue = next_queue
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
queue = list()
for x in range(H):
    for y in range(W):
        if map[x][y]=="#":
            queue.append([x, y])
def check_all_black():
    checktext = "".join(["".join(l) for l in map])
    if "." in checktext:
        return False
    else:
        return True
count = 0
if check_all_black():
    print(count)
    exit()
while queue:
    next_queue = list()
    for x, y in queue:
        for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
            if 0<=nx<H and 0<=ny<W:
                if map[nx][ny]==".":
                    map[nx][ny] = "#"
                    next_queue.append([nx, ny])
    queue = next_queue
    count += 1
    if check_all_black():
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
queue = list()
for x in range(H):
    for y in range(W):
        if map[x][y]=="#":
            queue.append([x, y])
def check_all_black():
    global map
    for x in range(H):
        for y in range(W):
            if map[x][y]==".":
                break
        else:
            continue
        break
    else:
        return True
    return False
count = 0
if check_all_black():
    print(count)
    exit()
while queue:
    next_queue = list()
    for x, y in queue:
        for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
            if 0<=nx<H and 0<=ny<W:
                if map[nx][ny]==".":
                    map[nx][ny] = "#"
                    next_queue.append([nx, ny])
    queue = next_queue
    count += 1
    if check_all_black():
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    H,W = map(int,input().split())
    masu = [list(input()) for _ in range(H)]
    def bfs():
        que = deque()
        seen = [[0]*(W+2)] + [[0] + [1]*(W)+[0]  for _ in range(H)] +[[0]*(W+2)] 
        for w in range(W):
            for h in range(H):
                if masu[h][w] == '#':
                    que.append((w,h,0))
                    seen[h+1][w+1] =0
        while que:
            a,b,k = que.popleft()
            for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
                nx = a+x
                ny = b+y
                if seen[ny+1][nx+1]:
                    seen[ny+1][nx+1] = 0
                    que.append((nx,ny,k+1))
        return k
    print(bfs())
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
masu = [list(input()) for _ in range(H)]
from collections import deque
def bfs():
    que = deque()
    seen = [[0]*(W+2)] + [[0] + [1]*(W)+[0]  for _ in range(H)] +[[0]*(W+2)] 
    for w in range(W):
        for h in range(H):
            if masu[h][w] == '#':
                que.append((w,h,0))
                seen[h+1][w+1] =0
    while que:
        a,b,k = que.popleft()
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = a+x
            ny = b+y
            if seen[ny+1][nx+1]:
                seen[ny+1][nx+1] = 0
                que.append((nx,ny,k+1))
    return k
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
masu = [list(input()) for _ in range(H)]
from collections import deque
def bfs():
    que = deque()
    seen = [[0]*(W+2)] + [[0] + [-1]*(W)+[0]  for _ in range(H)] +[[0]*(W+2)] 
    for w in range(W):
        for h in range(H):
            if masu[h][w] == '#':
                que.append((w,h))
                seen[h+1][w+1] =0
    while que:
        a,b = que.popleft()
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = a+x
            ny = b+y
            if seen[ny+1][nx+1] == -1:
                seen[ny+1][nx+1] = seen[b+1][a+1]+1
                que.append((nx,ny))
    ans = max(map(max,seen))
    return ans
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
masu = [list(input()) for _ in range(H)]
from collections import deque
def bfs():
    que = deque([])
    seen = [[0]*(W+2)] + [[0] + [float('inf')]*(W)+[0]  for _ in range(H)] +[[0]*(W+2)] 
    for w in range(W):
        for h in range(H):
            if masu[h][w] == '#':
                que.append((w,h))
                seen[h+1][w+1] =0
    while que:
        a,b = que.popleft()
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = a+x
            ny = b+y
            if seen[ny+1][nx+1] == float('inf') and masu[ny][nx] == '.':
                seen[ny+1][nx+1] = seen[b+1][a+1] +1
                que.append((nx,ny))
    ans = 0
    for i in range(H+2):
        for j in range(W+2):
            if seen[i][j] > ans:
                ans = seen[i][j]
    return ans
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
masu = [list(input()) for _ in range(H)]
from collections import deque
def bfs():
    que = deque([])
    seen = [[float('inf')]*W for _ in range(H)]
    for w in range(W):
        for h in range(H):
            if masu[h][w] == '#':
                que.append((w,h))
                seen[h][w] =0
    while que:
        a,b = que.popleft()
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = a+x
            ny = b+y
            if 0<=nx<W and 0<=ny<H and seen[ny][nx] == float('inf') and masu[ny][nx] != '#':
                seen[ny][nx] = seen[b][a] +1
                que.append((nx,ny))
    ans = 0
    for i in range(H):
        for j in range(W):
            if seen[i][j] > ans:
                ans = seen[i][j]
    return ans
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    R,C = NMI()
    #sy, sx = NMI()
    #gy, gx = NMI()
    board = [list(input()) for _ in range(R)]
    
    ans = 0

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

    #すべての点をINFで初期化
    INF = R*C*2
    distance = [[INF for _ in range(C)] for _ in range(R)]

    #地点を保存するqueを作成
    que = deque([])
    
    #スタート地点を取り出す
    for r in range(R):
        for c in range(C):
            if board[r][c] == '#':
                que.append((r,c))
                #スタート地点の距離は0
                distance[r][c] = 0

    #queが空になるまでループ
    while len(que) != 0:
        #取り出してきた状態
        pop = que.popleft()

        #移動4方向をループ
        for i in range(len(dx)):
            #移動した後の点をny,nxとする
            ny = pop[0]+dy[i]
            nx = pop[1]+dx[i]

            #nyが0以上R未満   nxが0以上C未満   まだ訪れたことがない
            if 0<= ny < R and 0 <= nx < C and distance[ny][nx] == INF:
                #つまり移動可能でまだ行ったことがなければqueへ入れる
                que.append((ny,nx))
                #その距離をもとのpopの最短距離+1でdistanceに記録
                distance[ny][nx] = distance[pop[0]][pop[1]]+1
                if ans < distance[ny][nx]:
                    ans = distance[ny][nx]
                
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    R,C = NMI()
    #sy, sx = NMI()
    #gy, gx = NMI()
    board = [list(input()) for _ in range(R)]


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

    #すべての点をINFで初期化
    INF = R*C*2
    distance = [[INF for _ in range(C)] for _ in range(R)]

    #地点を保存するqueを作成
    que = deque([])
    
    #スタート地点を取り出す
    for r in range(R):
        for c in range(C):
            if board[r][c] == '#':
                que.append((r,c))
                #スタート地点の距離は0
                distance[r][c] = 0

    #queが空になるまでループ
    while len(que) != 0:
        #取り出してきた状態
        pop = que.popleft()



        #移動4方向をループ
        for i in range(len(dx)):
            #移動した後の点をny,nxとする
            ny = pop[0]+dy[i]
            nx = pop[1]+dx[i]

            #nyが0以上R未満   nxが0以上C未満     盤上で黒ではない        まだ訪れたことがない
            if 0<= ny < R and 0 <= nx < C and board[ny][nx]!='#' and distance[ny][nx] == INF:
                #つまり移動可能でまだ行ったことがなければqueへ入れる
                que.append((ny,nx))
                #その距離をもとのpopの最短距離+1でdistanceに記録
                distance[ny][nx] = distance[pop[0]][pop[1]]+1
    
    ans = 0
    for r in range(R):
        ans = max(max(distance[r]),ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
grid = [["#"] * (W+2)]
for _ in range(H):
    grid.append(["#"] + list(sys.stdin.readline().strip()) + ["#"])
grid.append(["#"] * (W+2))
# print(grid)

q = deque()
for j in range(1, H+1):
    for i in range(1, W+1):
        if grid[j][i] == "#":
            q.append((i, j, 0))

visited = set()
ans = 0
while q:
    x, y, count = q.popleft()
    if (x, y) in visited:
        continue
    visited.add((x, y))
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if grid[y+dy][x+dx] != ".":
            continue
        grid[y+dy][x+dx] = count + 1
        ans = count + 1
        q.append((x+dx, y+dy, count + 1))

# print(grid)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
grid = [["#"] * (W+2)]
for _ in range(H):
    grid.append(["#"] + list(sys.stdin.readline().strip()) + ["#"])
grid.append(["#"] * (W+2))
# print(grid)

q = deque()
for j in range(1, H+1):
    for i in range(1, W+1):
        if grid[j][i] == "#":
            q.append((i, j, 0))

ans = 0
while q:
    x, y, count = q.popleft()
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if grid[y+dy][x+dx] != ".":
            continue
        grid[y+dy][x+dx] = count + 1
        ans = count + 1
        q.append((x+dx, y+dy, count + 1))

# print(grid)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
B = [[0 for _ in range(W)] for _ in range(H)]
que = deque([])
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            que.append((i,j,0))
            B[i][j] = 1
dmax = 0
while que:
    i,j,d = que.popleft()
    if j+1<W and B[i][j+1]==0:
        B[i][j+1]=d+1
        dmax = max(dmax,d+1)
        que.append((i,j+1,d+1))
    if i-1>=0 and B[i-1][j]==0:
        B[i-1][j]=d+1
        dmax = max(dmax,d+1)
        que.append((i-1,j,d+1))
    if j-1>=0 and B[i][j-1]==0:
        B[i][j-1]=d+1
        dmax = max(dmax,d+1)
        que.append((i,j-1,d+1))
    if i+1<H and B[i+1][j]==0:
        B[i+1][j]=d+1
        dmax = max(dmax,d+1)
        que.append((i+1,j,d+1))
print(dmax)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
tizu = [list(input()) for _ in range(h)]
check = [[False for _ in range(w)] for _ in range(h)]
ans = 0

queue = deque()
for i in range(h):
    for j in range(w):
        if tizu[i][j] == "#":
            queue.append([i, j])
            queue.append(0)
            check[i][j] = True

direct = [[1, 0], [-1, 0], [0, 1], [0, -1]]        
while queue:
    pos = queue.popleft()
    cnt = queue.popleft()
    for dy, dx in direct:
        n_y = pos[0] + dy
        n_x = pos[1] + dx
        if n_y == -1 or n_y == h or n_x == -1 or n_x == w:
            continue
        if check[n_y][n_x]:
            continue
        check[n_y][n_x] = True
        ans = max(ans, cnt + 1)
        queue.append([n_y, n_x])
        queue.append(cnt + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy = [0, 1, 0, -1] 
    dx = [1, 0, -1, 0]
 
    que = deque([])
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                que.append((i, j))
                d[i][j] = 0

    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                ans = max(ans, d[ny][nx]) 
    return ans

h, w = MAP()
s = []
for i in range(h):
    s.append(input())
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools,copy
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = []
dot_cnt = 0
for _ in range(H):
    a = input().rstrip()
    dot_cnt += a.count('.')
    s.append(list(a))

num_lis = [[float('inf')]*W for _ in range(H)]

#--#
for ih in range(H):
    for iw in range(W):
        if s[ih][iw]=='#':
            num_lis[ih][iw]=0
        else:
            if iw-1>=0:
                num_lis[ih][iw] = min(num_lis[ih][iw-1]+1,num_lis[ih][iw])
                
    for iw in range(W-1,-1,-1):
        
        if s[ih][iw]=='#':
            num_lis[ih][iw]=0
        else:
            if iw+1<=W-1:
                num_lis[ih][iw] = min(num_lis[ih][iw+1]+1,num_lis[ih][iw])

#--#
for iw in range(W):
    for ih in range(H):
        if s[ih][iw]=='#':
            num_lis[ih][iw]=0
        else:
            if ih-1>=0:
                num_lis[ih][iw] = min(num_lis[ih-1][iw]+1,num_lis[ih][iw])
                
    for ih in range(H-1,-1,-1):
        if s[ih][iw]=='#':
            num_lis[ih][iw]=0
        else:
            if ih+1<=H-1:
                num_lis[ih][iw] = min(num_lis[ih+1][iw]+1,num_lis[ih][iw])

maxOpe = 0
for iw in range(W):
    for ih in range(H):
        maxOpe = max(maxOpe,num_lis[ih][iw])
print(maxOpe)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools,copy
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = []
dot_cnt = 0
for _ in range(H):
    a = input().rstrip()
    dot_cnt += a.count('.')
    s.append(list(a))

numOpe = 0
while dot_cnt:
    numOpe += 1
    tmp = copy.deepcopy(s)
    for ih in range(H):
        for iw in range(W):
            if s[ih][iw]=='#':
                if (ih+1 != H) and (s[ih+1][iw]!='#')and(tmp[ih+1][iw]!='#'):
                    tmp[ih+1][iw]='#'
                    dot_cnt -=1
                if(ih-1 != -1) and (s[ih-1][iw]!='#')and(tmp[ih-1][iw]!='#'):
                    tmp[ih-1][iw]='#'
                    dot_cnt -=1
                if(iw+1 != W) and (s[ih][iw+1]!='#')and( tmp[ih][iw+1]!='#'):
                    tmp[ih][iw+1]='#'
                    dot_cnt -=1
                if(iw-1 != -1) and (s[ih][iw-1]!='#')and(tmp[ih][iw-1]!='#'):
                    tmp[ih][iw-1]='#'
                    dot_cnt -=1        

    s = copy.deepcopy(tmp)
print(numOpe)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
wall = '/'
grid = [[wall] * (w + 2)]
wn = 0

q = deque()
for y in range(1, h+1):
    grid.append([wall] + [c for c in input()] + [wall])
    for x in range(1, w+1):
        if grid[y][x] == '.':
            wn += 1
        if grid[y][x] == '#':
            q.append((y, x, 0))
grid.append([wall] * (w + 2))

move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while q:
    y, x, i = q.popleft()
    for dy, dx in move:
        if grid[y + dy][x + dx] == '.':
            grid[y + dy][x + dx] = '#'
            q.append((y + dy, x + dx, i + 1))
    
print(i)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split(' '))
grid = []
for i in range(h):
  grid.append(list(input()))
  
black = []
for y in range(h):
  for x in range(w):
    if grid[y][x] == '#':
      black.append((y, x, 0))
    
directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]      
ans = 0
 
while len(black) > 0:
  y, x, t = black.pop(0)
  for dy, dx in directions:
    if 0 <= y+dy < h and 0 <= x+dx < w and grid[y+dy][x+dx] == '.':
      grid[y+dy][x+dx] = '#'
      black.append((y+dy, x+dx, t+1))
      ans = max(ans, t+1)
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dis = [[10000]*w for i in range(h)]
q = deque([])

for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            q.append([i,j,0])
            dis[i][j] = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
while q:
    x,y,d = q.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and dis[nx][ny] > d+1:
            dis[nx][ny] = d + 1
            q.append([nx,ny,d+1])

ans = 0
for i in dis:
    ans = max(ans,max(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 白色マスで４方向のマスに黒マスが一つ以上存在するものを黒にかえる。
# 何回の操作でマスが全て黒マスになるか？
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
black_list = []
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            black_list.append((h, w))

count = 0
move = ((0, 1), (1, 0), (-1, 0), (0, -1))
while black_list:
    n_pl = []
    for b in black_list:
        for m in move:
            n_p = (b[0] + m[0], b[1] + m[1])
            if not(n_p[0] < 0 or n_p[1] < 0 or n_p[0] >= H or n_p[1] >= W) and field[n_p[0]][n_p[1]] == ".":
                field[n_p[0]][n_p[1]] = "#"
                n_pl.append(n_p)
    black_list = n_pl
    count += 1
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

H, W = map(int, sys.stdin.readline().split())
A = [sys.stdin.readline() for _ in range(H)]

steps = [[-1] * W for _ in range(H)]
q = collections.deque()

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

max_step = 0
while q:
    y, x, step = q.popleft()

    if y < 0 or H <= y or x < 0 or W <= x:
        continue

    if steps[y][x] != -1:
        continue

    q.append((y + 1, x, step + 1))
    q.append((y - 1, x, step + 1))
    q.append((y, x + 1, step + 1))
    q.append((y, x - 1, step + 1))

    steps[y][x] = step
    max_step = max((max_step, step))

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

H, W = map(int, sys.stdin.readline().split())
A = [sys.stdin.readline() for _ in range(H)]

steps = [[-1 for _ in range(W)] for _ in range(H)]
q = collections.deque()

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

max_step = 0
while q:
    y, x, step = q.popleft()

    if y < 0 or H <= y or x < 0 or W <= x:
        continue

    if steps[y][x] != -1:
        continue

    q.append((y + 1, x, step + 1))
    q.append((y - 1, x, step + 1))
    q.append((y, x + 1, step + 1))
    q.append((y, x - 1, step + 1))

    steps[y][x] = step
    max_step = max((max_step, step))

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

steps = [[-1 for _ in range(W)] for _ in range(H)]
q = collections.deque()

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

max_step = 0
while q:
    y, x, step = q.popleft()

    if y < 0 or H <= y or x < 0 or W <= x:
        continue

    if steps[y][x] != -1:
        continue

    q.append((y + 1, x, step + 1))
    q.append((y - 1, x, step + 1))
    q.append((y, x + 1, step + 1))
    q.append((y, x - 1, step + 1))

    steps[y][x] = step
    max_step = max((max_step, step))

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

steps = [[-1 for _ in range(W)] for _ in range(H)]
q = collections.deque()

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

while q:
    y, x, step = q.popleft()

    if y < 0 or H <= y or x < 0 or W <= x:
        continue

    if steps[y][x] != -1:
        continue

    q.append((y + 1, x, step + 1))
    q.append((y - 1, x, step + 1))
    q.append((y, x + 1, step + 1))
    q.append((y, x - 1, step + 1))

    steps[y][x] = step


print(max(step for steps_ in steps for step in steps_))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

steps = [[-1 for _ in range(W)] for _ in range(H)]
q = collections.deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == '#':

            q.append((y, x, 0))

while q:
    y, x, step = q.popleft()

    if y < 0 or H <= y or x < 0 or W <= x:
        continue

    if steps[y][x] != -1:
        continue

    q.append((y + 1, x, step + 1))
    q.append((y - 1, x, step + 1))
    q.append((y, x + 1, step + 1))
    q.append((y, x - 1, step + 1))

    steps[y][x] = step


print(max(step for steps_ in steps for step in steps_))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

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

ans = 0
for x in c:
    tmp = inf
    for y in b:
        tmp = min(tmp, abs(x[0]-y[0])+abs(x[1]-y[1]))
        if tmp <= ans:
            break
    ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

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

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            tmp = inf
            for x in b:
                tmp = min(tmp, abs(i-x[0])+abs(j-x[1]))
            ans = max(ans, tmp)
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())
a = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
black = []
r_append = black.append
for i,row in enumerate(a):
    for j,c in enumerate(row):
        if c == '#':
            r_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 row in visited:
    for j in row:
        ans = max(ans,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())
a = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
black = []
for i,row in enumerate(a):
    for j,c in enumerate(row):
        if c == '#':
            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 row in visited:
    for j in row:
        ans = max(ans,j)

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)]
visited = [[-1]*w for i in range(h)]
black = []
for i,row in enumerate(a):
    for j,c in enumerate(row):
        if c == '#':
            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 row in visited:
    for j in row:
        ans = max(ans,j)

print(ans)