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:
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]

cnt = 0
while True:
    c = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                c += 1
    if c == H*W:
        print(cnt)
        quit()
    else:
        cnt += 1
        ind_list = []
        for i in range(H):
            for j in range(W):
                if i != 0:
                    if A[i-1][j] == "#":
                        ind_list.append((i,j))
                if i != H-1:
                    if A[i+1][j] == "#":
                        ind_list.append((i,j))
                if j != 0:
                    if A[i][j-1] == "#":
                        ind_list.append((i,j))
                if j != W-1:
                    if A[i][j+1] == "#":
                        ind_list.append((i,j))
        for ind in ind_list:
            A[ind[0]][ind[1]] = "#"

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = [(0,1),(1,0),(0,-1),(-1,0)]
q = Queue()
for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      q.put((i,j))
      a[i][j] = 0
while not q.empty():
  y,x = q.get()
  for dx,dy in d:
    if 0 <= x+dx < w and 0 <= y+dy < h and a[y+dy][x+dx] == ".":
      a[y+dy][x+dx] = a[y][x] + 1
      q.put((y+dy,x+dx))
m = 0
for i in range(h):
  m = max(m,max(a[i]))
print(m)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

def become_black(A, i, j):
    return (i != 0 and A[i - 1][j] == '#') \
    or (j != 0 and A[i][j - 1] == '#') \
    or (i != H-1 and A[i + 1][j] == '#') \
    or (j != W-1 and A[i][j+1] == '#')


white_exist = True
counter = 0
while True:
    prev_A = copy.deepcopy(A)
    white_exist = False
    for i in range(H):
        if '.' in A[i]:
            white_exist = True
    if not white_exist:
        break

    for i in range(H):
        for j in range(W):
            if prev_A[i][j] == '.' and become_black(prev_A, i, j):
                A[i][j] = '#'
    counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w=map(int,input().split())
s=[input() for i in range(h)]

a=np.zeros((h+2,w+2,2))
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            a[i+1][j+1][0]=1


def update(a,count,t):
    flag=0
    for i in range(h):
        for j in range(w):
            if a[i+1][j+1][t]==0:
               if a[i][j+1][t]==1 or a[i+2][j+1][t]==1 or a[i+1][j][t]==1 or a[i+1][j+2][t]==1:
                   flag=1
                   a[i+1][j+1][1-t]=1
               else:
                   a[i+1][j+1][1-t]=0
            else:
               a[i+1][j+1][1-t]=1
    if flag==1:
        count+=1
    return count

count=0
t=0
dif=-10
while dif<0:
    buf=update(a,count,t)
    dif=count-buf
    #print(dif,buf,count)
    if dif==0:
        break
    count=buf
    t=1-t
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())
inmap=[input() for i in range(H)]
que = deque([],10000000)
# print(inmap)
checked = {}
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            que.append((i,j,0))
            checked[(i,j)] = 0

df=[(1,0),(-1,0),(0,1),(0,-1)]
resmax = 0
while len(que):
    (i,j,k) = que.popleft()
    # print(i,j,k)
    for dy, dx in df:
        if i+dy >= 0 and i+dy<H and j+dx<W and j+dx >=0 and not (i+dy, j+dx) in checked:
            que.append((i+dy,j+dx,k+1))
            resmax = max(resmax, k+1)
            checked[(i+dy,j+dx)] = k+1

print(resmax)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]
black = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            black += 1
ans = 0
while black < h * w:
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                if 0 < i:
                    if a[i - 1][j] == ".":
                        a[i - 1][j] = "%"
                        black += 1
                if 0 < j:
                    if a[i][j - 1] == ".":
                        a[i][j - 1] = "%"
                        black += 1
                if i < h - 1:
                    if a[i + 1][j] == ".":
                        a[i + 1][j] = "%"
                        black += 1
                if j < w - 1:
                    if a[i][j + 1] == ".":
                        a[i][j + 1] = "%"
                        black += 1
    ans += 1
    for i in range(h):
        for j in range(w):
            if a[i][j] == "%":
                a[i][j] = "#"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = (int(x) for x in input().split())
A = []
for i in range(H):
    A += [ ['@'] + list(input()) + ['@'] ]
A = [['@' for i in range(W+2)]] + A + [['@' for i in range(W+2)]]

around = [[-1,0],[1,0],[0,-1],[0,1]]

if any('.' in A[i] for i in range(1,H+1)):
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == '#':
                for k in around:
                    if A[i+k[0]][j+k[1]] == '.':
                        A[i+k[0]][j+k[1]] = 1
                    A[i][j] = '@'

    ans = 1
    while any('.' in A[i] for i in range(1,H+1)):
        for i in range(1,H+1):
            for j in range(1,W+1):
                if A[i][j] == ans:
                    for k in around:
                        if A[i+k[0]][j+k[1]] == '.':
                            A[i+k[0]][j+k[1]] = ans + 1
                        A[i][j] = '@'
        ans += 1

else:
    ans = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

H, W = map(int, input().split())
A = []
black = []
for i in range(H):
    tmp = input()
    A.append(tmp)
    black += [(i, j) for j in range(W) if tmp[j] == '#']
ans = 0
for i, j in product(range(H), range(W)):
    if A[i][j] == '.':
        dist_bl = min([abs(b[0] - i) + abs(b[1] - j) for b in black])
        ans = max(ans, dist_bl)
print(ans)

Submission status: Time Limit Exceeded

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

#test
f = True
cnt = 0
nxt = [[A[i][j] for j in range(W)] for i in range(H)]
while f:
    f = False
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                for py,px in [(i-1,j), (i,j-1), (i+1,j), (i, j+1)]:
                    # 可能
                    if 0 <= py < H and 0 <= px < W:
                        if A[py][px] == ".":
                            f = True #まだある
                            nxt[py][px] = "#"
    A = [[nxt[i][j] for j in range(W)] for i in range(H)]
    if f:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(1000000)

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

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        if s == '.':
            temp_field.append(0)
        else:
            temp_field.append(1)
    field.append(temp_field)
    
dp = [[0] * W for _ in range(H)]

def rec(i, j):
    if field[i][j] == 1:
        return 0
    
    if dp[i][j] != 0:
        return dp[i][j]
        
    dp[i][j] = H + W
        
    min_dist = H + W
    if i > 0:
        min_dist = min(min_dist, rec(i-1, j) + 1)
    if i < H - 1:
        min_dist = min(min_dist, rec(i+1, j) + 1)
    if j > 0:
        min_dist = min(min_dist, rec(i, j-1) + 1)
    if j < W - 1:
        min_dist = min(min_dist, rec(i, j+1) + 1)
        
    dp[i][j] = min_dist
    
    return min_dist
    
    
for i in range(H):
    for j in range(W):
        rec(i, j)
     
print(max([max(temp_dp) for temp_dp in dp]))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a_list=[]
for i in range(h):
    b=list(input())
    a_list.append(b)
count=-1
end=0
while end==0:
    end=1
    c_list=[]
    for i in range(h):
        for j in range(w):
            if a_list[i][j]=='#':
                if i>0:
                    c_list.append((i-1,j))
                if i<h-1:
                    c_list.append((i+1,j))
                if j>0:
                    c_list.append((i,j-1))
                if j<w-1:
                    c_list.append((i,j+1))
            else:
                end=0
    for k in c_list:
        a_list[k[0]][k[1]]='#'
    count=count+1
print(count)

Submission status: Time Limit Exceeded

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


def main():
  height, width = map(int, input().split())
  max_value = height * width
  values = []
  queue = []

  for y in range(height):
    values.append([0 if v == '#' else max_value for v in input().strip()])
    queue.extend((x, y) for x, v in enumerate(values[-1]) if v == 0)

  targets = set(queue)

  while len(queue) > 0:
    x, y = queue.pop()
    v = values[y][x] + 1

    targets.remove((x, y))

    if x > 0 and values[y][x - 1] > v:
      values[y][x - 1] = v

      if (x - 1, y) not in targets:
        queue.append((x - 1, y))
        targets.add((x - 1, y))

    if x < width - 1 and values[y][x + 1] > v:
      values[y][x + 1] = v

      if (x + 1, y) not in targets:
        queue.append((x + 1, y))
        targets.add((x + 1, y))

    if y > 0 and values[y - 1][x ] > v:
      values[y - 1][x] = v

      if (x , y - 1) not in targets:
        queue.append((x, y - 1))
        targets.add((x, y - 1))

    if y < height - 1 and values[y + 1][x] > v:
      values[y + 1][x] = v

      if (x , y + 1) not in targets:
        queue.append((x, y + 1))
        targets.add((x, y + 1))

  print(max(max(v) for v in values), flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def all_black(board):
  for row in board:
    for cell in row:
      if cell == '.':
        return False
  return True

def show(board):
  to_show = ''
  for row in board:
    to_show += ''.join(row) + '\n'
  print(to_show)

def proceed(board, h, w):
  board2 = []
  for row in board:
    r = []
    for cell in row:
      r.append(cell)
    board2.append(r)
  for row in range(h):
    for column in range(w):
      board2[row][column] = '.'
      #print('check for board2 at {}'.format((row, column)))
      for rr in [row-1, row, row+1]:
        if rr < 0 or rr >= h:
          continue
        neighbor = board[rr][column]
        if neighbor == '#':
          board2[row][column] = '#'
          #print('neighbor board {} is black'.format((rr, column)))
      for cc in [column-1, column, column+1]:
        if cc < 0 or cc >= w:
          continue
        neighbor = board[row][cc]
        if neighbor == '#':
          board2[row][column] = '#'
          #print('neighbor board {} is black'.format((row, cc)))
  return board2


h, w = map(int, input().split())
board = []
cnt = 0

for hh in range(h):
  board.append(list(input()))

#show(board)

while not all_black(board):
  board = proceed(board, h, w)
  #show(board)
  cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())
inmap=[input() for i in range(H)]
que = deque([])
# print(inmap)
checked = {}
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            que.append((i,j,0))
            checked[(i,j)] = 0

df=[(1,0),(-1,0),(0,1),(0,-1)]
resmax = 0
while len(que):
    (i,j,k) = que.popleft()
    # print(i,j,k)
    for dy, dx in df:
        if i+dy >= 0 and i+dy<H and j+dx<W and j+dx >=0 and not (i+dy, j+dx) in checked:
            que.append((i+dy,j+dx,k+1))
            resmax = max(resmax, k+1)
            checked[(i+dy,j+dx)] = k+1

print(resmax)

Submission status: Time Limit Exceeded

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

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

turn = 0
while len(white_cells) > 0:
    not_changed_cells = []
    changed_cells = []
    for cell in white_cells:
        is_changed = False
        for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            x += cell[0]
            y += cell[1]
            if x >= 0 and x < W and y >= 0 and y < H:
                if A[y][x] == '#':
                    changed_cells.append(cell)
                    is_changed = True
                    break
        if not is_changed:
            not_changed_cells.append(cell)
    white_cells = not_changed_cells
    for x, y in changed_cells:
        A[y][x] = '#'
    turn += 1
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import math


def main():
    h, w = map(int, raw_input().split())
    aa = []
    for _ in xrange(h):
        aa.append(raw_input())
    q = []
    dist = [[float('inf')] * w for _ in xrange(h)]
    for y in xrange(h):
        row = aa[y]
        for x in xrange(w):
            if row[x] == '#':
                dist[y][x] = 0
                q.append([-0, x, y])
    heapq.heapify(q)
    while q:
        d, x, y = heapq.heappop(q)
        dd = -d + 1
        for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            xx = x + dx
            yy = y + dy
            if 0 <= xx < w and 0 <= yy < h:
                if aa[yy][xx] == '.' and dist[yy][xx] > dd:
                    dist[yy][xx] = dd
                    heapq.heappush(q, [-dd, xx, yy])
    m = 0
    for row in dist:
        for v in row:
            if not math.isinf(v) and v > m:
                m = v
    print m


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
y,x = map(int,input().split())
board = []
black_list = []
white_list = []
for i in range(y):

    tmp_list = list(str(input()))
    for index,s in enumerate(tmp_list):
        if s == "#":
            black_list.append((i,index))
        else:
            white_list.append((i,index))
#print(black_list)
#print(white_list)
max_diff = 0
for white in white_list:
    tmp_min = y+x
    for black in black_list:
        tmp_val = abs(white[0]-black[0]) + abs(white[1]-black[1])
        #print("tmp_val:{}".format(tmp_val))
        if tmp_val < tmp_min:
            tmp_min = tmp_val
    if tmp_min > max_diff:
        max_diff = tmp_min
print(max_diff)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline

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

A = [readline().strip() for i in range(H)]
A = [[a == '#' for a in line] for line in A]
count = 0

def check():
    flag = True
    for row in A:
        flag = flag and all(row)
        if not flag:
            return False
    return flag

while not check():
    after = [[False] * W for i in range(H)]
    for y in range(H):
        for x in range(W):
            if A[y][x] or (y >= 1 and A[y-1][x]) or \
                (y < H-1 and A[y + 1][x]) or (x >=1 and A[y][x-1]) or \
                (x < W - 1 and A[y][x + 1]):
                after[y][x] = True
            else:
                after[y][x] = False
    A = after
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

L = [[float("inf") for x in range(W)] for y in range(H)]



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

Q = deque()

for y in range(H) :
    for x in range(W) :
        if A[y][x] != "#" :
            continue
        
        L[y][x] = 0
        
        Q.append((y,x))

while Q :
    y,x = Q.popleft()

    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx

        if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
            continue

        if L[ny][nx] <= (L[y][x] + 1) :
            continue
        
        L[ny][nx] = L[y][x] + 1
        
        Q.append((ny,nx))

ans = 0

for y in range(H) :
    for x in range(W) :
        ans = max(ans, L[y][x])
print(ans)

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

#A
def A():
    h,w = LI()
    a = [sys.stdin.readline() for i in range(h)]
    s = 0
    p = [None for i in range(w*h)]
    q = [None for j in range(w*h)]
    l = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                p[s] = (i,j)
                s += 1
            else:
                q[l] = (i,j)
                l += 1
    if s == h*w:
        print(0)
        quit()
    ans = 0
    M = w*h
    for i,j in q[:h*w-s]:
        if a[i][j] == ".":
            m = M
            for x,y in p[:s]:
                if abs(i-x)+abs(j-y) < m:
                    m = abs(i-x)+abs(j-y)
            if m > ans:
                ans = m
    print(ans)
    return

#B
def B():
    n = I()
    return

#C
def C():
    n = I()
    return

#D
def D():
    n = I()
    return

#E
def E():
    n = I()
    return

#F
def F():
    n = I()
    return

#Solve
if __name__ == "__main__":
    A()

Submission status: Time Limit Exceeded

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

result = 0
while True:
    count = 0
    for i in range(H):
        count += A[i].count("#")

    if count == H * W:
        break

    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    if 0 <= i + di < H and 0 <= j + dj < W:
                        nA[i + di][j + dj] = "#"

    for i in range(H):
        A[i] = nA[i][:]

    result += 1


print(result)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())

a = [list(str(input())) for i in range(h)]
pre_a = [x[:] for x in a]
ans = 0

while True:
    count_dot = 0
    for i in range(h):
        for j in range(w):
            if pre_a[i][j] == "#":
                if i - 1 >= 0:
                    a[i-1][j] = "#"
                if i + 1 <= h-1:
                    a[i+1][j] = "#"
                if j - 1 >= 0:
                    a[i][j-1] = "#"
                if j + 1 <= w-1:
                    a[i][j+1] = "#"
            else:
                count_dot += 1
    pre_a = [x[:] for x in a]
    if count_dot > 0:
        ans += 1
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
a=[[float("inf")]*w for i in range(h)]
def f(x,y,t):
    if 0<=x<h and 0<=y<w:
        if s[x][y]=="#":
            a[x][y]=0
            f(x,y+1,1)
            f(x+1,y,1)
            f(x-1,y,1)
            f(x,y-1,1)
        else:
            if a[x][y]>t:
                a[x][y]=t
                f(x,y+1,t+1)
                f(x+1,y,t+1)
                f(x-1,y,t+1)
                f(x,y-1,t+1)
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            f(i,j,0)
            break
print(max(max(i)for i in a))

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[]
black=[]
white=[]
for i in range(0,H):
    A=str(input())
    for j in range(0,W):
        if(A[j]=='#'):
            black.append([i,j])
        else:
            white.append([i,j])

ans=0
tmp=0
for W in white:
    tmp=20000
    for B in black:
        tmp=min(tmp,abs(W[0]-B[0])+abs(W[1]-B[1]))
    if(tmp>ans):
        ans=tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j]=='#':
            que.append((i, j))

cnt=0
while len(que)!=0:
    ln=len(que)
    for i in range(ln):
        cur=que.popleft()
        # 4方向見る
        for direction in directions:
            nxt = list(map(lambda x,y: x+y, cur, direction))
            # 壁と黒はスキップ
            if grid[nxt[0]][nxt[1]]=='*' or grid[nxt[0]][nxt[1]]=='#':
                continue
            # 白を埋める
            if grid[nxt[0]][nxt[1]]=='.':
                grid[nxt[0]][nxt[1]]='#'
                que.append(nxt)
    cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
li=[input() for i in range(h)]
black=[]

for i in range(h):
    for j  in range(w):
        if li[i][j]=="#":
            black.append([i,j])
            
def check(li,i,j,black):
    v=[]
    for k in black:
        v.append(abs(k[0]-i)+abs(k[1]-j))
 #   print(min(v))
    return min(v)
    
        
        
    

count=0

for i in range(h):
    for j  in range(w):
        if li[i][j]==".":
            count=max(count,check(li,i,j,black))
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

import itertools


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


def count_operations(h, w, stage):
    is_black = [[cell == "#" for cell in line] for line in stage]
    for num_ops in itertools.count():
        rep_cells = set()
        for r0, c0 in itertools.product(range(h), range(w)):
            if not is_black[r0][c0]:
                for dr, dc in DS:
                    r, c = r0 + dr, c0 + dc
                    if 0 <= r < h and 0 <= c < w and is_black[r][c]:
                        rep_cells.add((r0, c0))
        for r, c in rep_cells:
            is_black[r][c] = True
        if not rep_cells:
            return num_ops


def main():
    h, w = (int(z) for z in input().split())
    stage = [input() for _ in range(h)]
    res = count_operations(h, w, stage)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
H, W = map(int, input().split())
field = []
for i in range(H):
    field.append(input())
new_field = copy.deepcopy(field)

def check():
    for h in range(H):
        if field[h].count('.'):
            return True
    return False

dirs = [[0, 1], [1, 0], [-1, 0], [0, -1]]

count = 0
while check():
    for h in range(H):
        for w in range(W):
            if field[h][w] == '#':
                for dir in dirs:
                    t = h + dir[0]
                    y = w + dir[1]
                    if 0 <= t <= H-1 and 0 <= y <= W-1:
                        new_field[t] = new_field[t][:y] + '#' + new_field[t][y+1:]
    field = copy.deepcopy(new_field)
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
cs = []
q = deque()
s = set()
for h in range(H):
    cs.append(input())
    for w in range(W):
        if cs[h][w] == '#':
            s.add((h+1, w+1))
            q.append((h+1, w+1, 0))
vx = [0, 1, 0, -1]
vy = [1, 0, -1, 0]
ans = 0
while len(s) < H * W:
    y, x, n = q.popleft()
    for i in range(4):
        ny = y + vy[i]
        nx = x + vx[i]
        if ny >= 1 and ny <= H and nx >= 1 and nx <= W:
            if cs[ny-1][nx-1] == '.' and ((ny, nx) not in s):
                s.add((ny, nx))
                q.append((ny, nx, n+1))
                ans = max(ans, n+1)
print(ans)

Submission status: Time Limit Exceeded

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

table = []
for _ in range(H):
    table.append(["k"] + list(input()) + ["k"])
    
table = [["k"]*(W+2)] + table + [["k"]*(W+2)]

import queue
q = queue.Queue()

min_memo = [[None]*(W+2) for _ in range(H+2)]

for y, r in enumerate(table):
    for x, c in enumerate(r):
        if c == "#":
            q.put([y,x,0])
            min_memo[y][x] = 0

while True:
    if q.empty():
        print(cnt)
        break
    y, x, cnt = q.get()
    for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if table[y+dy][x+dx] == ".":
            if min_memo[y+dy][x+dx] == None:
                min_memo[y+dy][x+dx] = cnt+1
                q.put([y+dy, x+dx, cnt+1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

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

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

q = deque()

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

count = 0
while q: # 10**6
    r = copy.copy(q)
    q = deque()
    while r:
        this_pos = this_x, this_y = r.popleft()

        for ad_x, ad_y in ADS:
            x, y = this_x+ad_x, this_y+ad_y
            if not ((0 <= x < W) and (0 <= y < H)):
                continue
            if A[y][x] == "#":
                continue
            A[y][x] = "#"
            q.append((x, y))
    count += 1
    # print(A, q, count)

print(count-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().rstrip().split(' ')))
a = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    inputs = [c for c in input().rstrip()]
    for j in range(W):
       a[i][j] = 0 if inputs[j] == '.' else 1 

v = [[(H + W + 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] == 1:
            for h in range(H):
                for w in range(W):
                    v[h][w] = min(v[h][w], abs(h - i) + abs(w - j))

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

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(i,x) for x in range(W) if t[x] == '#'])

ans = -1

for y in range(H):
	for x in range(W):
		t = min([abs(x-x2)+abs(y-y2) for y2,x2 in bk])
		ans = max(t,ans)

print(ans)

Submission status: Time Limit Exceeded

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


def main():
  height, width = map(int, input().split())
  max_value = height * width
  values = []
  queue = set()

  for y in range(height):
    values.append([0 if v == '#' else max_value for v in input().strip()])
    queue |= set((x, y) for x, v in enumerate(values[-1]) if v == 0)

  while len(queue) > 0:
    x, y = queue.pop()
    v = values[y][x] + 1

    if x > 0 and values[y][x - 1] > v:
      values[y][x - 1] = v
      queue.add((x - 1, y))

    if x < width - 1 and values[y][x + 1] > v:
      values[y][x + 1] = v
      queue.add((x + 1, y))

    if y > 0 and values[y - 1][x ] > v:
      values[y - 1][x] = v
      queue.add((x, y - 1))

    if y < height - 1 and values[y + 1][x] > v:
      values[y + 1][x] = v
      queue.add((x, y + 1))

  print(max(max(v) for v in values), flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j]=='#':
            que.append((i, j))

cnt=0
while len(que) != 0:
    ln=len(que)
    for i in range(ln):
        cur=que.popleft()
        # 4方向見る
        for direction in directions:
            nxt = list(map(lambda x,y: x+y, cur, direction))
            # 壁と黒はスキップ
            if grid[nxt[0]][nxt[1]]=='*' or grid[nxt[0]][nxt[1]]=='#':
                continue
            # 白を埋める
            if grid[nxt[0]][nxt[1]]=='.':
                grid[nxt[0]][nxt[1]]='#'
                que.append(nxt)
    cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
black,white = [],[]

for h in range(H):
    a = input()
    for w in range(W):
        if a[w]=="#":
            black.append((h,w))
        else:
            white.append((h,w))

ans = 0
for wh,ww in white:
    tmp = float("inf")
    for bh,bw in black:
        if tmp > abs(wh-bh) + abs(ww-bw):
            tmp =  abs(wh-bh) + abs(ww-bw)
    ans = max(ans, tmp)
print(ans)