Problem:


Score : 400 points

Problem Statement

Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.

The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is #, and a "road" square if S_{ij} is ..

From a road square, you can move to a horizontally or vertically adjacent road square.

You cannot move out of the maze, move to a wall square, or move diagonally.

Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.

Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.

In this situation, find the maximum possible number of moves Aoki has to make.

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

Any road square can be reached from any road square in zero or more moves.

Input

Input is given from Standard Input in the following format:

H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

Output

Print the maximum possible number of moves Aoki has to make.

Sample Input 1

3 3
...
...
...

Sample Output 1

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Sample Input 2

3 5
...#.
.#.#.
.#...

Sample Output 2

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue

        c=deque()    
        s=0
        c+=[i,j]
        
        t=len(c)//2
        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):
                        m = c.popleft()
                        n = c.popleft()
                        T[m][n]=s
                        if m != H-1:
                                if T[m+1][n]==0:
                                        c.append(m+1)
                                        c.append(n)
                        if m != 0:
                                if T[m-1][n]==0:
                                        c.append(m-1)
                                        c.append(n)
 
                        if n != W-1:
                                if T[m][n+1]==0:
                                        c.append(m)
                                        c.append(n+1)
                                        
                        if n != 0:
                                if T[m][n-1]==0:
                                        c.append(m)
                                        c.append(n-1)

        #print(T)
        d = max(d,s)
        T=B.copy()
        
print(d-2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue

        c=deque()    
        s=0
        c+=[i,j]
        
        t=len(c)//2
        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):
                        m = c.popleft()
                        n = c.popleft()
                        T[m][n]=s
                        if m != H-1:
                                if T[m+1][n]==0:c+=[m+1,n]
                        if m != 0:
                                if T[m-1][n]==0:c+=[m-1,n] 
                        if n != W-1:
                                if T[m][n+1]==0:c+=[m,n+1]
                        if n != 0:
                                if T[m][n-1]==0:c+=[m,n-1]
                        #c += (chk_route([c.popleft(),c.popleft()]))
                
        #print(T)
        d = max(d,s)
        T=B.copy()
        
print(d-2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
 
def chk_route(c):
    global H,W,T
    ans=[]
    if c[0] != H-1:
        if T[c[0]+1][c[1]]==0:
            ans+=[c[0]+1,c[1]]
    if c[0] != 0:
        if T[c[0]-1][c[1]]==0:
            ans+=[c[0]-1,c[1]] 
    if c[1] != W-1:
        if T[c[0]][c[1]+1]==0:
            ans+=[c[0],c[1]+1]
 
    if c[1] != 0:
        if T[c[0]][c[1]-1]==0:
            ans+=[c[0],c[1]-1]

    return ans
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue

        c=deque()    
        s=0
        c+=[i,j]
        
        t=len(c)//2
        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):
                        T[c[0]][c[1]]=s
                        c += (chk_route([c.popleft(),c.popleft()]))
                
        #print(T)
        d = max(d,s)
        T=B.copy()
        
print(d-2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
 
def chk_route(c):
    global H,W,T
    ans=[]
    if c[0] != H-1:
        if T[c[0]+1][c[1]]==0:
            ans+=[c[0]+1,c[1]]
    if c[0] != 0:
        if T[c[0]-1][c[1]]==0:
            ans+=[c[0]-1,c[1]] 
    if c[1] != W-1:
        if T[c[0]][c[1]+1]==0:
            ans+=[c[0],c[1]+1]
 
    if c[1] != 0:
        if T[c[0]][c[1]-1]==0:
            ans+=[c[0],c[1]-1]

    return ans
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue

        c=deque()    
        s=0
        c.append(i)
        c.append(j)
        T=B.copy()
        t=len(c)//2

        while t>0:
                s+=1
                t=len(c)//2
                for k in range(t):T[c[0+k*2]][c[1+k*2]]=s
                for k in range(t):
                        c += (chk_route([c.popleft(),c.popleft()]))
                
        #print(T)
        d = max(d,s)
         
print(d-2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
 
def chk_route(c):
    global H,W
    ans=[]
    if c[0] != H-1:
        if T[c[0]+1][c[1]]==0:
            ans.append(c[0]+1)
            ans.append(c[1])
    if c[0] != 0:
        if T[c[0]-1][c[1]]==0:
            ans.append(c[0]-1)
            ans.append(c[1])
 
    if c[1] != W-1:
        if T[c[0]][c[1]+1]==0:
            ans.append(c[0])
            ans.append(c[1]+1)
 
    if c[1] != 0:
        if T[c[0]][c[1]-1]==0:
            ans.append(c[0])
            ans.append(c[1]-1)
    return ans
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
        c=deque()    

        s=1
        c.append(i)
        c.append(j)
        T=B.copy()
        t=len(c)//2

        while t>0: 
                t=len(c)//2
                for k in range(t):T[c[0+k*2]][c[1+k*2]]=s
                for k in range(t):
                        c += (chk_route([c.popleft(),c.popleft()]))
                s+=1
        d = max(d,np.max(T))
 
print(d-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
def chk_route(c):
    global H,W
    ans=[]
    if c[0] != H-1:
        if T[c[0]+1][c[1]]==0:
            ans.append(c[0]+1)
            ans.append(c[1])
    if c[0] != 0:
        if T[c[0]-1][c[1]]==0:
            ans.append(c[0]-1)
            ans.append(c[1])
 
    if c[1] != W-1:
        if T[c[0]][c[1]+1]==0:
            ans.append(c[0])
            ans.append(c[1]+1)
 
    if c[1] != 0:
        if T[c[0]][c[1]-1]==0:
            ans.append(c[0])
            ans.append(c[1]-1)
    return ans
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)

for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
B=T.copy()    
d=0
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
        c=[]    

        s=1
        c.append(i)
        c.append(j)
        T=B.copy()
        t=len(c)//2

        while t>0: 
                t=len(c)//2
                for k in range(t):T[c[0+k*2]][c[1+k*2]]=s
                for k in range(t):
                        c += (chk_route([c.pop(0),c.pop(0)]))
                s+=1
        d = max(d,np.max(T))
 
print(d-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, copy
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial

sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
maze = [[c for c in input()] for _ in range(H)]

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

def chkcell(maze_copy, h, w):
    if 0<=h and h<H and 0<=w and w<W and maze_copy[h][w]=='.':
        return True

def count_steps(q, maze_copy):
    steps = -1
    while len(q):
#        print('q:', q)
#        print('maze:')
#        for row in maze_copy:
#            print(row)
        steps += 1
        next_cells = []
        cells = q.pop()
        for cell in cells:
            maze_copy[cell[0]][cell[1]] = '#'
            for move in moves:
                newcell = tuple(i+j for i, j in zip(cell, move))
                if chkcell(maze_copy=maze_copy, h=newcell[0], w=newcell[1]):
                    next_cells.append(newcell)
        if next_cells:
            q.append(next_cells)

#    print('max_step:', steps)
    return steps

def main():
    res = 0
    for i in range(H):
        for j in range(W):
#        print('i, j', i, j)
            if maze[i][j] == '#':
                continue
            q = deque()
            q.append([[i, j]])
#        maze_copy = copy.deepcopy(maze)
            maze_copy = [[c for c in row] for row in maze]
            val = count_steps(q, maze_copy)
            if res < val: res = val

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, math, copy
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial

sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
maze = [[c for c in input()] for _ in range(H)]

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

def chkcell(maze_copy, h, w):
    if 0<=h and h<H and 0<=w and w<W and maze_copy[h][w]=='.':
        return True

def count_steps(q, maze_copy):
    steps = -1
    while len(q):
#        print('q:', q)
#        print('maze:')
#        for row in maze_copy:
#            print(row)
        steps += 1
        next_cells = []
        cells = q.pop()
        for cell in cells:
            maze_copy[cell[0]][cell[1]] = '#'
            for move in moves:
                newcell = tuple(i+j for i, j in zip(cell, move))
                if chkcell(maze_copy=maze_copy, h=newcell[0], w=newcell[1]):
                    next_cells.append(newcell)
        if next_cells:
            q.append(next_cells)

#    print('max_step:', steps)
    return steps

res = 0
for i in range(H):
    for j in range(W):
#        print('i, j', i, j)
        if maze[i][j] == '#':
            continue
        q = deque()
        q.append([[i, j]])
#        maze_copy = copy.deepcopy(maze)
        maze_copy = [[c for c in row] for row in maze]
        val = count_steps(q, maze_copy)
        if res < val: res = val

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, copy
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial

sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
maze = [[c for c in input()] for _ in range(H)]

moves = [[-1, 0], [1, 0], [0, -1], [0, 1]]

def chkcell(maze_copy, h, w):
    if 0<=h and h<H and 0<=w and w<W and maze_copy[h][w]=='.':
        return True

def count_steps(q, maze_copy):
    steps = -1
    while len(q):
#        print('q:', q)
#        print('maze:')
#        for row in maze_copy:
#            print(row)
        steps += 1
        next_cells = []
        cells = q.pop()
        for cell in cells:
            maze_copy[cell[0]][cell[1]] = '#'
            for move in moves:
                newcell = [i+j for i, j in zip(cell, move)]
                if chkcell(maze_copy=maze_copy, h=newcell[0], w=newcell[1]):
                    next_cells.append(newcell)
        if next_cells:
            q.append(next_cells)

#    print('max_step:', steps)
    return steps

res = 0
for i in range(H):
    for j in range(W):
#        print('i, j', i, j)
        if maze[i][j] == '#':
            continue
        q = deque()
        q.append([[i, j]])
#        maze_copy = copy.deepcopy(maze)
        maze_copy = [[c for c in row] for row in maze]
        val = count_steps(q, maze_copy)
        if res < val: res = val

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, copy
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial

sys.setrecursionlimit(10**7)
H, W = map(int, input().split())
maze = [[c for c in input()] for _ in range(H)]

moves = [[-1, 0], [1, 0], [0, -1], [0, 1]]

def chkcell(maze_copy, h, w):
    if 0<=h and h<H and 0<=w and w<W and maze_copy[h][w]=='.':
        return True

def count_steps(q, maze_copy):
    steps = -1
    while len(q):
#        print('q:', q)
#        print('maze:')
#        for row in maze_copy:
#            print(row)
        steps += 1
        next_cells = []
        cells = q.pop()
        for cell in cells:
            maze_copy[cell[0]][cell[1]] = '#'
            for move in moves:
                newcell = [i+j for i, j in zip(cell, move)]
                if chkcell(maze_copy=maze_copy, h=newcell[0], w=newcell[1]):
                    next_cells.append(newcell)
        if next_cells:
            q.append(next_cells)

#    print('max_step:', steps)
    return steps

res = 0
for i in range(H):
    for j in range(W):
#        print('i, j', i, j)
        if maze[i][j] == '#':
            continue
        q = deque()
        q.append([[i, j]])
        maze_copy = copy.deepcopy(maze)
        val = count_steps(q, maze_copy)
        if res < val: res = val

print(res)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
from itertools import product
import numpy as np

NOT_VISITED = 0
SCHEDULED = 1
VISITED = 2

H, W = map(int, input().split())
S = np.zeros((H, W), dtype='U1')
for hi in range(H):
    raw = input()
    S[hi, :] = list(raw)

maxmove = np.zeros_like(S, dtype='int')

for hi, wi in product(range(H), range(W)):
    # hi, wiをスタート位置とする場合
    if S[hi, wi] == '#': continue

    # 必要な諸々を定義
    flag = np.zeros_like(S, dtype='int')
    flag[:] = NOT_VISITED
    flag[hi, wi] = VISITED
    nummove = np.zeros_like(S, dtype='int')
    queue = Queue()

    queue.put((hi, wi))
    while queue.empty() == False:
        hj, wj = queue.get()
        flag[hj, wj] = VISITED
        for neighbour in [(hj, wj-1), (hj, wj+1), (hj+1, wj), (hj-1, wj)]:
            if not (0 <= neighbour[0] < H and 0 <= neighbour[1] < W): continue
            if S[neighbour] == '#': continue
            if flag[neighbour] == NOT_VISITED:
                nummove[neighbour] = nummove[hj, wj] + 1
                queue.put(neighbour)
                flag[neighbour] = SCHEDULED
    
    maxmove[hi, wi] = np.max(nummove)

print(np.max(maxmove))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from copy import copy
from queue import Queue

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

maze = []
for _ in range(H):
  maze.append([i for i in input()])
  
# 無向グラフを作ってワーシャルフロイド法で解く

inf = float("inf")
d = defaultdict(lambda: inf)
for i in range(H):
  for j in range(W):
    if maze[i][j] == '.':
      d[((i, j), (i, j))] = 0

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(H):
  for j in range(W):
    if maze[i][j] == '.':
      for di, dj in directions:
        if i + di >= 0 and i + di < H\
        and j + dj >= 0 and j + dj < W\
        and maze[i + di][j + dj] == '.':
          d[((i, j), (i + di, j + dj))] = 1
          d[((i + di, j + dj), (i, j))] = 1

            
# 連結成分ごとにワーシャルフロイド法を実行し、最大距離を計算する
for i1 in range(H):
  for j1 in range(W):
    for i2 in range(H):
      for j2 in range(W):
        for i3 in range(H):
          for j3 in range(W):
            d[((i1, j1), (i3, j3))]\
            = min(
              d[((i1, j1), (i3, j3))],
              d[((i1, j1), (i2, j2))] + d[((i2, j2), (i3, j3))]
            )

# 全ての連結成分の最大距離を求めて出力

ret = 0
for i1 in range(H):
  for j1 in range(W):
    for i2 in range(H):
      for j2 in range(W):
        if d[((i1, j1), (i2, j2))] != inf\
        and d[((i1, j1), (i2, j2))] > ret:
          ret = d[((i1, j1), (i2, j2))]
          
print(ret)

Submission status: Time Limit Exceeded

Solution code:

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

array = []
for _ in range(H):
  array.append(input())
  
max_path = 0
import queue
for h in range(H):
  for w in range(W):    
    if array[h][w] == ".":
      que = queue.Queue()
      checked = [[-1 if array[h][w] =="." else -2 for w in range(W)] for h in range(H)]
      que.put((w, h, 0))
      while not que.empty():
        x, y, l = que.get()
        checked[y][x] = l
        max_path = max(max_path, l)
        if (x > 0) and (checked[y][x-1] == -1):
          que.put((x-1, y, l+1))
        if (y > 0) and (checked[y-1][x] == -1):
          que.put((x, y - 1, l+1))
        if (x < W - 1) and (checked[y][x+1] == -1):
          que.put((x + 1, y, l+1))
        if (y < H - 1) and (checked[y+1][x] == -1):
          que.put((x, y + 1, l+1))
        
          
        
  
print(max_path)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

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


def make_wall(W, Map):
    for map_row in Map:
        map_row.append("#")
        map_row.insert(0, "#")

    wall = ["#"]*(W+2)
    Map.append(wall)
    Map.insert(0, wall)
    return Map


start_list = deque()
search_list = deque()
Map = make_wall(W, Map)
H += 2
W += 2

start_h = 0
for h in range(H):
    start_w = 0
    for w in range(W):
        if Map[h][w] == ".":
            start_list.append([start_h, start_w])
        start_w += 1
    start_h += 1



max_cost = 0
while start_list != deque():
    search_list.append(start_list.popleft())
    cost_map = np.array([[0] * W for i in range(H)])
    search_map = np.array([[0] * W for i in range(H)])

    while search_list != deque():
        tmp = search_list.popleft()
        x = tmp[0]
        y = tmp[1]
        search_map[x][y] = 1
        if Map[x][y+1] == "." and search_map[x][y+1] == 0:
            if [x, y+1] not in search_list:
                search_list.append([x, y+1])
            cost_map[x][y+1] = cost_map[x][y]+1
        if Map[x][y-1] == "." and search_map[x][y-1] == 0:
            if [x, y-1] not in search_list:
                search_list.append([x, y-1])
            cost_map[x][y-1] = cost_map[x][y]+1
        if Map[x+1][y] == "." and search_map[x+1][y] == 0:
            if [x+1, y] not in search_list:
                search_list.append([x+1, y])
            cost_map[x+1][y] = cost_map[x][y]+1
        if Map[x-1][y] == "." and search_map[x-1][y] == 0:
            if [x-1, y] not in search_list:
                search_list.append([x-1, y])
            cost_map[x-1][y] = cost_map[x][y]+1
    cost_map = np.array(cost_map)
    if max_cost < np.amax(cost_map):
        max_cost = np.amax(cost_map)

print(max_cost)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
INF = 99999999999999999


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


def m_distance(si, sj):
    if (S[si][sj] == '#'):
        return -INF
    
    q = Queue()
    q.put((si, sj, 0))
    done = [[False] * W for x in range(H)]

    m = 0
    unit = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while not q.empty():
        i, j, w = q.get()
        done[i][j] = True
        

        for u in unit:
            nexti = i + u[0]
            nextj = j + u[1]
            if nexti >= 0 and nexti < H and nextj >= 0 and nextj < W and S[nexti][nextj] == '.' and (not done[nexti][nextj]):
                q.put((nexti, nextj, w+1))
                m = max(m, w+1)

    return m

m = 0
for i in range(H):
    for j in range(W):
        m = max(m, m_distance(i, j))
print(m)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
x4 = [ 1,0,-1,0 ]
y4 = [ 0,1,0,-1 ] 
max_int = 2**63-1
 
 
h,w = map(int, input().split(' '))
S = []
for i in range(h):
    S.append(input())

grid = [[False]*(w+2) for _ in range(h+2)]
for i in range(h):
    for j in range(w):
        grid[i+1][j+1] = S[i][j] == '.'

ans = 0
 
for i in range(1,h+1):
    for j in range(1,w+1):
        if not grid[i][j]:
            continue
 
        visited = [[False for o in range(w+2)] for l in range(h+2)]
        q = deque()
        d = [[max_int for o in range(w+2)] for l in range(h+2)]
 
        visited[i][j] = True
        q.append((i,j))
        d[i][j] = 0
 
        while q:
            cy, cx = q.popleft()
            visited[cy][cx] = True
            for dy,dx in zip(y4,x4):
                ny = cy + dy
                nx = cx + dx
                if grid[ny][nx] and not visited[ny][nx]:
                    q.append((ny, nx))
                    d[ny][nx] = min(d[ny][nx], d[cy][cx] + 1)
                    ans = max(d[ny][nx], ans)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

x4 = [ 1,0,-1,0 ]
y4 = [ 0,1,0,-1 ] 
max_int = 2**63-1


h,w = map(int, input().split(' '))
S = []
for i in range(h):
    S.append(input())

ans = 0

for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            continue

        visited = [[False for o in range(w)] for l in range(h)]
        q = deque()
        d = [[max_int for o in range(w)] for l in range(h)]

        visited[i][j] = True
        q.append((i,j))
        d[i][j] = 0

        while(q):
            cy, cx = q.popleft()
            visited[cy][cx] = True
            for k in range(4):
                ny = cy + y4[k]
                nx = cx + x4[k]
                if 0 <= nx < w and 0 <= ny < h and S[ny][nx] == '.' and visited[ny][nx] == False:
                    q.append((ny, nx))
                    d[ny][nx] = min(d[ny][nx], d[cy][cx] + 1)
                    ans = max(d[ny][nx], ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

x4 = [ 1,0,-1,0 ]
y4 = [ 0,1,0,-1 ] 
max_int = 2**63-1


h,w = map(int, input().split(' '))
S = []
for i in range(h):
    S.append(input())

ans = 0

for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            continue

        visited = [[False for o in range(w)] for l in range(h)]
        q = queue.Queue()
        d = [[max_int for o in range(w)] for l in range(h)]

        visited[i][j] = True
        q.put((i,j))
        d[i][j] = 0

        while(q.empty() == False):
            cy, cx = q.get()
            visited[cy][cx] = True
            for k in range(4):
                ny = cy + y4[k]
                nx = cx + x4[k]
                if 0 <= nx < w and 0 <= ny < h and S[ny][nx] == '.' and visited[ny][nx] == False:
                    q.put((ny, nx))
                    d[ny][nx] = min(d[ny][nx], d[cy][cx] + 1)
                    ans = max(d[ny][nx], ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
""""
3 5
...#.
.#.#.
.#...
"""
from collections import deque
#import numpy as np

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


def make_wall(W, Map):
    for map_row in Map:
        map_row.append("#")
        map_row.insert(0, "#")

    wall = ["#"]*(W+2)
    Map.append(wall)
    Map.insert(0, wall)
    return Map


start_list = deque()
search_list = deque()
Map = make_wall(W, Map)
H += 2
W += 2

start_h = 0
for h in range(H):
    start_w = 0
    for w in range(W):
        if Map[h][w] == ".":
            start_list.append([start_h, start_w])
        start_w += 1
    start_h += 1



max_cost = 0
while start_list != deque():
    search_list.append(start_list.popleft())
    #cost_map = np.array([[0] * W for i in range(H)])
    #search_map = np.array([[0] * W for i in range(H)])
    cost_map = [[0] * W for i in range(H)]
    search_map = [[0] * W for i in range(H)]
    while search_list != deque():
        tmp = search_list.popleft()
        x = tmp[0]
        y = tmp[1]
        search_map[x][y] = 1
        if Map[x][y+1] == "." and search_map[x][y+1] == 0:
            search_list.append([x, y+1])
            cost_map[x][y+1] = cost_map[x][y]+1
        if Map[x][y-1] == "." and search_map[x][y-1] == 0:
            search_list.append([x, y-1])
            cost_map[x][y-1] = cost_map[x][y]+1
        if Map[x+1][y] == "." and search_map[x+1][y] == 0:
            search_list.append([x+1, y])
            cost_map[x+1][y] = cost_map[x][y]+1
        if Map[x-1][y] == "." and search_map[x-1][y] == 0:
            search_list.append([x-1, y])
            cost_map[x-1][y] = cost_map[x][y]+1
    """"
    cost_map = np.array(cost_map)
    if max_cost < np.amax(cost_map):
        max_cost = np.amax(cost_map)
    """
    max_tmp = [0]*H
    for i in range(H):
        max_tmp[i] = max(cost_map[i])
    if max_cost < max(max_tmp):
        max_cost = max(max_tmp)

print(max_cost)

Submission status: Time Limit Exceeded

Solution code:
import queue

x4 = [ 1,0,-1,0 ]
y4 = [ 0,1,0,-1 ] 
max_int = 2**63-1


h,w = map(int, input().split(' '))
S = []
for i in range(h):
    S.append(input())

ans = 0

for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            continue

        visited = [[False for o in range(w)] for l in range(h)]
        q = queue.Queue()
        d = [[max_int for o in range(w)] for l in range(h)]

        visited[i][j] = True
        q.put((i,j))
        d[i][j] = 0

        while(q.empty() == False):
            cy, cx = q.get()
            visited[cy][cx] = True
            for k in range(4):
                ny = cy + y4[k]
                nx = cx + x4[k]
                if 0 <= nx < w and 0 <= ny < h and S[ny][nx] == '.' and visited[ny][nx] == False:
                    q.put((ny, nx))
                    d[ny][nx] = min(d[ny][nx], d[cy][cx] + 1)

        for o in range(h):
            for l in range(w):
                if S[o][l] == '#':
                    continue
                ans = max(d[o][l], ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

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


def make_wall(W, Map):
    for map_row in Map:
        map_row.append("#")
        map_row.insert(0, "#")

    wall = ["#"]*(W+2)
    Map.append(wall)
    Map.insert(0, wall)
    return Map


start_list = deque()
search_list = deque()
Map = make_wall(W, Map)
H += 2
W += 2

start_h = 0
for h in range(H):
    start_w = 0
    for w in range(W):
        if Map[h][w] == ".":
            start_list.append([start_h, start_w])
        start_w += 1
    start_h += 1



max_cost = 0
while start_list != deque():
    search_list.append(start_list.popleft())
    cost_map = np.array([[0] * W for i in range(H)])
    search_map = np.array([[0] * W for i in range(H)])
    while search_list != deque():
        tmp = search_list.popleft()
        x = tmp[0]
        y = tmp[1]
        search_map[x][y] = 1
        if Map[x][y+1] == "." and search_map[x][y+1] == 0:
            search_list.append([x, y+1])
            cost_map[x][y+1] = cost_map[x][y]+1
        if Map[x][y-1] == "." and search_map[x][y-1] == 0:
            search_list.append([x, y-1])
            cost_map[x][y-1] = cost_map[x][y]+1
        if Map[x+1][y] == "." and search_map[x+1][y] == 0:
            search_list.append([x+1, y])
            cost_map[x+1][y] = cost_map[x][y]+1
        if Map[x-1][y] == "." and search_map[x-1][y] == 0:
            search_list.append([x-1, y])
            cost_map[x-1][y] = cost_map[x][y]+1
    if max_cost < np.amax(cost_map):
        max_cost = np.amax(cost_map)


print(max_cost)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

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


def make_wall(W, Map):
    for map_row in Map:
        map_row.append("#")
        map_row.insert(0, "#")

    wall = ["#"]*(W+2)
    Map.append(wall)
    Map.insert(0, wall)
    return Map


start_list = deque()
search_list = deque()
Map = make_wall(W, Map)
H += 2
W += 2

start_h = 0
for h in range(H):
    start_w = 0
    for w in range(W):
        if Map[h][w] == ".":
            start_list.append([start_h, start_w])
        start_w += 1
    start_h += 1



max_cost = 0
while start_list != deque():
    search_list.append(start_list.popleft())
    cost_map = [[0] * W for i in range(H)]
    search_map = [[0] * W for i in range(H)]
    while search_list != deque():
        tmp = search_list.popleft()
        x = tmp[0]
        y = tmp[1]
        search_map[x][y] = 1
        if Map[x][y+1] == "." and search_map[x][y+1] == 0:
            search_list.append([x, y+1])
            cost_map[x][y+1] = cost_map[x][y]+1
        if Map[x][y-1] == "." and search_map[x][y-1] == 0:
            search_list.append([x, y-1])
            cost_map[x][y-1] = cost_map[x][y]+1
        if Map[x+1][y] == "." and search_map[x+1][y] == 0:
            search_list.append([x+1, y])
            cost_map[x+1][y] = cost_map[x][y]+1
        if Map[x-1][y] == "." and search_map[x-1][y] == 0:
            search_list.append([x-1, y])
            cost_map[x-1][y] = cost_map[x][y]+1
    cost_map = np.array(cost_map)
    if max_cost < np.amax(cost_map):
        max_cost = np.amax(cost_map)
print(max_cost)