Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[False] * w for _ in range(h)]
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] = True

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = depth[x][y] + 1
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
import copy
import sys
sys.setrecursionlimit(2147483647)

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


ans = 0

for i in range(w):
     for j in range(h):
          for k in range(w):
               for l in range(h):

                    maze2 = copy.deepcopy(maze)

                    if maze[j][i] == '#' or maze[l][k] == '#':
                         pass
                    else:
                         sx,sy,gx,gy = i,j,k,l
                         for y in range(h):
                              for x in range(w):
                                   if maze[y][x] == '.':
                                        maze2[y][x] = 100000


                         maze2[sy][sx]=0
                         que=deque([[sy,sx]])
                         while que:
                              y,x=que.popleft()
                              for m,n in [(1,0),(0,1),(-1,0),(0,-1)]:
                                   nexty,nextx=y+m,x+n
                                   if  nexty in range(h) and nextx in range(w):
                                        dist=maze2[nexty][nextx]
                                        if dist!='#':
                                             if dist>maze2[y][x]+1:
                                                  maze2[nexty][nextx]=maze2[y][x]+1
                                                  que.append([nexty,nextx])
                         if ans < maze2[gy][gx]:
                              ans = maze2[gy][gx]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = r
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
mass = [[ord(i) for i in input()]for _ in range(h)]
wall = ord("#")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[0] * w for _ in range(h)]
    depth = [[0] * w for _ in range(h)]
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = r

    u = 0
    for row in depth:
        u = max(u, max(row))
    return u


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
mass = [input() for _ in range(h)]

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


def bfs(s, t):
    if mass[s][t] == "#":
        return 0
    visited = [[0] * w for _ in range(h)]
    depth = [[0] * w for _ in range(h)]
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == "#":
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = r

    u = 0
    for row in depth:
        u = max(u, max(row))
    return u


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [list(input()) for _ in range(h)]

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


def bfs(s, t):
    if mass[s][t] == "#":
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == "#":
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = r
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [list(input()) for _ in range(h)]

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


def bfs(s, t):
    if mass[s][t] == "#":
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q = deque([[s, t]])
    while q:
        x, y = q.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == "#":
                continue
            if visited[nx][ny]:
                continue

            q.append([nx, ny])
            depth[nx][ny] = r
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [input() for _ in range(h)]

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


def bfs(s, t):
    if mass[s][t] == "#":
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q = deque([[s, t]])
    while q:
        x, y = q.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == "#":
                continue
            if visited[nx][ny]:
                continue

            q.append([nx, ny])
            depth[nx][ny] = r
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [input() for _ in range(h)]

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


def bfs(s, t):
    if mass[s][t] == "#":
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q = deque([[s, t]])
    while q:
        x, y = q.popleft()
        visited[x][y] += 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == "#":
                continue
            if visited[nx][ny]:
                continue

            q.append([nx, ny])
            depth[nx][ny] = depth[x][y] + 1
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
h, w = map(int, input().split())
road = [0]*h
for i in range(h):
  road[i] = input()

def judge(i, j):
  ans = []
  if i != 0 and road[i-1][j] == ".":
    ans.append([[i, j], [i-1, j]])
  if i != h-1 and road[i+1][j] == ".":
    ans.append([[i, j], [i+1, j]])
  if j != 0 and road[i][j-1] == ".":
    ans.append([[i, j], [i, j-1]])
  if j != w-1 and road[i][j+1] == ".":
    ans.append([[i, j], [i, j+1]])
  return ans

already = [[False]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    if road[i][j] == "#":
      already[i][j] = True
ans = 0
for i in range(h):
  for j in range(w):
    if road[i][j] == "#":
      continue
    
    yet = copy.deepcopy(already)
    yet[i][j] = True
    not_yet = deque(judge(i, j))
    depth = [[0]*w for i in range(h)]
    
    while not_yet:
      key = not_yet[0]
      bef_i, bef_j, aft_i, aft_j = key[0][0], key[0][1], key[1][0], key[1][1]
      not_yet.popleft()
      depth[aft_i][aft_j] = depth[bef_i][bef_j] + 1
      yet[aft_i][aft_j] = True
      
      judgement = judge(aft_i, aft_j)
      for value in judgement:
        if yet[value[1][0]][value[1][1]]:
          continue
        not_yet.append(value)
    max_depth = 0
    for p in range(h):
      p_depth = max(depth[p])
      if max_depth < p_depth:
        max_depth = p_depth 
    if ans < max_depth:
      ans = max_depth
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s = [[0]*w for _ in range(h)]
for i in range(h):
    s[i] = list(*input().split())

def cango(now,h,w):
    ans = []
    if now[0]>0:
        ans.append( (now[0]-1,now[1]) )
    if now[0]<h-1:
        ans.append( (now[0]+1,now[1]) )
    if now[1]>0:
        ans.append( (now[0],now[1]-1) )
    if now[1]<w-1:
        ans.append( (now[0],now[1]+1) )
    return ans

from collections import deque

ans=0
for hh in range(h):
    for ww in range(w):
        if s[hh][ww]==".":
            start = (hh,ww)
            q = deque( [] )
            q.append( ((-1,-1),start,0) )
            visit = [[0]*w for _ in range(h)]
            while q:
                old,now,dist = q.popleft()
                visit[now[0]][now[1]] = 1
#                 print(old,now,dist)
                if ans<dist:
                    ans=dist
                for new in cango(now,h,w):
                    if s[new[0]][new[1]]=="." and visit[new[0]][new[1]]==0:
                        q.append( (now,new,dist+1) )
print(ans )

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)
	
ans = 0


# 入力: 座標、かかってる時間
# 出力: 最深部に到達するまでにかかる時間
def bfs(sh, sw):
	distance = [[400 for _ in range(W)] for _ in range(H)]
	for i in range(H):
		for j in range(W):
			if lst[i][j] == "#":
				distance[i][j] = -1
	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:
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
from collections import deque
def bfs(sy, sx, gy, gx):
    d = [[-1] * w for _ in range(h)]
    que = deque([[sy, sx]])
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        if y == gy and x == gx:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
    return d[gy][gx]

ans = 0
for gy in range(h):
    for gx in range(w):
        for sy in range(h):
            for sx in range(w):
                ans = max(ans, bfs(gy, gx, sy, sx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import queue

def shortestpath(y0, x0):
    copymaze = deepcopy(maze)
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0][x0] = 0
    q = queue.Queue()
    q.put((y0, x0))
    while not q.empty():
        y, x = q.get()
        copymaze[y][x] = '#'
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w and copymaze[y_next][x_next] == '.':
                q.put((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]

h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]

max_steps = -1
for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] != '#':
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import queue

def shortestpath(y0, x0, maze, h, w):
    step_cnt = [[-1] * w for _ in range(h)]
    q = queue.Queue()
    step_cnt[y0][x0] = 0
    q.put((y0, x0))
    dy = [-1, 0, 1, 0]
    dx = [0, -1, 0, 1]
    while not q.empty():
        y, x = q.get()
        maze[y][x] = '#'
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w and maze[y_next][x_next] == '.':
                q.put((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]
 
h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
max_steps = -1

for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] == '#':
            continue
        copymaze = deepcopy(maze)
        max_steps = max(max_steps, shortestpath(y0, x0, copymaze, h, w))

print(max_steps)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import queue

def shortestpath(start, goal, maze, h, w):
    y1, x1 = start
    y2, x2 = goal
    if maze[y1][x1] == '#' or maze[y2][x2] == '#':
        return -1
    if start == goal:
        return -1
    
    step_cnt = [[-1] * w for _ in range(h)]
    q = queue.Queue()
    step_cnt[y1][x1] = 0
    q.put((y1, x1))
    dy = [-1, 0, 1, 0]
    dx = [0, -1, 0, 1]
    while not q.empty():
        y, x = q.get()
        maze[y][x] = '#'
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w and maze[y_next][x_next] == '.':
                q.put((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                if y_next == y2 and x_next == x2:
                    return step_cnt[y2][x2]
                    
    return -1

h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
max_steps = -1

for y1 in range(h):
    for x1 in range(w):
        for y2 in range(y1, h):
            for x2 in range(w):
                copymaze = deepcopy(maze)
                max_steps = max(max_steps, shortestpath((y1,x1), (y2,x2), copymaze, h, w))

print(max_steps)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
m=[input() for i in range(h)]
a=[list(map(int,m[i].replace('.','0').replace('#','1'))) for i in range(h)]
for i in range(h):
  for j in range(w):
    if a[i][j]==1:
      a[i][j]=-1

def dfs(y,x,c):
  a[y][x]=c
  tmp=[]
  for dyx in [[-1,0],[1,0],[0,-1],[0,1]]:
    ny=y+dyx[0]
    nx=x+dyx[1]
    if 0<=ny<=h-1 and 0<=nx<=w-1:
      if a[ny][nx]==0 or a[ny][nx]>c+1:
        tmp+=[[ny,nx]]
  c+=1
  for i in tmp:
    dfs(i[0],i[1],c)
  
s=[]
for i in range(h):
  for j in range(w):
    if a[i][j]!=-1:
      s+=[[i,j]]
ans=0
for k in s:
  a=[list(map(int,m[i].replace('.','0').replace('#','1'))) for i in range(h)]
  for i in range(h):
    for j in range(w):
      if a[i][j]==1:
        a[i][j]=-1
  dfs(k[0],k[1],1)
  ans=max(ans,max(map(max,a)))
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
m=[input() for i in range(h)]
a=[list(map(int,m[i].replace('.','0').replace('#','1'))) for i in range(h)]
for i in range(h):
  for j in range(w):
    if a[i][j]==1:
      a[i][j]=-1
def dfs(y,x,c):
  a[y][x]=c
  tmp=[]
  for dyx in [[-1,0],[1,0],[0,-1],[0,1]]:
    dy=dyx[0]
    dx=dyx[1]
    ny=y+dy
    nx=x+dx
    if 0<=ny<=h-1 and 0<=nx<=w-1:
      if a[ny][nx]==0 or a[ny][nx]>a[y][x]+1:
        tmp+=[[ny,nx]]
  c=a[y][x]+1
  for i in tmp:
    ny,nx=i[0],i[1]
    dfs(ny,nx,c)
  
s=[]
for i in range(h):
  for j in range(w):
    if a[i][j]!=-1:
      s+=[[i,j]]
ans=0
for k in s:
  a=[list(map(int,m[i].replace('.','0').replace('#','1'))) for i in range(h)]
  for i in range(h):
    for j in range(w):
      if a[i][j]==1:
        a[i][j]=-1
  sy=k[0]
  sx=k[1]
  dfs(sy,sx,1)
  ans=max(ans,max(map(max,a)))
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
R,C = map(int,input().split())
graph = [[i for i in input()] for j in range(R)]
visited = [[False for i in range(C)] for j in range(R)]

def dfs(start_y,start_x,goal_y,goal_x):
  queue = [[start_y,start_x,0]]
  while queue:
    now = queue.pop(0)
    visited[now[0]][now[1]] = True
    if now[0]==goal_y and now[1]==goal_x: return now[2]
    for next in [[1,0],[-1,0],[0,1],[0,-1]]:
      if now[0]+next[0] < 0 or now[1]+next[1] < 0: continue
      if now[0]+next[0] > R-1 or now[1]+next[1] > C-1: continue
      if visited[now[0]+next[0]][now[1]+next[1]]: continue
      if graph[now[0]+next[0]][now[1]+next[1]]=='#': continue
      queue.append([now[0]+next[0],now[1]+next[1],now[2]+1])
      visited[now[0]+next[0]][now[1]+next[1]] = True

ans = 0
for row_s in range(R):
  for column_s in range(C):
    for row_g in range(R):
      for column_g in range(C):
        if graph[row_s][column_s]=='#' or graph[row_g][column_g]=='#': continue
        visited = [[False for i in range(C)] for j in range(R)]
        ans = max(ans,dfs(row_s,column_s,row_g,column_g))
    
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(H):
    t = list(input())
    A.append(t)

tate = (-1,1,0,0)
yoko = (0,0,-1,1)
answer = 0

def move(i,j):
    for p, q in zip(tate, yoko):
        m = i + p
        n = j + q
        if m >= 0 and m < H:
            if n >= 0 and n < W:
                if A[m][n] == '.':
                    if dp[m][n] > dp[i][j]+1:
                        dp[m][n] = dp[i][j] + 1
                        move(m,n)

for i in range(H):
    for j in range(W):
        dp = [[10**4 for i in range(W)] for j in range(H)]
        if A[i][j] == '.':
            dp[i][j] = 0
            move(i,j)
            for k in range(H):
                for l in range(W):
                    if dp[k][l] < 10**4:
                        answer = max(answer,dp[k][l])

print(answer)

Submission status: Time Limit Exceeded

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

for i in range(H):
    t = list(input())
    A.append(t)

tate = (-1,1,0,0)
yoko = (0,0,-1,1)
answer = 0

def move(i,j):
    for p, q in zip(tate, yoko):
        m = i + p
        n = j + q
        if m >= 0 and m < H:
            if n >= 0 and n < W:
                if A[m][n] == '.':
                    if dp[m][n] > dp[i][j]:
                        dp[m][n] = dp[i][j] + 1
                        move(m,n)

for i in range(H):
    for j in range(W):
        dp = [[10**4 for i in range(W)] for j in range(H)]
        if A[i][j] == '.':
            dp[i][j] = 0
            move(i,j)
            for k in range(H):
                for l in range(W):
                    if dp[k][l] < 10**4:
                        answer = max(answer,dp[k][l])

print(answer)

Submission status: Time Limit Exceeded

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

max_count = 0

import itertools

s_list = list(itertools.product(range(H), range(W)))

for start, goal in itertools.combinations(s_list, 2):
    ys = start[0]
    xs = start[1]
    yg = goal[0]
    xg = goal[1]
    if (ys, xs) == (yg, xg):
        continue
    if S[ys][xs] == '#' or S[yg][xg] == '#':
        continue

    n = [(ys, xs)]
    route = {n[0]: 0}
    p = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    count = 1
    while (yg, xg) not in route and count != 500:
        n2 = []
        for i in n:
            for j in p:
                np = (i[0] + j[0], i[1] + j[1])
                if np[0] >= H or np[1] >= W or np[0] < 0 or np[1] < 0:
                    continue
                if S[np[0]][np[1]] == '.' and np not in route:
                    n2.append(np)
                    route[np] = count
        n=n2
        count+=1
    if (yg, xg) in route:
        max_count = max(max_count, route[(yg, xg)])

print(max_count)

Submission status: Time Limit Exceeded

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

max_count = 0

import itertools

s_list = list(itertools.product(range(H), range(W)))
# g_list = list(itertools.product(range(H), range(W)))
s_g_list = list(itertools.combinations(s_list, 2))

for start, goal in itertools.combinations(s_list, 2):
    ys = start[0]
    xs = start[1]
    yg = goal[0]
    xg = goal[1]
    if (ys, xs) == (yg, xg):
        continue
    if S[ys][xs] == '#' or S[yg][xg] == '#':
        continue

    n = [(ys, xs)]
    route = {n[0]: 0}
    p = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    count = 1
    while (yg, xg) not in route and count != 500:
        n2 = []
        for i in n:
            for j in p:
                np = (i[0] + j[0], i[1] + j[1])


                if np[0] >= H or np[1] >= W or np[0] < 0 or np[1] < 0:
                    continue
                if S[np[0]][np[1]] == '.' and route.get(np, -1) == -1:
                    n2.append(np)
                    route[np] = count
        n=n2
        count+=1
    if (yg, xg) in route:
        max_count = max(max_count, route[(yg, xg)])

print(max_count)

Submission status: Time Limit Exceeded

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

max_count = 0

import itertools

for ys, xs in itertools.product(range(H), range(W)):
    for yg, xg in itertools.product(range(H), range(W)):
        if (ys, xs) == (yg, xg):
            continue
        if S[ys][xs] == '#' or S[yg][xg] == '#':
            continue

        n = [(ys, xs)]
        route = {n[0]: 0}
        p = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        count = 1
        while (yg, xg) not in route and count != 500:
            n2 = []
            for i in n:
                for j in p:
                    np = (i[0] + j[0], i[1] + j[1])


                    if np[0] >= H or np[1] >= W or np[0] < 0 or np[1] < 0:
                        continue
                    if S[np[0]][np[1]] == '.' and route.get(np, -1) == -1:
                        n2.append(np)
                        route[np] = count
            n=n2
            count+=1
        if (yg, xg) in route:
            max_count = max(max_count, route[(yg, xg)])

print(max_count)

Submission status: Time Limit Exceeded

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

max_count = 0

import itertools

for ys, xs in itertools.product(range(H), range(W)):
    for yg, xg in itertools.product(range(H), range(W)):
        if (ys, xs) == (yg, xg):
            continue
        if S[ys][xs] == '#' or S[yg][xg] == '#':
            continue

        n = [(ys, xs)]
        route = {n[0]: 0}
        p = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        count = 1
        while route.get((yg, xg), 0) == 0 and count != 10000:
            # print(route)
            n2 = []
            for i in n:
                for j in p:
                    np = (i[0] + j[0], i[1] + j[1])


                    if np[0] >= H or np[1] >= W or np[0] < 0 or np[1] < 0:
                        continue
                    if S[np[0]][np[1]] == '.' and route.get(np, -1) == -1:
                        n2.append(np)
                        route[np] = count
            n=n2
            count+=1
        if (yg, xg) in route:
            max_count = max(max_count, route[(yg, xg)])

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
# from collections import deque
H, W = list(map(int, input().split()))
# dp = [[1000 for _ in range(W)] for _ in range(H)]

S = [['#']*(W+2)] + [['#']+list(input())+['#'] for h in range(H)] + [['#']*(W+2)]
# S = (H+2, W+2)
# S =  [input().split() for h in range(H)]
max_n = 0

for h1 in range(1,H+1):
  for w1 in range(1,W+1):
    if S[h1][w1] == '#':
      continue
    distance = [[1000 for _ in range(W+2)] for _ in range(H+2)]
    distance[h1][w1] = 0
    que = []
    que.append([h1,w1])
    que_i = 0
    while que_i < len(que):
      h, w = que[que_i]
      if S[h-1][w] == '.' and [h-1, w] not in que:
        que.append([h-1,w])
        distance[h-1][w] = min(distance[h][w] + 1, distance[h-1][w])
      if S[h+1][w] == '.' and [h+1, w] not in que:
        que.append([h+1,w])
        distance[h+1][w] = min(distance[h][w] + 1, distance[h+1][w])
      if S[h][w-1] == '.' and [h, w-1] not in que:
        que.append([h,w-1])
        distance[h][w-1] = min(distance[h][w] + 1, distance[h][w-1])
      if S[h][w+1] == '.' and [h-1, w+1] not in que:
        que.append([h,w+1])
        distance[h][w+1] = min(distance[h][w] + 1, distance[h][w+1])
      que_i += 1
    hw_max_n = 0
    for h2 in range(1,H+1):
      for w2 in range(1,W+1):
        if distance[h2][w2] != 1000:
          hw_max_n = max(hw_max_n, distance[h2][w2])
    max_n = max(max_n, hw_max_n)
print(max_n)

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):
            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])
                            ans=max(ans,field[ny][nx])
                            next_list.append([ny,nx])
    print(ans)
if __name__ == '__main__':
    main()