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 sys
sys.setrecursionlimit(10**7)
from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
m=[[-1]*W for i in range(H)]

from collections import deque
q=deque()
for y in range(H):
  for x in range(W):
    if A[y][x]=='#':
      q.append((y,x))
      m[y][x]=0      
      
def bfs(q,m):
  d=0
  while q:
    y,x=q.popleft()
    d=m[y][x]
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W and m[ny][nx]==-1 and A[ny][nx]!='#':
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1            
bfs(q,m)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,m[i][j])    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
INF=10**6
dy=[0,0,1,-1]
dx=[1,-1,0,0]
m=[[INF]*W for i in range(H)]

from collections import deque

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

      
def bfs(q,m):
  d=0
  while q:
    y,x=q.popleft()
    d=m[y][x]
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W and m[ny][nx]==INF and A[ny][nx]!='#':
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1
            
bfs(q,m)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,m[i][j])
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
INF=10**6
dy=[0,0,1,-1]
dx=[1,-1,0,0]
m=[[INF]*W for i in range(H)]

from collections import deque

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

      
def bfs(q,m):
  d=0
  while q:
    y,x=q.popleft()
    d=m[y][x]
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W and m[ny][nx]==INF and A[ny][nx]!='#':
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1
            
bfs(q,m)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,m[i][j])
    
print(ans)

Submission status: Time Limit Exceeded

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

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0

for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]

from collections import deque
def bfs(maze):
    ans = 0
    d = [[-1] * w for _ in range(h)]
    que = deque([])
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '#':
                que.append([i, j])
                d[i][j] = 0
    #que = deque([[sy, sx]])
    #d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w  and 0 <= ny < h  and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                ans = max(ans, d[ny][nx])
                que.append([ny, nx])
                
    return ans

print(bfs(maze))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
from collections import deque
def bfs(maze):
    d = [[-1] * w for _ in range(h)]
    que = deque([])
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '#':
                que.append([i, j])
                d[i][j] = 0
    #que = deque([[sy, sx]])
    #d[sy][sx] = 0
    while que:
        y, x = que.popleft()
 
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w  and 0 <= ny < h  and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
                
    return d
import numpy as np
ansray = np.array(bfs(maze))
print(np.max(ansray))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]

ans = 0
Q = []
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            A[h][w]="."
            Q.append((0,h,w))
while Q:
    c,h,w = Q.pop(0)
    if min(h,w)<0 or h>=H or w>=W:continue
    if A[h][w]=="#":continue
    A[h][w] = "#"
    for i in [-1,1]:
        Q.append((c+1,h+i,w))
        Q.append((c+1,h,w+i))
    ans = max(ans,c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dist = [[float('inf')]*w for _ in range(h)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))
visited = [[0]*w for _ in range(h)]

def bfs(li):
  q = deque(li)
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy 
      nx = x + dx 
      if 0<=ny<h and 0<=nx<w and a[ny][nx]=='.' and visited[ny][nx]==0 and dist[ny][nx]>dist[y][x]+1:
        dist[ny][nx] = dist[y][x] + 1
        visited[ny][nx] = 1
        q += [[ny, nx]]

li = []
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      li += [[i, j]]
      dist[i][j] = 0
      visited[i][j] = 1

bfs(li)

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, dist[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dist = [[float('inf')]*w for _ in range(h)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(li):
  q = deque(li)
  visited = [[0]*w for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy 
      nx = x + dx 
      if 0<=ny<h and 0<=nx<w and a[ny][nx]=='.' and visited[ny][nx]==0 and dist[ny][nx]>dist[y][x]+1:
        dist[ny][nx] = dist[y][x] + 1
        visited[ny][nx] = 1
        q += [[ny, nx]]

li = []
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      li += [[i, j]]
      dist[i][j] = 0

bfs(li)

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, dist[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dist = [[float('inf')]*w for _ in range(h)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
  q = deque([[sy, sx]])
  dist[sy][sx] = 0 
  visited = [[0]*w for _ in range(h)]
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy 
      nx = x + dx 
      if 0<=ny<h and 0<=nx<w and a[ny][nx]=='.' and visited[ny][nx]==0 and dist[ny][nx]>dist[y][x]+1:
        dist[ny][nx] = dist[y][x] + 1
        visited[ny][nx] = 1
        q += [[ny, nx]]


for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      bfs(i,j)

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, dist[i][j])

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)]
#print(a)
#黒のマスを探索する
#黒のマスの周囲四マスを黒に変更する
#探索済みのところはTrueにする
log=[[-1]*W for i in range(H)]
def bfs():
    task=deque([])
    #初め黒のマスを検索する
    for i in range(H):
        for j in range(W):
            if a[i][j]=='#':
                task.append((i,j))
                log[i][j]=0

    dh=[0,1,0,-1]
    dw=[1,0,-1,0]

    while task:
        h,w=task.popleft()
        #四マスを探索する
        for i in range(4):
            nh=h+dh[i]
            nw=w+dw[i]
            if not(0<=nh<H and 0<=nw<W):continue
            if a[nh][nw]=='#':continue
            a[nh][nw]='#'
            log[nh][nw]=log[h][w]+1
            task.append((nh,nw))

def ans_check():
    ans=0
    for i in range(H):
        for j in range(W):
            if ans<log[i][j]:ans=log[i][j]

    print(ans)

bfs()
ans_check()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split()) 
a=[list(map(int,list(input().replace('.','0').replace('#','1')))) for i in range(h)] 


cnt=0 
while sum(map(sum, a))<h*w: 
    cnt+=1 
    tmp=[] 
    for i in range(h): 
        for j in range(w): 
            if a[i][j]==1: 
                tmp+=[[i,j]] 
    for tmpxy in tmp: 
        i,j=tmpxy[0],tmpxy[1] 
        if i>0: 
            a[i-1][j]=1 
        if i<h-1: 
            a[i+1][j]=1 
        if j>0: 
            a[i][j-1]=1 
        if j<w-1: 
            a[i][j+1]=1 
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w=map(int,input().split())
a = [input() for _ in range(h)]
move=((1,0),(0,1),(-1,0),(0,-1))

que=deque([])
visited=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            que.append((i,j,0))
            visited[i][j]=1


while len(que)>0:       
    ci,cj,d=que.popleft()
    for mi,mj in move:
        ni,nj=mi+ci,mj+cj
        if 0<=ni<h and 0<=nj<w and visited[ni][nj]==0:
            if a[ni][nj]==".":
                visited[ni][nj]=1
                que.append((ni,nj,d+1))

print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = deque([])
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.append((i, j))
            D[i][j] = 0
    A.append(S)

while q:
    pos = q.popleft()
    py, px = pos[0], pos[1]
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, D[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = deque([])
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.append((i, j))
            D[i][j] = 0
    A.append(S)

ans = 0
while q:
    pos = q.popleft()
    py, px = pos[0], pos[1]
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            ans = max(ans, D[ny][nx])
            q.append((ny, nx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = queue.Queue()
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.put((i, j))
            D[i][j] = 0
    A.append(S)

ans = 0
while not q.empty():
    pos = q.get()
    py, px = pos[0], pos[1]
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            ans = max(ans, D[ny][nx])
            q.put((ny, nx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	for i,j in q:
		for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
			if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
				grid[r][c] = grid[i][j] + 1
				maxx = max(maxx,grid[r][c])
				q.append([r,c])
	return maxx

H,W = map(int, raw_input().split())
grid = []
for h in range(H):
	s = list(raw_input())
	grid.append(s)
ans = solve(grid)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	for i,j in q:
		for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
			if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
				grid[r][c] = grid[i][j] + 1
				maxx = max(maxx,grid[r][c])
				q.append([r,c])
	return maxx

H,W = map(int, input().split())
grid = []
for h in range(H):
	s = list(input())
	grid.append(s)
ans = solve(grid)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = queue.Queue()
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.put((i, j))
            D[i][j] = 0
    A.append(S)

ans = 0
while not q.empty():
    pos = q.get()
    py, px = pos[0], pos[1]
    ans = max(ans, D[py][px])
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            q.put((ny, nx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, raw_input().split())
grid = []
for h in range(H):
	s = list(raw_input())
	grid.append(s)
ans = solve(grid)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *                # alpha = ascii_lowercase
from random import *                # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from sys import stdin
from sys import maxsize
from operator import *                # d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter        # d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, stdin.readline().rstrip().split())
grid = []
for h in range(H):
	s = list(input())
	grid.append(s)
ans = solve(grid)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = queue.Queue()
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.put((i, j))
            D[i][j] = 0
    A.append(S)

ans = 0
while not q.empty():
    pos = q.get()
    ans = max(ans, D[pos[0]][pos[1]])
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = pos[0] + y
        nx = pos[1] + x
        if 0 <= nx and nx < W and 0 <= ny and ny < H:
            if D[ny][nx] < 0:
                D[ny][nx] = D[pos[0]][pos[1]] + 1
                q.put((ny, nx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *                # alpha = ascii_lowercase
from random import *                # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from sys import stdin
from sys import maxsize
from operator import *                # d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter        # d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, stdin.readline().rstrip().split())
grid = []
for h in range(H):
	s = list(input())
	grid.append(s)
ans = solve(grid)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from string import *                # alpha = ascii_lowercase
from random import *                # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from sys import stdin
from sys import maxsize
from operator import *                # d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter        # d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	for i,j in q:
		for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
			if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
				grid[r][c] = grid[i][j] + 1
				maxx = max(maxx,grid[r][c])
				q.append([r,c])
	return maxx

H,W = map(int, stdin.readline().rstrip().split())
grid = []
for h in range(H):
	s = list(input())
	grid.append(s)
ans = solve(grid)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

ans = 0
while queue:
    point = queue.popleft()
    ans = max(ans,point[2])
    for y,x in ((1,0),(0,1),(-1,0),(0,-1)):
        if A[point[0]+y][point[1]+x] == ".":
            A[point[0]+y][point[1]+x] = "#"
            queue.append((point[0]+y,point[1]+x,point[2]+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF=float("inf")
def main():
    H,W=map(int, input().split())
    A=[input()for _ in range(H)]
    D=[[0 if A[h][w]=="#" else INF for w in range(W)] for h in range(H)]
    for h in range(H):
        for w in range(1,W):
            D[h][w]=min(D[h][w],D[h][w-1]+1)
        for w in range(W-2, -1, -1):
            D[h][w]=min(D[h][w],D[h][w+1]+1)
    for w in range(W):
        for h in range(1,H):
            D[h][w]=min(D[h][w],D[h-1][w]+1)
        for h in range(H-2, -1, -1):
            D[h][w]=min(D[h][w],D[h+1][w]+1)
    print(max(d for dd in D for d in dd))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import sys
import heapq
#import copy
#import numpy as np
from collections import deque

h,w=list(map(int,input().split()))
a=[['.']*w for i in range(h)]
q=deque()
cnt=0
for i in range(h):
    for j,x in enumerate(input()):
        if x=='#':
            deque.append(q,[i,j])
            a[i][j]=0

while len(q)>0:
    hh,ww=deque.popleft(q)

    for nh,nw in [[hh+dh,ww+dw] for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]]:
        
        if 0>nh or nh>=h or 0>nw or nw>=w or a[nh][nw]!='.':
            continue
        
        a[nh][nw]=a[hh][ww]+1
        cnt=max(cnt,a[nh][nw])

        deque.append(q,[nh,nw])

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import copy
import numpy as np
from collections import deque

h,w=list(map(int,input().split()))
a=[['.']*w for i in range(h)]
q=deque()
cnt=0
for i in range(h):
    for j,x in enumerate(sys.stdin.readline().strip()):
        if x=='#':
            deque.append(q,[i,j])
            a[i][j]=0

while len(q)>0:
    hh,ww=deque.popleft(q)

    for nh,nw in [[hh+dh,ww+dw] for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]]:
        
        if 0>nh or nh>=h or 0>nw or nw>=w or a[nh][nw]!='.':
            continue
        
        a[nh][nw]=a[hh][ww]+1
        cnt=max(cnt,a[nh][nw])

        deque.append(q,[nh,nw])

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import copy
import numpy as np
from collections import deque

h,w=list(map(int,input().split()))
a=[['.']*w for i in range(h)]
q=deque()
cnt=0
for i in range(h):
    for j,x in enumerate(input()):
        if x=='#':
            deque.append(q,[i,j])
            a[i][j]=0

while len(q)>0:
    hh,ww=deque.popleft(q)

    for nh,nw in [[hh+dh,ww+dw] for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]]:
        
        if 0>nh or nh>=h or 0>nw or nw>=w or a[nh][nw]!='.':
            continue
        
        a[nh][nw]=a[hh][ww]+1
        cnt=max(cnt,a[nh][nw])

        deque.append(q,[nh,nw])

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from queue import Queue

(h, w) = [int(i) for i in input().rstrip().split(" ")]
map = [input() for i in range(h)]
step = [[h * w + 1 for i in range(w)] for j in range(h)]


class Pos:
    def __init__(self, r, c):
        self.r = r
        self.c = c


queue = Queue()

for i in range(h):
    for j in range(w):
        if map[i][j] == "#":
            queue.put(Pos(i,j))
            step[i][j] = 0

while not queue.empty():
    cur = queue.get()
    next = step[cur.r][cur.c] + 1
    for i in range(cur.r-1, cur.r + 2):
        if i < 0:
            continue
        if i >= h:
            break
        for j in range(cur.c-1, cur.c + 2):
            if j < 0:
                continue
            if j >= w:
                break
            if cur.r == i and cur.c == j:
                continue
            if cur.r != i and cur.c != j:
                continue
            if step[i][j] <= next:
                continue
            step[i][j] = next
            queue.put(Pos(i,j))

ans = max([max(i) for i in step])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

H,W=map(int,input().split())
c=["$"*(W+2)]+["$"+input()+"$" for _ in range(H)]+["$"*(W+2)]

ans=0
dist=[[-1]*(W+2) for _ in range(H+2)]
que=queue.Queue()

for i in range(H+2):
    for g in range(W+2):
        if c[i][g]=="#":
            que.put((i,g))
            dist[i][g]=0

while not que.empty():
    h,w=que.get()
    direction=[(0,-1),(0,1),(1,0),(-1,0)]
    for y,x in direction:
        if c[h+y][w+x]=="." and dist[h+y][w+x]==-1:
            que.put((h+y,w+x))
            dist[h+y][w+x]=dist[h][w]+1
            ans=max(ans,dist[h+y][w+x])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  import sys
  
  h,w=map(int,input().split())
  a=[list(map(str,sys.stdin.readline().strip("\n"))) for e in range(h)]
  b=[[True if x=="#" else False for x in y] for y in a]
  xy=[(1,0),(-1,0),(0,1),(0,-1)]
  
  que=deque()
  que.append("LOOP")
  for i in range(h):
    for j in range(w):
      if b[i][j]:
        que.append([i,j])
  count=0

  while(True):
    
    check=all(all(x) for x in b)
    if check:
      break
    
    p=que.popleft()
    
    if p=="LOOP":
      count+=1
      que.append("LOOP")
      continue
    
    i,j=p[0],p[1]
    
    for x,y in xy:
      if 0<=i+x<h and 0<=j+y<w and b[i+x][j+y]==False:
        b[i+x][j+y]=True
        que.append([i+x,j+y])
    
  print(count)
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  
  h,w=map(int,input().split())
  a=[list(map(str,input().strip("\n"))) for e in range(h)]
  b=[[True if x=="#" else False for x in y] for y in a]
  xy=[(1,0),(-1,0),(0,1),(0,-1)]
  
  que=deque()
  que.append("LOOP")
  for i in range(h):
    for j in range(w):
      if b[i][j]:
        que.append([i,j])
  count=0

  while(True):
    
    check=all(all(x) for x in b)
    if check:
      break
    
    p=que.popleft()
    
    if p=="LOOP":
      count+=1
      que.append("LOOP")
      continue
    
    i,j=p[0],p[1]
    
    for x,y in xy:
      if 0<=i+x<h and 0<=j+y<w and b[i+x][j+y]==False:
        b[i+x][j+y]=True
        que.append([i+x,j+y])
    
  print(count)
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

A = []
for i in range(H):
  A.append(input())
  
Q = deque()
visited = [[False for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      Q.append([i,j,0])
      visited[i][j] = True

ans = 0
while len(Q) > 0:
  i,j,dist = Q.popleft()
  for dy, dx in [[1,0], [-1,0], [0,-1], [0,1]]:
    y = i + dy
    x = j + dx
    if y < 0 or H <= y or x < 0 or W <= x:
      continue
    if visited[y][x]:
      continue
    visited[y][x] = True
    Q.append([y,x,dist+1])
    ans = max(ans, dist+1)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import itertools

  h,w=map(int,input().split())
  a=[list(map(str,input().strip("\n"))) for e in range(h)]
  b=[[i,j] for i,j in itertools.product(range(h),range(w)) if a[i][j]=="."]
  xy=[(1,0),(-1,0),(0,1),(0,-1)]

  count=0
  
  while(b):
    k=[]
    for p in b:
      i,j=p[0],p[1]
      f=any(a[i+x][j+y]=="#" for x,y in xy if 0<=i+x<h and 0<=j+y<w)
      if f:
        k.append([i,j])
    
    for q in k:
      i,j=q[0],q[1]
      a[i][j]="#"
      b.remove([i,j])
    count+=1

  print(count)
  

if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

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

checked = [[False for _ in range(W)] for _ in range(H)]

que = deque()
flag = False
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            que.append((i, j))
            checked[i][j] = True
            flag = True

if flag is False:
    print(0)
    exit()

n_que = deque()
step = 0
while len(que):

    h, w = que[0][0], que[0][1]
    que.popleft()
    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if checked[nh][nw] is True:
            continue
        n_que.append((nh, nw))
        checked[nh][nw] = True

    if len(que) == 0:
        if len(n_que) == 0:
            print(step)
            exit()
        que = n_que
        n_que = deque()
        step += 1

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque


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


def make_new_map(p_map):

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

    update_flag = False
    n_map = copy.deepcopy(p_map)
    reached = [[False for _ in range(W)] for _ in range(H)]

    for sh in range(H):
        for sw in range(W):
            if (reached[sh][sw] is False) and (p_map[sh][sw] == '#'):
                # start bfs
                togo = deque()
                togo.append((sh, sw))
                reached[sh][sw] = True
                while len(togo):
                    h, w = togo[0][0], togo[0][1]
                    togo.popleft()
                    for d in range(4):
                        nh, nw = h + dy[d], w + dx[d]
                        if nh < 0 or nw < 0 or nh >= H or nw >= W:
                            continue
                        if reached[nh][nw] is True:
                            continue
                        if n_map[nh][nw] == '.':
                            n_map[nh][nw] = '#'
                            update_flag = True
                        if p_map[nh][nw] == '.':
                            continue
                        togo.append((nh, nw))
                        reached[nh][nw] = True
    return n_map, update_flag


count = 0
past_map, flag = make_new_map(past_map)
while flag:
    count += 1
    past_map, flag = make_new_map(past_map)
print(count)