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

import numpy as np
indexes = list(map(list, np.array(np.where(np.array(A) == '#')).T))

cnt = 0
flag = False

if W == 1 and H == 1:
    flag = True
if not flag:
    for i, j in indexes:
        if i == 0 and j == 0:
            A[i + 1][j] = '#'
            A[i][j + 1] = '#'
        elif i == 0 and j == W - 1:
            A[i + 1][j] = '#'
            A[i][j - 1] = '#'
        elif i == H - 1 and j == 0:
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
        elif i == H - 1 and j == W - 1:
            A[i - 1][j] = '#'
            A[i][j - 1] = '#'
        elif i == 0:
            A[i + 1][j] = '#'
            A[i][j + 1] = '#'
            A[i][j - 1] = '#'
        elif j == 0:
            A[i + 1][j] = '#'
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
        elif i == H - 1:
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
            A[i][j - 1] = '#'
        elif j == W - 1:
            A[i + 1][j] = '#'
            A[i - 1][j] = '#'
            A[i][j - 1] = '#'
        else:
            A[i + 1][j] = '#'
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
            A[i][j - 1] = '#'
    cnt += 1
    flag = all([all(np.array(A)[i] == '#') for i in range(len(A))])
    indexes = list(map(list, np.array(np.where(np.array(A) == '.')).T))

while not flag:
    saved_index = []
    for i, j in indexes:
        if i == 0 and j == 0:
            if A[i + 1][j] == '#' or A[i][j + 1] == '#':
                saved_index.append([i, j])
        elif i == 0 and j == W - 1:
            if A[i + 1][j] == '#' or A[i][j - 1] == '#':
                saved_index.append([i, j])
        elif i == H - 1 and j == 0:
            if A[i - 1][j] == '#' or A[i][j + 1] == '#':
                saved_index.append([i, j])
        elif i == H - 1 and j == W - 1:
            if A[i - 1][j] == '#' or A[i][j - 1] == '#':
                saved_index.append([i, j])
        elif i == 0:
            if A[i + 1][j] == '#' or A[i][j + 1] == '#' or A[i][j - 1] == '#':
                saved_index.append([i, j])
        elif j == 0:
            if A[i + 1][j] == '#' or A[i - 1][j] == '#' or A[i][j + 1] == '#':
                saved_index.append([i, j])
        elif i == H - 1:
            if A[i - 1][j] == '#' or A[i][j + 1] == '#' or A[i][j - 1] == '#':
                saved_index.append([i, j])
        elif j == W - 1:
            if A[i + 1][j] == '#' or A[i - 1][j] == '#' or A[i][j - 1] == '#':
                saved_index.append([i, j])
        else:
            if A[i + 1][j] == '#' or A[i - 1][j] == '#' or A[i][j + 1] == '#' or A[i][j - 1] == '#':
                saved_index.append([i, j])
    for i, j in saved_index:
        A[i][j] = '#'
    cnt += 1
    flag = all([all(np.array(A)[i] == '#') for i in range(len(A))])
    indexes = list(set(map(tuple, indexes)) - set(map(tuple, list(map(list, np.array(np.where(np.array(A) == '#')).T)))))
    

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def st(s):
    x=[]
    for i in range(W):
        if s[i]=="#": x.append(0)
        else: x.append(-1)
    return x
"""
chk(i,j):
    if a[i][j]!=-1: return a[i][j]
    x=[]
    if i>0: x.append(chk(i-1,j))
    if i<H-1: x.append(chk(i+1,j))
    if j>0: x.append(chk(i,j-1))
    if i<W-1: x.append(chk(i,j+1))
    a[i][j]=min(x)+1
    return a[i][j] 

cul(i,j):
    if a[i][j]!=-1: return
    x=[]
    if i>0 and a[i-1][j]!=-1: x.append(a(i-1,j))
    if i<H-1 and a[i+1][j]!=1: x.append(a(i+1,j))
    if j>0: x.append(a(i,j-1))
    if i<W-1and: x.append(a(i,j+1))
    a[i][j]=min(x)+1
    return a[i][j] 
"""
H,W=map(int,input().split())
a=[ st(input()) for i in range(H)]


x=[]
for i in range(H):
    for j in range(W):
        if a[i][j]==0:
            x.append([i,j])

ans=0
for i in range(H):
    for j in range(W):
        tmp=H+W
        for k in range(len(x)):
            q=abs(i-x[k][0])+abs(j-x[k][1])
            if q<=ans:
                tmp=0
                break
            tmp=min(tmp,q)
        ans=max(tmp,ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
A = []
for _ in range(H):
    v = 0
    for w, x in zip(range(W), input()):
        if x == "#":
            v |= 1 << w
    A += [ v ]

import numpy as np


A = np.array(A)
WK = np.zeros(A.shape)
MASK = pow(2, W) - 1
MASKSUM = MASK * H
i = 0
while True:
    if np.sum(A) == MASKSUM:
        break
    WK = 0+A
    A[:-1] |= WK[1:]
    A[1:] |= WK[:-1]
    A |= ((WK << 1)&MASK) | (WK >> 1)
    i += 1

print(i)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a,s=[],[["x"for i in range(w+2)]]
for i in range(h):
  t,tt=input(),[]
  for j in range(w):
    if t[j]=="#":a.append([i+1,j+1])
    tt.append(t[j])
  s.append(["x"]+tt+["x"])
s.append(["x"for i in range(w+2)])
f=1
while 1:
  b=[]
  for k in a:
    i,j=k[0],k[1]
    if s[i-1][j]==".":s[i-1][j]=f;b.append([i-1,j])
    if s[i+1][j]==".":s[i+1][j]=f;b.append([i+1,j])
    if s[i][j-1]==".":s[i][j-1]=f;b.append([i,j-1])
    if s[i][j+1]==".":s[i][j+1]=f;b.append([i,j+1])
  a=b[:]
  f+=1
  if len(a)==0:break
print(f-2)

Submission status: Time Limit Exceeded

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


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,count):
    v=[]
    for k in black:
        v.append(abs(k[0]-i)+abs(k[1]-j))
            
 #   print(min(v))
    return min(v)
    
        
        
    

count=0
point=0
dist=0
for i in range(h):
    for j  in range(w):
        if li[i][j]==".":
            
            if dist+abs(point-j)>0:
                dist=check(li,i,j,black,count)
                point=j
                
            count=max(count,dist)
            

            
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy, copy
def solve():
    h, w = map(int, input().split())
    hw = h * w
    MAP = [list(input()) for _ in range(h)]
    S = set()
    for r in range(h):
        for c in range(w):
            if MAP[r][c] == '#':
                S.add((r, c))
    cnt = 0
    while len(S) != hw:
        S2 = deepcopy(S)
        for r, c in S2:
            for nr, nc in ((r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)):
                if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in S:
                    S.add((nr, nc))
        cnt += 1
    print(cnt)
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
a=[[float("inf")]*w for i in range(h)]
b=[[False]*w for i in range(h)]
def f(x,y,t):
    if 0<=x<h and 0<=y<w:
        if s[x][y]=="#":
            if b[x][y]==False:
                a[x][y]=0
                b[x][y]=True
                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 and t<h+w:
                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())
c_set = set()
for i in range(H):
  b = input()
  count_b = b.count('#')
  index = 0
  for x in range(count_b):
    index = b.find('#', x)
    c_set.add((i, index))
ans = 0
for i in range(H+W):
  ll = c_set.copy()
  if len(c_set) >= H*W:
    break;
  else:
    ans += 1
    for c in ll:
      if not c[0]-1 < 0:
        c_set.add((c[0]-1, c[1]))
      if not c[0]+1 > W-1:
        c_set.add((c[0]+1, c[1]))
      if not c[1]-1 < 0:
        c_set.add((c[0], c[1]-1))
      if not c[1]+1 > W-1:
        c_set.add((c[0], c[1]+1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
dict = {}
fuchi = {}
for i in range(h):
    Ai = input()
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            dict[(i, j)] = 1
            fuchi[(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

def check(poj):
    i, j = poj[0], poj[1]
    if (i + 1, j) in dict and (i  - 1, j) in dict and (i, j + 1) in dict and (i, j - 1) in dict:
        return True
    else:
        return False

c = 0

while(True):
    if len(dict) == h * w:
        print(c)
        break
    pojs = {}
    for poj in fuchi.keys():
        for item in add(poj):
            if item != 0:
                pojs[(poj[0] + item[0], poj[1] + item[1])] = 1
    for poj in pojs:
        dict[poj] = 1
        fuchi[poj] = 1
    for item in [poj for poj in fuchi if check(poj)]:
        fuchi.pop(item)
    c += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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



d = defaultdict(list)
used = set()
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            d[0].append((h, w))
            used.add((h, w))

ans = 0
tmp =0
for x in range(1999):
    for (_h, _w) in (d[x]):
        for i,j in [(0,1),(0,-1),(1,0),(-1,0)]:
            h = _h+i
            w = _w +j
            tmp +=1
            if h < 0 or H <= h:
                continue
            if w < 0 or W <= w:
                continue
            if (h, w) not in used:
                d[x + 1].append((h, w))
                used.add((h, w))
                ans = x + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
x = input().split()
H = int(x[0])
W = int(x[1])
time = 0

Field = []
for i in range(0,H):
    al = list(input())
    Field.append(al)

def change():
    num_list = []
    for h in range(0,H):
        for w in range(0,W):
            if Field[h][w] == '#':
                pass
            elif 0<= h-1 <= H-1 and Field[h-1][w] == '#':
                num_list.append([h,w])
            elif 0<= h+1 <= H-1 and Field[h+1][w] == '#':
                num_list.append([h,w])
            elif 0<= w-1 <= W-1 and Field[h][w-1] == '#':
                num_list.append([h,w])
            elif 0<= w+1 <= W-1 and Field[h][w+1] == '#':
                num_list.append([h,w])
            else:
                pass
    for k in range(0,len(num_list)):
        h = num_list[k][0]
        w = num_list[k][1]
        Field[h][w] = '#'

for h in range(0,H):
    for w in range(0,W):
        if Field[h][w] == '.':
            change()
            time = time + 1
        else:
            pass
print(time)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
A = np.zeros((h, w))
for i in range(h):
    B = [str(x) for x in input()]
    for j in range(w):
        if B[j] == "#":
            A[i, j] = 1

ans = 0
while int(sum(sum(A))) != h * w:
    C = np.zeros((h, w))
    ans += 1
    for i in range(h):
        if sum(A[i, :]) == h:
            continue
        for j in range(w):
            if A[i, j] == 1.:
                if i - 1 >= 0:
                    C[i - 1, j] = 1.
                if i + 1 < h:
                    C[i + 1, j] = 1.
                if j - 1 >= 0:
                    C[i, j - 1] = 1.
                if j + 1 < w:
                    C[i, j + 1] = 1.
    A[np.logical_or(A, C)] = 1
print(ans)

Submission status: Time Limit Exceeded

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

result = 0
'''
3 3
...
.#.
...

'''

yCnt =0
isEnd =False
while not isEnd:
    import copy
    target_pre = copy.deepcopy(target)
    result +=1

    cnt =0
    for yoko in target:
        if yoko.count('#') == W:
            cnt +=1
        else:
            break

    if cnt == H:
        isEnd = True
        result -=1
        break

    for i,yoko in enumerate(target):
        if yoko.count('#') == W  or yoko.count('.') == W:
           continue

        for j ,y in enumerate(yoko):
            if y == '#' and target_pre[i][j] != '.':
                if i == 0 and j == 0:
                    if H == 1:
                        target[0][1] = '#'
                    else:
                        target[0][1] = '#'
                        target[1][0] = '#'
                if i == H - 1 and j ==0:
                    if H == 1:
                        target[H-1][1] = '#'
                    else:
                        target[H-1][1] = '#'
                        target[H-2][0] = '#'
                if i == 0 and j == W -1:
                    if H == 1:
                        target[0][W-2] = '#'
                    else:
                        target[0][W-2] = '#'
                        target[1][W-1] = '#'

                if i == H-1 and j == W -1:
                    if H == 1:
                        target[H-1][W-2] = '#'
                    else:
                        target[H-1][W-2] = '#'
                        target[H-2][W-1] = '#'
                if i == 0 and j != 0 and j != W-1:
                    if H == 1:
                        target[0][j-1] = '#'
                        target[0][j+1] = '#'
                    else:
                        target[0][j-1] = '#'
                        target[0][j+1] = '#'
                        target[1][j] = '#'
                if i == H - 1 and j != 0 and j != W-1:
                    if H == 1:
                        target[H-1][j-1] = '#'
                        target[H-1][j+1] = '#'
                    else:
                        target[H-1][j-1] = '#'
                        target[H-1][j+1] = '#'
                        target[H-2][j] = '#'
                if j == 0 and i != 0 and i != H-1:
                    if H == 1:
                        target[0][1] = '#'
                    else:
                        target[i-1][0] = '#'
                        target[i+1][0] = '#'
                        target[i][1] = '#'
                if j == W - 1 and i != 0 and i != H-1:
                    if H == 1:
                        target[0][W-2] = '#'
                    else:
                        target[i-1][W-1] = '#'
                        target[i+1][W-1] = '#'
                        target[i][W-2] = '#'
                if i != 0 and i != H-1 and j!=0 and j != W - 1:
                    if H == 1:
                        target[0][j + 1] = '#'
                        target[0][j - 1] = '#'
                    else:
                        target[i][j + 1] = '#'
                        target[i][j - 1] = '#'
                        target[i + 1][j] = '#'
                        target[i -1][j] = '#'
                #print(target)

print(result)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
n = h*w
d = []
for i in range(h):
    d.append(list(input()))

c = 0
while True:
    hw_list = []
    dark = []
    for i in range(h):
        for j in range(w):
            if d[i][j] == "#":
                dark.append((i,j))
                hw_list.extend([(i,j+1),(i,j-1),(i+1,j),(i-1,j)])
    if len(dark) == n:
        break
    hw_list = list(set(hw_list)-set(dark))
    hw = [j for j in hw_list if min(j) >= 0 and j[0] < h and j[1] < w]
    for i in range(len(hw)):
        d[hw[i][0]][hw[i][1]] = "#"
    c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
import copy
  
x,y = list(map(int, input().split()))
input_mark = []
total_count = 0

for i in range(x):
  input_mark.append(list(input()))

input_mark_bk = copy.deepcopy(input_mark)

while True:
  #print(input_mark)
  black_row_index = []
  all_black_row_nums = 0
  for i in range(x):
    if '#' in input_mark[i]:
      black_row_index.append(i)
    if '.' not in input_mark[i]:
      all_black_row_nums += 1
  #print(black_row_index,all_black_row_nums)
  if all_black_row_nums == x:
    print(total_count)
    exit()
  for i in black_row_index:
    black_col_index = [k for k, x in enumerate(input_mark_bk[i]) if x == '#']
    for j in black_col_index:
      #print(input_mark_bk[i][j])
      if input_mark_bk[i][j] == '#':
        # i=0の時はi-1は操作対象外
        if i != 0:
          input_mark[i-1][j] = '#'
        # i=x-1の時はi+1は操作対象外
        if i != x-1:
          input_mark[i+1][j] = '#'
        # j=0の時はj-1は操作対象外
        if j != 0:
          input_mark[i][j-1] = '#'
        # j=y-1の時はj+1は操作対象外
        if j != y-1:
          input_mark[i][j+1] = '#'
  total_count+=1
  input_mark_bk = copy.deepcopy(input_mark)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
X = [int(i) for i in input().split()]
A = [[s=="#" for s in input()] for _ in range(X[0])]
if sum([sum(a) for a in A])==X[0]*X[1]:
    print(0)
    sys.exit(0)
for n in range(1,1000000):
    A_ = copy.deepcopy(A)
    for i in range(0,X[0]):
        for j in range(0,X[1]):
            up = max(0, i-1)
            down = min(i+1, X[0]-1)
            left = max(0, j-1)
            right = min(j+1, X[1]-1)
            # res = A[i][j]+A[up][j]+A[down][j]+A[i][right]+A[i][left]
            if A[i][j]:
                A_[i][j]=A_[up][j]=A_[down][j]=A_[i][right]=A_[i][left]=True
    A = copy.deepcopy(A_)
    if sum([sum(a) for a in A])==X[0]*X[1]:
        break
print(n)

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
h,w=map(int,input().split())
grid=[["#"]*(w+2)]+[list("#"+input()+"#")for x in range(h)]+[["#"]*(w+2)]

stack=[]
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[y][x]=="#":
            grid[y][x]=0
            stack.append((y,x))

for i in range(h*w):
    tmp=[]
    for my,mx in stack:
        for y,x in ([0,1],[1,0],[-1,0],[0,-1]):
            if grid[my+y][mx+x]==".":
                grid[my+y][mx+x]=i+1
                tmp.append([my+y,mx+x])
    stack=tmp
print(max(max(i[1:-1])for i in grid[1:-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
H, W = map(int, input().split())
arr = [0]*H
for i in range(H):
    arr[i] = [j for j in input()]

a, b = np.where(np.array(arr)=='#')
abb = np.array([list(a), list(b)])
res = 0
x = np.array(range(H))
y = np.array(range(W))
xx, yy = np.meshgrid(x,y)
z = np.c_[xx.ravel(),yy.ravel()]

for zz in z:
  res1 = 3000
  res1 = min(np.amin(np.sum(abs(zz.reshape(2, -1) - abb), axis=0)), res1)
  res = max(res1, res)
        
print(res)

Submission status: Time Limit Exceeded

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

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = 1
        else:
            S[i][j] = 0

def change_S():
    T = [[S[i][j] for j in range(W)] for i in range(H)]
    for i in range(H):
        for j in range(W):
            if (S[i][j] == 1) and (S[i][j] == T[i][j]):
                for k in range(-1, 2):
                    ni = i + k
                    if (0 <= ni < H) and (S[ni][j] != 1):
                        S[ni][j] += 1
                for l in range(-1, 2):
                    nj = j + l
                    if (0 <= nj < W) and (S[i][nj] != 1):
                        S[i][nj] += 1
    return S

cnt = 0
list_of_ones = [[1 for j in range(W)] for i in range(H)]

while (S != list_of_ones):
    cnt += 1
    change_S()

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
x = input().split()
H = int(x[0])
W = int(x[1])
time = 0

Field = []
for i in range(0,H):
    al = list(input())
    Field.append(al)
#print(Field)

def change():
    num_list = []
    for h in range(0,H):
        for w in range(0,W):
            if Field[h][w] == '#':
                pass
            elif 0<= h-1 <= H-1 and Field[h-1][w] == '#':
                num_list.append([h,w])
            elif 0<= h+1 <= H-1 and Field[h+1][w] == '#':
                num_list.append([h,w])
            elif 0<= w-1 <= W-1 and Field[h][w-1] == '#':
                num_list.append([h,w])
            elif 0<= w+1 <= W-1 and Field[h][w+1] == '#':
                num_list.append([h,w])
            else:
                pass
    len(num_list)
    for k in range(0,len(num_list)):
        h = num_list[k][0]
        w = num_list[k][1]
        Field[h][w] = '#'
    #print(Field)

for h in range(0,H):
    for w in range(0,W):
        if Field[h][w] == '.':
            change()
            time = time + 1
        else:
            pass
print(time)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

acol = ["."]*(h+2)
acol[0] = ["."]*(w+2)
acol[h+1] = ["."]*(w+2)
arow = ["."]*(w)
count = 0
flag = 1

for i in range(h):
    ac = input()

    for j in range(w):
        arow[j] = ac[j]

    acol[i+1] = ["."] + arow + ["."]

while flag != 0:
    flag = 0
    acolaf = copy.deepcopy(acol)

    for i in range(h):

        for j in range(w):

            if acol[i+1][j+1] != "#":
                
                if acol[i+1][j] == "#" or acol[i][j+1] == "#" or acol[i+2][j+1] == "#" or acol[i+1][j+2] == "#":
                    acolaf[i+1][j+1] = "#"
                    flag += 1
        
    if flag > 0:
        count += 1
    
    acol = acolaf
            
print(count)

Submission status: Time Limit Exceeded

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


flag = False
count = 0
white = 1

while white > 0:
    for i in range(H):
        A[i] = list(''.join(A[i]).replace('.#', '*#').replace('#.', '#*'))
    ta = list(map(list, zip(*A)))

    for j in range(W):
        ta[j] = list(''.join(ta[j]).replace('.#', '*#').replace('#.', '#*'))
    ad = list(map(list, zip(*ta)))

    white = 0
    for i in range(H):
        ad[i] = ['#' if c == '*' else c for c in ad[i]]
        if '.' in ad[i]:
            white += 1

    if ad != A:
        count += 1
        A = ad

print(count)

Submission status: Time Limit Exceeded

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)


# print(A)

from itertools import product


# 開始地点
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            start.append((i, j))


def mahattan(sy, sx, ey, ex):
    return abs(sy - ey) + abs(sx - ex)


ans = 0
for i, j in product(range(H), range(W)):
    if A[i][j] == '.':
        tmp = 10000
        for ey, ex in start:
            tmp = min(tmp, mahattan(i, j, ey, ex))
        ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
INF=10**10
a=[[INF for i in range(w)] for j in range(h)]
ans=0
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            a[i][j]=0
            
for i in range(h):
    for j in range(w):
        k=a[i][j]+1

        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k
        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

for i in range(h):
    for j in range(w):
        k=a[-1-i][-1-j]+1
        if i!=h-1:
            if k<a[-i-2][-j-1]:
                a[-i-2][-j-1]=k

        if j!=w-1:        
            if k<a[-i-1][-j-2]:
                a[-i-1][-j-2]=k

for i in range(h):
    ans=max(ans,max(a[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int,input().split())
arr = np.zeros(shape=(H, W))
for i in range(H):
    A = input()
    for j in range(W):
        if A[j] == '#':
            arr[i, j] = 1

arr_temp = arr.copy()
cnt = 0
while True:
    if np.count_nonzero(arr) == H*W:
        break
    cnt += 1
    arr_u = np.delete(arr, obj=0, axis=0)
    arr_u = np.vstack((arr_u, np.zeros(shape=(1, W))))
    arr_d = np.delete(arr, obj=H-1, axis=0)
    arr_d = np.vstack((np.zeros(shape=(1, W)), arr_d))
    arr_l = np.delete(arr, obj=0, axis=1)
    arr_l = np.hstack((arr_l, np.zeros(shape=(H, 1))))
    arr_r = np.delete(arr, obj=W-1, axis=1)
    arr_r = np.hstack((np.zeros(shape=(H, 1)), arr_r))
    arr = arr + arr_u + arr_d + arr_l + arr_r

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W=(int(x) for x in input().split())
yoko=[input() for _ in range(H)]
map=[[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if yoko[h][w]=='#':
            map[h][w]=1
i=2
man=str(map)
maa=man.find("0")
if maa==-1:
    print(0)
else:
    while i<2010:
        for h in range(H):
            for w in range(W):
                if map[h][w]==i-1:
                    if h-1>=0:
                        if map[h-1][w]==0:
                            map[h-1][w]=i
                    if w-1>=0:
                        if map[h][w-1]==0:
                            map[h][w-1]=i
                    if h+1<H:
                        if map[h+1][w]==0:
                            map[h+1][w]=i
                    if w+1<W:
                        if map[h][w+1]==0:
                            map[h][w+1]=i
        an=str(map)
        anan=an.find("0")
        if anan==-1:
            print(i-1)
            break
        i=i+1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

row = [0 for x in range(w+2)]

field = [row for x in range(h+2)]

for y in range(1, h+1):
  row = input().replace("#","1").replace(".","0")
  row = [0] + list(row) + [0]
  row = list(map(int, row))
  field[y] = row

field = np.array(field)
field_back = field.copy()
cnt = 0

while True:
  if field[1:h+1,1:w+1].sum() == h * w:
    break
  arr_1 = field_back[1:h+1,0:w]
  arr_2 = field_back[1:h+1,2:w+2]
  arr_3 = field_back[0:h,1:w+1]
  arr_4 = field_back[2:h+2,1:w+1]
  field[1:h+1, 1:w+1] = arr_1 + arr_2 + arr_3 + arr_4 + field_back[1:h+1, 1:w+1]
  field = np.clip(field,0,1)
  cnt += 1
  field_back = field.copy()

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H, W = map(int, input().split())
    mass = [[0] * W for _ in range(H)]
    for Hi in range(H):
        massHi = [0 if s == '.' else 1 for s in list(input())]
        for Wi in range(W):
            mass[Hi][Wi] = massHi[Wi]

    # import pprint
    # pprint.pprint(mass)

    result = 0
    for Hi in range(H):
        for Wi in range(W):
            if mass[Hi][Wi] == 1:
                break
            sub_result = 100000000
            for Hi2 in range(H):
                for Wi2 in range(W):
                    if mass[Hi2][Wi2] == 1:
                        sub_result = min(sub_result,
                                         abs(Hi2 - Hi) + abs(Wi2 - Wi))
            result = max(result, sub_result)
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    dict_ = {'#': 1, '.': 0}
    h, w = map(int, (input().split()))
    num = []
    for hh in range(h):
        s = input()
        for ww in range(len(s)):
            if s[ww]=='#':
                num.append(ww + hh * h)
    numpre = []
    numnex = copy.deepcopy(num)

    count = 0
    while len(num) < h*w:
        count += 1
        temp = list(set(num) ^ set(numpre))
        for nn in temp:
            if (nn % w) != 0:
                numnex.append(nn - 1)
            if (nn % w) != w-1:
                numnex.append(nn + 1)
            if nn >= w:
                numnex.append(nn - w)
            if nn < h * w - w:
                numnex.append(nn + w)
        numnex = list(set(numnex))
        numpre = copy.deepcopy(num)
        num = copy.deepcopy(numnex)
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
h,w=map(int,input().split())
grid=[["#"]*(w+2)]+[list("#"+input()+"#")for x in range(h)]+[["#"]*(w+2)]

stack=[]
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[y][x]=="#":
            grid[y][x]=0
            heappush(stack,(y,x))

for i in range(h*w):
    tmp=[]
    for my,mx in stack:
        for y,x in ([0,1],[1,0],[-1,0],[0,-1]):
            if grid[my+y][mx+x]==".":
                grid[my+y][mx+x]=i+1
                #tmp.append([my+y,mx+x])
                heappush(tmp,(my+y,mx+x))
    if all(all(j!="." for j in i)for i in grid):
        print(max(max(i[1:-1])for i in grid[1:-1]))
        exit()
    stack=tmp

Submission status: Time Limit Exceeded

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

from collections import deque

def bfs(ii, jj):
    Q = deque()
    visited = [[False for _ in range(W)] for _ in range(H)]

    Q.append((ii, jj, 0))
    while len(Q) > 0:
        i, j, dist = Q.popleft()
        visited[i][j] = True
        if A[i][j] == "#":
            return dist

        for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj]:
                Q.append((ni, nj, dist + 1))

ma = 0
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        ma = max(ma, bfs(i, j))
print(ma)