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, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

H, W = [int(x) for x in input().split()]
A = []
BQ = deque()
for _ in range(H):
    L = list(input())
    A.append(L)

bCnt = 0
for x in range(W):
    for y in range(H):
        if A[y][x] == '#':
            BQ.append((x, y))
            bCnt += 1


def check(a):
    a2 = sum(a, [])
    cnt = a2.count('.')
    return cnt == 0


def ok(x, y, W, H):
    if x >= 0 and x < W and y >= 0 and y < H:
        return True
    return False


# X,Y座標
DX = [1, -1, 0, 0]
DY = [0, 0, 1, -1]

cnt = 0

while bCnt != H * W:
    newBQ = deque()
    for (x, y) in BQ:
        for (dx, dy) in zip(DX, DY):
            X = x + dx
            Y = y + dy
            if ok(X, Y, W, H) and A[Y][X] == '.':
                A[Y][X] = '#'
                newBQ.append((X, Y))
                bCnt += 1

    cnt += 1

    # print("len:{}".format(len(newBQ)))
    # for a in A:
    #     print(a)
    # print("---")

    BQ = newBQ

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

H, W = [int(x) for x in input().split()]
A = []
BQ = deque()
for _ in range(H):
    L = list(input())
    A.append(L)

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


def check(a):
    a2 = sum(a, [])
    cnt = a2.count('.')
    return cnt == 0


def ok(x, y, W, H):
    if x >= 0 and x < W and y >= 0 and y < H:
        return True
    return False


# X,Y座標
DX = [1, -1, 0, 0]
DY = [0, 0, 1, -1]

cnt = 0
while check(A) == False:
    newBQ = deque()
    for (x, y) in BQ:
        for (dx, dy) in zip(DX, DY):
            X = x + dx
            Y = y + dy
            if ok(X, Y, W, H) and A[Y][X] == '.':
                A[Y][X] = '#'
                newBQ.append((X, Y))
    cnt += 1

    # print("len:{}".format(len(newBQ)))
    # for a in A:
    #     print(a)
    # print("---")

    BQ = newBQ

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

H, W = [int(x) for x in input().split()]
L = []
for _ in range(H):
    L.append(list(input()))

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


def check(M):
    return all([x == '#' for x in sum(M, [])])


def ok(x, y, W, H):
    if x >= 0 and x < W and y >= 0 and y < H:
        return True
    return False


def f(m1):
    ret = [['.'] * W for _ in range(H)]
    for x in range(W):
        for y in range(H):
            for i in range(5):
                X = x + dx[i]
                Y = y + dy[i]
                if ok(X, Y, W, H):
                    if m1[X][Y] == '#':
                        ret[x][y] = '#'
    return ret


def p(M):
    for l in M:
        print(l)


m1 = copy.deepcopy(L)
cnt = 0
while check(m1) == False:
    tmp = copy.deepcopy(m1)
    m1 = f(tmp)
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
dc=0
b=[]
for i in range(h):
  s=input()
  for j in range(w):
    if s[j]=="#":d.append((i,j));dc+=1
  b.append(list(s))
count=0
while dc!=0:
  ld=dc
  dc=0
  for i in range(ld):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==".":b[x[0]+1][x[1]]=count;d.append((x[0]+1,x[1]));dc+=1
    if 0<x[0]:
      if b[x[0]-1][x[1]]==".":b[x[0]-1][x[1]]=count;d.append((x[0]-1,x[1]));dc+=1
    if x[1]<w-1:
      if b[x[0]][x[1]+1]==".":b[x[0]][x[1]+1]=count;d.append((x[0],x[1]+1));dc+=1
    if 0<x[1]:
      if b[x[0]][x[1]-1]==".":b[x[0]][x[1]-1]=count;d.append((x[0],x[1]-1));dc+=1
  count+=1
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
dc=0
b=[]
for i in range(h):
  s=input()
  for j in range(w):
    if s[j]=="#":d.append([i,j]);dc+=1
  b.append(list(s))
count=0
while dc!=0:
  ld=dc
  dc=0
  for i in range(ld):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==".":b[x[0]+1][x[1]]=count;d.append([x[0]+1,x[1]]);dc+=1
    if 0<x[0]:
      if b[x[0]-1][x[1]]==".":b[x[0]-1][x[1]]=count;d.append([x[0]-1,x[1]]);dc+=1
    if x[1]<w-1:
      if b[x[0]][x[1]+1]==".":b[x[0]][x[1]+1]=count;d.append([x[0],x[1]+1]);dc+=1
    if 0<x[1]:
      if b[x[0]][x[1]-1]==".":b[x[0]][x[1]-1]=count;d.append([x[0],x[1]-1]);dc+=1
  count+=1
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
b=[]
for i in range(h):
  s=input()
  for j in range(w):
    if s[j]=="#":d.append([i,j])
  b.append(list(s))
count=0
while len(d)!=0:
  for i in range(len(d)):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==".":b[x[0]+1][x[1]]=count;d.append([x[0]+1,x[1]])
    if 0<x[0]:
      if b[x[0]-1][x[1]]==".":b[x[0]-1][x[1]]=count;d.append([x[0]-1,x[1]])
    if x[1]<w-1:
      if b[x[0]][x[1]+1]==".":b[x[0]][x[1]+1]=count;d.append([x[0],x[1]+1])
    if 0<x[1]:
      if b[x[0]][x[1]-1]==".":b[x[0]][x[1]-1]=count;d.append([x[0],x[1]-1])
  count+=1
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
b=[["#"]*(w+2)]
d=deque()
for i in range(h):
  b.append(["#"])
  s=input()
  for j in range(w):
    if s[j]=="#":d.append([i+1,j+1])
    b[i+1].append(s[j])
  b[i+1].append("#")
b.append(["#"]*(w+2))
count=0
while len(d)!=0:
  for i in range(len(d)):
    x=d.popleft()
    if b[x[0]+1][x[1]]==".":b[x[0]+1][x[1]]=count;d.append([x[0]+1,x[1]])
    if b[x[0]-1][x[1]]==".":b[x[0]-1][x[1]]=count;d.append([x[0]-1,x[1]])
    if b[x[0]][x[1]+1]==".":b[x[0]][x[1]+1]=count;d.append([x[0],x[1]+1])
    if b[x[0]][x[1]-1]==".":b[x[0]][x[1]-1]=count;d.append([x[0],x[1]-1])
  count+=1
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
h, w = map(int, input().split())
s = [input() for i in range(h)]
 
d = [[h+w for j in range(w)] for i in range(h)]
que = deque()
 
#黒だったらスタートキューに入れる
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
        que.append((i, j))
        d[i][j] = 0
 
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
 
 
while que:
    p = que.popleft()
    # 黒にする4方向をループ
    for i in range(4):
        nx = p[1] + dx[i]
        ny = p[0] + dy[i]
 
        if (0<=nx<w) and (0<=ny<h) and (d[ny][nx]==h+w):
            que.append((ny, nx))
            d[ny][nx] = d[p[0]][p[1]] + 1
 
res = max(map(max, d))
print(res)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[]
for i in range(h):
    a=input()
    s.append(a)
x=[[] for i in range(h)]
stack=[[],[]]
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            x[i].append(0)
            stack[0].append([i,j])
        else:
            x[i].append(1)
count=0
#print(x)
sw=0
while stack[sw]:
    [ix,iy]=stack[sw].pop(0)
    for p,m in zip([1,0,0,-1],[0,-1,1,0]):
        if -1<ix+p<h and -1<iy+m<w:
            if x[ix+p][iy+m]==1:
                stack[1-sw].append([ix+p,iy+m])
                x[ix+p][iy+m]=0
    if stack[sw]==[] and stack[1-sw]!=[]:
        sw=1-sw
        count+=1
#print(x)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
C = []
Q = deque()
dist = [[-1]*W for i in range(H)]

for i in range(H):
  s = list(input())
  yxidx = [(i,x) for x,v in enumerate(s) if v == "#"]
  for (y, x) in yxidx:
    Q.append((y,x))
    dist[y][x] = 0
  C.append(s)
X = [1,0,-1,0]
Y = [0,-1,0,1]


while Q:
  y,x = Q.popleft()
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dist[ny][nx] == -1):
      dist[ny][nx] = dist[y][x] + 1
      Q.append((ny,nx))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
C = []
Q = deque()
dist = [[-1]*W for i in range(H)]

for i in range(H):
  s = list(input())
  yxidx = [(i,x) for x,v in enumerate(s) if v == "#"]
  for (y, x) in yxidx:
    Q.append((y,x))
    dist[y][x] = 0
  C.append(s)
X = [1,0,-1,0]
Y = [0,-1,0,1]


while Q:
  y,x = Q.popleft()
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dist[ny][nx] == -1) and (C[ny][nx] != "#"):
      dist[ny][nx] = dist[y][x] + 1
      Q.append((ny,nx))

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

Submission status: Time Limit Exceeded

Solution code:
import os

import itertools
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
A = [list(sys.stdin.readline().rstrip()) for _ in range(H)]


def ok(h, w):
    return 0 <= h < H and 0 <= w < W and A[h][w] == '.'


nexts = []
for h, w in itertools.product(range(H), range(W)):
    if A[h][w] == '#':
        nexts.append((h, w))

delta = [[0, 1], [0, -1], [1, 0], [-1, 0]]
ans = 0
while nexts:
    nn = []
    for dh, dw in delta:
        for h, w in nexts:
            if ok(h + dh, w + dw):
                A[h + dh][w + dw] = '#'
                nn.append((h + dh, w + dw))
    if not nn:
        break
    ans += 1
    nexts = nn
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
HW = [[st for st in input()] for _ in range(H)]
inf = float('inf')
memo = [[inf]*W for _ in range(H)]

def bfs(HW,memo):
    black = []
    for ii in range(H):
        for jj in range(W):
            if HW[ii][jj] == "#":
                black.append((ii,jj))
                memo[ii][jj] = 0
    ans = 0
    while len(black) > 0:
            next = black.pop(0)
            i,j = next
            if 0 <= i - 1:
                if HW[i-1][j] == ".":
                    black.append((i-1,j))
                    HW[i-1][j] = "#"
                    memo[i-1][j] = min(memo[i-1][j],memo[i][j] + 1)
                    if memo[i-1][j] > ans:
                        ans = memo[i-1][j]
            if 0 <= i + 1 < H:
                if HW[i+1][j] == ".":
                    black.append((i+1,j))
                    HW[i+1][j] = "#"
                    memo[i+1][j] = min(memo[i+1][j],memo[i][j] + 1)
                    if memo[i+1][j] > ans:
                        ans = memo[i+1][j]
            if 0 <= j - 1:
                if HW[i][j-1] == ".":
                    black.append((i,j-1))
                    HW[i][j-1] = "#"
                    memo[i][j-1] = min(memo[i][j-1],memo[i][j] + 1)
                    if memo[i][j-1] > ans:
                        ans = memo[i][j-1]
            if j + 1 < W:
                if HW[i][j+1] == ".":
                    black.append((i,j+1))
                    HW[i][j+1] = "#"
                    memo[i][j+1] = min(memo[i][j+1],memo[i][j] + 1)
                    if memo[i][j+1] > ans:
                        ans = memo[i][j+1]
    return ans
print(bfs(HW,memo))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
HW = [[st for st in input()] for _ in range(H)]
inf = float('inf')
memo = [[inf]*W for _ in range(H)]

def bfs(HW,memo):
    black = []
    for ii in range(H):
        for jj in range(W):
            if HW[ii][jj] == "#":
                black.append((ii,jj))
                memo[ii][jj] = 0
    ans = 0
    while len(black) > 0:
            next = black.pop(0)
            i,j = next
            if 0 <= i - 1:
                if HW[i-1][j] == ".":
                    black.append((i-1,j))
                    HW[i-1][j] = "#"
                    memo[i-1][j] = min(memo[i-1][j],memo[i][j] + 1)
                    if memo[i-1][j] > ans:
                        ans = memo[i-1][j]
            if 0 <= i + 1 < H:
                if HW[i+1][j] == ".":
                    black.append((i+1,j))
                    HW[i+1][j] = "#"
                    memo[i+1][j] = min(memo[i+1][j],memo[i][j] + 1)
                    if memo[i+1][j] > ans:
                        ans = memo[i+1][j]
            if 0 <= j - 1:
                if HW[i][j-1] == ".":
                    black.append((i,j-1))
                    HW[i][j-1] = "#"
                    memo[i][j-1] = min(memo[i][j-1],memo[i][j] + 1)
                    if memo[i][j-1] > ans:
                        ans = memo[i][j-1]
            if j + 1 < W:
                if HW[i][j+1] == ".":
                    black.append((i,j+1))
                    HW[i][j+1] = "#"
                    memo[i][j+1] = min(memo[i][j+1],memo[i][j] + 1)
                    if memo[i][j+1] > ans:
                        ans = memo[i][j+1]
    return ans
print(bfs(HW,memo))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
INF = 10**9

Q = deque()
dist = [[INF]*W for i in range(H)]

for x in range(W):
  for y in range(H):
    if C[y][x] == "#":
      visited = [[0]*W for i in range(H)]
      visited[y][x] = 1
      Q.append((y,x))
      dist[y][x] = 0
      while Q:
        y,x = Q.popleft()
        for i in range(4):
          nx = x + X[i]
          ny = y + Y[i]
          if (0 <= nx < W) and (0 <= ny < H) and (visited[ny][nx] == 0) and (C[ny][nx] != "#"):
            visited[ny][nx] = 1
            dist[ny][nx] = min(dist[y][x] + 1,dist[ny][nx])
            Q.append((ny,nx))
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a=["."*(w+2)]
c=0
ans=0
for _ in range(h):
    k = "." + input() + "."
    c+=k.count(".")-2
    a.append(k)
a.append("."*(w+2))
while(c>0):
    b=a.copy()
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=="." and "#" in [a[i-1][j],a[i+1][j],a[i][j-1],a[i][j+1]]:
                b[i] = b[i][:j]+"#"+b[i][j+1:]
                c-=1
    a = b.copy()
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(i) for i in input().split()]
a = []
b = []
for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])

for cnt in range(h+w):
    c = []
    for i in range(len(b)):
        y = b[i][0]
        x = b[i][1]
        if y != 0:
            if a[y-1][x] != "#":
                a[y-1][x] = "#"
                c.append([y-1, x])
        if y != h-1:
            if a[y+1][x] != "#":
                a[y+1][x] = "#"
                c.append([y+1, x])
        if x != 0:
            if a[y][x-1] != "#":
                a[y][x-1] = "#"
                c.append([y, x-1])
        if x != w-1:
            if a[y][x+1] != "#":
                a[y][x+1] = "#"
                c.append([y, x+1])
    if len(c) == 0:
        print(cnt)
        break
    b = c

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(i) for i in input().split()]
a = []
b = []
for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])

for cnt in range(h+w):
    c = []
    for i in range(len(b)):
        y = b[i][0]
        x = b[i][1]
        if y > 0:
            if a[y-1][x] != "#":
                a[y-1][x] = "#"
                c.append([y-1, x])
        if y < h-1:
            if a[y+1][x] != "#":
                a[y+1][x] = "#"
                c.append([y+1, x])
        if x > 0:
            if a[y][x-1] != "#":
                a[y][x-1] = "#"
                c.append([y, x-1])
        if x < w-1:
            if a[y][x+1] != "#":
                a[y][x+1] = "#"
                c.append([y, x+1])
    if len(c) == 0:
        print(cnt)
        break
    b = c

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(i) for i in input().split()]
a = []
b = []
for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])

cnt = 0
while True:
    c = []
    for i in range(len(b)):
        y = b[i][0]
        x = b[i][1]
        if y > 0:
            if a[y-1][x] != "#":
                a[y-1][x] = "#"
                c.append([y-1, x])
        if y < h-1:
            if a[y+1][x] != "#":
                a[y+1][x] = "#"
                c.append([y+1, x])
        if x > 0:
            if a[y][x-1] != "#":
                a[y][x-1] = "#"
                c.append([y, x-1])
        if x < w-1:
            if a[y][x+1] != "#":
                a[y][x+1] = "#"
                c.append([y, x+1])
    if len(c) == 0:
        break
    cnt += 1
    b = c
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(i) for i in input().split()]
a = []
b = []
for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])

cnt = 0
ans = [["#" for i in range(w)] for j in range(h)]
while True:
    c = []
    for i in range(len(b)):
        y = b[i][0]
        x = b[i][1]
        if y > 0:
            if a[y-1][x] != "#":
                a[y-1][x] = "#"
                c.append([y-1, x])
        if y < h-1:
            if a[y+1][x] != "#":
                a[y+1][x] = "#"
                c.append([y+1, x])
        if x > 0:
            if a[y][x-1] != "#":
                a[y][x-1] = "#"
                c.append([y, x-1])
        if x < w-1:
            if a[y][x+1] != "#":
                a[y][x+1] = "#"
                c.append([y, x+1])
    if c == []:
        break
    cnt += 1
    b = c
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(i) for i in input().split()]
a = []
b = []
for i in range(h):
    a.append(list(input()))
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])

cnt = 0
ans = [["#" for i in range(w)] for j in range(h)]
while True:
    c = []
    if a == ans:
        break
    cnt += 1
    for i in range(len(b)):
        y = b[i][0]
        x = b[i][1]
        if y > 0:
            if a[y-1][x] != "#":
                a[y-1][x] = "#"
                c.append([y-1, x])
        if y < h-1:
            if a[y+1][x] != "#":
                a[y+1][x] = "#"
                c.append([y+1, x])
        if x > 0:
            if a[y][x-1] != "#":
                a[y][x-1] = "#"
                c.append([y, x-1])
        if x < w-1:
            if a[y][x+1] != "#":
                a[y][x+1] = "#"
                c.append([y, x+1])
    b = c
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

dist = [[-1]*W for _ in range(H)]
d = deque([])

for h in range(H):
    for w in range(W):
        if src[h][w]=="#":
            dist[h][w]=0
            d.append((w,h))
while d:
    x,y = d.popleft()
    for dx, dy in dxy:
        nx,ny = x+dx, y+dy
        if not 0<=nx<W: continue
        if not 0<=ny<H: continue
        if src[ny][nx] == "#": continue
        if dist[ny][nx] > 0: continue
        dist[ny][nx] = dist[y][x] + 1
        d.append((nx,ny))
print(max(map(max,dist)))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())

M = [list(map(lambda x:0 if x == "#" else -1, input())) for _ in range(H)]

def set(i, j, x):
    if x < 0 or M[i][j] == 0:
        return
    x += 1
    if M[i][j] < 0:
        M[i][j] = x
    else:
        M[i][j] = min(M[i][j], x)

for i in range(H):
    for j in range(W):
        if j > 0:
            set(i, j, M[i][j-1])
        if i > 0:
            set(i, j, M[i-1][j])

for i in range(H-1, -1, -1):
    for j in range(W-1, -1, -1):
        if j < W-1:
            set(i, j, M[i][j+1])
        if i < H-1:
            set(i, j, M[i+1][j])

print(max(y for x in M for y in x))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque



def main():
    h,w=map(int,input().split())
    w+=2

    a=[list('@'*w)]
    for i in range(h):
        a+=[list('@'+input()+'@')]
    a+=[list('@'*w)]
    h+=2

    xy=[(-1,0),(0,-1),(0,1),(1,0)]
    que=deque()



    A=[[float('inf')]*w for i in range(h)]

    for i in range(1,h-1):
        for j in range(1,w-1):
            if a[i][j]=='#':
                A[i][j]=0
                que.append((i,j))


    res=0
    while que:
        x,y=que.popleft()
        for dx,dy in xy:
            nx,ny=dx+x,dy+y
            tmp=A[x][y]+1
            if a[nx][ny]!='@':
                if A[nx][ny]<=tmp:continue
                A[nx][ny]=tmp
                que.append((nx,ny))
                res=max(res,tmp)

    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

a=[list('@'*w)]
for i in range(h):
    a+=[list('@'+input()+'@')]
a+=[list('@'*w)]
h+=2

xy=[(-1,0),(0,-1),(0,1),(1,0)]
que=deque()

def bfs():
    res=0
    while que:
        x,y=que.popleft()
        for dx,dy in xy:
            nx,ny=dx+x,dy+y
            tmp=A[x][y]+1
            if a[nx][ny]!='@':
                if A[nx][ny]<=tmp:continue
                A[nx][ny]=tmp
                que.append((nx,ny))
                res=max(res,tmp)
    return res


A=[[float('inf')]*w for i in range(h)]

res=0
for i in range(1,h-1):
    for j in range(1,w-1):
        if a[i][j]=='#':
            A[i][j]=0
            que.append((i,j))

res=bfs()
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

a=[list('@'*w)]
for i in range(h):
    a+=[list('@'+input()+'@')]
a+=[list('@'*w)]
h+=2

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

def bfs(sx,sy):
    A[sx][sy]=0
    que=deque()
    que.append((sx,sy))

    while que:
        x,y=que.popleft()
        for dx,dy in xy:
            nx,ny=dx+x,dy+y
            tmp=A[x][y]+1
            if a[nx][ny]!='@':
                if A[nx][ny]<=tmp:continue
                A[nx][ny]=tmp
                que.append((nx,ny))


A=[[float('inf')]*w for i in range(h)]

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

S=A[1:-1]

for e in S:
    res=max(res,max(e[1:-1]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def bfs(c,sy=0, sx=0, gy=0, gx=0, blocks=['#'], dire=[(1,0), (0,1), (-1,0), (0,-1)], return_maximum_distance=False):
    H = len(c)
    W = len(c[0])
    distance_limit = H*W+1
    dist = [[distance_limit]*W for i in range(H)]

    q = deque()

    q_append = q.append
    q_popleft = q.popleft

    if (type(sy)==list) or (type(sx)==list):
        for syi, sxi in zip(sy, sx):
            dist[syi][sxi] = 0
            q.append((syi, sxi))
    else:
        dist[sy][sx] = 0
        q_append((sy, sx))

    while q:
        y, x = q_popleft()
        d = dist[y][x]
        for dy, dx in dire:
            if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                if (c[y+dy][x+dx] in blocks):
                    continue
                else:
                    if (dist[y+dy][x+dx] > d+1):
                        dist[y+dy][x+dx] = d+1
                        q_append((y+dy, x+dx))
                    if (y+dy==gy) and (x+dx==gx):
                        return (d+1)
    if (return_maximum_distance):
        return d
    return -1

H, W = LI()
c = SR(H)

sy = []
sx = []

for i in range(H):
    for j in range(W):
        if (c[i][j]=="#"):
            sy.append(i)
            sx.append(j)

print(bfs(c, sy, sx, sy, sx, return_maximum_distance=True))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def bfs(c,sy=0, sx=0, gy=0, gx=0, blocks=['#'], dire=[(1,0), (0,1), (-1,0), (0,-1)], return_maximum_distance=False):
    H = len(c)
    W = len(c[0])
    distance_limit = H*W+1
    dist = [[distance_limit]*W for i in range(H)]

    q = deque()

    q_append = q.append
    q_popleft = q.popleft

    if (type(sy)==list) or (type(sx)==list):
        for syi, sxi in zip(sy, sx):
            dist[syi][sxi] = 0
            q.append((syi, sxi))
    else:
        dist[sy][sx] = 0
        q_append((sy, sx))

    while q:
        y, x = q_popleft()
        d = dist[y][x]
        for dy, dx in dire:
            if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                if (c[y+dy][x+dx] in blocks):
                    continue
                else:
                    if (y+dy==gy) and (x+dx==gx) and (not return_maximum_distance):
                        return (d+1)
                    elif (dist[y+dy][x+dx] > d+1):
                        dist[y+dy][x+dx] = d+1
                        q_append((y+dy, x+dx))
    if (return_maximum_distance):
        return d
    return -1

H, W = LI()
c = SR(H)

sy = []
sx = []

for i in range(H):
    for j in range(W):
        if (c[i][j]=="#"):
            sy.append(i)
            sx.append(j)

print(bfs(c, sy, sx, return_maximum_distance=True))

Submission status: Time Limit Exceeded

Solution code:
import queue

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

dxy_list = [(-1, 0), (0, 1), (1, 0), (0, -1)]
q = queue.Queue()
INF = 1000000
cost = [[INF] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if F[i][j] == '#':
            q.put((i, j))
            cost[i][j] = 0

while not q.empty():
    
    x, y = q.get()
    for dxy in dxy_list:
        nx = x + dxy[0]
        ny = y + dxy[1]

        if 0 <= nx < H and 0 <= ny < W and F[nx][ny] == '.':
            F[nx][ny] = '#'
            cost[nx][ny] = cost[x][y] + 1
            q.put((nx, ny))


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

Submission status: Time Limit Exceeded

Solution code:
import collections
h,w = map(int,input().split())
q = collections.deque()
A = []
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        if s[j] == '.':
            L.append(s[j])
        else:
            L.append(0)
            q.append([i,j])
    A.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    cur = q.popleft()
    for i in range(4):
        y = cur[0]+dy_dx[i][0]
        x = cur[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if A[y][x] == '.':
                A[y][x] = A[cur[0]][cur[1]]+1
                q.append([y,x])
ans = 0
for i in range(h):
    for j in range(w):
        if ans < A[i][j]:
            ans = A[i][j]
print(ans)