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())
l=[list(input()) 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])
while len(q)>0:
    i,j,x=q.popleft()
    if i>0 and l[i-1][j]==".":
        l[i-1][j]=x+1
        q.append([i-1,j,x+1])
    if i<h-1 and l[i+1][j]==".":
        l[i+1][j]=x+1
        q.append([i+1,j,x+1])
    if j>0 and l[i][j-1]==".":
        l[i][j-1]=x+1
        q.append([i,j-1,x+1])
    if j<w-1 and l[i][j+1]==".":
        l[i][j+1]=x+1
        q.append([i,j+1,x+1])
print(x)

Submission status: Time Limit Exceeded

Solution code:
"""
解説と提出 #5747380を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    # mass = [[False] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    mass = []
    mass.append([False] * (W + 2))  # 外枠
    for Hi in range(1, H + 1):
        mass.append([False] + [True if s == '.' else False for s in list(input())] + [False])
        for Wi in range(1, W + 1):
            if not mass[Hi][Wi]:
                queue1.append([Hi, Wi])
    mass.append([False] * (W + 2))  # 外枠
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append([h, w - 1])
            # right
            if mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append([h, w + 1])
            # top
            if mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append([h + 1, w])
            # button
            if mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append([h - 1, w])

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
"""
解説を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    for Hi in range(H):
        massHi = [True if s == '.' else False for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = massHi[Wi]
            if not massHi[Wi]:
                queue1.append([Hi, Wi])
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if w != 0 and mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append([h, w - 1])
            # right
            if w < W - 1 and mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append([h, w + 1])
            # top
            if h < H - 1 and mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append([h + 1, w])
            # button
            if h != 0 and mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append([h - 1, w])

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
"""
解説を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    for Hi in range(H):
        massHi = [0 if s == '.' else 1 for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = massHi[Wi]
            if massHi[Wi] == 1:
                queue1.append([Hi, Wi])
    # import datetime
    # d = datetime.datetime.now()
    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break
        for h, w in queue1:
            # left
            if w != 0 and mass[h][w - 1] == 0:
                mass[h][w - 1] = 1
                queue2.append([h, w - 1])
            # right
            if w < W - 1 and mass[h][w + 1] == 0:
                mass[h][w + 1] = 1
                queue2.append([h, w + 1])
            # top
            if h < H - 1 and mass[h + 1][w] == 0:
                mass[h + 1][w] = 1
                queue2.append([h + 1, w])
            # button
            if h != 0 and mass[h - 1][w] == 0:
                mass[h - 1][w] = 1
                queue2.append([h - 1, w])

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    # print(datetime.datetime.now() - d)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
"""
解説を参考に作成
提出 #5799729:
    TLE -> dequeではなくリストにしてみた
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    # queue1 = deque([])
    # queue2 = deque([])
    queue1 = []
    queue2 = []
    for Hi in range(H):
        massHi = [0 if s == '.' else 1 for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = [Hi, Wi, massHi[Wi]]
            if massHi[Wi] == 1:
                queue1.append(mass[Hi][Wi])

    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break

        while len(queue1) > 0:
            # h, w, a = queue1.popleft()
            h, w, a = queue1.pop()
            # left
            if w != 0 and mass[h][w - 1][2] == 0:
                mass[h][w - 1][2] = 1
                queue2.append(mass[h][w - 1])
            # right
            if w < W - 1 and mass[h][w + 1][2] == 0:
                mass[h][w + 1][2] = 1
                queue2.append(mass[h][w + 1])
            # top
            if h < H - 1 and mass[h + 1][w][2] == 0:
                mass[h + 1][w][2] = 1
                queue2.append(mass[h + 1][w])
            # button
            if h != 0 and mass[h - 1][w][2] == 0:
                mass[h - 1][w][2] = 1
                queue2.append(mass[h - 1][w])

        count += 1
        queue1 = queue2
        queue2 = deque([])
    print(count)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
"""
解説を参考に作成
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    queue1 = deque([])
    queue2 = deque([])
    for Hi in range(H):
        massHi = [0 if s == '.' else 1 for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = [Hi, Wi, massHi[Wi]]
            if massHi[Wi] == 1:
                queue1.append(mass[Hi][Wi])

    count = -1
    while True:
        # print('count: {}, queue:{}'.format(count, len(queue1)))
        if len(queue1) == 0:
            break

        while len(queue1) > 0:
            h, w, a = queue1.popleft()
            # left
            if w != 0 and mass[h][w - 1][2] == 0:
                mass[h][w - 1][2] = 1
                queue2.append(mass[h][w - 1])
            # right
            if w < W - 1 and mass[h][w + 1][2] == 0:
                mass[h][w + 1][2] = 1
                queue2.append(mass[h][w + 1])
            # top
            if h < H - 1 and mass[h + 1][w][2] == 0:
                mass[h + 1][w][2] = 1
                queue2.append(mass[h + 1][w])
            # button
            if h != 0 and mass[h - 1][w][2] == 0:
                mass[h - 1][w][2] = 1
                queue2.append(mass[h - 1][w])

        count += 1
        queue1 = queue2
        queue2 = deque([])
    print(count)


if __name__ == '__main__':
    solve()

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)]
q=deque([])
for i in range(h):
    for j in range(w):
        if l[i][j]=="#":
            if i>0 and l[i-1][j]==".":
                l[i-1][j]=1
                q.append([i-1,j,1])
            if i<h-1 and l[i+1][j]==".":
                l[i+1][j]=1
                q.append([i+1,j,1])
            if j>0 and l[i][j-1]==".":
                l[i][j-1]=1
                q.append([i,j-1,1])
            if j<w-1 and l[i][j+1]==".":
                l[i][j+1]=1
                q.append([i,j+1,1])
x=0
while len(q)>0:
    i,j,x=q.popleft()
    if i>0 and l[i-1][j]==".":
        l[i-1][j]=x+1
        q.append([i-1,j,x+1])
    if i<h-1 and l[i+1][j]==".":
        l[i+1][j]=x+1
        q.append([i+1,j,x+1])
    if j>0 and l[i][j-1]==".":
        l[i][j-1]=x+1
        q.append([i,j-1,x+1])
    if j<w-1 and l[i][j+1]==".":
        l[i][j+1]=x+1
        q.append([i,j+1,x+1])
print(x)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
q=[]
for i in range(h):
    for j in range(w):
        if l[i][j]=="#":
            if i>0 and l[i-1][j]==".":
                l[i-1][j]=1
                q.append([i-1,j])
            if i<h-1 and l[i+1][j]==".":
                l[i+1][j]=1
                q.append([i+1,j])
            if j>0 and l[i][j-1]==".":
                l[i][j-1]=1
                q.append([i,j-1])
            if j<w-1 and l[i][j+1]==".":
                l[i][j+1]=1
                q.append([i,j+1])
x=0
while len(q)>0:
    qi=q[:]
    q=[]
    x+=1
    for i,j in qi:
        if i>0 and l[i-1][j]==".":
            l[i-1][j]=x+1
            q.append([i-1,j])
        if i<h-1 and l[i+1][j]==".":
            l[i+1][j]=x+1
            q.append([i+1,j])
        if j>0 and l[i][j-1]==".":
            l[i][j-1]=x+1
            q.append([i,j-1])
        if j<w-1 and l[i][j+1]==".":
            l[i][j+1]=x+1
            q.append([i,j+1])
print(x)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
A = [["#"] + [s for s in input()] + ["#"] for k in range(H)]
A = [["#"]*(W+2)] + A + [["#"]*(W+2)]


que = []
for k in range(1,H+1):
    for l in range(1,W+1):
        if A[k][l] == "#":
            que.append([k,l])
if len(que) == H*W:
    print(0)
    exit(0)
ans = 0
while True:
    t = []
    while len(que) > 0:
        s = que.pop()
        k, l = s[0], s[1]
        if A[k][l-1] == ".":
            A[k][l-1] = "#"
            t.append([k,l-1])
        if A[k][l+1] == ".":
            A[k][l+1] = "#"
            t.append([k,l+1])
        if A[k-1][l] == ".":
            A[k-1][l] = "#"
            t.append([k-1,l])
        if  A[k+1][l] == ".":
            A[k+1][l] = "#"
            t.append([k+1,l])
    if len(t) > 0:
        ans += 1
        que = t
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2)
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

#enumerate input

def main():
    h,w=map(int,input().split())
    stack=deque()
    grid=[["#"]*(w+2)]
    for i in range(h):
        tmp=[]
        for k,v in enumerate(input()):
            if v=="#":
                tmp.append("#")
                stack.appendleft((i+1,k+1))
            else:
                tmp.append(v)
        grid.append(["#"]+tmp+["#"])
    grid.append(["#"]*(w+2))
#    for i in grid:
#        print(*i)
    for i in range(h*w):
        tmp=deque()
        while stack:
            y,x=stack.pop()
            for my,mx in ((0,1),(1,0),(-1,0),(0,-1)):
                if grid[y+my][x+mx]==".":
                    grid[y+my][x+mx]="#"
                    tmp.appendleft((y+my,x+mx))
        stack=tmp
        if not len(stack):
            print(i)
            exit()
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
h, w = map(int, input().split())
a = []
a = [[True] * (w + 2)]
for i in range(h):
    a.append([True] + [x == '#' for x in input()] + [True])
a.append([True] * (w + 2))
q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j]:
            q.append((i, j))

count = 0
while True:
    qq = []
    for i, j in q:
        if not a[i-1][j]:
            a[i-1][j] = True
            qq.append((i - 1, j))
        if not a[i+1][j]:
            a[i+1][j] = True
            qq.append((i + 1, j))
        if not a[i][j-1]:
            a[i][j-1] = True
            qq.append((i, j - 1))
        if not a[i][j+1]:
            a[i][j+1] = True
            qq.append((i, j + 1))
    q = qq
    if len(q) <= 0:
        break
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

h,w = map(int,input().split())
A = [list(input()) for _ in range(h)]
bl = []
ans = 0
for i in range(h):
	for j in range(w):
		if A[i][j] == "#":
			bl.append([i,j])
if bl:
	mass = [[0,1],[1,0],[-1,0],[0,-1]]
	bl_copy = []
	while 1:
		ans += 1
		# print(ans,'周目')
		for x,y in bl:
			for xx,yy in mass:
				if 0 <= x+xx < h and 0 <= y+yy < w:
					# print(x+xx,y+yy)
					if A[x+xx][y+yy] == ".":
						A[x+xx][y+yy] = str(ans)
						bl_copy.append([x+xx,y+yy])
		if bl_copy:
			bl = deepcopy(bl_copy)
			bl_copy = []
		else:
			ans -= 1
			break
else:
	ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.spatial.distance import cityblock
B = []
Distance = []

H,W = map(int,input().split())
minD = 0
for row in range(H):
    Inputs = list(input())
    for column in [i for i, x in enumerate(Inputs) if x == '#']:
        B.append((column,row))

for column in range(W):
    for row in range(H):
        Distance = []
        a = (column,row)
        for b in B:
            Manhattan = cityblock(a,b)
            if Manhattan > minD:
                Distance.append(Manhattan)
            else:
                break
        if len(Distance) == len(B):
            if min(Distance) > minD:
                minD = min(Distance)
print(minD)

Submission status: Time Limit Exceeded

Solution code:
import queue

q = queue.Queue()

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

board = [[i for i in list(str(input()))] for i in range(h)]
hist = [[False] * w for i in range(h)]

step = 0
count = 0
next_count = 0

for y in range(h):
    for x in range(w):
        if board[y][x] == "#":
            q.put((y, x))
            count += 1
            hist[y][x] = True

while not q.empty():
    y, x = q.get()
    if 0 <= y - 1 and not hist[y - 1][x]:
        if board[y - 1][x] == ".":
            board[y - 1][x] = "#"
            q.put((y - 1, x))
            hist[y - 1][x] = True
            next_count += 1
    if y + 1 < h and not hist[y + 1][x]:
        if board[y + 1][x] == ".":
            board[y + 1][x] = "#"
            q.put((y + 1, x))
            hist[y + 1][x] = True
            next_count += 1
    if 0 <= x - 1 and not hist[y][x - 1]:
        if board[y][x - 1] == ".":
            board[y][x - 1] = "#"
            q.put((y, x - 1))
            hist[y][x - 1] = True
            next_count += 1
    if x + 1 < w and not hist[y][x + 1]:
        if board[y][x + 1] == ".":
            board[y][x + 1] = "#"
            q.put((y, x + 1))
            hist[y][x + 1] = True
            next_count += 1
    count -= 1
    if count == 0:
        step += 1
        count = next_count
        next_count = 0
print(step - 1)

Submission status: Time Limit Exceeded

Solution code:
import queue

q = queue.Queue()

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

board = [[i for i in list(str(input()))] for i in range(h)]
hist = [[False] * w for i in range(h)]

step = 0
count = 0
next_count = 0

for y in range(h):
    for x in range(w):
        if board[y][x] == "#":
            q.put((y, x))
            count += 1
            hist[y][x] = True

while not q.empty():
    y, x = q.get()
    if 0 <= y - 1 and not hist[y - 1][x] and board[y - 1][x] == ".":
        board[y - 1][x] = "#"
        q.put((y - 1, x))
        hist[y - 1][x] = True
        next_count += 1
    if y + 1 < h and not hist[y + 1][x] and board[y + 1][x] == ".":
        board[y + 1][x] = "#"
        q.put((y + 1, x))
        hist[y + 1][x] = True
        next_count += 1
    if 0 <= x - 1 and not hist[y][x - 1] and board[y][x - 1] == ".":
        board[y][x - 1] = "#"
        q.put((y, x - 1))
        hist[y][x - 1] = True
        next_count += 1
    if x + 1 < w and not hist[y][x + 1] and board[y][x + 1] == ".":
        board[y][x + 1] = "#"
        q.put((y, x + 1))
        hist[y][x + 1] = True
        next_count += 1
    count -= 1
    if count == 0:
        step += 1
        count = next_count
        next_count = 0
print(step - 1)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

field = [list(input()) for t in range(h)]
count = 0 
blk_list = []
rem_list = []

for y in range(h):
    for x in range(w):
        if field[y][x] == '#':
            blk_list.append((x, y))          
        else:
            rem_list.append((x, y))

while True:
    if len(rem_list) == 0:
        break
    else:
        nxt_blk = []
        for elm in blk_list:
            nb1 = (elm[0] - 1, elm[1])
            nb2 = (elm[0] + 1, elm[1])
            nb3 = (elm[0], elm[1] - 1)
            nb4 = (elm[0], elm[1] + 1)
            if nb1 in rem_list:
                nxt_blk.append(nb1)
                rem_list.remove(nb1)
            if nb2 in rem_list:
                nxt_blk.append(nb2)
                rem_list.remove(nb2)
            if nb3 in rem_list:
                nxt_blk.append(nb3)
                rem_list.remove(nb3)
            if nb4 in rem_list:
                nxt_blk.append(nb4)
                rem_list.remove(nb4)
        count += 1
        blk_list = copy.deepcopy(nxt_blk)

        
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

field = [list(input()) for t in range(h)]
count = 0 
blk_list = []
rem_list = []

for y in range(h):
    for x in range(w):
        if field[y][x] == '#':
            blk_list.append((x, y))

rem_list = copy.deepcopy(blk_list)        

while True:
    if len(rem_list) == w * h:
        break
    else:
        nxt_blk = []
        # print(count, len(blk_list))
        for elm in blk_list:
            if elm[0] > 0:
                nb1 = (elm[0] - 1, elm[1])
                if field[nb1[1]][nb1[0]] == '.':
                    field[nb1[1]][nb1[0]] = '#'
                    nxt_blk.append(nb1)
                    rem_list.append(nb1)
            if elm[0] < w -1:
                nb2 = (elm[0] + 1, elm[1])
                if field[nb2[1]][nb2[0]] == '.':
                    field[nb2[1]][nb2[0]] = '#'
                    nxt_blk.append(nb2)
                    rem_list.append(nb2)
            if elm[1] > 0:
                nb3 = (elm[0], elm[1] - 1)
                if field[nb3[1]][nb3[0]] == '.':
                    field[nb3[1]][nb3[0]] = '#'
                    nxt_blk.append(nb3)
                    rem_list.append(nb3)
            if elm[1] < h -1:
                nb4 = (elm[0], elm[1] + 1)
                if field[nb4[1]][nb4[0]] == '.':
                    field[nb4[1]][nb4[0]] = '#'
                    nxt_blk.append(nb4)
                    rem_list.append(nb4)
        count += 1
        blk_list = copy.deepcopy(nxt_blk)

        
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

field = [list(input()) for t in range(h)]
count = 0 
blk_list = []
rem_list = []

for y in range(h):
    for x in range(w):
        if field[y][x] == '#':
            blk_list.append((x, y))          

while True:
    if len(rem_list) == w*h:
        break
    else:
        nxt_blk = []
        print(count, len(blk_list))
        for elm in blk_list:
            if elm[0] > 0:
                nb1 = (elm[0] - 1, elm[1])
                if field[nb1[1]][nb1[0]] == '.':
                    field[nb1[1]][nb1[0]] = '#'
                    nxt_blk.append(nb1)
                    rem_list.append(nb1)
            if elm[0] < w -1:
                nb2 = (elm[0] + 1, elm[1])
                if field[nb2[1]][nb2[0]] == '.':
                    field[nb2[1]][nb2[0]] = '#'
                    nxt_blk.append(nb2)
                    rem_list.append(nb2)
            if elm[1] > 0:
                nb3 = (elm[0], elm[1] - 1)
                if field[nb3[1]][nb3[0]] == '.':
                    field[nb3[1]][nb3[0]] = '#'
                    nxt_blk.append(nb3)
                    rem_list.append(nb3)
            if elm[1] < h -1:
                nb4 = (elm[0], elm[1] + 1)
                if field[nb4[1]][nb4[0]] == '.':
                    field[nb4[1]][nb4[0]] = '#'
                    nxt_blk.append(nb4)
                    rem_list.append(nb4)
        count += 1
        blk_list = copy.deepcopy(nxt_blk)

        
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

field = [list(input()) for t in range(h)]
count = 0 
blk_list = []
rem_list = []

for y in range(h):
    for x in range(w):
        if field[y][x] == '#':
            blk_list.append((x, y))          
        else:
            rem_list.append((x, y))

while True:
    if len(rem_list) == 0:
        break
    else:
        nxt_blk = []
        for elm in blk_list:
            if elm[0] > 0:
                nb1 = (elm[0] - 1, elm[1])
                if field[nb1[1]][nb1[0]] == '.':
                    field[nb1[1]][nb1[0]] = '#'
                    nxt_blk.append(nb1)
                    rem_list.remove(nb1)
            if elm[0] < w -1:
                nb2 = (elm[0] + 1, elm[1])
                if field[nb2[1]][nb2[0]] == '.':
                    field[nb2[1]][nb2[0]] = '#'
                    nxt_blk.append(nb2)
                    rem_list.remove(nb2)
            if elm[1] > 0:
                nb3 = (elm[0], elm[1] - 1)
                if field[nb3[1]][nb3[0]] == '.':
                    field[nb3[1]][nb3[0]] = '#'
                    nxt_blk.append(nb3)
                    rem_list.remove(nb3)
            if elm[1] < h -1:
                nb4 = (elm[0], elm[1] + 1)
                if field[nb4[1]][nb4[0]] == '.':
                    field[nb4[1]][nb4[0]] = '#'
                    nxt_blk.append(nb4)
                    rem_list.remove(nb4)
        count += 1
        blk_list = copy.deepcopy(nxt_blk)

        
print(count)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
As =[input() for _ in range(H)]
ds =[[0]*W for _ in range(H)]
S = []
T = []
for i in range(H):
    for j in range(W):
        if As[i][j] == '#':
            S.append((i, j))
            T.append((i, j))
while S:
    S2 = []
    for x, y in S:
        for pos in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            x2, y2 = pos
            if 0<= x2 <= H-1 and 0<= y2 <= W-1 and pos not in T:
                ds[x2][y2] = ds[x][y]+1
                S2.append(pos)
                T.append(pos)
    S = S2
ans = 0
for d in ds:
    for i in d:
        if i > ans:
            ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

field = [list(input()) for t in range(h)]
new_field = copy.deepcopy(field)
count = 0 
# print(new_field)

while True:
    if '.' in sum(field, []):
        count += 1
        for y in range(h):
            for x in range(w):
                if field[y][x] == '#':
                    new_field[y][x] = '$'
                    if y > 0:
                        if new_field[y-1][x] == '.': 
                            new_field[y-1][x] = '#'
                    if y < h - 1:
                        if new_field[y+1][x] == '.':
                            new_field[y+1][x] = '#'
                    if x > 0:
                        if new_field[y][x-1] == '.':
                            new_field[y][x-1] = '#'
                    if x < w - 1:
                        if new_field[y][x+1] == '.':
                            new_field[y][x+1] = '#'
        field = copy.deepcopy(new_field)
    else:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

field = [list(input()) for t in range(h)]
new_field = copy.deepcopy(field)
count = 0 
# print(new_field)

while True:
    if '.' in sum(new_field, []):
        count += 1
        for y in range(h):
            for x in range(w):
                if field[y][x] == '.':
                    check = []
                    if y > 0:
                        check.append(field[y-1][x])
                    if y < h - 1:
                        check.append(field[y+1][x])
                    if x > 0:
                        check.append(field[y][x-1])
                    if x < w - 1:
                        check.append(field[y][x+1])
                    if '#' in check:
                        new_field[y][x] = '#'
                    else:
                        new_field[y][x] = '.'
                else:
                    new_field[y][x] = field[y][x]
        field = copy.deepcopy(new_field)
    else:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[[None]*(W+2)]
A.extend([[i=="." for i in "#"+input()+"#"] for _ in range(H)])
A.append([None]*(W+2))

q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]

for k in range(2000):
    q.append([])
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=None
            q[k+1].append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=None
            q[k+1].append([i+1,j])
        if A[i][j-1]:
            A[i][j-1]=None
            q[k+1].append([i,j-1])
        if A[i][j+1]:
            A[i][j+1]=None
            q[k+1].append([i,j+1])
    if q[k+1]==[]:
        break
print(k)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
  return sys.stdin.readline()

H,W=map(int,input().split())
A=[[None]*(W+2)]+\
  [[i=="." for i in "#"+input()+"#"] for _ in range(H)] + \
  [[None]*(W+2)]

q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]

for k in range(2000):
    q.append([])
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=None
            q[k+1].append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=None
            q[k+1].append([i+1,j])
        if A[i][j-1]:
            A[i][j-1]=None
            q[k+1].append([i,j-1])
        if A[i][j+1]:
            A[i][j+1]=None
            q[k+1].append([i,j+1])
    if q[k+1]==[]:
        break
print(k)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[[None]*(W+2)]+\
  [[i=="." for i in "#"+input()+"#"] for _ in range(H)] + \
  [[None]*(W+2)]

q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]

for k in range(2000):
    q.append([])
    f=True
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=None
            q[k+1].append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=None
            q[k+1].append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=None
            q[k+1].append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=None
            q[k+1].append((i,j+1))
    if not q[k+1]:
        break
print(k)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[[False]*(W+2)]+\
  [[i=="." for i in "#"+input()+"#"] for _ in range(H)] + \
  [[False]*(W+2)]

q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]

for k in range(2000):
    q.append([])
    f=True
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=False
            q[k+1].append((i-1,j))
            f=False
        if A[i+1][j]:
            A[i+1][j]=False
            q[k+1].append((i+1,j))
            f=False
        if A[i][j-1]:
            A[i][j-1]=False
            q[k+1].append((i,j-1))
            f=False
        if A[i][j+1]:
            A[i][j+1]=False
            q[k+1].append((i,j+1))
            f=False
    if f:
        break
print(k)

Submission status: Time Limit Exceeded

Solution code:
import sys

H,W=map(int,sys.stdin.readline().split())
A=[[None]*(W+2)]+\
  [[None] + [i=="." for i in sys.stdin.readline()] + [None] for _ in range(H)] + \
  [[None]*(W+2)]
 
cnt=0
q,r=[],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]==False:
            q.append((i,j))
if len(q)==H*W:
    print(0)
    sys.exit()
for k in range(2000):
    for i,j in q:
        if A[i-1][j]:
            A[i-1][j]=False
            r.append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=False
            r.append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=False
            r.append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=False
            r.append((i,j+1))
    q=[i for i in r]
    r=[]
    if q==[]:
        break
    cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[[False]*(W+2)]+\
  [[False] + [i=="." for i in input()] + [False] for _ in range(H)] + \
  [[False]*(W+2)]

q,r=[[] for _ in range(2000)],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]==False:
            q[0].append((i,j))
if len(q[0])==H*W:
    print(0)
    import sys
    sys.exit()
for k in range(2000):
    f=True
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=False
            q[k+1].append((i-1,j))
            f=False
        if A[i+1][j]:
            A[i+1][j]=False
            q[k+1].append((i+1,j))
            f=False
        if A[i][j-1]:
            A[i][j-1]=False
            q[k+1].append((i,j-1))
            f=False
        if A[i][j+1]:
            A[i][j+1]=False
            q[k+1].append((i,j+1))
            f=False
    if f:
        break
print(k)