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,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
for i in range(2000):
  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])
  if b==[]:break
  f+=1
  a=b[:]
print(f-1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a_list = [list(input()) for _ in range(h)]
dis = []
black_list = []
for i in range(h):
    for j in range(w):
        if a_list[i][j]=='#':
            black_list.append([i,j])

for i in range(h):
    for j in range(w):
        max_dis = 10**6
        for x,y in black_list:
            max_dis = min(max_dis,abs(x-i)+abs(y-j))
        dis.append(max_dis)
print(max(dis))

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()))
B = copy.deepcopy(A)
x = 0
while A.count(list('#' * w)) < h:
	for i in range(h):
		for k in range(w):
			if A[i][k] == '#' and i != 0:
				B[i - 1][k] = '#'
			if A[i][k] == '#' and i != h - 1:
				B[i + 1][k] = '#'
			if A[i][k] == '#' and k != 0:
				B[i][k - 1] = '#'
			if A[i][k] == '#' and k != w - 1:
				B[i][k + 1] = '#'
	x += 1
	A = copy.deepcopy(B)
print(x)

Submission status: Time Limit Exceeded

Solution code:

def main():
    h, w = map(int, input().rstrip().split(' '))
    a = [None] * h
    b = set()
    whites = set()
    for i in range(h):
        a[i] = [None] * w
        for j, c in enumerate(input().rstrip()):
            if c == '#':
                a[i][j] = True
                b.add((i, j))
            else:
                a[i][j] = False
                whites.add((i, j))
    
    max_dist = 0

    while len(whites) > 0:
        i, j = whites.pop()
        min_dist = 1000000
        min_dist_black = None
        for black in b:
            p, q = black
            d = abs(p - i) + abs(q - j)
            if d < min_dist:
                min_dist = d
                min_dist_black = black
        # tweak to remove non farthest whites
        # for w0 in range(min(i, min_dist_black[0]), max(i, min_dist_black[0]) + 1):
        #     for w1 in range(min(j, min_dist_black[1]), max(j, min_dist_black[1]) + 1):
        #         if (w0, w1) in whites:
        #             whites.remove((w0, w1))
        if max_dist < min_dist:
            max_dist = min_dist
    
    print(max_dist)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = [int(i) for i in input().split()]
c = np.full((h, w), 10000)
# c = [[float("inf") for _ in range(w)] for _ in range(h)]
for i in range(h):
    _a = input()
    for j in range(w):
        if _a[j] == "#":
            c[i, j] = 0


for i in range(h):
    for j in range(1, w):
        c[i, j] = min(c[i, j], c[i, j - 1] + 1)


for i in range(1, h):
    for j in range(w):
        c[i, j] = min(c[i, j], c[i - 1, j] + 1)


for i in range(h):
    for j in reversed(range(w - 1)):
        # if c[i][j + 1] != -1:
        c[i, j] = min(c[i, j], c[i, j + 1] + 1)


_max = 0
for i in reversed(range(h - 1)):
    for j in range(w):
        # if c[i+1][j] != -1:
        tmp = min(c[i, j], c[i + 1, j] + 1)
        c[i, j] = tmp
        _max = max(_max, tmp)
print(int(max(_max, c[-1].max())))

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(i) for i in input().split()]
c = [[float("inf") for _ in range(w)] for _ in range(h)]
for i in range(h):
    _a = input()
    for j in range(w):
        if _a[j] == "#":
            c[i][j] = 0

def right():
    for i in range(h):
        for j in range(1, w):
            c[i][j] = min(c[i][j], c[i][j-1]+1)

def down():
    for i in range(1, h):
        for j in range(w):
            c[i][j] = min(c[i][j], c[i - 1][j]+1)

def left():
    for i in range(h):
        for j in reversed(range(w-1)):
            # if c[i][j + 1] != -1:
            c[i][j] = min(c[i][j], c[i][j+1]+1)
def up():
    _max = 0
    for i in reversed(range(h-1)):
        for j in range(w):
            # if c[i+1][j] != -1:
            tmp = min(c[i][j], c[i + 1][j]+1)
            c[i][j] = tmp
            _max = max(_max, tmp)
    _max = max(_max, max(c[-1]))
    return _max
right()
left()
down()
print(up())
# _max = 0
# for i in range(len(c)):
    # print(c[i])
    # _max = max(_max, max(c[i]))
# print(_max)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
#input = sys.stdin.readline
h, w = map(int,input().split())
grid = np.array([list(input()) for _ in range(h)])

large_grid = np.array([["." for _ in range(w+2)] for _ in range(h+2)])
goal_grid = [["#" for _ in range(w)] for _ in range(h)]
cnt = 0

for i in range(1000):
    if (grid == goal_grid).all():
        print(cnt)
        break
    for row in range(h):
        for col in range(w):
            if grid[row][col] == "#":
                large_grid[row][col+1] = "#"
                large_grid[row+2][col+1] = "#"
                large_grid[row+1][col+1] = "#"
                large_grid[row+1][col+2] = "#"
                large_grid[row+1][col] = "#"

    grid3 = large_grid[1:h+1, 1:w+1]
    #grid = grid3#参照元とかの問題でバグる
    grid = np.copy(grid3)
    cnt +=1

#     grid = grid2
#     print(grid2)
#     print(grid)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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

grid = [list(input()) for _ in range(h)]
black = set()
targets = set()
count = 0

for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            black.add((i, j))

def get_arounds(t, h, w):
    arounds = {(t[0] - 1, t[1]),
               (t[0] + 1, t[1]),
               (t[0], t[1] - 1),
               (t[0], t[1] + 1)}
    return set(filter(lambda x: 0 <= x[0] < h and 0 <= x[1] < w, arounds))

targets = black
while len(black) < h * w:
    count += 1
    n_targets = reduce(lambda acc, x: acc | get_arounds(x, h, w), targets, set())
    targets = n_targets - (n_targets & black)
    black |= targets

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

def is_complete(boad):
    for col in boad:
        if ['.'] in col:
            return False
    return True

def change_cell(cell):
    if cell == ['#']:
        return ['#']
    return ['#']

def change_around_cells(boad, h, w, x, y):
    # 5を中心とした座標の辞書
    index_dic = {1:(-1, 0), 2:(0, -1), 3:(0, 1), 4:(1, 0)}
    # 一番左の列に中心
    if x - 1 < 0:
        index_dic.pop(1)

    # 一番右の列に中心
    if x + 1 >= w:
        index_dic.pop(4)

    # 一番上の行に中心
    if y - 1 < 0:
        index_dic.pop(2)

    # 一番下の行に中心
    if y + 1 >= h:
        index_dic.pop(3)

    for key in index_dic.keys():
        i, j = index_dic[key]
        boad[y + j][x + i] = change_cell(boad[y + j][x + i])


    return boad


def main():
    #マス目入力
    input_data = input().split()
    h, w = (int(i) for i in input_data)
    # print(h,w)
    #盤面入力
    boad = []
    for i in range(h):
        boad.append(list(list(i) for i in input()))
    # print(boad)

    new_boad = copy.deepcopy(boad)

    cnt = 0
    complete_flag = is_complete(boad)
    while(not complete_flag):
        cnt += 1
        for y, col in enumerate(boad):
            if ['#'] in col:
                for x, cell in enumerate(col):
                    if cell == ['#']:
                        new_boad = change_around_cells(new_boad, h, w, x, y)
                        complete_flag = is_complete(new_boad)
                        if complete_flag:
                            break
                    if ['#'] not in col[x:]:
                        break
            if complete_flag:
                break
        boad = copy.deepcopy(new_boad)
        # for b in new_boad:
        #     print(b)
        # print("++++++++")
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

h, w  = map(int,input().split())
grid = [0]*h
for i in range(h):
    grid[i] = list(input())



memo = [[0]*(w+2) for j in range(h+2)]


#メモの初期化
for i in range(h+2):
    for j in range(w+2):
        memo[i][j] = 0

for i in range(h):
    for j in range(w):
        if grid[i][j] == '.':
            memo[i+1][j+1] = 0
        else:
            memo[i+1][j+1] = 1

another = copy.deepcopy(memo)

count = 0
while 1:
    f = 0
    
    for i in range(1,h+1):
        for j in range(1,w+1):
            if memo[i][j] == 0:
                f = 1
                another[i][j] = memo[i-1][j] or memo[i+1][j] or memo[i][j-1] or memo[i][j+1]

    memo = copy.deepcopy(another)
    

    if f == 0:
        break
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def dark(i,j):
    h = len(mas)
    w = len(mas[0])
    x = 0
    if i != h-1:
        if not[i+1,j] in dk:
            dk.append([i+1,j])
            x += 1
    if i != 0:
        if not[i-1,j] in dk:
            dk.append([i-1,j])
            x += 1
    if j != w-1:
        if not[i,j+1] in dk:
            dk.append([i,j+1])
            x += 1
    if j != 0:
        if not[i,j-1] in dk:
            dk.append([i,j-1])
            x += 1
    return x

h,w = map(int,input().split())
mas = [[0 for i in range(w)] for j in range(h)]
dk = []
for i in range(h):
    tmp = list(input())
    for j in range(w):
        if tmp[j] == "#":
            dk.append([i,j])
        mas[i][j] = tmp[j]

#print(dk)
res = 0
oldl = 0
l = len(dk)
while l < w*h:
    t = len(dk)
    for i in range(oldl,t):
        l += dark(dk[i][0],dk[i][1])
    oldl = t
    
    #pprint.pprint(mas)
    res += 1
    #print(len(dk))
print(res)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
A = [list(input()) for i in range(h)]
A_check = [(i,j) for i in range(h) for j in range(w)]
  
ans = 0
while 1:
  continue_flag = False
  A_tmp = [A[i].copy() for i in range(h)]
  for i, j in A_check:
    if A[i][j]=='#':
      i_s = max(0,i-1)
      i_l = min(h-1,i+1)
      j_s = max(0,j-1)
      j_l = min(w-1,j+1)
      A_tmp[i_s][j]='#'
      A_tmp[i_l][j]='#'
      A_tmp[i][j_s]='#'
      A_tmp[i][j_l]='#'
      A_check.remove((i,j))
    else:
      # 1つでも#以外があれば、操作回数に1を足してループを継続する
      continue_flag = True
  if continue_flag==False:
    break
  ans+=1
  A = A_tmp
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
a = list(map(int, input().split()))
b = [[c for c in input()] for r in range(a[0])]
s = []

def d(i, j, x, y):
    return (x - j) ** 2 + (y - i) ** 2

for i in range(a[0]):
    for j in range(a[1]):
        if b[i][j] == '#':
            s.append([i, j])

d_max = 0
diag = d(0, 0, a[1], a[0])

for i in range(a[0]):
    for j in range(a[1]):
        if b[i][j] == '.':
            d_min = diag
            for p in s:
                d_min = min(d_min, d(i, j, p[1], p[0]))
            d_max = max(d_max, d_min)

print(math.ceil(math.sqrt(d_max)))

Submission status: Time Limit Exceeded

Solution code:
import copy
h, w = [int(x) for x in input().split()]

f = [[1 for x in range(w+2)]]
check = []
muki = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1]
]
for i in range(h):
  s = input()
  for index, x in enumerate(s):
    if x == "#":
      check.append([i+1, index+1])
  f.append([1]+[0 if x == "." else 1 for x in s]+[1])
f.append([1 for x in range(w+2)])

ans = 0
while(True):
  cc = []
  for m in check:
    for x in muki:
      if f[m[0]+x[0]][m[1]+x[1]] == 0:
        f[m[0]+x[0]][m[1]+x[1]] = 1
        cc.append([m[0]+x[0], m[1]+x[1]])
  
  


  if cc == []:
   	break
  check = copy.deepcopy(cc)
  ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
l = []
l2 = []
a = [input() for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            l.append((i,j))
        else:
            l2.append((i,j))
answer = 0
while len(l2):
    if answer == 5:
        break
    b = []
    answer += 1
    for i, j in l2:
        for x, y in l:
            d = abs(i-x)+abs(j-y)
            if d == answer:
                b.append((i,j))
    b = set(b)
    for z in b:
        l2.remove(z)
                

print(answer)

Submission status: Time Limit Exceeded

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

for i in range(H):
  a = list(input())
  for j in range(W):
    if (a[j] == '#'):
      black.append([i, j])
    else:
      white.append([i, j])


if (len(white) == 0):
  print(0)
  exit()

ans = 0

for w in white:
  m = 10 ** 6
  for b in black:
    m = min(m, abs(b[0] - w[0]) + abs(b[1] - w[1]))
  ans = max(ans, m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = list(map(int,input().split()))
a = list()
b = [[5000]*w for i in range(0,h)]
c = list()
now = 1
count = 0
for i in range(0,h):
    a.append(list(input()))
for i in range(0,h):
    for j in range(0,w):
        if a[i][j] == "#":
            b[i][j] = 1
            c.append([i,j])
     
while(True):
    if c == []:
        break
    d = list()
    now += 1
    for i in c:
        if i[1]+1 < w:
            if b[i[0]][i[1]+1] > now:
                b[i[0]][i[1]+1] =now
                d.append([i[0],i[1]+1])
        if i[1] > 0:
            if b[i[0]][i[1]-1] > now:
                b[i[0]][i[1]-1] =now
                d.append([i[0],i[1]-1])
        if i[0]+1 < h:
            if b[i[0]+1][i[1]] > now:
                b[i[0]+1][i[1]] =now
                d.append([i[0]+1,i[1]])
        if i[0] > 0:
            if b[i[0]-1][i[1]] > now:
                b[i[0]-1][i[1]] =now
                d.append([i[0]-1,i[1]])
    c = d
print(now-2)

Submission status: Time Limit Exceeded

Solution code:
import queue

h,w=map(int, input().split())
a=[list(list(input())) for i in range(h)]
q = queue.Queue()
ans=0

for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            for dy, dx in ([0, -1], [-1, 0], [0, 1], [1, 0]):
                ny=i+dy
                nx=j+dx
                if ny<0 or ny>=h or nx<0 or nx>=w:
                    continue
                if a[ny][nx]=='.':
                    q.put((ny,nx))
while not q.empty():
    ans+=1
    l=set()
    while not q.empty():
        l.add(q.get())
    for e in l:
        a[e[0]][e[1]]='#'
        for dy, dx in ([0, -1], [-1, 0], [0, 1], [1, 0]):
            ny=e[0]+dy
            nx=e[1]+dx
            if ny<0 or ny>=h or nx<0 or nx>=w:
                continue
            if a[ny][nx]=='.':
                q.put((ny,nx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/agc033/tasks/agc033_a

HW = [int(i) for i in input().split()]
A = []
for i in range(HW[0]):
    A.append(list(str(input())))

B = []
for i in range(len(A)):
    B.append([])
    for j in range(len(A[i])):
        B[i].append(A[i][j])

count = 0
count2 = 0
flag = False
tmp = ['.'] * len(A[0])
while True:
    for i in range(len(A)):
        if i > 0:
            tmp = A[i-1]
        j = 0
        while True:
            if A[i][j] == '.':
                if flag == True:
                    B[i][j] = '#'
                    flag = False
                    j += 1
                else:
                    if tmp[j] == '#':
                        B[i][j] = '#'
                        j += 1
                    elif i < len(A) - 1 and A[i+1][j] == '#':
                        B[i][j] = '#'
                        j += 1
                    elif j < len(A[i]) - 1 and A[i][j+1] == '#':
                        B[i][j] = '#'
                        j += 2
                        count += 1
                        flag = True
                    else:
                        j += 1
            else:
                count += 1
                flag = True
                j += 1
            
            if j >= len(A[i]):
                break
    
    for i in range(len(A)):
        for j in range(len(A[i])):
            A[i][j] = B[i][j]
    if count == HW[0] * HW[1]:
        break
    else:
        count = 0
        count2 += 1

print(count2)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
m = ['X' + input() + 'X' for i in range(H)]
m.insert(0, 'X' * (W+2))
m.insert(H+1, 'X' * (W+2))

cnt = 0
while(True):
  flag = True
  mm = [['X' for i in range(W+2)] for j in range(H+2)]
  for i in range(1, 1+H):
    for j in range(1, 1+W):
      if m[i][j] == '.':
        if m[i+1][j] == '#' or m[i-1][j] == '#' or m[i][j+1] == '#' or m[i][j-1] == '#':
          mm[i][j] = '#'
        else:
          mm[i][j] = '.'
        if flag:
          flag = False
      elif m[i][j] == '#':
        mm[i][j] = '#'
  cnt += 1
  m = mm.copy()
  if flag:
    break

print(cnt-1)

Submission status: Time Limit Exceeded

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

lists = []
cnt = 0
mozi = ""
size = h * w
kaiseki = []

for i in range(h):
    s = input()
    mozi += s

lists = list(mozi)

while True:
    result = set(lists)
    if len(result) == 1:
        break
    check = 0
    for i in range(size):
        if lists[i] == "#":
            kaiseki.append(i)
            check += 1
    cnt += 1
    for i in range(check):
        if int(kaiseki[i]) - w >= 0:
            lists[int(kaiseki[i]) - w] = "#"
        if int(kaiseki[i]) + w <= size - 1:
            lists[int(kaiseki[i]) + w] = "#"
        amari = int(kaiseki[i]) % w
        if amari != 0:
            lists[int(kaiseki[i]) - 1] = "#"
        if amari != w-1:
            lists[int(kaiseki[i]) + 1] = "#"
    kaiseki.clear()


print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0

for t in range(1000):
    check_t = 0
    change = []
    for i in range(h):
        for j in range(w):
            check_s = 0
            if a[i][j] == ".":
                check_t = 1
                if not i == 0:
                    if a[i - 1][j] == "#":
                        check_s = 1
                if not i == h - 1:
                    if a[i + 1][j] == "#":
                        check_s = 1
                if not j == 0:
                    if a[i][j - 1] == "#":
                        check_s = 1
                if not j == w - 1:
                    if a[i][j + 1] == "#":
                        check_s = 1
            if check_s == 1:
                change.append([i, j])
    for x in change:
        a[x[0]][x[1]] = "#"
    if check_t == 0:
        ans = t
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
h,w = map(int,input().split())
a = []
for i in range(h+2):
  a.append([2] * (w+2))
d = 0
for i in range(h):
  b = input()
  c = 0
  for k in b:
    if k == '.':
      a[i+1][c+1] = 0
      d += 1
    else:
      a[i+1][c+1] = 1
    c += 1
count = 0
while d != 0:
  count += 1
  d = 0
  b = copy.deepcopy(a)
  for i in range(h):
    for k in range(w):
      if a[i+1][k+1] == 0:
        if b[i][k+1] == 1 or b[i+2][k+1] == 1 or b[i+1][k] == 1 or b[i+1][k+2] == 1:
          a[i+1][k+1] = 1
        else:
          d += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import os
import copy
from math import *

nums = []
for i in list(input().split()):
  nums.append(int(i))

#print(nums)

fields = []
for i in range(nums[0]):
	n = []
	words = list(input())
	for j in range(nums[1]):
		if words[j] == '#':
			n.append(1)
		else:
			n.append(0)
	fields.append(n)

#print(fields)

count = 0
while True:
	changed = 0
	c_field = copy.deepcopy(fields)
	for i in range(nums[0]):
		for j in range(nums[1]):
			if fields[i][j] == 1:
				if 0 < i:
					if fields[i-1][j] == 0:
						c_field[i-1][j] = 1
						changed = 1

				if i < nums[0]-1:
					if fields[i+1][j] == 0:
						c_field[i+1][j] = 1
						changed = 1

				if 0 < j:
					if fields[i][j-1] == 0:
						c_field[i][j-1] = 1
						changed = 1

				if j < nums[1]-1:
					if fields[i][j+1] == 0:
						c_field[i][j+1] = 1
						changed = 1

	#print(fields, c_field)

	fields = c_field[:]

	if changed:
		count = count + 1
	else:
		break

print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N = [int(x) for x in stdin.readline().rstrip().split()]
Input = [list(stdin.readline().rstrip()) for _ in range(N[0])]


Room = [[1 for j in range(N[1] + 2)] for i in range(N[0] + 2)]
Room_next = [[1 for j in range(N[1] + 2)] for i in range(N[0] + 2)]
count = 0


def is_darkroom(array):
    p = True
    for i in range(1, N[0] + 1):
        for j in range(1, N[1] + 1):
            if array[i][j] == 1:
                p = False
    return p

for i in range(N[0] + 2):
    for j in range(N[1] + 2):
        if i == 0 or i == N[0] + 1 or j == 0 or j == N[1] + 1:
            Room[i][j] = 1
        else:
            Room[i][j] = 1 if Input[i-1][j-1] == "." else 0

for k in range(N[0] + N[1] + 2):
    if k % 2 == 0:
        if is_darkroom(Room):
            count = k
            break
        for i in range(1, N[0] + 1):
            for j in range(1, N[1] + 1):
                Room_next[i][j] = Room[i][j] * Room[i - 1][j] * Room[i + 1][j] * Room[i][j - 1] * Room[i][j + 1]

        Room = [[1 for j in range(N[1] + 2)] for i in range(N[0] + 2)]
    else:
        if is_darkroom(Room_next):
            count = k
            break
        for i in range(1, N[0] + 1):
            for j in range(1, N[1] + 1):
                Room[i][j] = Room_next[i][j] * Room_next[i - 1][j] * Room_next[i + 1][j] * Room_next[i][j - 1] * Room_next[i][j + 1]

        Room_next = [[1 for j in range(N[1] + 2)] for i in range(N[0] + 2)]       

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:
        for r, c in list(S):
            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:
ms = input()

h = int(ms.split()[0])
w = int(ms.split()[1])

mass_list = list([[int(9)]*(w+2)])
for row in range(h):
  wb = input()
  lst = [int(0)]*w
  lst.append(int(9))
  lst.insert(0, int(9))
  for column in range(w):
    w_or_b = wb[column]
    if w_or_b == "#":
      lst[column] = int(1)
  mass_list.append(lst)
mass_list.append(list([int(9)]*(w+2)))
print(mass_list)
count = 0
while True:
  end = 0
  count += 1
  for r in range(1, h+1):
    for c in range(1, w+1):
      if mass_list[r][c] == 0:
        while True:
          if mass_list[r+1][c] == 1:
            mass_list[r][c] = 1
            break
          if mass_list[r-1][c] == 1:
            mass_list[r][c] = 1
            break
          if mass_list[r][c+1] == 1:
            mass_list[r][c] = 1
            break
          if mass_list[r][c-1] == 1:
            mass_list[r][c] = 1
            break
      else:
        end +=1
  if end == h + w:
    break
print(count)

Submission status: Time Limit Exceeded

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

white = []
black = []

length = sum([a.count(".") for a in A])
cnt = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
        else:
            white.append([i,j])

while (length > 0):
    gray = []
       
    for l in black:
        c1 = [l[0],l[1]-1]
        if c1 in white and c1 not in gray:
            gray.append(c1)
        c2 = [l[0],l[1]+1]
        if c2 in white and c2 not in gray:
            gray.append(c2)
        c3 = [l[0]-1,l[1]]
        if c3 in white and c3 not in gray:
            gray.append(c3)
        c4 = [l[0]+1,l[1]]
        if c4 in white and c4 not in gray:
            gray.append(c4)
    
    for l in gray:
        black.append(l)
        white.remove(l)
        
    cnt += 1
    length = len(white)
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#N = int(input())
#A = [int(x) for x in input().split()]
#a, b, c = map(int, input().split())
#name1 = str(input())
#alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
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] == 0.:
                if i - 1 >= 0 and A[i - 1, j] == 1:
                    C[i, j] = 1.
                elif i + 1 < h and A[i + 1, j] == 1:
                    C[i, j] = 1.
                elif j - 1 >= 0 and A[i, j - 1] == 1:
                    C[i, j] = 1.
                elif j + 1 < w and A[i, j + 1] == 1:
                    C[i, j + 1] = 1.
    A[np.logical_or(A, C)] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):
    tmp=input()
    tmp2=[]
    for j in tmp:
        if j=='.':
            a.append(0)
        else:
            a.append(1)
b=[i for i, x in enumerate(a) if x == 1]
import copy
c=b.copy()
d=[]
count=0
while len(b)<h*w:
    count=count+1
    for i in b:
        if i%h!=h-1:
            c.append(i+1)
        if i%h!=0:
            c.append(i-1)
        if i>=h:
            c.append(i-h)
        if i+h<h*w:
            c.append(i+h)
    b=set(c).copy()
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

def is_complete(boad):
    for col in boad:
        if ['.'] in col:
            return False
    return True

def change_cell(cell):
    if cell == ['#']:
        return ['#']
    return ['#']

def change_around_cells(boad, h, w, x, y):
    # 5を中心とした座標の辞書
    index_dic = {1:(-1, 0), 2:(0, -1), 3:(0, 1), 4:(1, 0)}
    # 一番左の列に中心
    if x - 1 < 0:
        index_dic.pop(1)

    # 一番右の列に中心
    if x + 1 >= w:
        index_dic.pop(4)

    # 一番上の行に中心
    if y - 1 < 0:
        index_dic.pop(2)

    # 一番下の行に中心
    if y + 1 >= h:
        index_dic.pop(3)

    for key in index_dic.keys():
        i, j = index_dic[key]
        boad[y + j][x + i] = change_cell(boad[y + j][x + i])


    return boad


def main():
    #マス目入力
    input_data = input().split()
    h, w = (int(i) for i in input_data)
    # print(h,w)
    #盤面入力
    boad = []
    for i in range(h):
        boad.append(list(list(i) for i in input()))
    # print(boad)

    new_boad = copy.deepcopy(boad)

    cnt = 0
    complete_flag = is_complete(boad)
    while(not complete_flag):
        cnt += 1
        for y, col in enumerate(boad):
            for x, cell in enumerate(col):
                if cell == ['#']:
                    new_boad = change_around_cells(new_boad, h, w, x, y)
                    complete_flag = is_complete(new_boad)
                    if complete_flag:
                        break
            if complete_flag:
                break
        boad = copy.deepcopy(new_boad)
        # for b in new_boad:
        #     print(b)
        # print("++++++++")
    print(cnt)


if __name__ == '__main__':
    main()