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:
def main():
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j]==".":
                a[i][j]=99999
    ans=0
    import collections
    from copy import deepcopy
    direction=[[0,1],[0,-1],[1,0],[-1,0]]
    for sh in range(h):
        for sw in range(w):
            tmp=0
            if a[sh][sw]==99999:
                field=deepcopy(a)
                field[sh][sw]=0
                completed=[]
                next_list=collections.deque([[sh,sw]])
                while next_list:
                    n=next_list.popleft()
                    completed.append(n)
                    for dx,dy in direction:
                        ny,nx=n[0]+dy,n[1]+dx
                        if 0<=ny<=h-1 and 0<=nx<=w-1 and field[ny][nx]!="#" and [ny,nx] not in completed:
                            field[ny][nx]=min(field[n[0]][n[1]]+1,field[ny][nx])
                            next_list.append([ny,nx])
                for i in range(h):
                    for j in range(w):
                        if field[i][j]!="#":
                            tmp=max(tmp,field[i][j])
                ans=max(ans,tmp)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]==".":
            a[i][j]=99999
ans=0
import collections
from copy import deepcopy
direction=[[0,1],[0,-1],[1,0],[-1,0]]
for sh in range(h):
    for sw in range(w):
        tmp=0
        if a[sh][sw]==99999:
            field=deepcopy(a)
            field[sh][sw]=0
            completed=[]
            next_list=collections.deque([[sh,sw]])
            while next_list:
                n=next_list.popleft()
                completed.append(n)
                for dx,dy in direction:
                    ny,nx=n[0]+dy,n[1]+dx
                    if 0<=ny<=h-1 and 0<=nx<=w-1 and field[ny][nx]!="#" and [ny,nx] not in completed:
                        field[ny][nx]=min(field[n[0]][n[1]]+1,field[ny][nx])
                        next_list.append([ny,nx])
            for i in range(h):
                for j in range(w):
                    if field[i][j]!="#":
                        tmp=max(tmp,field[i][j])
            ans=max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
from itertools import product

h, w = map(int, input().split())
S = np.array([['' for i in range(w)] for j in range(h)])
for i in range(h):
  line = input()
  for j in range(w):
    S[i][j] = line[j]
#print(S)
  
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]

q = deque()

def update(vs, i, j, x, q):
  if vs[i, j] != np.inf or S[i, j] == '#':
    return
  vs[i, j] = x
  q.append((i,j))

mx = 0
for i, j in product(range(h), range(w)):
  if S[i, j] == '#':
    continue
  vs = np.array([[np.inf for i in range(w)] for j in range(h)])
  x = 0
  update(vs, i, j, x , q)
  while len(q) > 0:
    #print(q)
    #print(vs)
    # x += 1
    current_q = q.popleft()
    qi, qj = current_q[0], current_q[1]
    for k in range(4):
      ni, nj = qi + di[k], qj + dj[k]
      if not(0 <= ni < h) or not(0 <= nj < w):
        continue
      update(vs, ni, nj, vs[qi][qj]+1, q)
  for i, j in product(range(h), range(w)):
    if vs[i,j] == np.inf: continue
    mx = max(mx, vs[i,j])
print(int(mx))

Submission status: Time Limit Exceeded

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

load=[]
for i in range(0,H):
    for j in range(0,W):
        if S[i][0][j]=='.':
            load.append((i,j))

ans=0
for i,j in load:
    start=(i,j)
    dp=[[500 for i in range(0,W)] for i in range(0,H)]
    dp[i][j]=0
    q=[]
    q.append((i,j))
    sub=[]
    while q!=[]:
        while q!=[]:
            x=q[0]
            q.remove(x)
            s=x[0]
            t=x[1]
            if (s+1,t) in load and dp[s+1][t]>dp[s][t]+1:
                sub.append((s+1,t))
                dp[s+1][t]=dp[s][t]+1
            if (s,t+1) in load and dp[s][t+1]>dp[s][t]+1:
                sub.append((s,t+1))
                dp[s][t+1]=dp[s][t]+1
            if (s-1,t) in load and dp[s-1][t]>dp[s][t]+1:
                sub.append((s-1,t))
                dp[s-1][t]=dp[s][t]+1
            if (s,t-1) in load and dp[s][t-1]>dp[s][t]+1:
                sub.append((s,t-1))
                dp[s][t-1]=dp[s][t]+1
            if q==[]:
                q=sub
                sub=[]
                break
    test=max(dp[i][j] for i in range(0,H) for j in range(0,W) if (i,j) in load)
    if test>ans:
        ans=test
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools

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

for i in range(H):
  w = list(input())
  labyrinth[i] = w
  for j in range(W):
    if w[j] == ".":
      points.append([j,i])


com = list(itertools.combinations(points,2))

#移動パターン
movex = [1,0,-1,0]
movey = [0,1,0,-1]

def shortest_path(sx,sy,gx,gy,labyrinth):
  INF = 10 ** 2

  x_length = W
  y_length = H
  distance = [[INF for i in range(x_length)] for j in range(y_length)]
  
  queue = deque()
  queue.append((sx,sy))
  distance[sy][sx] = 0
  
  #幅優先探索
  def bfs():
    #探索候補がある限り
    while len(queue) > 0:
      x,y = queue.popleft()
      
      #ゴールの座標に達したら中止
      if x == gx and y == gy:
        break
        
      for i in range(0, 4):
        nx = x + movex[i]
        ny = y + movey[i]

        #探索迷路内であり
        if (0 <= nx and ny < y_length and 0 <= ny and nx < x_length):
          #通行可能かつ未到達であれば
          if (labyrinth[ny][nx] != "#"  and distance[ny][nx] == INF):
            queue.append((nx,ny))
            distance[ny][nx] = distance[y][x] + 1
    
    return distance[gy][gx]

  return bfs()

path = []

for i in range(len(com)):
  s = com[i][0]
  g = com[i][1]
  sx = s[0]
  sy = s[1]
  gx = g[0]
  gy = g[1]
  dist = shortest_path(sx,sy,gx,gy,labyrinth)
  path.append(dist)
  
print(max(path))

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(S, start):
    H = len(S)
    W = len(S[0])
    stack = [start]
    closed = set()
    r = 0
    while stack:
        next_stack = []
        for s in stack:
            closed.add(s)
            for d in (-1, 1):
                for p in ((s[0] + d, s[1]), (s[0], s[1] + d)):
                    if p in closed:
                        continue
                    if p[0] < 0 or H <= p[0] or p[1] < 0 or W <= p[1]:
                        continue
                    if S[p[0]][p[1]] == "#":
                        continue
                    next_stack.append(p)
        stack = next_stack
        r += 1
    return r - 1


def main():
    H, W = read_values()
    S = [input() for _ in range(H)]

    res = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                continue
            res = max(res, f(S, (h, w)))
    print(res)

        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))
maps2 = list(maps2)

for i in range(1, H + 1):
    for l in range(1, W + 1):
        maps = copy.deepcopy(maps2)
        if maps2[i][l] != "#":
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))
maps2 = list(maps2)

for i in range(1, H + 1):
    for l in range(1, W + 1):
        maps = copy.deepcopy(maps2)
        if maps2[i][l] != "#":
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        maps = copy.deepcopy(maps2)
        if maps2[i][l] != "#":
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        maps = copy.deepcopy(maps2)
        if maps2[i][l] != "#":
            pos = [[i, l, 0]]
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth
                maps[y][x] = "$"

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, deque, defaultdict
from functools import lru_cache

h,w=map(lambda x:int(x),input().split())
g=[[0 for j in range(w)] for i in range(h)]
s=set()
for i in range(h):
	x = input()
	for j in range(len(x)):
		if x[j] == '#':
			s.add((i,j))
		g[i][j] = x[j]

tmax=0
adj=[[1e9 for i in range(h * w)] for j in range(h*w)]
for i in range(h*w):
	c = i%w
	r=i//w
	if g[r][c] == '#':
		continue
	adj[i][i]=0
	if c + 1 < w and g[r][c+1] =='.':
		adj[i][i+1]=1
	if c-1 >=0 and g[r][c-1]=='.':
		adj[i][i-1]=1
	if r+1<h and g[r+1][c]=='.':
		adj[i][i+w]=1
	if r-1>=0 and g[r-1][c]=='.':
		adj[i][i-w]=1

tmax = 0
for k in range(h*w):
	for i in range(w*h):
		for j in range(h*w):
			if g[k//w][k%w] == '#' or g[i//w][i%w] == '#' or g[j//w][j%w]=='#':
				continue
			adj[i][j]=min(adj[i][j], adj[i][k] + adj[k][j])
for i in range(h*w):
	for j in range(h*w):
		if adj[i][j] < 1e9:
			tmax=max(tmax, adj[i][j])
print(tmax)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
lst = []
for _ in range(H):
	S = list(map(str, input()))
	lst.append(S)
	
distance_ord = [[400 for _ in range(W)] for _ in range(H)]
for i in range(H):
	for j in range(W):
		if lst[i][j] == "#":
			distance_ord[i][j] = -1
	
ans = 0


# 入力: 座標、かかってる時間
# 出力: 最深部に到達するまでにかかる時間
def bfs(sh, sw):
	distance = copy.deepcopy(distance_ord)
	distance[sh][sw] = 0
	Q = deque([[sh, sw, 0]])
	while Q:
		ch, cw, time = Q.popleft()
		if distance[ch][cw] < time: # すでにもっと早い道が存在
			continue
		for move_h, move_w in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			new_h, new_w = ch + move_h, cw + move_w 
			if 0 <= new_h and new_h <= H - 1 and 0 <= new_w and new_w <= W - 1:
				if lst[new_h][new_w] == "#": continue
				Q.append([new_h, new_w, time + 1])
				distance[new_h][new_w] = min(distance[new_h][new_w], time + 1)
	res = 0
	for i in range(H):
		res = max(res, max(distance[i]))
	
	return res
	
# スタート位置全通り
for sh in range(H):
	for sw in range(W):
		if lst[sh][sw] == "#": continue # 壁の時はスキップ
		ans = max(ans, bfs(sh, sw))
		
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class Graph():
    def __init__(self):
        self.value = defaultdict(list)
        self.res = {}

    def addConnection(self, parent, child):
        self.value[parent].append(child)

    def addWays(self, node):
        for item in node:
            self.res[item] = 0

    def BFS(self, start, goal):
        visited = [start]
        queue = [start]
        while queue:
            x = queue.pop(0)
            # print(x, end=" ")
            for item in self.value[x]:
                if item not in visited:
                    queue.append(item)
                    visited.append(item)
                    self.res[item] = self.res[x] + 1
        if not self.res:
            return 0
        return self.res[goal]


h, w = list(map(int, input().split()))
s = [["#" for _ in range(w + 2)]]
for _ in range(h):
    s.append(["#"] + list(input()) + ["#"])
s.append(["#" for _ in range(w + 2)])
node = [i for i in range((h + 2) * (w + 2))]
size = len(node)
g_list = [Graph() for _ in node]
for ii in range(1, h + 1):
    for jj in range(1, w + 1):
        convd_index = ii * (w + 2) + jj
        g_list[convd_index].addWays(node)
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                convd = i * (w + 2) + j
                if s[i + 1][j] == ".":
                    g_list[convd_index].addConnection(
                        convd, ((i + 1) * (w + 2) + j))
                if s[i - 1][j] == ".":
                    g_list[convd_index].addConnection(
                        convd, ((i - 1) * (w + 2) + j))
                if s[i][j + 1] == ".":
                    g_list[convd_index].addConnection(
                        convd, (i * (w + 2) + j + 1))
                if s[i][j - 1] == ".":
                    g_list[convd_index].addConnection(
                        convd, (i * (w + 2) + j - 1))
res = 0
for start in range(size):
    for goal in range(size):
        if start == goal:
            continue
        bfs = g_list[start].BFS(start, goal)
        if bfs > res:
            res = bfs
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      while q:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
maze = [list(input()) for _ in range(H)]
dp = [[INF]*W*H for _ in range(W*H)]

for i in range(H*W):
	for j in range(H*W):
		if maze[i//W][i%W] == "#":
			continue
		if maze[j//W][j%W] == "#":
			continue
		if i == j:
			dp[i][j] = 0
		if i + W == j:
			dp[i][j] = 1
		if i + 1 == j:
			if i%W == W - 1:
				continue
			dp[i][j] = 1
		if i - W == j:
			dp[i][j] = 1
		if i - 1 == j:
			if i%W == 0:
				continue
			dp[i][j] = 1

# for i in range(W*H):
# 	for s in range(W*H):
# 		for e in range(W*H):
# 			# if maze[i//W][i%W] == "#":
# 			# 	continue
# 			# if maze[s//W][s%W] == "#":
# 			# 	continue
# 			# if maze[e//W][e%W] == "#":
# 			# 	continue
# 			dp[s][e] = min(dp[s][e], dp[s][i] + dp[i][e]);

for i in range(W*H):
    for j, c2 in enumerate(row[i] for row in dp):
           for k, (c1, c3) in enumerate(zip(dp[j], dp[i])):
               if c1 > c2+c3:
                   dp[j][k] = c2+c3

ma = 0
for i in range(len(dp)):
	for j in range(len(dp[i])):
		if dp[i][j] == INF:
			continue
		ma = max(ma, dp[i][j])

print(int(ma))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
maze = [list(input()) for _ in range(H)]
dp = [[INF]*W*H for _ in range(W*H)]

for i in range(H*W):
	for j in range(H*W):
		if maze[i//W][i%W] == "#":
			continue
		if maze[j//W][j%W] == "#":
			continue
		if i == j:
			dp[i][j] = 0
		if i + W == j:
			dp[i][j] = 1
		if i + 1 == j:
			if i%W == W - 1:
				continue
			dp[i][j] = 1
		if i - W == j:
			dp[i][j] = 1
		if i - 1 == j:
			if i%W == 0:
				continue
			dp[i][j] = 1

for i in range(W*H):
	for s in range(W*H):
		for e in range(W*H):
			if maze[i//W][i%W] == "#":
				continue
			if maze[s//W][s%W] == "#":
				continue
			if maze[e//W][e%W] == "#":
				continue
			dp[s][e] = min(dp[s][e], dp[s][i] + dp[i][e]);

ma = 0
for i in range(len(dp)):
	for j in range(len(dp[i])):
		if dp[i][j] == INF:
			continue
		ma = max(ma, dp[i][j])

print(int(ma))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
maze = [list(input()) for _ in range(H)]

import numpy as np
dp = np.array([[INF]*W*H for _ in range(W*H)])

for i in range(H*W):
	for j in range(H*W):
		if maze[i//W][i%W] == "#":
			continue
		if maze[j//W][j%W] == "#":
			continue
		if i == j:
			dp[i][j] = 0
		if i + W == j:
			dp[i][j] = 1
		if i + 1 == j:
			if i%W == W - 1:
				continue
			dp[i][j] = 1
		if i - W == j:
			dp[i][j] = 1
		if i - 1 == j:
			if i%W == 0:
				continue
			dp[i][j] = 1

for i in range(W*H):
	for s in range(W*H):
		for e in range(W*H):
			if maze[i//W][i%W] == "#":
				continue
			if maze[s//W][s%W] == "#":
				continue
			if maze[e//W][e%W] == "#":
				continue
			dp[s][e] = min(dp[s][e], dp[s][i] + dp[i][e]);

ma = 0
for i in range(len(dp)):
	for j in range(len(dp[i])):
		if dp[i][j] == INF:
			continue
		ma = max(ma, dp[i][j])

print(int(ma))

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

def replace(s, n, c):
    if n < 0 or n >= len(s):
        return s
    return s[:n]+c[0]+s[n+1:]

h, w = map(int, input().split())
l = [input() for _ in range(h)]

def dist(m, x1, y1, x2, y2):
    q = queue.Queue()
    q.put((x1, y1, 0))
    checked=[[False for _ in range(w)] for __ in range(h)]
    while not q.empty():
        x, y, count = q.get()
        if (x, y) == (x2, y2):
            return count
        if x > 0 and m[y][x-1] == "." and checked[y][x-1] == False:
            checked[y][x-1] = True
            q.put((x-1, y, count+1))
        if y > 0 and m[y-1][x] == "." and checked[y-1][x] == False:
            checked[y-1][x] = True
            q.put((x, y-1, count+1))
        if x < w-1 and m[y][x+1] == "." and checked[y][x+1] == False:
            checked[y][x+1] = True
            q.put((x+1, y, count+1))
        if y < h-1 and m[y+1][x] == "." and checked[y+1][x] == False:
            checked[y+1][x] = True
            q.put((x, y+1, count+1))

ans = 0
for i in range(h):
    for j in range(w):
        for _i in range(h):
            for _j in range(w):
                if l[i][j] == "." and l[_i][_j] == ".":
                    ans = max(ans, dist(l, j, i, _j, _i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

def replace(s, n, c):
    if n < 0 or n >= len(s):
        return s
    return s[:n]+c[0]+s[n+1:]

h, w = map(int, input().split())
l = [input() for _ in range(h)]

def dist(m, x1, y1, x2, y2):
    q = queue.Queue()
    q.put((x1, y1, 0))
    while not q.empty():
        x, y, count = q.get()
        if (x, y) == (x2, y2):
            return count
        if x > 0 and m[y][x-1] == ".":
            m[y] = replace(m[y], x-1, "#")
            q.put((x-1, y, count+1))
        if y > 0 and m[y-1][x] == ".":
            m[y-1] = replace(m[y-1], x, "#")
            q.put((x, y-1, count+1))
        if x < w-1 and m[y][x+1] == ".":
            m[y] = replace(m[y], x+1, "#")
            q.put((x+1, y, count+1))
        if y < h-1 and m[y+1][x] == ".":
            m[y+1] = replace(m[y+1], x, "#")
            q.put((x, y+1, count+1))

ans = 0
for i in range(h):
    for j in range(w):
        for _i in range(h):
            for _j in range(w):
                if l[i][j] == "." and l[_i][_j] == ".":
                    ans = max(ans, dist(copy.copy(l), j, i, _j, _i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if 0<=ny<h and 0<=nx<w:
            if field[ny][nx]=='#':
              continue
            if visited[ny][nx]!=-1:
              continue
            q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys,collections,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]

  ans=0
  _visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      visited=copy.deepcopy(_visited)
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if 0<=ny<h and 0<=nx<w:
            if field[ny][nx]=='#':
              continue
            if visited[ny][nx]!=-1:
              continue
            q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if 0<=ny<h and 0<=nx<w:
            if field[ny][nx]=='#':
              continue
            if visited[ny][nx]!=-1:
              continue
            q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())