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:
import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
for i in range(len(CORD)):
    for j in range(i+1, len(CORD)):
        st, en = CORD[i], CORD[j]
        if MP[st[0]][st[1]] == "." and MP[en[0]][en[1]] == ".":
            QUE=deque()
            visited = [[0]*W for i in range(H)]
            visited[st[0]][st[1]] = 1
            QUE.append((st[0], st[1], 0))
            res = 0
            while QUE:
                ii, jj, dist = QUE.popleft()
                if (ii, jj) == en:
                    res = dist
                    visited.clear()
                    break
                for iii, jjj in [(ii-1,jj),(ii+1,jj),(ii,jj-1),(ii,jj+1)]:
                    if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not visited[iii][jjj]:
                        QUE.append((iii, jjj, dist+1))
                        visited[iii][jjj] = 1

            max_dist = max(res, max_dist)

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
visited=set()
for i in range(len(CORD)):
    for j in range(i+1, len(CORD)):
        st, en = CORD[i], CORD[j]
        if MP[st[0]][st[1]] == "." and MP[en[0]][en[1]] == ".":
            QUE=deque()
            visited.add(st)
            QUE.append((st[0], st[1], 0))
            res = 0
            while QUE:
                ii, jj, dist = QUE.popleft()
                if (ii, jj) == en:
                    res = dist
                    visited.clear()
                    break
                for iii, jjj in [(ii-1,jj),(ii+1,jj),(ii,jj-1),(ii,jj+1)]:
                    if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                        QUE.append((iii, jjj, dist+1))
                        visited.add((iii, jjj))

            max_dist = max(res, max_dist)

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
visited=set()
for i in range(len(CORD)):
    for j in range(i+1, len(CORD)):
        st, en = CORD[i], CORD[j]
        if MP[st[0]][st[1]] == "." and MP[en[0]][en[1]] == ".":
            QUE=deque()
            visited.add(st)
            QUE.append((st[0], st[1], 0))
            res = 0
            while QUE:
                ii, jj, dist = QUE.popleft()
                if (ii, jj) == en:
                    res = dist
                    visited.clear()
                    break
                iii, jjj = ii-1, jj
                if iii >= 0 and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                    QUE.append((iii, jjj, dist+1))
                    visited.add((iii, jjj))

                iii, jjj = ii+1, jj
                if iii < H and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                    QUE.append((iii, jjj, dist+1))
                    visited.add((iii, jjj))

                iii, jjj = ii, jj-1
                if jjj >= 0 and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                    QUE.append((iii, jjj, dist+1))
                    visited.add((iii, jjj))
                iii, jjj = ii, jj+1
                if jjj < W and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                    QUE.append((iii, jjj, dist+1))
                    visited.add((iii, jjj))


            max_dist = max(res, max_dist)

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
H,W = (int(x) for x in input().split())
a = []
que = []
dis =[]
longDis = 0

for i in range(H):
    a += list(input().split())

h = -1
w = 0

for _ in range(H*W):
    k = 0
    dis = [k]
    l = 0

    if h < H-1:
        h += 1
    else:
        h = 0
        w += 1

    if a[h][w] != '.':
        continue

    que += [[h,w]]
    i = h
    j = w
    
    while True:
        k = dis[l] + 1

        #上
        if i-1 >= 0 and a[i-1][j] =='.':
            if [i-1,j] not in que:
                que += [[i-1,j]]
                dis += [k]

        #下
        if i+1 < H and a[i+1][j] == '.':
            if [i+1,j] not in que:
                que += [[i+1,j]]
                dis += [k]

        #左
        if j-1 >= 0 and a[i][j-1] == '.':
            if [i,j-1] not in que:
                que += [[i,j-1]]
                dis += [k]

        #右
        if j+1 < W and a[i][j+1] == '.':
            if [i,j+1] not in que:
                que += [[i,j+1]]
                dis += [k]

        l += 1

        if l == len(que):
            break
        
        i = que[l][0]
        j = que[l][1]


    for i in range(len(dis)):
        if dis[i] > longDis:
            longDis = dis[i]

    dis.clear()
    que.clear()

print(longDis)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
visited=set()
for st, en in combinations(CORD, 2):
    if MP[st[0]][st[1]] == "." and MP[en[0]][en[1]] == ".":
        QUE=deque()
        visited.add(st)
        QUE.append((st[0], st[1], 0))
        res = 0
        while QUE:
            ii, jj, dist = QUE.popleft()
            if (ii, jj) == en:
                res = dist
                visited.clear()
                # print("st:{} en:{} dist:{}".format(st, en, dist))
                break
            for iii, jjj in [(ii-1,jj),(ii+1,jj),(ii,jj-1),(ii,jj+1)]:
                if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                    QUE.append((iii, jjj, dist+1))
                    visited.add((iii, jjj))

        max_dist = max(res, max_dist)

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
visited=set()
for st, en in combinations(CORD, 2):
    if MP[st[0]][st[1]] == "." and MP[en[0]][en[1]] == ".":
        QUE=deque()
        visited.add(st)
        QUE.append((st[0], st[1], 0))
        res = 0
        while QUE:
            ii, jj, dist = QUE.popleft()
            if (ii, jj) == en:
                res = dist
                visited.clear()
                # print("st:{} en:{} dist:{}".format(st, en, dist))
                break
            for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
                iii,jjj = ii+di, jj+dj
                if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                    QUE.append((iii, jjj, dist+1))
                    visited.add((iii, jjj))

        max_dist = max(res, max_dist)

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
for st, en in combinations(CORD, 2):
    if MP[st[0]][st[1]] == "." and MP[en[0]][en[1]] == ".":
        QUE=deque()
        visited={ st }
        QUE.append((st[0], st[1], 0))
        res = 0
        while QUE:
            ii, jj, dist = QUE.popleft()
            if (ii, jj) == en:
                res = dist
                # print("st:{} en:{} dist:{}".format(st, en, dist))
                break
            for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
                iii,jjj = ii+di, jj+dj
                if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not (iii, jjj) in visited:
                    QUE.append((iii, jjj, dist+1))
                    visited.add((iii, jjj))

        max_dist = max(res, max_dist)

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
grid=[None]*H
for i in range(H):
  grid[i]=input()
  
from collections import deque
ans=0
for y1 in range(H):
  for x1 in range(W):
    for y2 in range(H):
      for x2 in range(W):
        if grid[y2][x2]=="#" or grid[y1][x1]=="#":
          continue
        q=deque()
        q.append([y1,x1,0])
        seen=[[False for j in range(W)] for i in range(H)]
        while q:
          node=q.popleft()
          y=node[0]
          x=node[1]
          dist=node[2]
          if seen[y][x]:
            continue
          if grid[y][x]=="#":
            continue
          if y==y2 and x==x2:
            if ans<dist:
              ans=dist
          seen[y][x]=True
          if y-1>=0:
            q.append([y-1,x,dist+1])
          if y+1<H:
            q.append([y+1,x,dist+1])
          if x-1>=0:
            q.append([y,x-1,dist+1])
          if x+1<W:
            q.append([y,x+1,dist+1])
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
l=set()
for i in range(h):
    t=input()
    for j in range(w):
        if t[j]==".":
            l.add((i,j))
ans=0
from collections import deque
for i,j in l:
    q=deque([(i,j,0)])
    s=set()
    while q:
        x,y,z=q.popleft()
        s.add((x,y))
        tf=True
        if (x+1,y) in l and (x+1,y) not in s:
            q.append((x+1,y,z+1))
            tf=False
        if (x-1,y) in l and (x-1,y) not in s:
            q.append((x-1,y,z+1))
            tf=False
        if (x,y+1) in l and (x,y+1) not in s:
            q.append((x,y+1,z+1))
            tf=False
        if (x,y-1) in l and (x,y-1) not in s:
            q.append((x,y-1,z+1))
            tf=False
        if tf:
            ans=max(ans,z)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
import copy

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

def solve(s):
    M = copy.deepcopy(S)
    d = ((1, 0), (-1, 0), (0, -1), (0, 1))
    queue = deque([s])
    steps = [[-1 for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        M[cy][cx] = '#'
        for i in d:
            ny = cy+i[0]
            nx = cx+i[1]
            # はみ出さないかつ通ってない
            if (0<=ny<H and 0<=nx<W) and M[ny][nx]!='#':
                queue.append([ny, nx])
                steps[ny][nx] = steps[cy][cx] + 1
        
    return max([max(i) for i in steps])

maxStep = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '.':
        maxStep = max(solve([s[0], s[1]]), maxStep)

print(maxStep)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint

INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]

# 入力
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * w + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx and nx < w and -1 < ny and ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    #print(wsmap(y, x))
                    #print("--")
                    #print("y, x {0}, {1}".format(ny, nx))
                    #print(wsmap(ny, nx))
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
#print(dp)
res = -1
for i in range(h * w):
    for j in range(h * w):
        if dp[i][j] != INF:
            res = max(res, dp[i][j])
print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
#-------------------------------------------------------------------
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
H,W = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

S=[ "" for _ in range(H+2) ]
#p(S)

S[0]="#"*(W+2)
S[H+1]="#"*(W+2)
for h in range(1,H+1):
	s = input()
	S[h] = "#" + s + "#"

#p(S)

XY=[[1,0],[-1,0],[0,1],[0,-1]]

INF=float("inf") # 正の無限大
ans=0

from collections import deque

for h in range(1,H+1):
	for w in range(1,W+1):

		if S[h][w]=="#": continue

		M=[[ INF for w in range(W+2) ] for h in range(H+2)]
		M[h][w]=0

		Q = deque()
		Q.append([h,w])
		mmax=0

		#p("Q=",Q)
		
		while Q:
			h,w=Q.pop()
			
			if S[h][w]=="#": continue
			
			m = M[h][w]
			mmax=max(mmax,m)
			for x,y in XY:
				if S[h+y][w+x]=="#": continue
				
				if M[h+y][w+x] > (m+1):
					M[h+y][w+x] = m+1
					Q.append([h+y,w+x])
					mmax=max(mmax,m+1)

			#p("h,w,Q,m=",h,w,Q,m)

		for MH in M:
			for m in MH:
				if m==INF: continue
				ans=max(ans,m)


#for m in M:
#	print(m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S_ = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
for i, j in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S_[i][j] == '.':
        S = copy.deepcopy(S_)
        q = collections.deque([(i, j, 0)])
        while q:
            x, y, d = q.popleft()
            S[x][y] = ','
            for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                if S[x + dx][y + dy] == '.':
                    X, Y = x + dx, y + dy
                    q += [(X, Y, d + 1)]
        ans = max(d, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]<0 and S[data[0]-1][data[1]]=='.':
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]<0 and S[data[0]+1][data[1]]=='.':
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]<0 and S[data[0]][data[1]-1]=='.':
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]<0 and S[data[0]][data[1]+1]=='.':
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-1]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
      if data[2]>out:
        out=data[2]
      
print(out)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]<0 and S[data[0]-1][data[1]]=='.':
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]<0 and S[data[0]+1][data[1]]=='.':
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]<0 and S[data[0]][data[1]-1]=='.':
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]<0 and S[data[0]][data[1]+1]=='.':
    q.append([data[0], data[1]+1, data[2]+1])
  return data[2]

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-1]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      tmp=f(data)
      if tmp>out:
        out=tmp
      
print(out)

Submission status: Time Limit Exceeded

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))

        while q:
            y, x, v = q.popleft()
            m[y][x] = v
            for dj, di in ((y, x + 1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                if ans < v+1:
                    ans = v+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]<0 and S[data[0]-1][data[1]]=='.':
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]<0 and S[data[0]+1][data[1]]=='.':
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]<0 and S[data[0]][data[1]-1]=='.':
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]<0 and S[data[0]][data[1]+1]=='.':
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-1]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
    tmp=np.max(m)
    if tmp>out:
      out=tmp
      
print(out)

Submission status: Time Limit Exceeded

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))

        while q:
            y, x, v = q.popleft()
            m[y][x] = v
            for d in ((y, x + 1), (y, x-1), (y+1, x), (y-1, x)):
                dj, di = d
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                if ans < v+1:
                    ans = v+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]<0 and S[data[0]-1][data[1]]=='.':
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]<0 and S[data[0]+1][data[1]]=='.':
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]<0 and S[data[0]][data[1]-1]=='.':
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]<0 and S[data[0]][data[1]+1]=='.':
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-1]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
    tmp=max([max(m[i]) for i in range(1, H+1)])
    if tmp>out:
      out=tmp
      
print(out)

Submission status: Time Limit Exceeded

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))

        while q:
            y, x, v = q.popleft()
            m[y][x] = v
            for d in ((y, x + 1), (y, x-1), (y+1, x), (y-1, x)):
                dj, di = d
                if S[dj][di] == "." and m[dj][di] == -1:
                    q.append((dj, di, v+1))
                    if ans < v+1:
                        ans = v+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]<0 and S[data[0]-1][data[1]]=='.':
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]<0 and S[data[0]+1][data[1]]=='.':
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]<0 and S[data[0]][data[1]-1]=='.':
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]<0 and S[data[0]][data[1]+1]=='.':
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-1]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
    tmp=max([max(m[i]) for i in range(1, H+1)])
    if tmp>out:
      out=tmp
      
print(out)

Submission status: Time Limit Exceeded

Solution code:
# ABC151 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from collections import deque
def bfs(sy,sx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="#":
                continue
            if path[ny][nx]=="." and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
        ret=-1
        for i in range(h):
            for j in range(w):
                ret=max(visited[i][j],ret)
    return ret
h,w=nm()
path=[input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=0,0
ans=0
for i in range(h):
    for j in range(w):
        if path[i][j]=='#':
            continue
        sy,sx=i,j
        visited = [[-1]*w for i in range(h)]
        t=bfs(sy,sx)
        ans=max(t,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

def sol():
    h,w=map(int,input().split())
    d=[]
    for i in range(h):
        s=input()
        d.append(s)
    x=h*w
    p=[[x+1]*x for i in range(x)]
    for i in range(x):
        for j in range(i+1):
            if i==j:
                p[i][j]=0
                p[j][i]=0
            ih,iw,jh,jw=i//w,i%w,j//w,j%w
            if d[ih][iw]==d[jh][jw]=="." and ih==jh and abs(iw-jw)==1:
                p[i][j]=1
                p[j][i]=1
            if d[ih][iw]==d[jh][jw]=="." and iw==jw and abs(ih-jh)==1:
                p[i][j]=1
                p[j][i]=1


    for i in range(x):
        ih,iw=i//w,i%w
        if d[ih][iw]!=".": continue
        for j in range(x):
            ih,iw=i//w,i%w
            jh,jw=j//w,j%w
            if d[jh][jw]!=".": continue
            for k in range(x):
                ih,iw=i//w,i%w
                jh,jw=j//w,j%w
                kh,kw=k//w,k%w
                if d[kh][kw]==".":
                    p[j][k]=min(p[j][k],p[j][i]+p[i][k])
    ans=0
    for i in p:
        for j in i:
            if j<x+1:
                ans=max(ans,j)
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

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

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

ans = 0

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


def bfs(x, y):
    m = []
    for _ in range(H):
        m.append([-1] * W)

    q = deque()
    q.append([y, x, 0])
    maximus = 0

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        for dd in d:
            dj = j + dd[0]
            di = i + dd[1]
            if dj < 0 or dj >= H or di < 0 or di >= W or m[dj][di] != -1 or S[dj][di] == "#":
                continue
            q.append([dj, di, v+1])
            if maximus < v+1:
                maximus = v+1

    return maximus


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.pop()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
        
    A = [a for b in A for a in b if a!=inf]
    ans = max(ans,max(A))
    
print(ans)