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:
#ライブラリインポート
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	#初期化
	H, W = getlist()
	AL = []
	AL += ["x"] * (W + 2)
	for i in range(H):
		AL += ["x"] + list(input()) + ["x"]
	AL += ["x"] * (W + 2)

	#BFS初期化
	visit = [0] * (H + 2) * (W + 2)
	time = [0] * (H + 2) * (W + 2)
	q = queue.Queue()
	for i in range((H + 2) * (W + 2)):
		if AL[i] == "#":
			q.put(i)
			visit[i] = 1
		elif AL[i] == "x":
			visit[i] = 1

	while not q.empty():
		v = q.get()
		if visit[v - 1] != 1:
			q.put(v - 1)
			time[v - 1] = time[v] + 1
			visit[v - 1] = 1
		if visit[v + 1] != 1:
			q.put(v + 1)
			time[v + 1] = time[v] + 1
			visit[v + 1] = 1
		if visit[v - W - 2] != 1:
			q.put(v - W - 2)
			time[v - W - 2] = time[v] + 1
			visit[v - W - 2] = 1
		if visit[v + W + 2] != 1:
			q.put(v + W + 2)
			time[v + W + 2] = time[v] + 1
			visit[v + W + 2] = 1
	
	print(max(time))
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
#ライブラリインポート
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	H, W = getlist()
	AL = []
	for i in range(H):
		AL.extend(list(input()))

	#BFS初期化
	visit = [0] * (H * W)
	time = [0] * (H * W)
	q = queue.Queue()
	for i in range(H * W):
		if AL[i] == "#":
			q.put(i)
			visit[i] = 1

	while not q.empty():
		v = q.get()
		if v % W != 0:
			if visit[v - 1] != 1:
				q.put(v - 1)
				time[v - 1] = time[v] + 1
				visit[v - 1] = 1
		if v % W != W - 1:
			if visit[v + 1] != 1:
				q.put(v + 1)
				time[v + 1] = time[v] + 1
				visit[v + 1] = 1
		if W < v:
			if visit[v - W] != 1:
				q.put(v - W)
				time[v - W] = time[v] + 1
				visit[v - W] = 1
		if v < (H - 1) * W :
			if visit[v + W] != 1:
				q.put(v + W)
				time[v + W] = time[v] + 1
				visit[v + W] = 1

	print(max(time))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def isallblack(a):
    h=len(a)-2
    w=len(a[0])-2
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=='.':
                return False
    return True

H,W=map(int,input().split())
a=['.'*(W+2)]
for i in range(H):
    a.append('.'+input()+'.')
a.append('.'*(W+2))

c=[[False for j in range(W+2)] for i in range(H+2)]
cnt=0

while not isallblack(a):
    for i in range(1,H+1):
        for j in range(1,W+1):
            c[i][j]=(a[i][j]=='#' or a[i-1][j]=='#' or a[i+1][j]=='#' or a[i][j-1]=='#' or a[i][j+1]=='#')
    for i in range(1,H+1):
        for j in range(1,W+1):
            if c[i][j]:
                a[i]=a[i][:j]+'#'+a[i][j+1:]
    cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

H, W = map(int, input().split())
M = [[True] * (W+2)]
for i in range(H):
  M += [[True] + [x == '#' for x in sys.stdin.readline().rstrip()] + [True]]
M += [[True] * (W+2)]


nq = []
for y in range(1, H+1):
  for x in range(1, W+1):
    if M[y][x]:
      nq += [(x, y)]

res = 0
while len(nq) > 0:
  q = nq
  nq = []
  for x, y in q:
    if not M[y-1][x]:
      nq += [(x, y-1)]
      M[y-1][x] = True
    if not M[y+1][x]:
      nq += [(x, y+1)]
      M[y+1][x] = True
    if not M[y][x-1]:
      nq += [(x-1, y)]
      M[y][x-1] = True
    if not M[y][x+1]:
      nq += [(x+1, y)]
      M[y][x+1] = True
  res += 1

print(res-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
M = [[True] * (W+2)]
for i in range(H):
  M.append([True] + [x == '#' for x in input()] + [True])
M.append([True] * (W+2))


nq = []
for y in range(1, H+1):
  for x in range(1, W+1):
    if M[y][x]:
      nq += [(x, y)]

res = 0
while len(nq) > 0:
  q = nq
  nq = []
  for x, y in q:
    if not M[y-1][x]:
      nq += [(x, y-1)]
      M[y-1][x] = True
    if not M[y+1][x]:
      nq += [(x, y+1)]
      M[y+1][x] = True
    if not M[y][x-1]:
      nq += [(x-1, y)]
      M[y][x-1] = True
    if not M[y][x+1]:
      nq += [(x+1, y)]
      M[y][x+1] = True
  res += 1

print(res-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
M = [[True] * (W+2)]
for i in range(H):
  M.append([True] + [x == '#' for x in input()] + [True])
M.append([True] * (W+2))


nq = []
for y in range(1, H+1):
  for x in range(1, W+1):
    if M[y][x]:
      nq.append((x, y))

nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
while len(nq) > 0:
  q = nq
  nq = []
  while len(q) > 0:
    x, y = q.pop()
    if not M[y-1][x]:
      nq.append((x, y-1))
      M[y-1][x] = True
    if not M[y+1][x]:
      nq.append((x, y+1))
      M[y+1][x] = True
    if not M[y][x-1]:
      nq.append((x-1, y))
      M[y][x-1] = True
    if not M[y][x+1]:
      nq.append((x+1, y))
      M[y][x+1] = True
  res += 1

print(res-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
M = [[True] * (W+2)]
for i in range(H):
  M.append([True] + [x == '#' for x in input()] + [True])
M.append([True] * (W+2))


nq = []
for y in range(1, H+1):
  for x in range(1, W+1):
    if M[y][x]:
      nq.append((x, y))

nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
while len(nq) > 0:
  q = nq[:]
  nq = []
  while len(q) > 0:
    x, y = q.pop()
    if not M[y-1][x]:
      nq.append((x, y-1))
      M[y-1][x] = True
    if not M[y+1][x]:
      nq.append((x, y+1))
      M[y+1][x] = True
    if not M[y][x-1]:
      nq.append((x-1, y))
      M[y][x-1] = True
    if not M[y][x+1]:
      nq.append((x+1, y))
      M[y][x+1] = True
  q = nq
  res += 1

print(res-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
M = [[True] * (W+2)]
for i in range(H):
  M.append([True] + [x == '#' for x in input()] + [True])
M.append([True] * (W+2))


nq = []
for y in range(1, H+1):
  for x in range(1, W+1):
    if M[y][x]:
      nq.append((x, y))

nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
while len(nq) > 0:
  q = nq[:]
  nq = []
  while len(q) > 0:
    x, y = q.pop()
    for dx, dy in nexts:
      nx, ny = x+dx, y+dy
      if M[ny][nx]:
        continue
      nq.append((nx, ny))
      M[ny][nx] = True
  q = nq
  res += 1

print(res-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
M = [list(input()) for i in range(H)]
reached = [[False for i in range(W)] for j in range(H)]
nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]

nq = []
for y in range(H):
  for x in range(W):
    if M[y][x] == '#':
      reached[y][x] = True
      nq.append((x, y))

res = 0
while len(nq) > 0:
  q = nq[:]
  nq = []
  while len(q) > 0:
    x, y = q.pop()
    for dx, dy in nexts:
      nx, ny = x+dx, y+dy
      if nx < 0 or nx >= W or ny < 0 or ny >= H or reached[ny][nx]:
        continue
      nq.append((nx, ny))
      reached[ny][nx] = True
  q = nq
  res += 1

print(res-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
M = [list(input()) for i in range(H)]
reached = [[False for i in range(W)] for j in range(H)]
nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]

nq = []
for y in range(H):
  for x in range(W):
    if M[y][x] == '#':
      reached[y][x] = True
      nq.append((x, y))

res = 0
while len(nq) > 0:
  q = nq[:]
  nq = []
  while len(q) > 0:
    x, y = q.pop()
    for dx, dy in nexts:
      nx, ny = x+dx, y+dy
      if nx < 0 or nx >= W or ny < 0 or ny >= H or reached[ny][nx]:
        continue
      nq.append((nx, ny))
      reached[ny][nx] = True
  if len(nq) > 0:
    q = nq
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
M = [list(input()) for i in range(H)]
reached = [[False for i in range(W)] for j in range(H)]
nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]

nq = []
for y in range(H):
  for x in range(W):
    if M[y][x] == '#':
      nq.append((x, y))

res = 0
while len(nq) > 0:
  q = nq[:]
  nq = []
  while len(q) > 0:
    x, y = q.pop()
    for dx, dy in nexts:
      nx, ny = x+dx, y+dy
      if nx < 0 or nx >= W or ny < 0 or ny >= H:
        continue
      if M[ny][nx] == '#' or reached[ny][nx]:
        continue
      nq.append((nx, ny))
      reached[ny][nx] = True
  if len(nq) > 0:
    q = nq
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
M = [list(input()) for i in range(H)]
reached = [[False for i in range(W)] for j in range(H)]
nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]

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

res = 0
while len(q) > 0:
  nq = deque()
  while len(q) > 0:
    x, y = q.popleft()
    for dx, dy in nexts:
      nx, ny = x+dx, y+dy
      if nx < 0 or nx >= W or ny < 0 or ny >= H:
        continue
      if M[ny][nx] == '#' or reached[ny][nx]:
        continue
      nq.append((nx, ny))
      reached[ny][nx] = True
  if len(nq) > 0:
    q = nq
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
"""
出典:https://atcoder.jp/contests/agc033/tasks/agc033_a
"""
H, W = map(int, input().split())
field = [input() for _ in range(H)]
black_field =[[0]*W for _ in range(H)]
queue = []
for h in range(H):
  for w in range(W):
    if field[h][w]=="#":
      black_field[h][w]=1
      queue.append((h,w,1))

dyx = [(1,0),(-1,0),(0,1),(0,-1)]

def main():
  cnt = 0
  while queue:
    y,x,n = queue.pop(0)
    cnt = max(cnt, n)
    for dy, dx in dyx:
      ny, nx = y+dy, x+dx
      if 0<=ny<H and 0<=nx<W:
        if not black_field[ny][nx]:
          black_field[ny][nx] = black_field[y][x]+1
          queue.append((ny,nx,black_field[y][x]+1))
  print(cnt-1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(init):
  q = deque()
  q.append(init)
  while len(q) > 0:
    u = q.popleft()
    x, y = u
    for dx, dy in nexts:
      nx, ny = x+dx, y+dy
      if nx < 0 or nx >= W or ny < 0 or ny >= H:
        continue
      if M[ny][nx] == '#':
        continue
      if d[ny][nx] > d[y][x] + 1:
        d[ny][nx] = d[y][x] + 1
        q.append((nx, ny))


H, W = map(int, input().split())
M = [list(input()) for i in range(H)]
INF = 10 ** 10
d = [[INF for i in range(W)] for j in range(H)]
nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for y in range(H):
  for x in range(W):
    if M[y][x] == '#':
      d[y][x] = 0
      bfs((x, y))

res = 0
for y in range(H):
  for x in range(W):
    if d[y][x] != INF and d[y][x] > res:
      res = d[y][x]

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def main():
    buf = sys.stdin.buffer
    R,C = map(int,buf.readline().split())
    # \nが含まれるから列要素の数が+1
    black = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#')
    sharps = np.where(black==True)[0]

    coord_x = np.array([[j for i in range(C)] for j in range(R)])
    coord_y = np.array([[i for i in range(C)] for j in range(R)])

    sharps = sharps[sharps%(C+1)!=C]

    sharps_x = sharps//(C+1)
    sharps_y = sharps%(C+1)
    for i,(one_sharp_x,one_sharp_y) in enumerate(zip(sharps_x,sharps_y)):
        #one_sharp_x = one//(C+1)
        #one_sharp_y = one%(C+1)
        if i == 0:
            result_np = abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y)
        else:
            result_np = np.minimum(result_np,abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y))

    print(max(result_np.flatten()))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

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

H, W = list(map(int, input().split()))

A = []
for i in range(H):
	A.append(input())

num = [[0]*W for _ in range(H)]
for i in range(H):
	for j in range(W):
		if A[i][j] == ".":
			num[i][j] = 1000000

dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def saiki(i, j, count):
	next_to = []
	#print(i, j)
	#count = copy.deepcopy(count)
	count[i][j] = 1
	for n in range(4):
		x = i + dxy[n][0]
		y = j + dxy[n][1]
		if x < H and y < W and 0 <= x and 0 <= y:
			if num[x][y] > 10000 and count[x][y] == 0:
				saiki(x, y, count)
				#print(i, j)
			next_to.append(num[x][y])
	num[i][j] = min(next_to) + 1
	#print(i, j, num[i][j], next_to,num)

count = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		if num[i][j] > 10000:

			saiki(i, j, count)

max_num = 0
for i in range(H):
	for j in range(W):
		max_num = max(max_num, num[i][j])

print(max_num)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
# \nが含まれるから列要素の数が+1
black = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#')
sharps = np.where(black==True)[0]

coord_x = np.array([[j for i in range(C)] for j in range(R)])
coord_y = np.array([[i for i in range(C)] for j in range(R)])

sharps = sharps[sharps%(C+1)!=C]

sharps_x = sharps//(C+1)
sharps_y = sharps%(C+1)
for i,(one_sharp_x,one_sharp_y) in enumerate(zip(sharps_x,sharps_y)):
    #one_sharp_x = one//(C+1)
    #one_sharp_y = one%(C+1)
    if i == 0:
        result_np = abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y)
    else:
        result_np = np.minimum(result_np,abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y))

print(max(result_np.flatten()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
# \nが含まれるから列要素の数が+1
black = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#')
sharps = np.where(black==True)[0]

coord_x = np.array([[j for i in range(C)] for j in range(R)])
coord_y = np.array([[i for i in range(C)] for j in range(R)])

sharps = sharps[sharps%(C+1)!=C]
for i,one in enumerate(sharps):
    one_sharp_x = one//(C+1)
    one_sharp_y = one%(C+1)
    if i == 0:
        result_np = abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y)
    else:
        result_np = np.minimum(result_np,abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y))

print(max(result_np.flatten()))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int,input().split())
field=[]
spos=deque([])
for i in range(H):
  s=list(input())
  for j in range(W):
    if s[j]=="#":
      spos.append((j,i))
  field.append(s)
  
dx=[1,0,-1,0]
dy=[0,1,0,-1]

ans=-1
while spos:
  for _ in range(len(spos)):
    x,y=spos.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=W or ny<0 or ny>=H:
        pass
      elif field[ny][nx]==".":
        field[ny][nx]="#"
        spos.append((nx,ny))
  ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
field=[]
spos=[]
for i in range(H):
  s=list(input())
  for j in range(W):
    if s[j]=="#":
      spos.append((j,i))
  field.append(s)

dx=[1,0,-1,0]
dy=[0,1,0,-1]

ans=0
while field.count(["#"]*W)<H:
  for _ in range(len(spos)):
    x,y=spos.pop(0)
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=W or ny<0 or ny>=H:
        pass
      elif field[ny][nx]==".":
        field[ny][nx]="#"
        spos.append((nx,ny))
  ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
m = ["" for _ in range(H)] 
sharps = []
for i in range(H):
    m[i] = input()
    for j in enumerate(m[i]):
        if j[1] == "#":
            sharps += [(i,j[0])]

coord = [[(i,j)for i in range(W)] for j in range(H)]

ref_max = 0
for i in range(H):
    for j in range(W):
        tmp_max = min([abs(coord[i][j][0] - one[0]) + abs(coord[i][j][1] - one[1]) for one in sharps])
        if tmp_max > ref_max:
            ref_max = tmp_max
            
print(ref_max)

Submission status: Time Limit Exceeded

Solution code:
H, V = map(int, input().strip().split())
#print(H, V)
grid = [['.'] * V + ['.'] + ['.']]
for i in range(H):
    row = list(input().strip())
    grid.append(['.'] + row + ['.'])
grid.append(['.'] * V + ['.'] + ['.'])
#print(grid)
flag = 1
counter = 0
while flag == 1:
    test = []
    flag = 0
    for i in range(1, H + 1):
        test.append(grid[i][1:-1])
        if '.' in grid[i][1:-1]:
            flag = 1
            counter += 1
            break
    # print(test)
    for i in range(1, H + 1):
        for j in range(1, V + 1):
            #print(i, j, grid[i][j])
            if grid[i][j] == '#':
                #print()
                #print(i, j, grid[i][j])
                #print()
                if grid[i][j + 1] != '#':
                    grid[i][j + 1] = '*'
                if grid[i][j - 1] != '#':
                    grid[i][j - 1] = '*'
                if grid[i + 1][j] != '#':
                    grid[i + 1][j] = '*'
                if grid[i - 1][j] != '#':
                    grid[i - 1][j] = '*'
    #print()
    #print(grid)
    #print()
    for i in range(1, H + 1):
        for j in range(1, V + 1):
            if grid[i][j] == '*':
                grid[i][j] = '#'
    #print(grid)
    #print()
    
#print()
print(counter)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np


def bfs(h, w, board, visited):
    queue = deque([])
    for i in range(h):
        for j in range(w):
            if board[i][j] == "#":
                queue.append([i, j])
                visited[i][j] = 0
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            yn, xn = y+i, x+j
            if yn >= h or xn >= w or yn < 0 or xn < 0:
                continue
            if visited[yn][xn] == -1 and board[yn][xn] == ".":
                visited[yn][xn] = visited[y][x] + 1
                queue.append([yn, xn])

    return np.max(np.array(visited))


def main():
    h, w = map(int, input().split())
    board = [input() for _ in range(h)]
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    print(bfs(h, w, board, visited))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

    q = deque()

    arrived = [[True] * (w + 2)] + \
              [[True] + [False] * w + [True] for _ in range(h)] + \
              [[True] * (w + 2)]

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

    ans = 0
    while q:
        ans += 1
        pop_max = len(q)
        cnt = 0
        while cnt != pop_max:
            i, j = q.popleft()
            if not arrived[i-1][j]:
                arrived[i-1][j] = True
                q.append([i-1, j])

            if not arrived[i + 1][j]:
                arrived[i + 1][j] = True
                q.append([i + 1, j])

            if not arrived[i][j - 1]:
                arrived[i][j - 1] = True
                q.append([i, j - 1])

            if not arrived[i][j + 1]:
                arrived[i][j + 1] = True
                q.append([i, j + 1])

            cnt += 1

    ans -= 1
    print(ans)


def main():
    solve()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


def main():
    h, w = map(int, input().split())
    a = [["#"] * (w + 2)]\
        + [["#"] + list(input()) + ["#"] for _ in range(h)]\
        + [["#"] * (w + 2)]

    fin = [["#"] * (w + 2) for _ in range(h + 2)]

    cnt = 0
    while a != fin:
        cnt += 1
        tmp = deepcopy(a)
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if a[i][j] == "#":
                    tmp[i-1][j] = tmp[i+1][j] = tmp[i][j-1] = tmp[i][j+1] = "#"

        a = deepcopy(tmp)

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def fill(queue):
        footsteps = [[None] * width for _ in range(height)]
        for p, s in queue:
            footsteps[p[1]][p[0]] = -1

        while queue:
            p, s = queue.popleft()
            footsteps[p[1]][p[0]] = s

            for x, y in [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]:
                if 0 <= x < width and 0 <= y < height and footsteps[y][x] is None:
                    queue.append(((x, y), s + 1))
                    footsteps[y][x] = -1  # placeholder

        return s

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '#':
                queue.append(((x, y), 0))
    # queue.append(((10, 10), 0))

    return fill(queue)


def main():
    print(solve())


main()

Submission status: Time Limit Exceeded

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def fill(queue):
        footsteps = dict()
        for pp, s in queue:
            footsteps[pp] = -1

        while queue:
            p, s = queue.popleft()
            footsteps[p] = s

            for pp in [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]:
                if pp not in footsteps and 0 <= pp[0] < width and 0 <= pp[1] < height:
                    queue.append((pp, s + 1))
                    footsteps[pp] = -1  # placeholder

        return s

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '#':
                queue.append(((x, y), 0))
    # queue.append(((10, 10), 0))

    return fill(queue)


def main():
    print(solve())


main()

Submission status: Time Limit Exceeded

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def fill(queue):
        footsteps = dict()
        for pp, s in queue:
            footsteps[pp] = -1

        while queue:
            p, s = queue.popleft()
            footsteps[p] = s

            for pp in [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]:
                if 0 <= pp[0] < width and 0 <= pp[1] < height and pp not in footsteps:
                    queue.append((pp, s + 1))
                    footsteps[pp] = -1  # placeholder

        return s

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '#':
                queue.append(((x, y), 0))

    return fill(queue)


def main():
    print(solve())


main()

Submission status: Time Limit Exceeded

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def fill(queue):
        footsteps = dict()

        s = None
        while queue:
            p, s = queue.popleft()
            footsteps[p] = s

            for pp in [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]:
                if 0 <= pp[0] < width and 0 <= pp[1] < height and field[pp[1]][pp[0]] == '.' and pp not in footsteps:
                    queue.append((pp, s + 1))
                    footsteps[pp] = -1  # placeholder

        return s

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]
    queue = deque()

    for y, line in enumerate(field):
        for x, c in enumerate(line):
            if c == '#':
                queue.append(((x, y), 0))

    return fill(queue)


def main():
    print(solve())


main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
visited = [[False] * w for _ in range(h)]
pts = []
for i in range(h):
    s = input().rstrip()
    for j in range(w):
        if s[j] == '#':
            visited[i][j] = True
            pts.append((i, j))
res = 0
ds = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while True:
    new_pts = []
    for i, j in pts:
        for dx, dy in ds:
            new_i = i + dy
            new_j = j + dx
            if 0 <= new_i < h and 0 <= new_j < w and not visited[new_i][new_j]:
                visited[new_i][new_j] = True
                new_pts.append((new_i, new_j))
    if len(new_pts) > 0:
        res += 1
        pts = new_pts
    else:
        break
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

que=deque([(i,j) for i in range(h) for j in range(w) if a[i][j]])
count=0
while True:
  count+=1
  nque=deque()
  while que:
    y,x=que.popleft()
    if x>0 and not a[y][x-1]:
      a[y][x-1]=True
      nque.append((y,x-1))
    if x<w-1 and not a[y][x+1]:
      a[y][x+1]=True
      nque.append((y,x+1))
    if y>0 and not a[y-1][x]:
      a[y-1][x]=True
      nque.append((y-1,x))
    if y<h-1 and not a[y+1][x]:
      a[y+1][x]=True
      nque.append((y+1,x))
  if nque:
    que=copy.copy(nque)
  else:
    break
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
import queue

def getlist():
	return list(map(int, input().split()))

#初期化
H, W = getlist()
AL = []
AL += ["x"] * (W + 2)
for i in range(H):
	AL += ["x"] + list(input()) + ["x"]
AL += ["x"] * (W + 2)

#BFS初期化
visit = [0] * (H + 2) * (W + 2)
time = [0] * (H + 2) * (W + 2)
q = queue.Queue()
for i in range((H + 2) * (W + 2)):
	if AL[i] == "#":
		q.put(i)
		visit[i] = 1
	elif AL[i] == "x":
		visit[i] = 1

while not q.empty():
	v = q.get()
	if visit[v - 1] != 1:
		q.put(v - 1)
		time[v - 1] = time[v] + 1
		visit[v - 1] = 1
	if visit[v + 1] != 1:
		q.put(v + 1)
		time[v + 1] = time[v] + 1
		visit[v + 1] = 1
	if visit[v - W - 2] != 1:
		q.put(v - W - 2)
		time[v - W - 2] = time[v] + 1
		visit[v - W - 2] = 1
	if visit[v + W + 2] != 1:
		q.put(v + W + 2)
		time[v + W + 2] = time[v] + 1
		visit[v + W + 2] = 1

print(max(time))

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

H,W = inpl()

Alist = [[-1]*W for _ in range(H)]
d_queue = queue.Queue()

count = 0
ans = 0

for k in range(H):
    templist = list(input())
    for l in range(W):
        if templist[l] == "#":
            Alist[k][l] = 0
            d_queue.put((k,l,count))

while not d_queue.empty():
    h,w,c = d_queue.get()
    for a,b in [(0,1),(1,0),(0,-1),(-1,0)]:
        if 0 <= h+a < H and 0 <= w+b < W:
            if Alist[h+a][w+b] == -1:
                d_queue.put((h+a,w+b,c+1))
                ans = max(ans,c+1)
                Alist[h+a][w+b] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
field=[[float('inf') for i in range(w)]for j in range(h)]
q=deque()

for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            field[i][j]=0
ans=0
while q:
    y,x=q.popleft()
    ans=max(ans,field[y][x])
    for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
        ny=dy+y
        nx=dx+x
        if 0<=ny<h and 0<=nx<w and field[ny][nx]==float('inf'):
            field[ny][nx]=field[y][x]+1
            q.append((ny,nx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

H,W = inpl()

Alist = list()

for _ in range(H):
    Alist.append(list(input()))

d_queue = queue.Queue()

count = 0
ans = 0
for i in range(H):
    for j in range(W):
        if Alist[i][j] == "#":
            d_queue.put((i,j,count))

while not d_queue.empty():
    h,w,c = d_queue.get()
    for a,b in [(0,1),(1,0),(0,-1),(-1,0)]:
        if 0 <= h+a < H and 0 <= w+b < W:
            if Alist[h+a][w+b] == ".":
                d_queue.put((h+a,w+b,c+1))
                ans = max(ans,c+1)
                Alist[h+a][w+b] = "#"

print(ans)