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 itertools import *
from collections import *
h,w=map(int,input().split())
a=[]
l=[(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    t=list(input())
    a.append(t)
ans=[[float("inf")]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            ans[i][j]=0
            q.append((i,j))
aa=0
while q:
    x,y=q.popleft()
    for xx,yy in l:
        nx,ny=x+xx,y+yy
        if 0<=nx<h and 0<=ny<w:
            if ans[nx][ny]>ans[x][y]+1:
                ans[nx][ny]=ans[x][y]+1
                if ans[nx][ny]>aa:
                    aa=ans[nx][ny]
                if (nx,ny) not in q:
                    q.append((nx,ny))
print(aa)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
from collections import *
from sys import *
input=stdin.readline
h,w=map(int,input().split())
a=[]
l=[(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    t=list(input())
    a.append(t)
ans=[[float("inf")]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            ans[i][j]=0
            q.append((i,j))
while q:
    x,y=q.popleft()
    for xx,yy in l:
        nx,ny=x+xx,y+yy
        if 0<=nx<h and 0<=ny<w:
            if ans[nx][ny]>ans[x][y]+1:
                ans[nx][ny]=ans[x][y]+1
                if (nx,ny) not in q:
                    q.append((nx,ny))
aa=[]
for i in range(h):
    aa.append(max(ans[i]))
print(max(aa))

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
from collections import *
h,w=map(int,input().split())
a=[]
l=[(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    t=list(input())
    a.append(t)
ans=[[float("inf")]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            ans[i][j]=0
            q.append((i,j))
while q:
    x,y=q.popleft()
    for xx,yy in l:
        nx,ny=x+xx,y+yy
        if 0<=nx<h and 0<=ny<w:
            if ans[nx][ny]>ans[x][y]+1:
                ans[nx][ny]=ans[x][y]+1
                if (nx,ny) not in q:
                    q.append((nx,ny))
aa=[]
for i in range(h):
    aa.append(max(ans[i]))
print(max(aa))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
INF=10**18
a=[input() for _ in range(h)]
d=[[INF for _ in range(w)]for _ in range(h)]
q=deque([])
for i in range(h):
  for j in range(w):
    if a[i][j]=='#':
      d[i][j]=0
      q.append((i,j))
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ans=0
while q:
  x,y=q.popleft()
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if 0<=nx<h and 0<=ny<w:
      if d[nx][ny]==INF:
        q.append((nx,ny))
        d[nx][ny]=d[x][y]+1
        ans=max(ans,d[nx][ny])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	mp = [list(input()) for _ in range(h)]
	dist=[[-1] * w for _ in range(h)]
	open_list=queue.Queue()
	for hi, l in enumerate(mp):
		for wi, c in enumerate(l):
			if c == '#':
				dist[hi][wi]=0
				open_list.put(hi*2000+wi)
				
	max_dist=0
	while not open_list.empty():
		hi_wi = open_list.get()
		hi = hi_wi // 2000
		wi = hi_wi % 2000
		d = dist[hi][wi]
		for dw, dh in [(0,1),(0,-1),(1,0),(-1,0)]:
			if -1 == wi+dw or -1 == hi + dh or w == wi+dw or h == hi + dh:
				continue
			if dist[hi+dh][wi+dw] >= 0:
				continue
			#if dist[hi+dh][wi+dw]==-2:
				
			dist[hi+dh][wi+dw]=d+1
			open_list.put(((hi+dh)*2000+wi+dw))
			max_dist=d+1
	print(max_dist)
	#for l in dist:
	#	print(l)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	mp = [list(input()) for _ in range(h)]
	dist=[[-1] * w for _ in range(h)]
	open_list=queue.Queue()
	for hi, l in enumerate(mp):
		for wi, c in enumerate(l):
			if c == '#':
				dist[hi][wi]=0
				open_list.put(hi*2000+wi)
				
	max_dist=0
	while not open_list.empty():
		hi_wi = open_list.get()
		hi = hi_wi // 2000
		wi = hi_wi % 2000
		d = dist[hi][wi]
		for dw, dh in [(0,1),(0,-1),(1,0),(-1,0)]:
			if -1 == wi+dw or -1 == hi + dh or w == wi+dw or h == hi + dh:
				continue
			if dist[hi+dh][wi+dw] >= 0:
				continue
			#if dist[hi+dh][wi+dw]==-2:
				
			dist[hi+dh][wi+dw]=d+1
			open_list.put(((hi+dh)*2000+wi+dw))
			max_dist=d+1
	print(max_dist)
	#for l in dist:
	#	print(l)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	mp = [list(input()) for _ in range(h)]
	dist=[[-1] * w for _ in range(h)]
	open_list=queue.Queue()
	for hi, l in enumerate(mp):
		for wi, c in enumerate(l):
			if c == '#':
				dist[hi][wi]=0
				open_list.put((hi,wi,0))
				
	max_dist=0
	while not open_list.empty():
		hi, wi, d = open_list.get()
		for dw, dh in [(0,1),(0,-1),(1,0),(-1,0)]:
			if -1 == wi+dw or -1 == hi + dh or w == wi+dw or h == hi + dh:
				continue
			if dist[hi+dh][wi+dw] >= 0:
				continue
			dist[hi+dh][wi+dw]=d+1
			open_list.put((hi+dh,wi+dw,d+1))
			max_dist=d+1
	print(max_dist)
	#for l in dist:
	#	print(l)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
 
 
 
print(ans)

Submission status: Time Limit Exceeded

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

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

def dfs(y,x,i):
  d=[[0,1],[0,-1],[1,0],[-1,0]]
  for m in d:
    nx=x+m[0]
    ny=y+m[1]
    if (0<=nx<=w-1) and (0<=ny<=h-1) and b[ny][nx]==0:
      b[ny][nx]=1
      st.append([ny,nx,i+1])

while st:
  y,x,c=st.popleft()
  dfs(y,x,c)
print(c-1)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit


@jit
def main():
    INF = 10 ** 6
    H, W = list(map(int, input().split(' ')))
    A = [input() for _ in range(H)]
    d = [[INF for _ in range(W)] for _ in range(H)]
    # 距離テーブルの初期化
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                d[h][w] = 0
    # 黒マスまでの横方向の最短距離を出す
    for h in range(H):
        # 左から右方向へ探索
        for w in range(1, W):
            d[h][w] = min(d[h][w], 1 + d[h][w - 1])
        # 逆方向
        for w in range(W - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h][w + 1])
    # 縦方向も同様に探索
    for w in range(W):
        for h in range(1, H):
            d[h][w] = min(d[h][w], 1 + d[h - 1][w])
        for h in range(H - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h + 1][w])
    # 黒マスまでの最長距離が答え
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, d[h][w])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    INF = 10 ** 6
    H, W = list(map(int, input().split(' ')))
    A = [input() for _ in range(H)]
    d = [[INF for _ in range(W)] for _ in range(H)]
    # 距離テーブルの初期化
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                d[h][w] = 0
    # 黒マスまでの横方向の最短距離を出す
    for h in range(H):
        # 左から右方向へ探索
        for w in range(1, W):
            d[h][w] = min(d[h][w], 1 + d[h][w - 1])
        # 逆方向
        for w in range(W - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h][w + 1])
    # 縦方向も同様に探索
    for w in range(W):
        for h in range(1, H):
            d[h][w] = min(d[h][w], 1 + d[h - 1][w])
        for h in range(H - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h + 1][w])
    # 黒マスまでの最長距離が答え
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, d[h][w])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in read() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def solve(H, W, grid):

    ans = 0
    while np.sum(grid) != 0:
        next_grid = grid.copy()
        for y in range(H):
            for x in range(W):
                if not grid[x + y * W]:
                    continue
                for i in range(4):
                    if i == 0:
                        nx, ny = x, y + 1
                    elif i == 1:
                        nx, ny = x, y - 1
                    elif i == 2:
                        nx, ny = x + 1, y
                    elif i == 3:
                        nx, ny = x - 1, y
                    if 0 <= nx < W and 0 <= ny < H:
                        if not grid[nx + ny * W]:
                            next_grid[x + y * W] = False
                            break
        ans += 1
        grid = next_grid
    return ans


def main():

    H, W = in_nn()
    grid = np.array(in_map(), np.int8)

    print(solve(H, W, grid))


# AOTコンパイル
def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i4,i4,i1[:])')(solve)
    cc.compile()


if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in read() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    H, W = in_nn()
    grid = in_map()

    ans = 0
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while sum(grid) != 0:

        next_grid = copy.copy(grid)
        for y in range(H):
            for x in range(W):
                if not grid[x + y * W]:
                    continue
                for (px, py) in move:
                    nx, ny = x + px, y + py
                    if 0 <= nx < W and 0 <= ny < H:
                        if not grid[nx + ny * W]:
                            next_grid[x + y * W] = False
                            break
        ans += 1
        grid = next_grid

    # print(grid)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
# from collections import deque
# import pprint
import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# q = deque()
q = []
# for i, j in itertools.product(range(H), range(W)):
for i in range(H):
    for j in range(W):
        if Board[i][j] == '#':
            # Board[i][j] = 0
            q.append((i, j))

ans = 0
# while q:
for i in itertools.count():
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y = yx[0] + d[0]
            x = yx[1] + d[1]
            # y, x = [i+j for i, j in zip(yx, d)]
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                # Board[y][x] = Board[q[0][0]][q[0][1]] + 1
                Board[y][x] = '#'
                qq.append((y, x))
    q = qq
    if not q:
        break

# ans = max(list(itertools.chain.from_iterable(Board)))
# ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
# from collections import deque
# import pprint
# import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# q = deque()
q = []
# for i, j in itertools.product(range(H), range(W)):
for i in range(H):
    for j in range(W):
        if Board[i][j] == '#':
            # Board[i][j] = 0
            q.append((i, j))

ans = 0
while q:
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y, x = [i+j for i, j in zip(yx, d)]
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                # Board[y][x] = Board[q[0][0]][q[0][1]] + 1
                Board[y][x] = '#'
                qq.append((y, x))
    q = qq

# ans = max(list(itertools.chain.from_iterable(Board)))
# ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
# from collections import deque
# import pprint
import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# q = deque()
q = []
for i, j in itertools.product(range(H), range(W)):
    if Board[i][j] == '#':
        # Board[i][j] = 0
        q.append((i, j))

ans = 0
while q:
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y, x = [i+j for i, j in zip(yx, d)]
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                # Board[y][x] = Board[q[0][0]][q[0][1]] + 1
                Board[y][x] = '#'
                qq.append((y, x))
    q = qq

# ans = max(list(itertools.chain.from_iterable(Board)))
# ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
from collections import deque
# import pprint
import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

# q = deque()
q = []
for i, j in itertools.product(range(H), range(W)):
    if Board[i][j] == '#':
        # Board[i][j] = 0
        q.append((i, j))

ans = 0
while q:
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y, x = [i+j for i, j in zip(yx, d)]
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                # Board[y][x] = Board[q[0][0]][q[0][1]] + 1
                Board[y][x] = '#'
                qq.append((y, x))
    q = qq

# ans = max(list(itertools.chain.from_iterable(Board)))
# ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
#!/home/matsumotokazuho/.pyenv/shims/pypy
# import math
# from copy import deepcopy
# from operator import itemgetter
# from collections import defaultdict
# from collections import Counter
from collections import deque
# import pprint
import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

q = deque()
for i, j in itertools.product(range(H), range(W)):
    if Board[i][j] == '#':
        Board[i][j] = 0
        q.append((i, j))

while q:
    for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        y, x = [i+j for i, j in zip(q[0], d)]
        if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
            pass
        elif Board[y][x] == '.':
            Board[y][x] = Board[q[0][0]][q[0][1]] + 1
            q.append((y, x))
    q.popleft()

# ans = max(list(itertools.chain.from_iterable(Board)))
ans = max(itertools.chain.from_iterable(Board))
# pprint.pprint(Board)
print(ans)

Submission status: Time Limit Exceeded

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


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    H,W=map(int,input().split())
    maze=[list(input()) for i in range(H)]
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        for j in range(W) :
            if maze[i][j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :                             #forではなく各if構文だと通った…
        h,w,depth=pos.popleft()
        if not D[h+1][w] :
            pos.append([h+1,w,depth+1])
            D[h+1][w]=True

        if not D[h-1][w] :
            pos.append([h-1,w,depth+1])
            D[h-1][w]=True

        if not D[h][w+1] :
            pos.append([h,w+1,depth+1])
            D[h][w+1]=True

        if not D[h][w-1] :
            pos.append([h,w-1,depth+1])
            D[h][w-1]=True

    return depth            

print(search())

Submission status: Time Limit Exceeded

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

#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        for j in range(W) :
            if maze[i][j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :                             #forではなく各if構文だと通った…
        h,w,depth=pos.popleft()
        if not D[h+1][w] :
            pos.append([h+1,w,depth+1])
            D[h+1][w]=True

        if not D[h-1][w] :
            pos.append([h-1,w,depth+1])
            D[h-1][w]=True

        if not D[h][w+1] :
            pos.append([h,w+1,depth+1])
            D[h][w+1]=True

        if not D[h][w-1] :
            pos.append([h,w-1,depth+1])
            D[h][w-1]=True

    return depth            

print(search())

Submission status: Time Limit Exceeded

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


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    H,W=map(int,input().split())
    pos=deque([])

    D= [[True]*(W+2)]                                  #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]     #True FalseFalseTrue
    D.append([True]*(W+2))                             #True True True True

    for i in range(H) :
        maze=input()
        for j in range(W) :
            if maze[j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :
        h,w,depth=pos.popleft()
        for p,q in [[-1,0],[1,0],[0,-1],[0,1]] :
            if not D[h+p][w+q] :
                pos.append([h+p,w+q,depth+1])
                D[h+p][w+q]=True

    return depth            

print(search())

Submission status: Time Limit Exceeded

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



#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    pos=deque([])

    D= [[True]*(W+2)]   
    D+=[[True]+[False]*W+[True] for i in range(H)]
    D.append([True]*(W+2))

    for i in range(H) :
        for j in range(W) :
            if maze[i][j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :
        h,w,depth=pos.popleft()
        for p,q in [[-1,0],[1,0],[0,-1],[0,1]] :
            if not D[h+p][w+q] :
                pos.append([h+p,w+q,depth+1])
                D[h+p][w+q]=True

    return depth            

#-------------------------------------------------------------------------
#動作
print(search())

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    A = [False] * (H * W)
    Q = queue.Queue()

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.put((h, w, 0))
                A[h * W + w] = True

    res = V(max)
    while not Q.empty():
        h, w, d = Q.get()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if A[hh * W + ww]:
                    continue
                Q.put((hh, ww, d + 1))
                A[hh * W + ww] = True
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    S = set()
    Q = queue.Queue()

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.put((h, w, 0))
                S.add((h, w))

    res = V(max)
    while not Q.empty():
        h, w, d = Q.get()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if (hh, ww) in S:
                    continue
                Q.put((hh, ww, d + 1))
                S.add((hh, ww))
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    A = [[False for _ in range(W)] for _ in range(H)]
    Q = queue.Queue()

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.put((h, w, 0))
                A[h][w] = True

    res = V(max)
    while not Q.empty():
        h, w, d = Q.get()
        res.ud(d)

        L = [(h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)]
        for hh, ww in L:
            if 0 <= hh < H and 0 <= ww < W:
                if A[hh][ww]:
                    continue
                Q.put((hh, ww, d + 1))
                A[hh][ww] = True
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    # 黒のマスからbfsする
    queue = deque()
    visit = [-1] * (W*H)

    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append(W*i + j)
                visit[W*i + j] = 0
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    adj[W*i + j].append(W*y + x)
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
    print(max(visit))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(4100000)
def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
    visited = [[0] * W for _ in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while Q:
        y, x = Q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H and not visited[ny][nx]:
                visited[ny][nx] = visited[y][x] + 1
                Q.append((ny,nx))

    ans = 0
    for h in range(H):
        ans = max(ans, max(visited[h]))

    print(ans)




if __name__ == "__main__":
    main()