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 copy
h,w = map(int,input().split())

#aij = [input() for i in range(h)]

moji = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    aij = input()
    #print(aij)
    for j in range(w):
        moji[i][j] = aij[j]

#moji = aij
#print(moji,aij)
#exit()

#print(aij)
vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0
flag = False

while flag == False:
    #print(moji)
    moji_old = copy.deepcopy(moji)
    for i in range(h*w):
        y = i//w
        x = i%w
        if moji_old[y][x] == '.':
            flag = False
            break
        else:
            flag = True
    
    for i in range(h*w):
        y = i//w
        x = i%w
        #print(i)
        if moji_old[y][x] == '#':
            for j in range(4):
                nx = x+vx[j]
                ny = y+vy[j]
                #print(ny,nx)
                if nx < 0 or nx >= w or ny < 0 or ny >= h:
                    continue
                moji[ny][nx] = '#'
    
    if flag == True:
        break
                
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#import collections
#from math import gcd 旧環境でこれを有効化するとREを吐きます
import sys
input = sys.stdin.readline


def main():
    s = input().split()
    p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
    H = p[0]
    W = p[1]

    queue = []
    #input = sys.stdin.readline
    A = [list(input()) for _ in range(H)]
    #print('A:{}'.format(A))
    c = [['w'] * (W+2)]
    #print('c:{}'.format(c))
    for i in range(H):
        c.append(['w'])
        for j in range(W):
            if(A[i][j] == '#'):
                queue.append([i+1, j+1])
            c[-1].append(A[i][j])
        c[-1].append('w')
    c.append(['w'] * (W+2))
    #print('c:{}'.format(c))
    #print('queue:{}'.format(queue))

    '''
    a = []
    for i in range(H):
        a.append(input())


    #白ベースで最寄りの黒を探す方針
    #パディングは'.'でも'#'でもないもので埋める
    b = ''
    for i in range(W+2):
        b += 'w'
    #print(b)
    #上と下と右と左に空きマスを挿入する
    a.insert(0, b)
    for i in range(1, 1+H):
        a[i] = 'w' + a[i] + 'w'
    a.append(b)


    header = ' '
    for i in range(len(a[0])):
        header += ('{}'.format(i))

    c=[]
    for i in range(H+2):
        c.append([])
    queue = []
    for i in range(H+2):
        for j in range(W+2):
            if(a[i][j] == '#'):
                queue.append([i, j])
            c[i].append(a[i][j])


    def see_banmen():
        print(header)
        for i in range(len(c)):
            print('{}{}'.format(i,''.join(c[i])))
    #see_banmen()
    '''


    #queue = [start]
    next_list = [] #次の歩数で探すものを格納しておく
    step = 1
    #mode = 0
    #answer_mode = 0
    status = True #ゴール判定でゴールについていたらFalseにする
    #answer = -1




    '''
    for i in range(H+2):
        for j in range(W+2):
            if(c[i][j] == '#'):
                queue.append([i, j])
    '''
    while status:
        if(len(queue) > 0):
            pivot = queue.pop(0) #軸足はqueueの先頭
            x = pivot[0]
            y = pivot[1]
            if(c[x+1][y] == '.'):
                c[x+1][y] = str(step)
                next_list.append([x+1, y])
            if(c[x-1][y] == '.'):
                c[x-1][y] = str(step)
                next_list.append([x-1, y])
            if(c[x][y+1] == '.'):
                c[x][y+1] = str(step)
                next_list.append([x, y+1])
            if(c[x][y-1] == '.'):
                c[x][y-1] = str(step)
                next_list.append([x, y-1])
        else:
            #queueの中身が空っぽになった
            #基本的にはstep += 1
            if(len(next_list) > 0):
                #next_listの中身がある場合（まだ探索が終了していない場合）
                #next_list -> queue にして next_listはからにする
                '''
                for i in range(len(next_list)):
                    queue.append(next_list.pop(0))
                next_list = []
                '''
                queue = next_list
                next_list = []
                

                #print()
                #print('step{}end'.format(step))
                #see_banmen()
                #次の探索に移る
                step += 1
            else:
                #初めてnext_listの中身がなくなった場合（探索は終了したい）
                #もう進めない
                #print()
                #print('もう進めない')
                #print('step{}end'.format(step))
                #see_banmen()
                status = False

    print(step - 1)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
import collections
#from math import gcd 旧環境でこれを有効化するとREを吐きます


def main():
    s = input().split()
    p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
    H = p[0]
    W = p[1]

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


    #白ベースで最寄りの黒を探す方針
    #パディングは'.'でも'#'でもないもので埋める
    b = ''
    for i in range(W+2):
        b += 'w'
    #print(b)
    #上と下と右と左に空きマスを挿入する
    a.insert(0, b)
    for i in range(1, 1+H):
        a[i] = 'w' + a[i] + 'w'
    a.append(b)


    header = ' '
    for i in range(len(a[0])):
        header += ('{}'.format(i))

    c=[]
    for i in range(H+2):
        c.append([])
    queue = []
    for i in range(H+2):
        for j in range(W+2):
            if(a[i][j] == '#'):
                queue.append([i, j])
            c[i].append(a[i][j])


    def see_banmen():
        print(header)
        for i in range(len(c)):
            print('{}{}'.format(i,''.join(c[i])))
    #see_banmen()



    #queue = [start]
    next_list = [] #次の歩数で探すものを格納しておく
    step = 1
    #mode = 0
    #answer_mode = 0
    status = True #ゴール判定でゴールについていたらFalseにする
    #answer = -1

    #queue = []
    '''
    for i in range(H+2):
        for j in range(W+2):
            if(c[i][j] == '#'):
                queue.append([i, j])
    '''
    while status:
        if(len(queue) > 0):
            pivot = queue.pop() #軸足はqueueの先頭
            x = pivot[0]
            y = pivot[1]
            if(c[x+1][y] == '.'):
                c[x+1][y] = str(step)
                next_list.append([x+1, y])
            if(c[x-1][y] == '.'):
                c[x-1][y] = str(step)
                next_list.append([x-1, y])
            if(c[x][y+1] == '.'):
                c[x][y+1] = str(step)
                next_list.append([x, y+1])
            if(c[x][y-1] == '.'):
                c[x][y-1] = str(step)
                next_list.append([x, y-1])
        else:
            #queueの中身が空っぽになった
            #基本的にはstep += 1
            if(len(next_list) > 0):
                #next_listの中身がある場合（まだ探索が終了していない場合）
                #next_list -> queue にして next_listはからにする
                '''
                for i in range(len(next_list)):
                    queue.append(next_list.pop(0))
                next_list = []
                '''
                queue = next_list
                next_list = []
                

                #print()
                #print('step{}end'.format(step))
                #see_banmen()
                #次の探索に移る
                step += 1
            else:
                #初めてnext_listの中身がなくなった場合（探索は終了したい）
                #もう進めない
                #print()
                #print('もう進めない')
                #print('step{}end'.format(step))
                #see_banmen()
                status = False

    print(step - 1)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#from math import gcd 旧環境でこれを有効化するとREを吐きます


def main():
    s = input().split()
    p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
    H = p[0]
    W = p[1]

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


    #白ベースで最寄りの黒を探す方針
    #パディングは'.'でも'#'でもないもので埋める
    b = ''
    for i in range(W+2):
        b += 'w'
    #print(b)
    #上と下と右と左に空きマスを挿入する
    a.insert(0, b)
    for i in range(1, 1+H):
        a[i] = 'w' + a[i] + 'w'
    a.append(b)


    header = ' '
    for i in range(len(a[0])):
        header += ('{}'.format(i))

    c=[]
    for i in range(H+2):
        c.append([])
    queue = []
    for i in range(H+2):
        for j in range(W+2):
            if(a[i][j] == '#'):
                queue.append([i, j])
            c[i].append(a[i][j])


    def see_banmen():
        print(header)
        for i in range(len(c)):
            print('{}{}'.format(i,''.join(c[i])))
    #see_banmen()



    #queue = [start]
    next_list = [] #次の歩数で探すものを格納しておく
    step = 1
    #mode = 0
    #answer_mode = 0
    status = True #ゴール判定でゴールについていたらFalseにする
    #answer = -1

    #queue = []
    '''
    for i in range(H+2):
        for j in range(W+2):
            if(c[i][j] == '#'):
                queue.append([i, j])
    '''
    while status:
        if(len(queue) > 0):
            pivot = queue.pop(0) #軸足はqueueの先頭
            x = pivot[0]
            y = pivot[1]
            if(c[x+1][y] == '.'):
                c[x+1][y] = str(step)
                next_list.append([x+1, y])
            if(c[x-1][y] == '.'):
                c[x-1][y] = str(step)
                next_list.append([x-1, y])
            if(c[x][y+1] == '.'):
                c[x][y+1] = str(step)
                next_list.append([x, y+1])
            if(c[x][y-1] == '.'):
                c[x][y-1] = str(step)
                next_list.append([x, y-1])
        else:
            #queueの中身が空っぽになった
            #基本的にはstep += 1
            if(len(next_list) > 0):
                #next_listの中身がある場合（まだ探索が終了していない場合）
                #next_list -> queue にして next_listはからにする
                '''
                for i in range(len(next_list)):
                    queue.append(next_list.pop(0))
                next_list = []
                '''
                queue = next_list
                next_list = []
                

                #print()
                #print('step{}end'.format(step))
                #see_banmen()
                #次の探索に移る
                step += 1
            else:
                #初めてnext_listの中身がなくなった場合（探索は終了したい）
                #もう進めない
                #print()
                #print('もう進めない')
                #print('step{}end'.format(step))
                #see_banmen()
                status = False

    print(step - 1)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#from math import gcd 旧環境でこれを有効化するとREを吐きます


def main():
    s = input().split()
    p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
    H = p[0]
    W = p[1]

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


    #白ベースで最寄りの黒を探す方針
    #パディングは'.'でも'#'でもないもので埋める
    b = ''
    for i in range(W+2):
        b += 'w'
    #print(b)
    #上と下と右と左に空きマスを挿入する
    a.insert(0, b)
    for i in range(1, 1+H):
        a[i] = 'w' + a[i] + 'w'
    a.append(b)


    header = ' '
    for i in range(len(a[0])):
        header += ('{}'.format(i))

    c=[]
    for i in range(H+2):
        c.append([])
    queue = []
    for i in range(H+2):
        for j in range(W+2):
            if(a[i][j] == '#'):
                queue.append([i, j])
            c[i].append(a[i][j])


    def see_banmen():
        print(header)
        for i in range(len(c)):
            print('{}{}'.format(i,''.join(c[i])))
    #see_banmen()



    #queue = [start]
    next_list = [] #次の歩数で探すものを格納しておく
    step = 1
    #mode = 0
    #answer_mode = 0
    status = True #ゴール判定でゴールについていたらFalseにする
    #answer = -1

    #queue = []
    '''
    for i in range(H+2):
        for j in range(W+2):
            if(c[i][j] == '#'):
                queue.append([i, j])
    '''
    while status:
        if(len(queue) > 0):
            pivot = queue.pop(0) #軸足はqueueの先頭
            x = pivot[0]
            y = pivot[1]
            if(c[x+1][y] == '.'):
                c[x+1][y] = str(step)
                next_list.append([x+1, y])
            if(c[x-1][y] == '.'):
                c[x-1][y] = str(step)
                next_list.append([x-1, y])
            if(c[x][y+1] == '.'):
                c[x][y+1] = str(step)
                next_list.append([x, y+1])
            if(c[x][y-1] == '.'):
                c[x][y-1] = str(step)
                next_list.append([x, y-1])
        else:
            #queueの中身が空っぽになった
            #基本的にはstep += 1
            if(len(next_list) > 0):
                #next_listの中身がある場合（まだ探索が終了していない場合）
                #next_list -> queue にして next_listはからにする
                for i in range(len(next_list)):
                    queue.append(next_list.pop(0))
                next_list = []
                #print()
                #print('step{}end'.format(step))
                #see_banmen()
                #次の探索に移る
                step += 1
            else:
                #初めてnext_listの中身がなくなった場合（探索は終了したい）
                #もう進めない
                #print()
                #print('もう進めない')
                #print('step{}end'.format(step))
                #see_banmen()
                status = False

    print(step - 1)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#from math import gcd 旧環境でこれを有効化するとREを吐きます

s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
H = p[0]
W = p[1]

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


#白ベースで最寄りの黒を探す方針
#パディングは'.'でも'#'でもないもので埋める
b = ''
for i in range(W+2):
    b += 'w'
#print(b)
#上と下と右と左に空きマスを挿入する
a.insert(0, b)
for i in range(1, 1+H):
    a[i] = 'w' + a[i] + 'w'
a.append(b)


header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))

c=[]
for i in range(H+2):
    c.append([])
queue = []
for i in range(H+2):
    for j in range(W+2):
        if(a[i][j] == '#'):
            queue.append([i, j])
        c[i].append(a[i][j])


def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))
#see_banmen()



#queue = [start]
next_list = [] #次の歩数で探すものを格納しておく
step = 1
#mode = 0
#answer_mode = 0
status = True #ゴール判定でゴールについていたらFalseにする
#answer = -1

#queue = []
'''
for i in range(H+2):
    for j in range(W+2):
        if(c[i][j] == '#'):
            queue.append([i, j])
'''
while status:
    if(len(queue) > 0):
        pivot = queue.pop(0) #軸足はqueueの先頭
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = str(step)
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = str(step)
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = str(step)
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = str(step)
            next_list.append([x, y-1])
    else:
        #queueの中身が空っぽになった
        #基本的にはstep += 1
        if(len(next_list) > 0):
            #next_listの中身がある場合（まだ探索が終了していない場合）
            #next_list -> queue にして next_listはからにする
            for i in range(len(next_list)):
                queue.append(next_list.pop(0))
            next_list = []
            #print()
            #print('step{}end'.format(step))
            #see_banmen()
            #次の探索に移る
            step += 1
        else:
            #初めてnext_listの中身がなくなった場合（探索は終了したい）
            #もう進めない
            #print()
            #print('もう進めない')
            #print('step{}end'.format(step))
            #see_banmen()
            status = False

print(step - 1)

Submission status: Time Limit Exceeded

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
#from math import gcd 旧環境でこれを有効化するとREを吐きます

s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
H = p[0]
W = p[1]

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


#白ベースで最寄りの黒を探す方針
#パディングは'.'でも'#'でもないもので埋める
b = ''
for i in range(W+2):
    b += 'w'
#print(b)
#上と下と右と左に空きマスを挿入する
a.insert(0, b)
for i in range(1, 1+H):
    a[i] = 'w' + a[i] + 'w'
a.append(b)


header = ' '
for i in range(len(a[0])):
    header += ('{}'.format(i))

c=[]
for i in range(H+2):
    c.append([])

for i in range(H+2):
    for j in range(W+2):
        c[i].append(a[i][j])


def see_banmen():
    print(header)
    for i in range(len(c)):
        print('{}{}'.format(i,''.join(c[i])))
#see_banmen()



#queue = [start]
next_list = [] #次の歩数で探すものを格納しておく
step = 1
#mode = 0
#answer_mode = 0
status = True #ゴール判定でゴールについていたらFalseにする
#answer = -1

queue = []
for i in range(H+2):
    for j in range(W+2):
        if(c[i][j] == '#'):
            queue.append([i, j])

while status:
    if(len(queue) > 0):
        pivot = queue.pop(0) #軸足はqueueの先頭
        x = pivot[0]
        y = pivot[1]
        if(c[x+1][y] == '.'):
            c[x+1][y] = str(step)
            next_list.append([x+1, y])
        if(c[x-1][y] == '.'):
            c[x-1][y] = str(step)
            next_list.append([x-1, y])
        if(c[x][y+1] == '.'):
            c[x][y+1] = str(step)
            next_list.append([x, y+1])
        if(c[x][y-1] == '.'):
            c[x][y-1] = str(step)
            next_list.append([x, y-1])
    else:
        #queueの中身が空っぽになった
        #基本的にはstep += 1
        if(len(next_list) > 0):
            #next_listの中身がある場合（まだ探索が終了していない場合）
            #next_list -> queue にして next_listはからにする
            for i in range(len(next_list)):
                queue.append(next_list.pop(0))
            next_list = []
            #print()
            #print('step{}end'.format(step))
            #see_banmen()
            #次の探索に移る
            step += 1
        else:
            #初めてnext_listの中身がなくなった場合（探索は終了したい）
            #もう進めない
            #print()
            #print('もう進めない')
            #print('step{}end'.format(step))
            #see_banmen()
            status = False

print(step - 1)

Submission status: Time Limit Exceeded

Solution code:
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    h,w = map(int,input().split())
    grid = [input() for _ in range(h)]
    q = deque([])
    dist = [[-1] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                dist[i][j] = 0
                q.append((i,j))
    
    ans = 0
    while q:
        i,j = q.popleft()
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if y < 0 or y >= h:
                continue
            if x < 0 or x >= w:
                continue
            if dist[y][x] < 0:
                dist[y][x] = dist[i][j] + 1
                ans = max(ans,dist[y][x])
                q.append((y,x))
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [['.'] * W for _ in range(H)]
ideal = [['#'] * W for _ in range(H)]
c_max = 0

def bfs(S):
    global visited
    global c_max
    c = 0

    for s in S:
        visited[s[0]][s[1]] = '#'
    que_init = [(s[0], s[1], 0) for s in S]
    que = deque(que_init)

    while que:
        if ideal == visited:
            return c_max

        ci, cj, c = que.popleft()
        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if 0 <= ni < H and 0 <= nj < W and visited[ni][nj] == '.' and C[ni][nj] != '#':
                visited[ni][nj] = '#'
                c_max = max(c_max, c+1)
                que.append((ni, nj, c+1))
    return 0


sg = []
ans = 0
for h in range(H):
    for w in range(W):
        if C[h][w] == '#':
            sg.append((h,w))

ans = bfs(sg)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
r, c = map(int, input().split())

cc = [input() for i in range(r)]

from collections import deque


# 縦がｙ 横がx　だから座標はy,xて書く
st=[]
for i in range(r):
    for j in range(c):
        if cc[i][j]=="#":
            st.append([i,j])

# 保留スタックtodoにスタートの位置情報を入れる
todo=deque(st)
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
seen=[[-1 for i in range(c)] for j in range(r)]

# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
for i in range(len(st)):
    seen[st[i][0]][st[i][1]]=0

# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]
m=0
# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.popleft() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny][nx]=seen[y][x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく
            if seen[ny][nx]>=m:
                m=seen[ny][nx]
       

print(m)

Submission status: Time Limit Exceeded

Solution code:
r, c = map(int, input().split())

cc = [input() for i in range(r)]

from collections import deque
import numpy as np

# 縦がｙ 横がx　だから座標はy,xて書く
st=[]
for i in range(r):
    for j in range(c):
        if cc[i][j]=="#":
            st.append([i,j])

# 保留スタックtodoにスタートの位置情報を入れる
todo=deque(st)
# 検知済みリストseenを-1で初期化 (何も検知してないてこと)
se=np.array([-1]*(r*c))
seen=se.reshape(r,c)

# seenにはどんだけの手数でそこに到達できるかを入れる
# 例えばスタート地点は手数0でいけるから0を入れる
for i in range(len(st)):
    seen[st[i][0],st[i][1]]=0

# 4方向の移動リスト これ使って移動していく
ido=[[1,0],[0,1],[-1,0],[0,-1]]

# 保留リストtodoが空になるまでやる
while todo:
    y, x=todo.popleft() # 現在地は保留からの先頭とりだす
    for i in range(4): # 現在地から4方向を見る
        ny, nx=y+ido[i][0], x+ido[i][1] # 現在地から隣の座標
        # 隣の座標が区画をはみ出さないかつ、検知してないときに
        if 0<=ny<r and 0<=nx<c and seen[ny, nx]==-1 and cc[ny][nx]!="#":
            # 隣に行けるということなので検知してその手数を格納
            seen[ny, nx]=seen[y,x]+1 # 手数＝前の地点の手数+1
            todo.append([ny,nx]) # 保留リストにも入れとく

print(seen.max())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(maze):
    h = len(maze)
    w = len(maze[0])
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    d = deque()
    
    last =[-1, -1]
    for y in range(h):
        for x in range(w):
            if maze[y][x] == '#':
                d.append([y, x])
                visited[y][x] = 0
                last[0] = y
                last[1] = x
    
    while d:
        y, x = d.popleft()
        
        for l, k in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_y, new_x = y + l, x + k
            
            if new_y < 0 or h <= new_y or new_x < 0 or w <= new_x:
                continue
            elif visited[new_y][new_x] != -1:
                continue
            elif maze[new_y][new_x] == '#':
                continue
            
            d.append([new_y, new_x])
            visited[new_y][new_x] = visited[y][x] + 1

        last[0] = y
        last[1] = x
        
    ''' 確認用
    print(last)
    for i in range(h):
        print(visited[i])
    '''
        
    return visited[last[0]][last[1]]

if __name__ == "__main__":
    h, w = map(int, input().split())
    maze = []
    for i in range(h):
        maze.append(list(input()))
    ''' 確認用
    for i in range(h):
        print(maze[i])
    '''
    
    print(bfs(maze))

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

input = sys.stdin.readline

H, W = map(int, input().split())
q = collections.deque()
grid = []
for i in range(H):
    grid.append(list(input().strip()))
    for j in range(W):
        if grid[i][j] == "#":
            q.append((i, j, 0))

maxc = 0
while q:
    i, j, c = q.popleft()
    if maxc < c:
        maxc = c
    if i > 0 and grid[i - 1][j] == ".":
        q.append((i - 1, j, c + 1))
        grid[i - 1][j] = "#"
    if i < H - 1 and grid[i + 1][j] == ".":
        q.append((i + 1, j, c + 1))
        grid[i + 1][j] = "#"
    if j > 0 and grid[i][j - 1] == ".":
        q.append((i, j - 1, c + 1))
        grid[i][j - 1] = "#"
    if j < W - 1 and grid[i][j + 1] == ".":
        q.append((i, j + 1, c + 1))
        grid[i][j + 1] = "#"

print(maxc)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
dist = [[float('inf')] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            dist[i][j] = 0
            queue = deque([(i, j)])
            while queue:
                a, b = queue.popleft()
                for da, db in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    na, nb = a + da, b + db
                    if 0 <= na < H and 0 <= nb < W and A[na][nb] == '.' and dist[na][nb] > dist[a][b] + 1:
                        dist[na][nb] = dist[a][b] + 1
                        queue.append((na, nb))
print(max(max(row) for row in dist))

Submission status: Time Limit Exceeded

Solution code:
#A
from collections import deque
inf = float("inf")
H,W = map(int,input().split())
A = [list(str(input())) for h in range(H)]

C = [[inf for w in range(W)] for h in range(H)]


start = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            start.append([h,w])
            C[h][w] = 0
            
while start:
    h,w = start.popleft()
    c_old = C[h][w]
    if h > 0:
        c_new = C[h-1][w]
        
        if c_new == inf:
            C[h-1][w] = c_old+1
            start.append([h-1,w])
            
    if w > 0:
        c_new = C[h][w-1]
        
        if c_new == inf:
            C[h][w-1] = c_old+1
            start.append([h,w-1])
            
    if w < W-1:
        c_new = C[h][w+1]
        
        if c_new == inf:
            C[h][w+1] = c_old+1
            start.append([h,w+1])
            
    if h < H-1:
        c_new = C[h+1][w]
        
        if c_new == inf:
            C[h+1][w] = c_old+1
            start.append([h+1,w])
            
            
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,C[h][w])
        
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#A
from collections import deque
inf = float("inf")
H,W = map(int,input().split())
A = [list(str(input())) for _ in range(H)]

C = [[inf for w in range(W)] for h in range(H)]


start = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            start.append([h,w])
            C[h][w] = 0
            
while start:
    h,w = start.popleft()
    if h > 0:
        c_old = C[h][w]
        c_new = C[h-1][w]
        
        if c_old+1 < c_new:
            C[h-1][w] = c_old+1
            start.append([h-1,w])
            
    if w > 0:
        c_old = C[h][w]
        c_new = C[h][w-1]
        
        if c_old+1 < c_new:
            C[h][w-1] = c_old+1
            start.append([h,w-1])
            
    if w < W-1:
        c_old = C[h][w]
        c_new = C[h][w+1]
        
        if c_old+1 < c_new:
            C[h][w+1] = c_old+1
            start.append([h,w+1])
            
    if h < H-1:
        c_old = C[h][w]
        c_new = C[h+1][w]
        
        if c_old+1 < c_new:
            C[h+1][w] = c_old+1
            start.append([h+1,w])
            
            
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,C[h][w])
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

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

    field = "#" * (W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#" * (W+2)

    move = [-1, 1, -(W+2), W+2]
    cost = [-1] * (H+2) * (W+2)

    def dfs(s):
        q = deque()
        enqueue = q.append
        dequeue = q.popleft

        for v in s:
            cost[v] = 0
            enqueue(v)

        while q:
            now = dequeue()
            for dx in move:
                nv = now + dx
                if field[nv] == "." and cost[nv] < 0:
                    cost[nv] = cost[now] + 1
                    enqueue(nv)
    
    starts = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            now = i*(W+2) + j
            if field[now] == "#":
                starts.append(now)
    dfs(starts)

    print(max(cost))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs(q):
    tmp=deque(q)
    ch = [[False for i in range(W)] for j in range(H)]
    count = 0
    d=[[-1,0],[1,0],[0,-1],[0,1]]
    while tmp:
        x,y=tmp.popleft()
        for a,b in d:
            nx=x+a
            ny=y+b
            if 0<=nx<H and 0<=ny<W:
                if ch[nx][ny]!=True and A[nx][ny]==".":
                    V[nx][ny]=V[x][y]+1
                    ch[nx][ny]=True
                    tmp.append([nx,ny])
            else:
                continue
ju=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            ju.append([i,j])
bfs(ju)
for i in range(H):
    for j in range(W):
        if not A[i][j]=="#":
             ans=max(ans,V[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
 
H, W = map(int, input().split())
A = [[0 for i in range(W)]for j in range(H)]
white_num = 0
for i in range(H):
    S = input()
    for j in range(W):
        A[i][j] = S[j]
        if A[i][j] == '.':
            white_num += 1
 
ans = 0
while white_num > 0:
    A_ = copy.deepcopy(A)
    ans += 1
    for y in range(H):
        for x in range(W):
            if A[y][x] == ".":
                continue
            if A[y][x] == "#":
                for k in range(4):
                    nx = x + [1, 0, -1, 0][k]
                    ny = y + [0, 1, 0, -1][k]
                    if nx < 0 or ny < 0 or nx >= W or ny >= W:
                        continue
                    if A[ny][nx] == "#":
                        continue
                    if A[ny][nx] == "." and A_[ny][nx] == ".":
                        A_[ny][nx] = "#"
                        white_num -= 1
    A = A_
print(ans)