Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
tmp_field = deepcopy(field)
def fill(x, y):
    ret = 0
    tmp = list()
    for nx, ny in ((1,0), (-1,0), (0,1), (0,-1)):
        nx += x
        ny += y
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue

        if "." == field[ny][nx]:
            tmp_field[ny][nx] = "#"
            ret = 1
    return ret

ret = -1
tmp = 1
while tmp > 0:
    tmp = 0
    ret += 1
    for h in range(H):
        for w in range(W):
            if field[h][w] == "#":
                tmp_field[h][w] = "$"
                tmp += fill(w, h)
    field = deepcopy(tmp_field)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
INF = 10**9
sheet = []
score = [[INF]*W for i in range(H)]
step = [(-1,0),(1,0),(0,-1),(0,1)]
stuck = []
ans = -1

for i in range(H):
  line = input()
  for j in range(W):
    if line[j]=='#':
      stuck += [(i,j,0)]
      score[i][j] = 0
      
while stuck:
  y, x, m = stuck.pop()
  for s in step:
    dx, dy = s
    if x+dx<0 or x+dx>W-1 or y+dy<0 or y+dy>H-1:
      continue
    if score[y+dy][x+dx]>m+1:
      score[y+dy][x+dx]=m+1
      stuck += [(y+dy, x+dx, m+1)]
      
for i in range(H):
  ans = max(ans, *score[i])
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
ans=0
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*" for i in range(w+2)]]
queue=deque([])
for H in range(h+2):
    for W in range(w+2):
        if field[H][W]=="#":
            queue.append((H,W))
            field[H][W]=0
        elif field[H][W]==".":
          field[H][W]=-1
move=[(0,1),(0,-1),(1,0),(-1,0)]
ans=0
while queue:
    pos=queue.popleft()
    for i in move:
      if field[pos[0]+i[0]][pos[1]+i[1]]!=-1:continue
      if field[pos[0]+i[0]][pos[1]+i[1]]=="*":continue
      field[pos[0]+i[0]][pos[1]+i[1]]=field[pos[0]][pos[1]]+1
      queue.append((pos[0]+i[0],pos[1]+i[1]))
      if ans < field[pos[0]+i[0]][pos[1]+i[1]]:ans=field[pos[0]+i[0]][pos[1]+i[1]]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 最初に黒マスを全部queueに突っ込めばOK
from collections import deque
import itertools

H, W = map(int, input().split())
d = deque()

score = []
for y in range(H):
    score_x = []
    c_temp = input()
    for x, c_t in enumerate(c_temp):
        if c_t == '#':
            score_x.append(0)
            d.append([y, x])
        else:
            score_x.append(-1)
    score.append(score_x)

while len(d) > 0:
    y, x = d.popleft()

    if x + 1 < W and score[y][x + 1] == -1:
        score[y][x + 1] = score[y][x] + 1
        d.append([y, x + 1])

    if x - 1 >= 0 and score[y][x - 1] == -1:
        score[y][x - 1] = score[y][x] + 1
        d.append([y, x - 1])

    if y + 1 < H and score[y + 1][x] == -1:
        score[y + 1][x] = score[y][x] + 1
        d.append([y + 1, x])

    if y - 1 >= 0 and score[y - 1][x] == -1:
        score[y - 1][x] = score[y][x] + 1
        d.append([y - 1, x])

print(max(list(itertools.chain.from_iterable(score))))

Submission status: Time Limit Exceeded

Solution code:
# 最初に黒マスを全部queueに突っ込めばOK
from collections import deque
import itertools

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

c = []
for _ in range(H):
    c.append(input())

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

for y in range(H):
    for x in range(W):
        if c[y][x] == '#':
            score[y][x] = 0
            d.append([y, x])

while len(d) > 0:
    y, x = d.popleft()

    if x + 1 < W and score[y][x + 1] == -1:
        score[y][x + 1] = score[y][x] + 1
        d.append([y, x + 1])

    if x - 1 >= 0 and score[y][x - 1] == -1:
        score[y][x - 1] = score[y][x] + 1
        d.append([y, x - 1])

    if y + 1 < H and score[y + 1][x] == -1:
        score[y + 1][x] = score[y][x] + 1
        d.append([y + 1, x])

    if y - 1 >= 0 and score[y - 1][x] == -1:
        score[y - 1][x] = score[y][x] + 1
        d.append([y - 1, x])

print(max(list(itertools.chain.from_iterable(score))))

Submission status: Time Limit Exceeded

Solution code:
# 最初に黒マスを全部queueに突っ込めばOK
from collections import deque
import itertools

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

c = []
for _ in range(H):
    c.append(input())

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

for y in range(H):
    for x in range(W):
        if c[y][x] == '#':
            score[y][x] = 0
            d.append([y, x])

diff = [[-1, 0], [1, 0], [0, -1], [0, 1]]

while len(d) > 0:
    y, x = d.popleft()

    for dy, dx in diff:
        ny, nx = y + dy, x + dx
        if nx >= 0 and ny >= 0 and nx < W and ny < H and score[ny][nx] == -1:
            score[ny][nx] = score[y][x] + 1
            d.append([ny, nx])


print(max(list(itertools.chain.from_iterable(score))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
fuchi = {}
kuro = {}
for i in range(h):
    Ai = input()
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            fuchi[(i, j)] = 1
            kuro[(i, j)] = 1

def add(poj):
    res = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    if poj[0] == 0:
        res[0] = 0
    if poj[0] == h - 1:
        res[1] = 0
    if poj[1] == 0:
        res[2] = 0
    if poj[1] == w - 1:
        res[3] = 0
    return res

c = 0
size = 0

while(True):
    pojs = list(fuchi.keys())
    if len(kuro) == h * w:
        print(c)
        break
    for poj in pojs:
        fuchi.pop(poj)
        for item in add(poj):
            if item != 0:
                cand = (poj[0] + item[0], poj[1] + item[1])
                if cand not in pojs:
                    kuro[cand] = 1
                    fuchi[cand] = 1
    c += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())

l=[input() for _ in range(H)]


def bfs(H,W,l):
  ans=0
  que=deque()
  count=[[-1]*W for _ in range(H)]
  num=H*W
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  for i in range(H):
    for j in range(W):
      if l[i][j]=='#':
        count[i][j]=0
        que.append([i,j])
        num-=1
  while num>0:
    x,y=que.popleft()
    for k in range(4):
      a, b=x+dx[k], y+dy[k]
      if a<0 or a>=H or b<0 or b>=W or count[a][b]!=-1:
        continue
      else:
        count[a][b]=count[x][y]+1
        que.append([a,b])
        num-=1
  for i in range(H):
    ans=max(ans,max(count[i]))
  return ans
print(bfs(H,W,l))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
c = []
d = [[-1 for i in range(w)] for j in range(h)]
q = deque()
for i in range(h):
	s = input()
	c.append(s)
	for j in range(w):
		if c[i][j] == '#':
			q.append([i, j, 0])
			d[i][j] = 0

dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]

while len(q) != 0:
	y, x, z = q[0]

	for i in range(4):
		ny, nx = y + dirr[i][0], x + dirr[i][1]
		if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == -1 and c[ny][nx] != "#":
			q.append([ny, nx, z + 1])
			d[ny][nx] = z + 1

	q.popleft()

print(z)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = [[False]*W for _ in range(H)]

q = []
for i in range(H):
    S = input()
    for j, x in enumerate(S):
        if x == '.':
            continue
        q.append((i, j))
        C[i][j] = True

cnt = 0
while q:
    cnt += 1
    q2 = []
    for x, y in q:
        if x-1 >= 0 and not C[x-1][y]:
            C[x-1][y] = True
            q2.append((x-1, y))
        if x+1 < H and not C[x+1][y]:
            C[x+1][y] = True
            q2.append((x+1, y))
        if y-1 >= 0 and not C[x][y-1]:
            C[x][y-1] = True
            q2.append((x, y-1))
        if y+1 < W and not C[x][y+1]:
            C[x][y+1] = True
            q2.append((x, y+1))
    q = q2
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = [[True] * (W+2)]
for _ in range(H):
    C.append([True] + [False] * W + [True])
C.append([True] * (W+2))

q = []
for i in range(H):
    S = input()
    for j, x in enumerate(S):
        if x == '.':
            continue
        q.append((i+1, j+1))
        C[i+1][j+1] = True

cnt = 0
while q:
    cnt += 1
    q2 = []
    for x, y in q:
        if not C[x-1][y]:
            C[x-1][y] = True
            q2.append((x-1, y))
        if not C[x+1][y]:
            C[x+1][y] = True
            q2.append((x+1, y))
        if not C[x][y-1]:
            C[x][y-1] = True
            q2.append((x, y-1))
        if not C[x][y+1]:
            C[x][y+1] = True
            q2.append((x, y+1))
    q = q2
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C = [[True] * (W+2)]
for _ in range(H):
    C.append([True] + [False] * W + [True])
C.append([True] * (W+2))

q = []
for i in range(H):
    S = input()
    for j, x in enumerate(S):
        if x == '.':
            continue
        q.append((i+1, j+1))
        C[i+1][j+1] = True

cnt = 0
while q:
    cnt += 1
    q2 = []
    for x, y in q:
        if not C[x-1][y]:
            C[x-1][y] = True
            q2.append((x-1, y))
        if not C[x+1][y]:
            C[x+1][y] = True
            q2.append((x+1, y))
        if not C[x][y-1]:
            C[x][y-1] = True
            q2.append((x, y-1))
        if not C[x][y+1]:
            C[x][y+1] = True
            q2.append((x, y+1))
    q = q2[:]
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C = [[True] * (W+2)]
for _ in range(H):
    C.append([True] + [False] * W + [True])
C.append([True] * (W+2))

q = []
for i in range(H):
    S = input()
    for j, x in enumerate(S):
        if x == '.':
            continue
        q.append((i+1, j+1))
        C[i+1][j+1] = True

cnt = 0
while q:
    cnt += 1
    q2 = []
    for x, y in q:
        if not C[x-1][y]:
            C[x-1][y] = True
            q2.append((x-1, y))
        if not C[x+1][y]:
            C[x+1][y] = True
            q2.append((x+1, y))
        if not C[x][y-1]:
            C[x][y-1] = True
            q2.append((x, y-1))
        if not C[x][y+1]:
            C[x][y+1] = True
            q2.append((x, y+1))
    q = q2
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
S = ['.' * (W+2)]
for _ in range(H):
    S.append('.'+input()+'.')
S.append('.' * (W+2))
C = [[True] * (W+2)]
for _ in range(H):
    C.append([True] + [False] * W + [True])
C.append([True] * (W+2))

q = []
for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i][j] == '.':
            continue
        q.append((i, j))
        C[i][j] = True

cnt = 0
while q:
    cnt += 1
    q2 = []
    for x, y in q:
        if not C[x-1][y]:
            C[x-1][y] = True
            q2.append((x-1, y))
        if not C[x+1][y]:
            C[x+1][y] = True
            q2.append((x+1, y))
        if not C[x][y-1]:
            C[x][y-1] = True
            q2.append((x, y-1))
        if not C[x][y+1]:
            C[x][y+1] = True
            q2.append((x, y+1))
    q = q2
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
S = ['.' * (W+2)]
for _ in range(H):
    S.append('.'+input()+'.')
S.append('.' * (W+2))
C = [[True] * (W+2)]
for _ in range(H):
    C.append([True] + [False] * W + [True])
C.append([True] * (W+2))

nexts = [[0, 0, -1, 1], [1, -1, 0, 0]]
q = []
for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i][j] == '.':
            continue
        q.append((i, j))
        C[i][j] = True

cnt = 0
while q:
    cnt += 1
    q2 = []
    for x, y in q:
        for k in range(4):
            mx = x + nexts[0][k]
            my = y + nexts[1][k]
            if C[mx][my]:
                continue
            C[mx][my] = True
            q2.append((mx, my))
    q = q2
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
S = ['.' * (W+2)]
for _ in range(H):
    S.append('.'+input()+'.')
S.append('.' * (W+2))
C = [[True] * (W+2)]
for _ in range(H):
    C.append([True] + [False] * W + [True])
C.append([True] * (W+2))

nexts = [[0, 0, -1, 1], [1, -1, 0, 0]]
q = deque()
for i in range(1, H+1):
    for j in range(1, W+1):
        if S[i][j] == '.':
            continue
        q.append((i, j))
        C[i][j] = True

cnt = 0
while q:
    cnt += 1
    q2 = deque()
    while q:
        x, y = q.popleft()
        for k in range(4):
            mx = x + nexts[0][k]
            my = y + nexts[1][k]
            if C[mx][my]:
                continue
            C[mx][my] = True
            q2.append((mx, my))
    q = q2
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]
C = [[False]*W for _ in range(H)]

nexts = [[0, 0, -1, 1], [1, -1, 0, 0]]
q = deque()
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            continue
        q.append((i, j))
        C[i][j] = True
cnt = 0
while q:
    cnt += 1
    q2 = deque()
    while q:
        x, y = q.popleft()
        for k in range(4):
            mx = x + nexts[0][k]
            my = y + nexts[1][k]
            if mx < 0 or my < 0 or mx >= H or my >= W or C[mx][my]:
                continue
            C[mx][my] = True
            q2.append((mx, my))
    q = q2
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
def bfs():
    r, c = map(int, input().split())#map size
    field = [list(input()) for _ in range(r)]#map data
    tests = ((0, 1), (1, 0), (-1, 0), (0, -1))
    queue = []
    for i in range(r):
        for j in range(c):
            if field[i][j]=="#":
                start_point = (i, j)
                field[start_point[0]][start_point[1]] = 0
                queue.append(start_point)

    moves = 0
 
    while queue:
        queue_next = []
        moves += 1
        for y, x in queue:
            for ny, nx in tests:
                ty, tx = y + ny, x + nx
                if (tx>=0 and tx<c and ty>=0 and ty<r and field[ty][tx] == '.') :                    
                    field[ty][tx] = moves#input turn number
                    queue_next.append((ty, tx))
                    
        queue = queue_next
        if queue_next==[]:
            break
 
    print(moves-1)
 
 
if __name__ == "__main__":
    bfs()

Submission status: Time Limit Exceeded

Solution code:
def bfs():
    r, c = map(int, input().split())#map size
    field = [list(input()) for _ in range(r)]#map data
    tests = ((0, 1), (1, 0), (-1, 0), (0, -1))
    queue = []
    for i in range(r):
        for j in range(c):
            if field[i][j]=="#":
                start_point = (i, j)
                field[start_point[0]][start_point[1]] = 0
                queue.append(start_point)

    moves = 0
 
    while queue:
        queue_next = []
        moves += 1
        for y, x in queue:
            for ny, nx in tests:
                ty, tx = y + ny, x + nx
                if (tx>=0 and tx<c and ty>=0 and ty<r) :                    
                    if field[ty][tx] == '.':
                        field[ty][tx] = moves#input turn number
                        queue_next.append((ty, tx))
                    
        queue = queue_next
        if queue_next==[]:
            break
 
    print(moves-1)
 
 
if __name__ == "__main__":
    bfs()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
S = [input() for _ in range(H)]
C = [[False]*W for _ in range(H)]

nexts = [[0, 0, -1, 1], [1, -1, 0, 0]]
q = deque()
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            continue
        q.append((i, j))
        C[i][j] = True
cnt = 0
while True:
    cnt += 1
    q2 = deque()
    while q:
        x, y = q.popleft()
        for k in range(4):
            mx = x + nexts[0][k]
            my = y + nexts[1][k]
            if mx < 0 or my < 0 or mx >= H or my >= W or C[mx][my]:
                continue
            C[mx][my] = True
            q2.append((mx, my))
    if q2:
        q = copy.copy(q2)
    else:
        break
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())

        blacks = []
        field = defaultdict(lambda: '#')
        for h in range(H):
            for w, c in enumerate(input().rstrip()):
                field[(h + 1, w + 1)] = c
                if c == '#':
                    blacks.append((h + 1, w + 1))

        moving_range = ((1, 0), (-1, 0), (0, -1), (0, 1))

        ans = 0
        while blacks:
            next_blacks = []
            for b_h, b_w in blacks:
                for m_h, m_w in moving_range:
                    target = (b_h + m_h, b_w + m_w)
                    if field[target] == '.':
                        field[target] = '#'
                        next_blacks.append(target)
            if len(next_blacks) > 0:
                ans += 1
            blacks = next_blacks

        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())
        A = [list(input().rstrip()) for _ in range(H)]

        blacks = []
        for h in range(H):
            for w in range(W):
                if A[h][w] == '#':
                    blacks.append((h + 1, w + 1))

        moving_range = ((1, 0), (-1, 0), (0, -1), (0, 1))

        ans = 0
        while blacks:
            next_blacks = []
            for b_h, b_w in blacks:
                for m_h, m_w in moving_range:
                    h, w = b_h + m_h, b_w + m_w
                    if not (0 < h <= H and 0 < w <= W):
                        continue
                    if A[h-1][w-1] == '.':
                        A[h-1][w-1] = '#'
                        next_blacks.append((h, w))
            if len(next_blacks) > 0:
                ans += 1
            blacks = next_blacks

        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())

        blacks = []
        field = defaultdict(lambda: '#')
        for h in range(H):
            for w, c in enumerate(input().rstrip()):
                field[self.key((h + 1, w + 1))] = c
                if c == '#':
                    blacks.append((h + 1, w + 1))

        moving_range = ((1, 0), (-1, 0), (0, -1), (0, 1))

        ans = 0
        while blacks:
            next_blacks = []
            for b_h, b_w in blacks:
                for m_h, m_w in moving_range:
                    target = (b_h + m_h, b_w + m_w)
                    if field[self.key(target)] == '.':
                        field[self.key(target)] = '#'
                        next_blacks.append(target)
            if len(next_blacks) > 0:
                ans += 1
            blacks = next_blacks

        print(ans)

    def key(self, pos):
        return str(pos[0]) + '-' + str(pos[1])


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
S = [input() for _ in range(H)]
C = [[False]*W for _ in range(H)]

nexts = [[0, 0, -1, 1], [1, -1, 0, 0]]
q = deque()
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            continue
        q.append((i, j))
        C[i][j] = True
cnt = 0
while True:
    cnt += 1
    q2 = deque()
    while len(q) >= 1:
        x, y = q.popleft()
        for k in range(4):
            mx = x + nexts[0][k]
            my = y + nexts[1][k]
            if mx < 0 or my < 0 or mx >= H or my >= W or C[mx][my]:
                continue
            C[mx][my] = True
            q2.append((mx, my))
    if len(q2) >= 1:
        q = copy.copy(q2)
    else:
        break
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]
C = [[100000]*W for _ in range(H)]

nexts = [[0, 0, -1, 1], [1, -1, 0, 0]]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            continue
        q = deque()
        q.append((i, j))
        C[i][j] = 0
        while len(q) >= 1:
            x, y = q.popleft()
            for k in range(4):
                mx = x + nexts[0][k]
                my = y + nexts[1][k]
                if mx < 0 or my < 0 or mx >= H or my >= W:
                    continue
                if C[x][y] + 1 >= C[mx][my] or S[mx][my] == '#':
                    continue
                C[mx][my] = C[x][y] + 1
                q.append((mx, my))
print(max([max(i) for i in C]))

Submission status: Time Limit Exceeded

Solution code:
def main():

    from collections import deque

    h,w = map(int,input().split())
    A = [list(input()) for i in range(h)]

    queue = deque([])
    Distance = [[-1 for i in range(w)]for j in range(h)]

    for i in range(h):
        for j in range(w):
            if A[i][j]=='#':
                queue.append([i,j])
                Distance[i][j] = 0

    ans = 0

    while queue:
        x,y = queue.popleft()
        if x!=0:
            if A[x-1][y] == '.' and Distance[x-1][y] == -1:
                queue.append([x-1,y])
                ans = Distance[x-1][y] = Distance[x][y] + 1
        if x!=h-1:
            if A[x+1][y] == '.' and Distance[x+1][y] == -1:
                queue.append([x+1,y])
                ans = Distance[x+1][y] = Distance[x][y] + 1
        if y!=0:
            if A[x][y-1] == '.' and Distance[x][y-1] == -1:
                queue.append([x,y-1])
                ans = Distance[x][y-1] = Distance[x][y] + 1
        if y!=w-1:
            if A[x][y+1] == '.' and Distance[x][y+1] == -1:
                queue.append([x,y+1])
                ans = Distance[x][y+1] = Distance[x][y] + 1

    print(ans)

if __name__ == '__main__':
    main()

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)]

queue = deque([])
Distance = [[-1 for i in range(w)]for j in range(h)]

for i in range(h):
  for j in range(w):
    if A[i][j]=='#':
      queue.append([i,j])
      Distance[i][j] = 0

while queue:
    x,y = queue.popleft()
    if x!=0:
        if A[x-1][y] == '.' and Distance[x-1][y] == -1:
            queue.append([x-1,y])
            Distance[x-1][y] = Distance[x][y] + 1
    if x!=h-1:
        if A[x+1][y] == '.' and Distance[x+1][y] == -1:
            queue.append([x+1,y])
            Distance[x+1][y] = Distance[x][y] + 1
    if y!=0:
        if A[x][y-1] == '.' and Distance[x][y-1] == -1:
            queue.append([x,y-1])
            Distance[x][y-1] = Distance[x][y] + 1
    if y!=w-1:
        if A[x][y+1] == '.' and Distance[x][y+1] == -1:
            queue.append([x,y+1])
            Distance[x][y+1] = Distance[x][y] + 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#(方針)「whiteから最も近いblackまでの距離」の最大値を求める
import queue
import copy
#sys.stdin.readline()
import sys
input = sys.stdin.readline

H,W = map(int,input().split())
white_index = []
Map = []
Map.append(['@']*(W+2))
for i in range(H):
  c = list('@'+input()+'@')
  Map.append(c)
  for j in range(W+2):
    if(c[j] == '.'): white_index.append([i+1,j])
Map.append(['@']*(W+2))


#幅優先探索
def bfs(sy,sx,Map):
  Map_[sy][sx] = 0
  qy,qx = queue.Queue(),queue.Queue()
  qy.put(sy),qx.put(sx)
  
  count = 0
  while(1):
   if(qx.empty() == True): return ans
    
   #座標の取り出し
   y,x = qy.get(),qx.get()
   if(Map_[y][x] == '#'): #ゴールなら終了
    return count

   #if((sy == 4)and(sx == 6)):
    #for i in range(H+2): print(Map_[i])
    #print('_____________')
    
   #次に進むところ
   vec_y = [0,0,1,-1]
   vec_x = [1,-1,0,0]
   for i in range(4):
     if(Map_[y+vec_y[i]][x+vec_x[i]] == '.'):
      Map_[y+vec_y[i]][x+vec_x[i]] = Map_[y][x] + 1
      qy.put(y+vec_y[i]),qx.put(x+vec_x[i])
     elif(Map_[y+vec_y[i]][x+vec_x[i]] == '#'): #ゴールなら終了
      count = Map_[y][x] + 1
      return count      
     

ans = 0
for i in range(len(white_index)):
 sy,sx = white_index[i][0],white_index[i][1]
 Map_ = copy.deepcopy(Map) #二次元リストのコピー
 ans = max(ans,bfs(sy,sx,Map_))  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#(方針)「whiteから最も近いblackまでの距離」の最大値を求める
import queue
import copy

H,W = map(int,input().split())
white_index = []
Map = []
Map.append(['@']*(W+2))
for i in range(H):
  c = list('@'+input()+'@')
  Map.append(c)
  for j in range(W+2):
    if(c[j] == '.'): white_index.append([i+1,j])
Map.append(['@']*(W+2))


#幅優先探索
def bfs(sy,sx,Map):
  Map_[sy][sx] = 0
  qy,qx = queue.Queue(),queue.Queue()
  qy.put(sy),qx.put(sx)
  
  count = 0
  while(1):
   if(qx.empty() == True): return ans
    
   #座標の取り出し
   y,x = qy.get(),qx.get()
   if(Map_[y][x] == '#'): #ゴールなら終了
    return count

   #if((sy == 4)and(sx == 6)):
    #for i in range(H+2): print(Map_[i])
    #print('_____________')
    
   #次に進むところ
   vec_y = [0,0,1,-1]
   vec_x = [1,-1,0,0]
   for i in range(4):
     if(Map_[y+vec_y[i]][x+vec_x[i]] == '.'):
      Map_[y+vec_y[i]][x+vec_x[i]] = Map_[y][x] + 1
      qy.put(y+vec_y[i]),qx.put(x+vec_x[i])
     elif(Map_[y+vec_y[i]][x+vec_x[i]] == '#'): #ゴールなら終了
      count = Map_[y][x] + 1
      return count      
     

ans = 0
for i in range(len(white_index)):
 sy,sx = white_index[i][0],white_index[i][1]
 Map_ = copy.deepcopy(Map) #二次元リストのコピー
 ans = max(ans,bfs(sy,sx,Map_))  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class Grid():
    def __init__(self,i,j,isblack):
        self.i=i
        self.j=j
        self.isblack=isblack
        self.distance=0

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

g=[]
for i in range(H):
    Ai=input()
    gi=[]    
    for j in range(W):
        gi.append(Grid(i,j,Ai[j]=='#'))
    g.append(gi)

d=deque()

# 黒マスのreachedをTrueにし，dequeに入れる
for row in g:
    for grid in row:
        if grid.isblack:
            d.append(grid)

while d:
    tg=d.popleft()
    i=tg.i
    j=tg.j
    if i>0 and not g[i-1][j].isblack:
        g[i-1][j].isblack=True
        g[i-1][j].distance=tg.distance+1
        d.append(g[i-1][j])
    if i<H-1 and not g[i+1][j].isblack:
        g[i+1][j].isblack=True
        g[i+1][j].distance=tg.distance+1
        d.append(g[i+1][j])
    if j>0 and not g[i][j-1].isblack:
        g[i][j-1].isblack=True
        g[i][j-1].distance=tg.distance+1
        d.append(g[i][j-1])
    if j<W-1 and not g[i][j+1].isblack:
        g[i][j+1].isblack=True
        g[i][j+1].distance=tg.distance+1
        d.append(g[i][j+1])

'''
for row in g:
    for grid in row:
#        print(grid.distance,end=' ')
#    print()
'''

print(max([max([grid.distance for grid in row]) for row in g]))

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
INF=H+W-1
a=[]
for i in range(H):
    ai=[]
    Ai=input()
    for j in range(W):
        if Ai[j]=='.':
            ai.append(False)
        else:
            ai.append(True)
    a.append(ai)

# print(a)

c=[[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j]:
            c[i][j]=0
        else:
            c[i][j]=INF

# print(c)

for i in range(H):
    for j in range(W):
        if a[i][j]:
            k=1
            while i-k>=0 and not a[i-k][j]:
                c[i-k][j]=min(c[i-k][j],k)
                k+=1
            k=1
            while i+k<=H-1 and not a[i+k][j]:
                c[i+k][j]=min(c[i+k][j],k)
                k+=1
            k=1
            while j-k>=0 and not a[i][j-k]:
                c[i][j-k]=min(c[i][j-k],k)
                k+=1
            k=1
            while j+k<=W-1 and not a[i][j+k]:
                c[i][j+k]=min(c[i][j+k],k)
                k+=1

# print(c)

for i in range(H):
    for j in range(W):
        if 0<c[i][j]<INF:
            k=1
            while i-k>=0 and not a[i-k][j]:
                c[i-k][j]=min(c[i-k][j],c[i][j]+k)
                k+=1
            k=1
            while i+k<=H-1 and not a[i+k][j]:
                c[i+k][j]=min(c[i+k][j],c[i][j]+k)
                k+=1
            k=1
            while j-k>=0 and not a[i][j-k]:
                c[i][j-k]=min(c[i][j-k],c[i][j]+k)
                k+=1
            k=1
            while j+k<=W-1 and not a[i][j+k]:
                c[i][j+k]=min(c[i][j+k],c[i][j]+k)
                k+=1

# print(c)

ans=max([max(ci) for ci in c])

print(ans)

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
	
	ans = 0
	for i in time:
		if i > ans:
			ans = i
	print(ans)

if __name__ == '__main__':
	main()