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 heapq
import numpy as np
H,W=map(int, input().split())
dist=np.array([[10**8]*W+[0] for _ in range(H)]+[[0]*(W+1)])
q=[] #priorityque
for i in range(H):
    for j, s in enumerate(input()):
        if s =='#':
            dist[i,j]=0
            heapq.heappush(q,(0,i,j))
while len(q)>0:
    res = heapq.heappop(q)
    new=dist[res[1],res[2]]+1
    #up
    if dist[res[1],res[2]+1]>new:
        dist[res[1],res[2]+1]=new
        heapq.heappush(q,(new, res[1], res[2]+1))
    #down
    if dist[res[1],res[2]-1]>new:
        dist[res[1],res[2]-1]=new
        heapq.heappush(q,(new, res[1], res[2]-1))
    #right
    if dist[res[1]+1,res[2]]>new:
        dist[res[1]+1,res[2]]=new
        heapq.heappush(q,(new, res[1]+1, res[2]))
    #left
    if dist[res[1]-1,res[2]]>new:
        dist[res[1]-1,res[2]]=new
        heapq.heappush(q,(new, res[1]-1, res[2]))
print(np.max(dist))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math 
import numpy as np
from collections import deque
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

H,W = na()
field = []
black_list = deque()
for i in range(H):
    tmp = input()
    for j in range(W):
        if(tmp[j] == "#"):
            black_list.append([i,j,0])
    field.append(list(tmp))
d = [[1,0],[0,1],[-1,0],[0,-1]]
ans = -1
while black_list:
    r,c,cnt = black_list.popleft()
    for i,j in d:
        r_n = r+i
        c_n = c+j
        if(r_n<=H-1 and r_n>=0 and c_n<=W-1 and c_n>=0):
            if(field[r_n][c_n]=="."):
                field[r_n][c_n]="#"
                black_list.append([r_n,c_n,cnt+1])
    ans = max(ans,cnt)

print(ans)
#print(field)

Submission status: Time Limit Exceeded

Solution code:
def nextcell(a,y,x,h,w):
    ans = []
    if y+1 < h and a[y+1][x] == ".":
        ans.append([y+1,x])
    if y-1 >= 0 and a[y-1][x] == ".":
        ans.append([y-1,x])
    if x+1 < w and a[y][x+1] == ".":
        ans.append([y,x+1])
    if x-1 >= 0 and a[y][x-1] == ".":
        ans.append([y,x-1])
    return ans 

h,w = map(int,input().split())
a = []
q = []
for i in range(h):
    temp = list(input())
    for k in range(w):
        if temp[k] == "#":
            q.append([i,k])
    a.append(temp)

counter = 0
while len(q) != 0:
    n = len(q)
    for i in range(n):
        white = nextcell(a,q[0][0],q[0][1],h,w)
        for k in range(len(white)):
            q.append(white[k])
            a[white[k][0]][white[k][1]] = "#"
        q.pop(0)
    counter += 1
print(counter-1)

Submission status: Time Limit Exceeded

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

def position_sharp(self, xmax, ymax):
    p_s = []
    for i in range(xmax):
        for j in range(ymax):
            if a[i][j] == '#':
                p_s.append((i, j))
    if len(p_s) == xmax*ymax:
        return False
    else:
        return p_s

def position_new(self, xmax, ymax):
    p = position_sharp(self,xmax,ymax)
    if p == False:
        return False
    for i in range(len(p)):
        xlow = p[i][0]-1
        x = p[i][0]
        xhigh = p[i][0]+1
        
        ylow = p[i][1]-1
        y = p[i][1]
        yhigh = p[i][1]+1
        if 0 <= xlow and xlow < xmax:
            a[xlow][y] = '#'
        if 0 <= ylow and ylow < ymax:
            a[x][ylow] = '#'
        if 0 <= xhigh and xhigh < xmax:
            a[xhigh][y] = '#'
        if 0 <= yhigh and yhigh < ymax:
            a[x][yhigh] = '#'
            
    return a

def main(self,xmax,ymax):
    count = 0
    result = True
    while result == True:
        self = position_new(self,xmax,ymax)
        if self == False:
            result = False
            break
        count += 1
    return count, self

count, a = main(a,H,W)

print(count)

Submission status: Time Limit Exceeded

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

def position_sharp(self, xmax, ymax):
    p_s = []
    for i in range(xmax):
        for j in range(ymax):
            if self[i][j] == '#':
                p_s.append((i, j))
    return p_s

def position_new(self, xmax, ymax):
    p = position_sharp(self,xmax,ymax)
    for i in range(len(p)):
        xlow = p[i][0]-1
        x = p[i][0]
        xhigh = p[i][0]+1
        
        ylow = p[i][1]-1
        y = p[i][1]
        yhigh = p[i][1]+1
        if 0 <= xlow and xlow < xmax:
            self[xlow][y] = '#'
        if 0 <= ylow and ylow < ymax:
            self[x][ylow] = '#'
        if 0 <= xhigh and xhigh < xmax:
            self[xhigh][y] = '#'
        if 0 <= yhigh and yhigh < ymax:
            self[x][yhigh] = '#'
            
    return self

def main(self,xmax,ymax):
    count = 0
    result = True
    while result == True:
        for i in range(xmax):
            for j in range(ymax):
                if self[i][j] == '.':
                    self = position_new(self,xmax,ymax)
                    count += 1
                    result = False
    return count, self

count, matrix = main(matrix,H,W)

print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

INF = 10 ** 8
dist = [[INF] * w for _ in range(h)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]


def bfs():
    q = collections.deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                q.append((i, j))
                dist[i][j] = 0
                # grid[i][j] = str(0)

    while len(q):
        py, px = q.popleft()
        for i in range(4):
            ny = py + dy[i]
            nx = px + dx[i]
            if -1 < ny < h and -1 < nx < w and grid[ny][nx] == '.' and dist[ny][nx] == INF:
                q.append((ny, nx))
                dist[ny][nx] = dist[py][px] + 1
                # grid[ny][nx] = str(dist[py][px] + 1)

    return max(max(dist, key=lambda x: max(x)))


if __name__ == '__main__':
    print(bfs())
    # for g in grid:
    #     for s in g:
    #         print(s,end='')
    #     print()
    # print()
    # for d in dist:
    #     for i in d:
    #         print(i,end='')
    #     print()

Submission status: Time Limit Exceeded

Solution code:
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())
    kuros = list(kuro.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 kuros:
                    kuro[cand] = 1
                    fuchi[cand] = 1
    c += 1

Submission status: Time Limit Exceeded

Solution code:
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:
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:
        for item in add(poj):
            if item != 0:
                fuchi[(poj[0] + item[0], poj[1] + item[1])] = 1
                kuro[(poj[0] + item[0], poj[1] + item[1])] = 1
    for poj in pojs:
        fuchi.pop(poj)
    c += 1

Submission status: Time Limit Exceeded

Solution code:
import collections
import numpy as np
from sys import stdin

H,W=map(int,stdin.readline().split())

l=[]
for i in range(H):
  l.append(list(stdin.readline()))

q=collections.deque()
cost=np.empty((H,W),dtype=np.int32)
for h in range(H):
  for w in range(W):
    if l[h][w] == '#':
      cost[h][w] = 0
      q.append([h,w])
    else:
      cost[h][w]=100000000

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

while q:
  h,w=q.popleft() 
  for i in range(4):
    fh=h+dh[i]
    fw=w+dw[i]
    if fh<0 or fh>=H or fw<0 or fw>=W:
      continue
    if cost[fh][fw]<=cost[h][w]+1:
      continue
    cost[fh][fw]=cost[h][w]+1
    q.append([fh,fw])

ans=0
for h in range(H):
  for w in range(W):
    ans=max(ans,cost[h][w])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import collections

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

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

q=collections.deque()
cost=[[1000000000 for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(W):
    if l[h][w] == '#':
      cost[h][w] = 0
      q.append([h,w])

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

while q:
  h,w = q.popleft() 
  for i in range(4):
    fh=h+dh[i]
    fw=w+dw[i]
    if fh<0 or fh>=H or fw<0 or fw>=W:
      continue
    if cost[fh][fw]<=cost[h][w]+1:
      continue
    cost[fh][fw]=cost[h][w]+1
    q.append([fh,fw])

ans=0
for h in range(H):
  for w in range(W):
    ans=max(ans,cost[h][w])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

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

q=queue.Queue()
cost=[[1000000000 for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(W):
    if l[h][w] == '#':
      cost[h][w] = 0
      q.put([h,w])

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

while not q.empty():
  h, w = q.get()  
  for i in range(4):
    fh=h+dh[i]
    fw=w+dw[i]
    if fh<0 or fh>=H or fw<0 or fw>=W:
      continue
    if cost[fh][fw]<=cost[h][w]+1:
      continue
    cost[fh][fw]=cost[h][w]+1
    q.put([fh,fw])

ans=0
for h in range(H):
  for w in range(W):
    ans=max(ans,cost[h][w])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import queue

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

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

q=queue.Queue()
cost=np.full((H,W),100000000,dtype=np.int32)
for h in range(H):
  for w in range(W):
    if l[h][w] == '#':
      cost[h][w] = 0
      q.put([h,w])

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

while not q.empty():
  h,w = q.get()  
  for i in range(4):
    fh=h+dh[i]
    fw=w+dw[i]
    if fh<0 or fh>=H or fw<0 or fw>=W:
      continue
    if cost[fh][fw]<=cost[h][w]+1:
      continue
    cost[fh][fw]=cost[h][w]+1
    q.put([fh,fw])

ans=0
for h in range(H):
  for w in range(W):
    ans=max(ans,cost[h][w])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

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

q=queue.Queue()
cost=[[1000000 for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(W):
    if l[h][w] == '#':
      cost[h][w] = 0
      q.put([h,w])

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

while not q.empty():
  h,w = q.get()  
  for i in range(4):
    fh=h+dh[i]
    fw=w+dw[i]
    if fh<0 or fh>=H or fw<0 or fw>=W:
      continue
    if cost[fh][fw]<=cost[h][w]+1:
      continue
    cost[fh][fw]=cost[h][w]+1
    q.put([fh,fw])

ans=0
for h in range(H):
  for w in range(W):
    ans=max(ans,cost[h][w])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, insort

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

lines = [input() for s in range(H)]
distance = [k for k in range(H*W) if lines[k//W][k%W] == '#']
nb = len(distance)
if(nb == H*W):
  print(0)
  exit()
number = 0
new_distance = distance[:]
while(nb < H*W):
  tmp = []
  for k in new_distance:
    if k%W-1 >= 0:
      tmp.append(k-1)
    if k%W+1 <= W-1:
      tmp.append(k+1)
    if k-W >= 0:
      tmp.append(k-W)
    if k+W <= (H)*W-1:
      tmp.append(k+W)
  tmp = list(set(tmp))
  new_distance = tmp[:]
  distance.extend(tmp)
  distance = list(set(distance))
  number += 1
  nb = len(distance)
print(number)

Submission status: Time Limit Exceeded

Solution code:
delta=[(1,0),(-1,0),(0,1),(0,-1)]

def dig(tag,end):
    h=tag[0]
    w=tag[1]
    next=set()
    for y, x in delta:
        h2 = h + y
        w2 = w + x
        if not h2<0 and not h2>=H and not w2<0 and not w2>=W and tag not in end:
            next.add((h2,w2))
    return next

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

for h in range(H):
    line=input()
    for w in range(W):
        if line[w] == '#':
            black_mass.add((h,w))

count=-1
end=set()
targets=black_mass
while True:
    count+=1
    next_que=set()
    for tag in targets:
        next_que.update(dig(tag,end))
        end.add(tag)
    targets=next_que
    if len(end) == H*W:
        print(count)
        exit(0)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, insort

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

lines = [input() for s in range(H)]
distance = [k for k in range(H*W) if lines[k//W][k%W] == '#']
nb = len(distance)
if(nb == H*W):
  print(0)
  exit()
number = 0
new_distance = distance[:]
while(nb < H*W):
  tmp = []
  for k in new_distance:
    if k%W-1 >= 0:
      tmp.append(k-1)
    if k%W+1 <= W-1:
      tmp.append(k+1)
    if k-W >= 0:
      tmp.append(k-W)
    if k+W <= (H)*W-1:
      tmp.append(k+W)
  tmp = list(set(tmp))
  new_distance = tmp[:]
  for k in tmp:
    insort(distance, k)
  distance = list(set(distance))
  number += 1
  nb = len(distance)
print(number)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from bisect import bisect_left, insort
from collections import deque

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

lines = [input() for s in range(H)]
distance = [k for k in range(H*W) if lines[k//W][k%W] == '#']
nb = len(distance)
if(nb == H*W):
  print(0)
  exit()
number = 0
new_distance = distance[:]
while(nb < H*W):
  tmp = []
  for k in new_distance:
    if k%W-1 >= 0:
      if distance[bisect_left(distance, k-1)] < k-1:
        tmp.append(k-1)
        print('l', k-1)
    if k%W+1 <= W-1:
      if bisect_left(distance, k+1) == nb:
        tmp.append(k+1)
        print('r', k+1)
      elif distance[bisect_left(distance, k+1)] < k+1:
        tmp.append(k+1)
        print('r', k+1)
    if k-W >= 0:
      if distance[bisect_left(distance, k-W)] < k-W:
        tmp.append(k-W)
        print('t', k-W)
    if k+W <= (H)*W-1:
      if bisect_left(distance, k+W) == nb:
        tmp.append(k+W)
        print('b', k+W)
      elif distance[bisect_left(distance, k+W)] < k+W:
        tmp.append(k+W)
        print('b', k+W)
  tmp = list(set(tmp))
  new_distance = tmp[:]
  for k in tmp:
    insort(distance, k)
  number += 1
  nb = len(distance)
  print(nb)
print(number)

Submission status: Time Limit Exceeded

Solution code:
def dig(tag,end):
    h=tag[0]
    w=tag[1]
    delta=[(1,0),(-1,0),(0,1),(0,-1)]
    next=set()
    for d in delta:
        if not h+d[0]<0 and not h+d[0]>=H and not w+d[1]<0 and not w+d[1]>=W and tag not in end:
            next.add((h+d[0],w+d[1]))
    return next

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

for h in range(H):
    line=input()
    for w in range(W):
        if line[w] == '#':
            black_mass.add((h,w))

count=-1
end=set()
targets=black_mass
next_que=set()
while True:
    count+=1
    next_que=set()
    for tag in targets:
        next_que.update(dig(tag,end))
        end.add(tag)
    # print('next que',next_que)
    # print('end:',end)
    targets=next_que
    if len(end) == H*W:
        print(count)
        exit(0)

Submission status: Time Limit Exceeded

Solution code:
def dig(tag,end):
    h=tag[0]
    w=tag[1]
    delta=[(1,0),(-1,0),(0,1),(0,-1)]
    next=set()
    for d in delta:
        if not h+d[0]<0 and not h+d[0]>=H and not w+d[1]<0 and not w+d[1]>=W and tag not in end:
            next.add((h+d[0],w+d[1]))
    return next

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

for h in range(H):
    line=input()
    for w in range(W):
        if line[w] == '#':
            black_mass.add((h,w))

count=-1
end=set()
targets=black_mass
next_que=set()
while True:
    count+=1
    next_que=set()
    for tag in targets:
        next_que= next_que | dig(tag,end)
        end.add(tag)
    # print('next que',next_que)
    # print('end:',end)
    targets=next_que
    if len(end) == H*W:
        print(count)
        exit(0)

Submission status: Time Limit Exceeded

Solution code:
def allblack(array):
  for i in array:
    for j in i:
      if j!='#':
        return False
  return True
  
def action(array,H,W):
  mask = [[0 for j in range(W)] for i in range(H)]
  for i in range(H):
    for j in range(W):
      if array[i][j] == '.':
        if array[max(0,i-1)][j] == '#' or array[i][max(0,j-1)] == '#' or array[i][min(j+1,W-1)] == '#' or array[min(H-1,i+1)][j] == '#':
          mask[i][j] = 1
  for i in range(H):
    for j in range(W):
      if mask[i][j] == 1:
        array[i][j] = '#'
  return array

a = list(map(int,input().split()))
H,W = a[0],a[1]
board = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
  temp = input()
  for j in range(W):
    board[i][j] = temp[j]

# print(board)

actions = 0
while(allblack(board)==False):
  actions += 1
  board = action(board,H,W)
print(actions)

Submission status: Time Limit Exceeded

Solution code:
def allblack(array):
  for i in array:
    for j in i:
      if j!='#':
        return False
  return True
  
def action(array,H,W):
  board = [[0 for j in range(W)] for i in range(H)]
  for i in range(H):
    for j in range(W):
      if array[i][j] == '.':
        if array[max(0,i-1)][j] == '#' or array[i][max(0,j-1)] == '#' or array[i][min(j+1,W-1)] == '#' or array[min(H-1,i+1)][j] == '#':
          board[i][j] = '#'
        else:
          board[i][j] = '.'
      else:
        board[i][j] = array[i][j]
  return board
      
a = list(map(int,input().split()))
H,W = a[0],a[1]
board = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
  temp = input()
  for j in range(W):
    board[i][j] = temp[j]

# print(board)

actions = 0
while(allblack(board)==False):
  actions += 1
  board = action(board,H,W)
print(actions)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

table = []
bla_list = []
whi_count = 0
roop = 0

for h in range(H):
  col = list(input())
  for w,mas in enumerate(col):
    if mas == "#":
      bla_list.append([h,w])
    else:
      whi_count+=1
  table.append(col)

while(whi_count > 0):
  roop += 1
  nex = []
  for bla in bla_list:
    for i in range(4):
      nh,nw = bla[0] + [1, 0, -1, 0][i], bla[1] + [0, 1, 0, -1][i]
      if 0<=nh<H and 0<=nw<W:
        if table[nh][nw] == ".":
          nex.append([nh,nw])
          table[nh][nw] = "#"
          whi_count -= 1
  bla_list = nex
print(roop)

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = map(int, input().split())
m = [[i for i in input()] for j in range(H)]
q = queue.Queue()

for h in range(H):
    for w in range(W):
        if m[h][w] == '#':
            m[h][w] = 1
            q.put([h, w])

while not q.empty():
    h, w = q.get()
    if h - 1 >= 0 and m[h - 1][w] == '.':
        m[h - 1][w] = m[h][w] + 1
        q.put([h-1, w])
    if w - 1 >= 0 and m[h][w - 1] == '.':
        m[h][w - 1] = m[h][w] + 1
        q.put([h, w-1])
    if h + 1 < H and m[h + 1][w] == '.':
        m[h + 1][w] = m[h][w] + 1
        q.put([h+1, w])
    if w + 1 < W and m[h][w + 1] == '.':
        m[h][w + 1] = m[h][w] + 1
        q.put([h, w+1])

mx = 0
for h in range(H):
    mx = max(max(m[h]), mx)
print(mx-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
d = deque()
memo = [[-1] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append((i, j))
    memo[i][j] = 0
while d:
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and (memo[dhn][dwn] < 0):
            d.append((dhn, dwn))
            memo[dhn][dwn] = memo[dh][dw] + 1
ans = max([max(e) for e in memo])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
A - Darker and Darker
https://atcoder.jp/contests/agc033/tasks/agc033_a

"""
import sys


from collections import deque

def solve(H, W, grid):
    seen = set()
    stack = deque()
    for y, row in enumerate(grid):
        for x, ch in enumerate(row):
            if ch == '#':
                grid[y][x] = 0
                stack.append((x, y))
                seen.add((x, y))

    while stack:
        sx, sy = stack.popleft()
        for nx, ny in ((sx, sy-1), (sx, sy+1), (sx-1, sy), (sx+1, sy)):
            if 0 <= nx < W and 0 <= ny < H and (nx, ny) not in seen and grid[ny][nx] == '.':
                grid[ny][nx] = grid[sy][sx] + 1
                stack.append((nx, ny))
                seen.add((nx, ny))
    return  max([max(row) for row in grid])


def main(args):
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(list(input()))
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
A - Darker and Darker
https://atcoder.jp/contests/agc033/tasks/agc033_a

"""
import sys


from collections import deque

def solve(H, W, grid):
    seen = set()
    stack = deque()
    for y, row in enumerate(grid):
        for x, ch in enumerate(row):
            if ch == '#':
                stack.append((x, y))
                seen.add((x, y))
    ans = 0
    while len(seen) < H*W:
        darken = deque()
        while stack:
            sx, sy = stack.popleft()
            for nx, ny in ((sx, sy-1), (sx, sy+1), (sx-1, sy), (sx+1, sy)):
                if 0 <= nx < W and 0 <= ny < H and (nx, ny) not in seen:
                    darken.append((nx, ny))
                    # grid[ny][nx] = '#'
                    seen.add((nx, ny))
        ans += 1
        stack = darken
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(list(input()))
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
A - Darker and Darker
https://atcoder.jp/contests/agc033/tasks/agc033_a

"""
import sys
#from typing import List


def solve(H, W, grid):
    seen = set()
    stack = []
    for y, row in enumerate(grid):
        for x, ch in enumerate(row):
            if ch == '#':
                stack.append((x, y))
                seen.add((x, y))
    ans = 0
    while len(seen) < H*W:
        darken = []
        while stack:
            sx, sy = stack.pop()
            for nx, ny in ((sx, sy-1), (sx, sy+1), (sx-1, sy), (sx+1, sy)):
                if 0 <= nx < W and 0 <= ny < H and (nx, ny) not in seen:
                    darken.append((nx, ny))
                    # grid[ny][nx] = '#'
                    seen.add((nx, ny))
        ans += 1
        stack = darken
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(list(input()))
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
A - Darker and Darker
https://atcoder.jp/contests/agc033/tasks/agc033_a

"""
import sys
# from typing import List


def solve(H, W, grid):
    seen = set()
    stack = []
    for y, row in enumerate(grid):
        for x, ch in enumerate(row):
            if ch == '#':
                stack.append((x, y))
                seen.add((x, y))
    ans = 0
    while len(seen) < H*W:
        darken = []
        while stack:
            sx, sy = stack.pop()
            for nx, ny in ((sx, sy-1), (sx, sy+1), (sx-1, sy), (sx+1, sy)):
                if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] == '.' and (nx, ny) not in seen:
                    darken.append((nx, ny))
                    grid[ny][nx] = '#'
                    seen.add((nx, ny))
        ans += 1
        stack = darken
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(list(input()))
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import queue


# input
H,W = map(int, input().split())
dist = [[-1 for j in range(W)] for i in range(H)]
que = queue.Queue()
for i in range(H):
  s = list(str(input()))
  for j in range(W):
    if s[j] == '#':
      dist[i][j] = 0
      que.put([i,j])


while not que.empty():
  nx,ny = que.get()
  for px,py in [[1,0],[-1,0],[0,1],[0,-1]]:
    i,j = [nx+px, ny+py]
    if i<0 or H<=i or j<0 or W<=j : continue
    if dist[i][j]==-1:
      dist[i][j]=dist[nx][ny]+1
      que.put([i,j])

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

Submission status: Time Limit Exceeded

Solution code:

h, w = list(map(int, input().split()))
a = [[0] * w for i in range(h)]
count = 0
black = []
for i in range(h):
    l = input()
    for j in range(w):
        if l[j] == '#':
            black.append([i, j])

size = len(black)
nsize = 0

for b in black:
    if len(black) > h*w:
        break

    if b[0]-1 > -1 and [b[0]-1, b[1]] not in black:
        black.append([b[0]-1, b[1]])
        nsize += 1

    if b[0]+1 < h and [b[0]+1, b[1]] not in black:
        black.append([b[0]+1, b[1]])
        nsize += 1

    if b[1]-1 > -1 and [b[0], b[1]-1] not in black:
        black.append([b[0], b[1]-1])
        nsize += 1

    if b[1]+1 < w and [b[0], b[1]+1] not in black:
        black.append([b[0], b[1]+1])
        nsize += 1

    size -= 1
    if size == 0:
        count += 1
        size = nsize
        nsize = 0

#    print(size, nsize, count)

print(count-1)

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-


# input
H,W = map(int, input().split())
Wn = []
Bn = []
for i in range(H):
  aw = list(str(input()))
  for j in range(W):
    if aw[j] == '#':
      Bn.append([i,j])
    else:
      Wn.append([i,j])

# solve
ans = 0
for i,j in Wn:
  e = 2001
  for k,l in Bn:
    e = min(e, abs(i-k)+abs(j-l))
  ans = max(ans,e)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-


# input
H,W = map(int, input().split())
Bn = []
for i in range(H):
  aw = list(str(input()))
  for j in range(W):
    if aw[j] == '#':
      Bn.append([i,j])

# solve
ans = 0
for i in range(H):
  for j in range(W):
    if [i,j] in Bn:
      continue
    l = 2001
    for k in Bn:
      l = min(l,abs(i-k[0])+abs(j-k[1]))
    ans = max(ans,l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

tmp_lst = input().split()
H, W = int(tmp_lst[0]), int(tmp_lst[1])

brack_time_table = np.zeros((H, W))
brack_time_table -= 1   #   全てのマスに初期値の—1
new_bracks_list = []    #   新しく黒くなったマスの座標を表すタプルのリスト

for i in range(H):
    colors_str = input()
    for j in range(W):
        if colors_str[j] == "#":
            brack_time_table[i, j] = 0
            new_bracks_list.append((i, j))

def all_brack(brack_time_table):
    if np.min(brack_time_table) == -1:
        return False
    return True

count = 0
while not all_brack(brack_time_table):
    count += 1
    for i in range(len(new_bracks_list)):
        (y, x) = new_bracks_list.pop(0)
        if y + 1 < H:
            if brack_time_table[y+1, x] == -1:
                brack_time_table[y+1, x] = count
                new_bracks_list.append((y+1, x))
        if x + 1 < W:
            if brack_time_table[y, x+1] == -1:
                brack_time_table[y, x+1] = count
                new_bracks_list.append((y, x+1))
        if y - 1 >= 0:
            if brack_time_table[y-1, x] == -1:
                brack_time_table[y-1, x] = count
                new_bracks_list.append((y-1, x))
        if x - 1 >= 0:
            if brack_time_table[y, x-1] == -1:
                brack_time_table[y, x-1] = count
                new_bracks_list.append((y, x-1))


print(count)

Submission status: Time Limit Exceeded

Solution code:

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

blacks = []
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            blacks.append((i, j))
# print(blacks)

count = 0
while len(blacks) != 0:
    count += 1
#     print(blacks)
    nexts = []
    for x, y in blacks:
        for nx, ny in [(x-1, y), (x+1,y), (x,y-1),(x,y+1)]:
            if 0<=nx<H and 0<=ny<W and maze[nx][ny] == '.':
                maze[nx][ny] = '#'
                nexts.append((nx, ny))
#     print(maze)
    blacks = nexts
    
print(count-1)