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
import sys
input=sys.stdin.readline

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+i
            y0 = y+j
            if not counts[x0][y0]:
                counts[x0][y0] = True
                q.append([x0, y0, z+1])
    print(z)

cal()

Submission status: Time Limit Exceeded

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

def cal():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j, 0])
                counts[j+1][i+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if not counts[y0+1][x0+1]:
                counts[y0+1][x0+1] = True
                q.append([x0, y0, z+1])
    print(z)

cal()

Submission status: Time Limit Exceeded

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

def cal(h, w, a):
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j, 0])
                counts[j+1][i+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if not counts[y0+1][x0+1]:
                counts[y0+1][x0+1] = True
                q.append([x0, y0, z+1])
    return z

print(cal(h, w, a))

Submission status: Time Limit Exceeded

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

@jit
def cal(h, w, a):
    q = deque()
    counts = [[False for _ in range(w)] for _ in range(h)]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j, 0])
                counts[j][i] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if not counts[y0][x0]:
                    counts[y0][x0] = True
                    q.append([x0, y0, z+1])
    return z

print(cal(h, w, a))

Submission status: Time Limit Exceeded

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

def cal(h, w, a):
    q = deque()
    counts = [[False for _ in range(w)] for _ in range(h)]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j, 0])
                counts[j][i] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if not counts[y0][x0]:
                    counts[y0][x0] = True
                    q.append([x0, y0, z+1])
    return z

print(cal(h, w, a))

Submission status: Time Limit Exceeded

Solution code:
def cal():
    from collections import deque
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = deque()
    counts = [[False for _ in range(w)] for _ in range(h)]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j, 0])
                counts[j][i] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if not counts[y0][x0]:
                    counts[y0][x0] = True
                    q.append([x0, y0, z+1])
    return z

print(cal())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def cal():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = deque()
    INF = float('inf')
    counts = [[False]*w for _ in range(h)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j, 0])
                counts[j][i] = True

    while q:
        x, y, z = q.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if counts[y0][x0] is False:
                    counts[y0][x0] = True
                    q.append([x0, y0, z+1])
    print(z)

cal()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def cal():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = deque()
    INF = float('inf')
    counts = [[INF]*w for _ in range(h)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.append([i, j])
                counts[j][i] = 0

    while q:
        x, y = q.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if a[y0][x0] == '.' and counts[y][x]+1 < counts[y0][x0]:
                    a[y0][x0] = '#'
                    counts[y0][x0] = counts[y][x]+1
                    q.append([x0, y0])
    ans = 0
    for i in counts:
        ans = max(ans, max(i))
    print(ans)

cal()

Submission status: Time Limit Exceeded

Solution code:
import queue
def cal():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = queue.Queue()
    INF = float('inf')
    counts = [[INF]*w for _ in range(h)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.put([i, j])
                counts[j][i] = 0

    while not q.empty():
        x, y = q.get()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if a[y0][x0] == '#':
                    continue
                elif counts[y][x]+1 < counts[y0][x0]:
                    a[y0][x0] = '#'
                    counts[y0][x0] = counts[y][x]+1
                    q.put([x0, y0])
    ans = 0
    for i in counts:
        ans = max(ans, max(i))
    print(ans)

cal()

Submission status: Time Limit Exceeded

Solution code:
import queue
def cal():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = queue.Queue()
    INF = float('inf')
    counts = [[INF]*w for _ in range(h)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.put([i, j])
                counts[j][i] = 0

    while not q.empty():
        x, y = q.get()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if counts[y][x]+1 < counts[y0][x0] and a[y0][x0] == '.':
                    a[y0][x0] = '#'
                    counts[y0][x0] = counts[y][x]+1
                    q.put([x0, y0])
    ans = 0
    for i in counts:
        ans = max(ans, max(i))
    print(ans)

cal()

Submission status: Time Limit Exceeded

Solution code:
import queue
def cal():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    q = queue.Queue()
    INF = float('inf')
    counts = [[INF]*w for _ in range(h)]
    
    for i in range(w):
        for j in range(h):
            if a[j][i] == '#':
                q.put([i, j])
                counts[j][i] = 0

    while not q.empty():
        x, y = q.get()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x0 = x+j
            y0 = y+i
            if 0 <= x0 < w and 0 <= y0 < h:
                if counts[y][x]+1 < counts[y0][x0]:
                    a[y0][x0] = '#'
                    counts[y0][x0] = counts[y][x]+1
                    q.put([x0, y0])
    ans = 0
    for i in counts:
        ans = max(ans, max(i))
    print(ans)

cal()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i in range(h) for j in range(w) if S[i][j]=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i in range(h) for j in range(w) if S[i][j]=='#']
    q = deque(q)
    ans = 0
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < h*w:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i in range(h) for j in range(w) if S[i][j]=='#']
    q = deque(q)
    ans = 0
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < h*w:
        ans += 1
        q_ = deque([])
        while len(q)>0:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = deque()
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
    ans = 0
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while len(q)>0:
        ans += 1
        n = len(q)
        for _ in range(n):
            b = q.popleft()
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='#':
                        continue
                    S[mv[0]][mv[1]]='#'
                    q.append(mv)
    print(ans-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = deque()
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt<h*w:
        ans += 1
        n = len(q)
        for _ in range(n):
            b = q.popleft()
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='#':
                        continue
                    cnt += 1
                    S[mv[0]][mv[1]]='#'
                    q.append(mv)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = deque()
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt<h*w:
        q_ = deque()
        ans += 1
        while len(q)>0:
            b = q.pop()
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='#':
                        continue
                    cnt += 1
                    S[mv[0]][mv[1]]='#'
                    q_.append(mv)
        q = q_
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = []
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt<h*w:
        q_ = []
        ans += 1
        while len(q)>0:
            b = q.pop(0)
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='#':
                        continue
                    cnt += 1
                    S[mv[0]][mv[1]]='#'
                    q_.append(mv)
        q = q_
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = []
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt<h*w:
        q_ = []
        while len(q)>0:
            b = q.pop(0)
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='.':
                        cnt += 1
                        S[mv[0]][mv[1]]='#'
                        q_.append(mv)
        ans += 1
        q = q_
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = []
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    while True:
        ans += 1
        q_ = []
        while len(q)>0:
            b = q.pop(0)
            if b[0]>0:
                if S[b[0]-1][b[1]]=='.':
                    cnt += 1
                    S[b[0]-1][b[1]]='#'
                    q_.append([b[0]-1,b[1]])
                    if cnt==h*w:
                        print(ans)
                        return
            if b[0]<h-1:
                if S[b[0]+1][b[1]]=='.':
                    cnt += 1
                    S[b[0]+1][b[1]]='#'
                    q_.append([b[0]+1,b[1]])
                    if cnt==h*w:
                        print(ans)
                        return
            if b[1]>0:
                if S[b[0]][b[1]-1]=='.':
                    cnt+=1
                    S[b[0]][b[1]-1]='#'
                    q_.append([b[0],b[1]-1])
                    if cnt==h*w:
                        print(ans)
                        return
            if b[1]<w-1:
                if S[b[0]][b[1]+1]=='.':
                    cnt += 1
                    S[b[0]][b[1]+1]='#'
                    q_.append([b[0],b[1]+1])
                    if cnt==h*w:
                        print(ans)
                        return
        q = q_

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = []
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    while True:
        ans += 1
        q_ = []
        for _ in range(len(q)):
            b = q.pop(0)
            if b[0]>0:
                if S[b[0]-1][b[1]]=='.':
                    cnt += 1
                    S[b[0]-1][b[1]]='#'
                    q_.append([b[0]-1,b[1]])
                    if cnt==h*w:
                        print(ans)
                        return
            if b[0]<h-1:
                if S[b[0]+1][b[1]]=='.':
                    cnt += 1
                    S[b[0]+1][b[1]]='#'
                    q_.append([b[0]+1,b[1]])
                    if cnt==h*w:
                        print(ans)
                        return
            if b[1]>0:
                if S[b[0]][b[1]-1]=='.':
                    cnt+=1
                    S[b[0]][b[1]-1]='#'
                    q_.append([b[0],b[1]-1])
                    if cnt==h*w:
                        print(ans)
                        return
            if b[1]<w-1:
                if S[b[0]][b[1]+1]=='.':
                    cnt += 1
                    S[b[0]][b[1]+1]='#'
                    q_.append([b[0],b[1]+1])
                    if cnt==h*w:
                        print(ans)
                        return
        q = q_

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import queue
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = queue.Queue()
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.put([i,j])
                cnt += 1
    ans = 0
    while cnt<h*w:
        ans += 1
        q_ = queue.Queue()
        for _ in range(q.qsize()):
            b = q.get()
            if b[0]>0:
                if S[b[0]-1][b[1]]=='.':
                    cnt += 1
                    S[b[0]-1][b[1]]='#'
                    q_.put([b[0]-1,b[1]])
            if b[0]<h-1:
                if S[b[0]+1][b[1]]=='.':
                    cnt += 1
                    S[b[0]+1][b[1]]='#'
                    q_.put([b[0]+1,b[1]])
            if b[1]>0:
                if S[b[0]][b[1]-1]=='.':
                    cnt+=1
                    S[b[0]][b[1]-1]='#'
                    q_.put([b[0],b[1]-1])
            if b[1]<w-1:
                if S[b[0]][b[1]+1]=='.':
                    cnt += 1
                    S[b[0]][b[1]+1]='#'
                    q_.put([b[0],b[1]+1])
        q = q_
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import queue
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = queue.Queue()
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.put([i,j])
                cnt += 1
    ans = 0
    while cnt<h*w:
        ans += 1
        q_ = queue.Queue()
        while q.qsize()>0:
            b = q.get(0)
            if b[0]>0:
                if S[b[0]-1][b[1]]=='.':
                    cnt += 1
                    S[b[0]-1][b[1]]='#'
                    q_.put([b[0]-1,b[1]])
            if b[0]<h-1:
                if S[b[0]+1][b[1]]=='.':
                    cnt += 1
                    S[b[0]+1][b[1]]='#'
                    q_.put([b[0]+1,b[1]])
            if b[1]>0:
                if S[b[0]][b[1]-1]=='.':
                    cnt+=1
                    S[b[0]][b[1]-1]='#'
                    q_.put([b[0],b[1]-1])
            if b[1]<w-1:
                if S[b[0]][b[1]+1]=='.':
                    cnt += 1
                    S[b[0]][b[1]+1]='#'
                    q_.put([b[0],b[1]+1])
        q = q_
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    B = []
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                B.append([i,j])
                cnt += 1
    ans = 0
    while cnt<h*w:
        ans += 1
        B_ = []
        while len(B)>0:
            b = B.pop(0)
            if b[0]>0:
                if S[b[0]-1][b[1]]=='.':
                    cnt += 1
                    S[b[0]-1][b[1]]='#'
                    B_.append([b[0]-1,b[1]])
            if b[0]<h-1:
                if S[b[0]+1][b[1]]=='.':
                    cnt += 1
                    S[b[0]+1][b[1]]='#'
                    B_.append([b[0]+1,b[1]])
            if b[1]>0:
                if S[b[0]][b[1]-1]=='.':
                    cnt+=1
                    S[b[0]][b[1]-1]='#'
                    B_.append([b[0],b[1]-1])
            if b[1]<w-1:
                if S[b[0]][b[1]+1]=='.':
                    cnt += 1
                    S[b[0]][b[1]+1]='#'
                    B_.append([b[0],b[1]+1])
        B = B_
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import re
import copy
import numpy as np
import queue

def accept_input():
    H,W = map(int,input().split())
    S = []
    for _ in range(H):
        S.append(input())
    return H,W,S


def widthsearch(q):
    global curvisited
    movelist = [(0,1),(0,-1),(1,0),(-1,0)] 
    lastplace = ((0,0),0)
    cur = 0
    while curvisited < H*W:
        q1 = queue.Queue()
        cur += 1
        while not q.empty():
            pack = q.get()
            y = pack[0][0]
            x = pack[0][1]
            num = pack[1]
            for move in movelist:
                if y+move[0] == -1 or y + move[0] == H or x+move[1] == -1 or x + move[1] == W:
                    continue
                elif visitedlist[y+move[0]][x+move[1]] == 1:
                    continue
                elif S[y+move[0]][x+move[1]] == "#":
                    continue
                else:
                    visitedlist[y+move[0]][x+move[1]] = 1
                    curvisited += 1
                    q1.put(((y+move[0],x+move[1]),num+1))
            if curvisited == H*W:
                break
        q = q1
    return cur

H,W,S = accept_input()
q = queue.Queue()
visitedlist = np.zeros((H,W))
curvisited = 0
for i in range(len(S)):
    for j in range(len(S[i])):
        if S[i][j] == "#":
            q.put(((i,j),0))
            visitedlist[i][j] == 1
            curvisited += 1
#幅優先探索
result = widthsearch(q)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import re
import copy
import numpy as np
import queue

def accept_input():
    H,W = map(int,input().split())
    S = []
    for _ in range(H):
        S.append(input())
    return H,W,S


def widthsearch(q):
    movelist = [(0,1),(0,-1),(1,0),(-1,0)] 
    lastplace = ((0,0),0)
    while not q.empty():
        pack = q.get()
        lastplace = pack
        y = pack[0][0]
        x = pack[0][1]
        num = pack[1]
        for move in movelist:
            if y+move[0] == -1 or y + move[0] == H or x+move[1] == -1 or x + move[1] == W:
                continue
            elif visitedlist[y+move[0]][x+move[1]] == 1:
                continue
            elif S[y+move[0]][x+move[1]] == "#":
                continue
            else:
                visitedlist[y+move[0]][x+move[1]] = 1
                q.put(((y+move[0],x+move[1]),num+1))
    return lastplace[1]

H,W,S = accept_input()
q = queue.Queue()
visitedlist = np.zeros((H,W))

for i in range(len(S)):
    for j in range(len(S[i])):
        if S[i][j] == "#":
            q.put(((i,j),0))
            visitedlist[i][j] == 1
#幅優先探索
result = widthsearch(q)
print(result)

Submission status: Time Limit Exceeded

Solution code:
#!/bin/python3
import sys
from collections import deque
from itertools import chain

def chmax(x,y):return x if x>y else y

def bfs(x,y):
  queue=deque([(x,y)])
  visited[x][y]=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if nx>=0 and nx<h and ny>=0 and ny<w and s[nx][ny]=="." \
      	and (visited[nx][ny]==-1 or visited[nx][ny]>visited[x][y]+1):
        visited[nx][ny]=visited[x][y]+1
        queue.append((nx,ny))
        #print(queue)
  return
if __name__ == '__main__':
  input=sys.stdin.readline
  h,w=map(int,input().split())
  s=[tuple(input()) for _ in range(h)]

  #移動先4方向
  dx = (1, 0, -1,  0)
  dy = (0, 1,  0, -1)
  
  #訪問リストを作る
  visited=[[-1]*w for _ in range(h)]

  #黒マスの位置を取得
  starts=[(i,j) for i in range(h) for j in range(w) if s[i][j]=="#"]
  #print(*starts,sep="\n")
  for sx,sy in starts:
    bfs(sx,sy)
    #print("sx",sx,"sy",sy)
    #print(*visited,sep="\n")
  print(max(list(chain(*visited))))

Submission status: Time Limit Exceeded

Solution code:
#!/bin/python3
import sys
import operator
from collections import deque,Counter
from itertools import chain

def chmax(x,y):return x if x>y else y

def bfs(x,y):
  queue=deque([[x,y]])
  visited[x][y]=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if nx>=0 and nx<h and ny>=0 and ny<w and s[nx][ny]=="." \
      	and (visited[nx][ny]==-1 or visited[nx][ny]>visited[x][y]+1):
        visited[nx][ny]=visited[x][y]+1
        queue.append([nx,ny])
        #print(queue)
  return
if __name__ == '__main__':
  input=sys.stdin.readline
  h,w=map(int,input().split())
  s=[list(input()) for _ in range(h)]

  #移動先4方向
  dx = [1, 0, -1,  0]
  dy = [0, 1,  0, -1]
  #訪問リストを作る
  visited=[[-1]*w for _ in range(h)]

  #黒マスの位置を取得
  starts=[[i,j] for i in range(h) for j in range(w) if s[i][j]=="#"]
  #print(*starts,sep="\n")
  for sx,sy in starts:
    bfs(sx,sy)
    #print("sx",sx,"sy",sy)
    #print(*visited,sep="\n")
  max_=max(list(chain(*visited)))
  print(max_)

Submission status: Time Limit Exceeded

Solution code:
#!/bin/python3
import sys
import operator
from collections import deque,Counter

def chmax(x,y):return x if x>y else y

def bfs(x,y):
  queue=deque([[x,y]])
  visited[x][y]=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if nx>=0 and nx<h and ny>=0 and ny<w and s[nx][ny]=="." \
      	and (visited[nx][ny]==-1 or visited[nx][ny]>visited[x][y]+1):
        visited[nx][ny]=visited[x][y]+1
        queue.append([nx,ny])
        #print(queue)
  return
if __name__ == '__main__':
  input=sys.stdin.readline
  h,w=map(int,input().split())
  s=[list(input()) for _ in range(h)]

  #移動先4方向
  dx = [1, 0, -1,  0]
  dy = [0, 1,  0, -1]
  #訪問リストを作る
  visited=[[-1]*w for _ in range(h)]

  #黒マスの位置を取得
  starts=[[i,j] for i in range(h) for j in range(w) if s[i][j]=="#"]
  #print(*starts,sep="\n")
  for sx,sy in starts:
    bfs(sx,sy)
    #print("sx",sx,"sy",sy)
    #print(*visited,sep="\n")
  max_=0
  for i in range(h):
    for j in range(w):
      max_=chmax(visited[i][j],max_)
  print(max_)

Submission status: Time Limit Exceeded

Solution code:
#!/bin/python3
import sys
import operator
from collections import deque,Counter

input=sys.stdin.readline
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]

#移動先4方向
dx = [1, 0, -1,  0]
dy = [0, 1,  0, -1]
#訪問リストを作る
visited=[[-1]*w for _ in range(h)]

def bfs(x,y):
  queue=deque([[x,y]])
  visited[x][y]=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx,ny=x+dx[i],y+dy[i]
      if nx>=0 and nx<h and ny>=0 and ny<w and s[nx][ny]=="." \
      	and (visited[nx][ny]==-1 or visited[nx][ny]>visited[x][y]+1):
        visited[nx][ny]=visited[x][y]+1
        queue.append([nx,ny])
        #print(queue)
  return
if __name__ == '__main__':
  #黒マスの位置を取得
  starts=[[i,j] for i in range(h) for j in range(w) if s[i][j]=="#"]
  #print(*starts,sep="\n")
  for sx,sy in starts:
    bfs(sx,sy)
    #print("sx",sx,"sy",sy)
    #print(*visited,sep="\n")
  max_=0
  for i in range(h):
    for j in range(w):
      max_=max(visited[i][j],max_)
  print(max_)