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
from copy import deepcopy
H, W = map(int, input().split())
maze = [[]for i in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        maze[i].append(S[j])

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
ans = 0
Q = deque()

for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if (sx == gx) and (sy == gy):
                    continue
                if (maze[sy][sx] == '#') or (maze[gy][gx] == '#'):
                    continue
                mazenow = deepcopy(maze)
                Q.clear()
                Q.append((sy, sx))
                mazenow[sy][sx] = 0
                flag = True
                while (len(Q) >= 0) and flag:
                    y, x = Q.popleft()
                    for i in range(4):
                        ny = y + dy[i]
                        nx = x + dx[i]
                        if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W):
                            continue
                        elif (ny == gy) and (nx == gx):
                            ans = max(ans, mazenow[y][x] + 1)
                            flag = False
                            break
                        elif mazenow[ny][nx] == '.':
                            mazenow[ny][nx] = mazenow[y][x] + 1
                            Q.append((ny, nx))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
x = [''.join(["#"]*(w+2))]
s = x+["#"+input()+"#" for _ in range(h)]+x
ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        checked=[[i,j]]
        stack=[[i,j]]
        stack_=[]
        count = 1
        while stack:
            pair=stack.pop()
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                if [pair[0]+x,pair[1]+y] not in checked and s[pair[0]+x][pair[1]+y]==".":
                    stack_.append([pair[0]+x,pair[1]+y])
                    checked.append([pair[0]+x,pair[1]+y])
            if stack==[]:
                stack = stack_.copy()
                stack_ = []
                count += 1

        ans = max(ans,count)
        
print(ans-2)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
x = [''.join(["#"]*(w+2))]
s = x+["#"+input()+"#" for _ in range(h)]+x
ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        checked=[]
        stack=[[i,j]]
        stack_=[]
        count = 1
        while stack:
            pair=stack.pop()
            checked.append(pair)
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                if [pair[0]+x,pair[1]+y] not in checked and s[pair[0]+x][pair[1]+y]==".":
                    stack_.append([pair[0]+x,pair[1]+y])
            if stack==[]:
                stack = stack_.copy()
                stack_ = []
                count += 1

        ans = max(ans,count)
        
print(ans-2)

Submission status: Time Limit Exceeded

Solution code:
def next_locations(maze, H, W, i, j):
    if maze[i][j] == '#':
        return list()
    locations = list()
    if i - 1 >= 0 and maze[i - 1][j] == '.':
        locations.append((i - 1, j))
    if i + 1 < H and maze[i + 1][j] == '.':
        locations.append((i + 1, j))
    if j - 1 >= 0 and maze[i][j - 1] == '.':
        locations.append((i, j - 1))
    if j + 1 < W and maze[i][j + 1] == '.':
        locations.append((i, j + 1))
    return locations


def location_to_index(W, i, j):
    return W * i + j


def warshall_floyd(V, d):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min([d[i][j], d[i][k] + d[k][j]])
    return d


def main():
    H, W = list(map(int, input().split(' ')))
    INF = H * W
    maze = list()
    for _ in range(H):
        maze.append(input())
    d = [[INF for _ in range(H * W)] for _ in range(H * W)]
    for i in range(H):
        for j in range(W):
            from_index = location_to_index(W, i, j)
            locs = next_locations(maze, H, W, i, j)
            for loc in locs:
                to_index = location_to_index(W, loc[0], loc[1])
                d[from_index][to_index] = 1 if from_index != to_index else 0
    d = warshall_floyd(H * W, d)
    answer = 0
    for from_index in range(H * W):
        for to_index in range(H * W):
            dist = d[from_index][to_index]
            if dist == INF:
                continue
            if dist > answer:
                answer = dist
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import combinations

H,W=list(map(int,input().split()))
S=[input() for _ in range(H)]
pts=[[j,i] for i in range(W) for j in range(H)]
d=[[-1,0],[1,0],[0,1],[0,-1]]
ret=0

for s,g in combinations(pts,2):
    if S[s[0]][s[1]]=='#' or S[g[0]][g[1]]=='#':
        continue

    q=deque([s+[0]])
    while len(q)>0:
        h,w,cnt=deque.popleft(q)

        if g[0]==h and g[1]==w:
            ret=max(ret,cnt)
            break

        for dw,dh in d:
            if 0<=w+dw<W and 0<=h+dh<H and S[h+dh][w+dw]=='.':
                deque.append(q,[h+dh,w+dw,cnt+1])

print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import combinations

H,W=list(map(int,input().split()))
S=[input() for _ in range(H)]
pts=[[j,i] for i in range(W) for j in range(H)]
d=[[-1,0],[1,0],[0,1],[0,-1]]
ret=0

for s,g in combinations(pts,2):
    if S[s[0]][s[1]]=='#' or S[g[0]][g[1]]=='#':
        continue

    q=deque([s+[0]])
    while len(q)>0:
        h,w,cnt=q.popleft()

        if g[0]==h and g[1]==w:
            ret=max(ret,cnt)
            break

        for dw,dh in d:
            if 0<=w+dw<W and 0<=h+dh<H and S[h+dh][w+dw]=='.':
                q.append([h+dh,w+dw,cnt+1])

print(ret)

Submission status: Time Limit Exceeded

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

def warshall_floyd(vl,d):
  #d[vi][vj]: viからvjへの最短距離
  for vk in vl:
    for vi in vl:
      for vj in vl:
        if vk in d[vi] and vj in d[vk]:
          if not vj in d[vi]:
            d[vi][vj]=d[vi][vk]+d[vk][vj]
          else:
            d[vi][vj]=min(d[vi][vj],d[vi][vk]+d[vk][vj])
  return d

# vlistに点のリスト、dist[vi][vj]に辺(vi,vj)のコストを入れて呼び出す
mat=[[x=="." for x in input()] for _ in range(H)]
#print(mat)

vlist=[]
dist={}
for i in range(H):
  for j in range(W):
    if mat[i][j]:
      vlist.append((i,j))
      if not (i,j) in dist:
        dist[(i,j)]={}
      dist[(i,j)][(i,j)]=0
      if i>0 and mat[i-1][j]:
          dist[(i,j)][(i-1,j)]=1
      if i<H-1 and mat[i+1][j]:
          dist[(i,j)][(i+1,j)]=1
      if j>0 and mat[i][j-1]:
          dist[(i,j)][(i,j-1)]=1
      if j<W-1 and mat[i][j+1]:
          dist[(i,j)][(i,j+1)]=1

#print(vlist)
#print(dist)
dist=warshall_floyd(vlist,dist)
#print(dist)
answer=0
for x in dist:
  for y in dist[x]:
    answer=max(answer,dist[x][y])
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
h,w=map(int,input().split())
s=[input()for _ in range(h)]
a=np.full((h,w),400,np.int64)
ans=0
def bfs(b,i,j,s):
    b[i,j]=0
    seen=np.zeros((h,w),np.int64)
    todo=deque([(i,j)])
    while np.sum(seen)<h*w and len(todo)>0:
        x,y=todo.popleft()
        if seen[x,y]==1:
            continue
        seen[x,y]=1
        if x>0 and seen[x-1,y]==0 and s[x-1][y]=='.':
            b[x-1,y]=b[x,y]+1
            todo.append((x-1,y))
        if x>0 and s[x-1][y]=='#':
            seen[x-1,y]=1
        if x<h-1 and seen[x+1,y]==0 and s[x+1][y]=='.':
            b[x+1,y]=b[x,y]+1
            todo.append((x+1,y))
        if x<h-1 and s[x+1][y]=='#':
            seen[x+1,y]=1
        if y>0 and seen[x,y-1]==0 and s[x][y-1]=='.':
            b[x,y-1]=b[x,y]+1
            todo.append((x,y-1))
        if y>0 and s[x][y-1]=='#':
            seen[x,y-1]=1
        if y<w-1 and seen[x,y+1]==0 and s[x][y+1]=='.':
            b[x,y+1]=b[x,y]+1
            todo.append((x,y+1))
        if y<w-1 and s[x][y+1]=='#':
            seen[x,y+1]=1
    return np.max(b[b<400])

for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            b=a
            ans=max(ans,bfs(b,i,j,s))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def maze(h, w, sh, sw, list1):
    if list1[sh][sw]=="#":
        return 0
    
    que = deque()
    que.append([sh, sw, 0])
    list2 = list1.copy()
    direct = [(0,1), (0,-1), (1,0), (-1, 0)]
    count = 0
    while que:
        nh, nw, co = que.pop()
        count = co
        co +=1
        li=list(list2[nh])
        li[nw]="#"
        list2[nh]="".join(li)
        for i, j in direct:
            if nh+i<0 or nh+i>=h or nw+j<0 or nw+j>=w:
                pass
            elif list2[nh+i][nw+j]==".":
                que.appendleft([nh+i, nw+j, co])
    return count
        
h, w = (int(x) for x in input().split())
list1 = []
ans = 0
for i in range(h):
    list1.append(input())
for i in range(h):
    for j in range(w):
        ans_ij = maze(h, w, i, j , list1)
        if ans_ij>ans:
            ans=ans_ij
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

start = []
for i in range(h):
    for j in range(w):
        if MAZE[i][j] == ".":
            start.append((i, j))


# BFS
def bfs(start):
    i, j = start
    INF = 10**18
    dist = [[INF] * w for _ in range(h)]
    dist[i][j] = 0
    next_v = deque([start])
    visited = set()
    while next_v:
        i, j = next_v.popleft()
        direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in direction:
            x, y = i+di, j+dj
            if MAZE[x][y] == "#":
                continue
            if (x, y) in visited:
                continue
            dist[x][y] = dist[i][j] + 1
            visited.add((i, j))
            next_v.append((x, y))
    return dist


ans = 0
for s1 in start:
    r = bfs(s1)
    for s2 in start:
        ans = max(ans, r[s2[0]][s2[1]])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
way = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == ".":
            way.append(i*w+j)
wayn = len(way)
mat = 0

for i in way:
    al = [i]
    time = 0
    pp = [i]
    while not len(al) == wayn:
        np = [j for j in pp]
        pp = []
        for j in np:
            if j%w < w-1 and j+1 in way and (not j+1 in al) and (not j+1 in pp):
                pp.append(j+1)
                al.append(j+1)
            if j%w > 0 and j-1 in way and (not j-1 in al) and (not j-1 in pp):
                pp.append(j-1)
                al.append(j-1)
            if j//w < h-1 and j+w in way and (not j+w in al) and (not j+w in pp):
                pp.append(j+w)
                al.append(j+w)
            if j//w > 0 and j-w in way and (not j-w in al) and (not j-w in pp):
                pp.append(j-w)
                al.append(j-w)
        time += 1
    if time > mat:
        mat = time

print(mat)

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w=map(int,input().split())
table=[]

for i in range(h):
    line=input()
    table.append(line)
max_dis=0
for a in range(h):
    for b in range(w):
        if table[a][b]=="#":
            continue
        else:
            i=a
            j=b
            dp=[[0]*w for j_ in range(h)]
            q=queue.Queue()
            dp_set=set()
            q.put((i,j))
            while not q.empty():
                i,j=q.get()
                if (i-1,j) not in dp_set and 0<=i-1 and table[i-1][j]==".":
                    dp[i-1][j]=dp[i][j]+1
                    q.put((i-1,j))
                if (i,j-1) not in dp_set and 0<=j-1 and table[i][j-1]==".":
                    dp[i][j-1]=dp[i][j]+1
                    q.put((i,j-1))
                if (i+1,j) not in dp_set and i+1<=h-1 and table[i+1][j]==".":
                    dp[i+1][j]=dp[i][j]+1
                    q.put((i+1,j))
                if (i,j+1) not in dp_set and j+1<=w-1 and table[i][j+1]==".":
                    dp[i][j+1]=dp[i][j]+1    
                    q.put((i,j+1))
                dp_set.add((i,j))
            for i in range(h):
                for j in range(w):
                    if max_dis<dp[i][j]:
                        max_dis=dp[i][j] 
print(max_dis)

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy as np
h,w=map(int,input().split())
table=[]

for i in range(h):
    line=input()
    table.append(line)
max_dis=[]
for a in range(h):
    for b in range(w):
        if table[a][b]=="#":
            continue
        else:
            i=a
            j=b
            dp=[[0]*w for j_ in range(h)]
            q=queue.Queue()
            dp_set=set()
            q.put((i,j))
            while not q.empty():
                i,j=q.get()
                if (i-1,j) not in dp_set and 0<=i-1 and table[i-1][j]==".":
                    dp[i-1][j]=dp[i][j]+1
                    q.put((i-1,j))
                if (i,j-1) not in dp_set and 0<=j-1 and table[i][j-1]==".":
                    dp[i][j-1]=dp[i][j]+1
                    q.put((i,j-1))
                if (i+1,j) not in dp_set and i+1<=h-1 and table[i+1][j]==".":
                    dp[i+1][j]=dp[i][j]+1
                    q.put((i+1,j))
                if (i,j+1) not in dp_set and j+1<=w-1 and table[i][j+1]==".":
                    dp[i][j+1]=dp[i][j]+1    
                    q.put((i,j+1))
                dp_set.add((i,j))
            dp=np.array(dp)
            max_dis.append(np.max(dp))
            
print(max(max_dis))

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy as np
h,w=map(int,input().split())
table=[]

for i in range(h):
    line=input()
    table.append(line)
max_dis=0
for a in range(h):
    for b in range(w):
        if table[a][b]=="#":
            continue
        else:
            i=a
            j=b
            dp=[[0 for i_ in range(w) ] for j_ in range(h)]
            q=queue.Queue()
            dp_set=set()
            q.put((i,j))
            while not q.empty():
                i,j=q.get()
                if (i-1,j) not in dp_set and 0<=i-1 and table[i-1][j]==".":
                    dp[i-1][j]=dp[i][j]+1
                    q.put((i-1,j))
                if (i,j-1) not in dp_set and 0<=j-1 and table[i][j-1]==".":
                    dp[i][j-1]=dp[i][j]+1
                    q.put((i,j-1))
                if (i+1,j) not in dp_set and i+1<=h-1 and table[i+1][j]==".":
                    dp[i+1][j]=dp[i][j]+1
                    q.put((i+1,j))
                if (i,j+1) not in dp_set and j+1<=w-1 and table[i][j+1]==".":
                    dp[i][j+1]=dp[i][j]+1    
                    q.put((i,j+1))
                dp_set.add((i,j))
            dp=np.array(dp)
            max_dis=max(np.max(dp),max_dis)
            
print(max_dis)

Submission status: Time Limit Exceeded

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    h, w = mi()
    maze = []
    maze.append(['#'] * (w + 2))
    for _ in range(h):
        maze.append(['#'] + li() + ['#'])
    maze.append(['#'] * (w + 2))


    def bfs(point_dist):
        'point から BFS を行い最も離れていた点との距離を返す'
        q = deque([point_dist])
        max_distance = 0
        while q:
            point, dist = q.popleft()
            max_distance = max(max_distance, dist)
            i, j = point
            visited[i][j] = True
            tmp = [(i-1, j), (i, j-1), (i, j+1), (i+1, j)]
            for elm in tmp:
                if not visited[elm[0]][elm[1]] and maze[elm[0]][elm[1]] == '.':
                    q.append([elm, dist+1])
        return max_distance



    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if maze[i][j] == '.':
                visited = [[False] * (w + 2) for _ in range(h + 2)]
                ans = max(ans, bfs([(i, j), 0]))
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

s = ['']*(h+2)

s[0] = "#"*(w+2)
s[h+1] = "#"*(w+2)

for i in range(1,h+1):
	s[i] = '#'+input()+'#'

dn = [[0]*(w+2) for i in range(h+2)]

cnt = 0 

for i in range(1, h+1):
	for j in range(1, w+1):
		if s[i][j] == '.':
			dn[i][j] = cnt
			cnt += 1

d = [[float('inf')]*cnt for i in range(cnt)]

for i in range(1, h+1):
	for j in range(1, w+1):
		if s[i][j] == '.':
			if s[i-1][j] == '.':
				d[dn[i][j]][dn[i-1][j]] = 1
			if s[i+1][j] == '.':
				d[dn[i][j]][dn[i+1][j]] = 1
			if s[i][j-1] == '.':
				d[dn[i][j]][dn[i][j-1]] = 1
			if s[i][j+1] == '.':
				d[dn[i][j]][dn[i][j+1]] = 1
			d[dn[i][j]][dn[i][j]] = 0	

for k in range(cnt):
	for i in range(cnt):
		for j in range(cnt):
			d[i][j] = min(d[i][j],d[i][k] + d[k][j])

ans = 0
for i in range(cnt):
	ans = max(max(d[i]),ans)

print(ans)

Submission status: Time Limit Exceeded

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

field = []
dist = [[float('inf')] * (W * H) for h in range(W * H)]

for _ in range(H):
    field.append(input())

weight = 1
for i in range(H):
    for j in range(W):
        if j + 1 < W and field[i][j] == '.' and field[i][j + 1] == '.':
            dist[W * i + j][W * i + j + 1] = weight
            dist[W * i + j + 1][W * i + j] = weight
        if i + 1 < H and field[i][j] == '.' and field[i + 1][j] == '.':
            dist[W * i + j][W * (i + 1) + j] = weight
            dist[W * (i + 1) + j][W * i + j] = weight


def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


warshall_floyd(dist)

ans = 0
for i in range(H * W):
    for j in range(i + 1, H * W):
        if dist[i][j] != float('inf'):
            ans = max(ans, dist[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    def bfs(S,s,g,h,w):
        dist = np.ones((h,w))*-1
        dist[s[0],s[1]]=0
        que = [s]
        while len(que)>0:
            v = que.pop(0)
            if v==g:
                return dist[v[0]][v[1]]
            if v[0]+1<h:
                if S[v[0]+1][v[1]]=='.' and dist[v[0]+1][v[1]] == -1:
                    dist[v[0]+1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]+1,v[1]])
            if v[0]-1>-1:
                if S[v[0]-1][v[1]]=='.' and dist[v[0]-1][v[1]]==-1:
                    dist[v[0]-1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]-1,v[1]])
            if v[1]+1<w:
                if S[v[0]][v[1]+1]=='.' and dist[v[0]][v[1]+1]==-1:
                    dist[v[0]][v[1]+1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]+1])
            if v[1]-1>-1:
                if S[v[0]][v[1]-1]=='.' and dist[v[0]][v[1]-1]==-1:
                    dist[v[0]][v[1]-1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]-1])
        return -1

    h,w = map(int,input().split())
    S = []
    for i in range(h):
        S.append(input())
    m = 0
    spot = []
    for i in range(h):
        for j in range(w):
            spot.append([i,j])
    for i in range(len(spot)-1):
        for j in range(i+1,len(spot)):
            s,g = spot[i],spot[j]
            if S[s[0]][s[1]]=='#' or S[g[0]][g[1]]=='#':
                continue
            d = bfs(S,s,g,h,w)
            if m<d:
                m = d
    print(int(m))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    def bfs(S,s,g,h,w):
        dist = np.ones((h,w))*-1
        dist[s[0],s[1]]=0
        que = [s]
        while len(que)>0:
            v = que.pop(0)
            if v==g:
                return dist[v[0]][v[1]]
            if v[0]+1<h:
                if S[v[0]+1][v[1]]=='.' and dist[v[0]+1][v[1]] == -1:
                    dist[v[0]+1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]+1,v[1]])
            if v[0]-1>-1:
                if S[v[0]-1][v[1]]=='.' and dist[v[0]-1][v[1]]==-1:
                    dist[v[0]-1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]-1,v[1]])
            if v[1]+1<w:
                if S[v[0]][v[1]+1]=='.' and dist[v[0]][v[1]+1]==-1:
                    dist[v[0]][v[1]+1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]+1])
            if v[1]-1>-1:
                if S[v[0]][v[1]-1]=='.' and dist[v[0]][v[1]-1]==-1:
                    dist[v[0]][v[1]-1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]-1])
        return -1

    h,w = map(int,input().split())
    S = []
    for i in range(h):
        S.append(input())
    m = 0
    for i in range(h):
        for j in range(w):
            s = [i,j]
            if S[i][j]=='#':
                continue
            for k in range(h):
                for l in range(w):
                    g = [k,l]
                    if S[k][l]=='#':
                        continue
                    if m<bfs(S,s,g,h,w):
                        m = bfs(S,s,g,h,w)
    print(int(m))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def bfs_longest(x,y):
    queuex = [x]
    queuey = [y]
    queuedis = [0]
    looked = [[x,y]]
    ans = [0]
    while(len(queuex)):
        nowx = queuex.pop(0)
        nowy = queuey.pop(0)
        nowdis = queuedis.pop(0)
        search = [[nowx+1,nowy],[nowx-1,nowy],[nowx,nowy+1],[nowx,nowy-1]]
        for i in range(len(search)):
            if not (search[i] in looked):
                if maze[search[i][0]][search[i][1]] == ".":
                    queuex.append(search[i][0])
                    queuey.append(search[i][1])
                    queuedis.append(nowdis+1)
                    ans.append(nowdis+1)
                    looked.append([search[i][0],search[i][1]])
    return max(ans)

h,w = map(int,input().split())
maze = [["#" for _ in range(w+2)]for p in range(h+2)]
anchor = []
for i in range(h):
    data = str(input())
    for j in range(w):
        maze[i+1][j+1] = data[j]
        if data[j] == ".":
            anchor.append([i+1,j+1])

answer = 0
for i in range(len(anchor)):
    answer = max(bfs_longest(anchor[i][0],anchor[i][1]),answer)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def bfs_longest(x,y):
    queuex = [x]
    queuey = [y]
    queuedis = [0]
    looked = [[x,y]]
    ans = [0]
    while(len(queuex)):
        nowx = queuex.pop(0)
        nowy = queuey.pop(0)
        nowdis = queuedis.pop(0)
        search = [[nowx+1,nowy],[nowx-1,nowy],[nowx,nowy+1],[nowx,nowy-1]]
        for i in range(len(search)):
            if not (search[i] in looked):
                if maze[search[i][0]][search[i][1]] == ".":
                    queuex.append(search[i][0])
                    queuey.append(search[i][1])
                    queuedis.append(nowdis+1)
                    ans.append(nowdis+1)
                    looked.append([search[i][0],search[i][1]])
    return max(ans)

h,w = map(int,input().split())
maze = [["#" for _ in range(w+2)]for p in range(h+2)]
anchor = []
for i in range(h):
    data = str(input())
    for j in range(w):
        maze[i+1][j+1] = data[j]
        if data[j] == ".":
            anchor.append([i+1,j+1])

answer = 0
for i in range(len(anchor)):
    answer = max(bfs_longest(anchor[i][0],anchor[i][1]),answer)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
l=[list(map(str,input())) for _ in range(h)]  
def maze(MAZE,sx,sy):
  dmap=[[h*w+1]*w for _ in range(h)]
  dmap[sx][sy]=0
  cand=[]
  cand.append([sx,sy])
  while len(cand)!=0:
    x,y=cand.pop()
    for next_y,next_x in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
      if 0<=next_x<=h-1 and 0<=next_y<=w-1 and MAZE[next_x][next_y]=='.':
        if dmap[x][y]+1<dmap[next_x][next_y]:
          dmap[next_x][next_y]=dmap[x][y]+1
          cand.append([next_x,next_y])
  return max([dmap[i][j] for i in range(h) for j in range(w) if dmap[i][j]<=h*w])
c=0
for ix in range(h):
  for iy in range(w):
    if l[ix][iy]!='#':
      d=maze(l,ix,iy)
      if c<d:
        c=d
print(c)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
l=[list(map(str,input())) for _ in range(h)]  
def maze(MAZE,sx,sy,gx,gy):
  dmap=[[h*w]*w for _ in range(h)]
  dmap[sx][sy]=0
  dist=h*w
  cand=[]
  visited=set()
  if sx==gx and sy==gy:
    dist=0
  else:
    cand.append([sx,sy])
  while len(cand)!=0:
    x,y=cand.pop()
    visited.add((x,y))
    for next_y,next_x in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
      if next_x==gx and next_y==gy:
        if dist>dmap[x][y]+1:
          dist=dmap[x][y]+1
        break
      elif 0<=next_x<=h-1 and 0<=next_y<=w-1 and MAZE[next_x][next_y]=='.' and not (next_x,next_y) in visited:
        cand.append([next_x,next_y])
        dmap[next_x][next_y]=min(dmap[x][y]+1,dmap[next_x][next_y])
  return dist
c=0
for ix in range(h):
  for iy in range(w):
    if l[ix][iy]!='#':
      for jx in range(h):
        for jy in range(w):
          if l[jx][jy]!='#':
            d=maze(l,ix,iy,jx,jy)
            if c<d:
              c=d
print(c)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
sys.setrecursionlimit(10**5)

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

# for e in field:
#    print("".join(e))

# H 3 W 5
poss = []
for h in range(H):
    for w in range(W):
        if field[h][w] == '.':
            poss.append([h, w])


def get_dist(start, goal):
    step = 0
    pattern = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    current_positions = [start]
    ifFound = False
    while not ifFound:
        next_position = []
        step += 1
        for c_p in current_positions:
            for pat in pattern:
                n_p = [c_p[0] + pat[0], c_p[1] + pat[1]]
                if n_p[0] >= 0 and n_p[0] < H and n_p[1] >= 0 and n_p[1] < W and field[n_p[0]][n_p[1]] == '.':
                    if n_p == goal:
                        ifFound = True
                    next_position.append(n_p)
        # think when its unreachable
        current_positions = next_position
    return step


result = []
for comb in list(itertools.combinations(poss, 2)):
    result.append(get_dist(comb[0], comb[1]))
    result.append(get_dist(comb[1], comb[0]))

print(max(result))