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 queue
import copy

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

def movable(S,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S[px][py] == ".":
            return True
        else:
            return False
    else:
        return False

def bfs(S,sx,sy):
    S_dist = [[0 for _ in range(W)] for _ in range(H)]
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    while not q.empty():
        p = q.get()
        S[p[0]][p[1]] = "#"
        for vx,vy in vec:
            if movable(S,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                q.put((p[0]+vx,p[1]+vy))
    ret = 0
    for i in range(len(S_dist)):
        tmp_max = max(S_dist[i])
        ret = max(ret,tmp_max)
    return ret

ans = 0
for i in range(H*W):
    if S[i//W][i%W] == ".":
        S_ = copy.deepcopy(S)
        ans = max(ans,bfs(S_,i//W,i%W))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

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

def movable(S,px,py):
    if  0 <= px and px < H and 0 <= py and py < W:
        if S[px][py] == ".":
            return True
        else:
            return False
    else:
        return False

def bfs(S,sx,sy,gx,gy):
    S_dist = [[0 for _ in range(W)] for _ in range(H)]
    q = queue.Queue()
    q.put((sx,sy))
    vec = [(0,1),(0,-1),(1,0),(-1,0)]
    while not q.empty():
        p = q.get()
        S[p[0]][p[1]] = "#"
        if p == (gx,gy):
            return S_dist[gx][gy]
        for vx,vy in vec:
            if movable(S,p[0]+vx,p[1]+vy):
                S_dist[p[0]+vx][p[1]+vy] = S_dist[p[0]][p[1]]+1
                q.put((p[0]+vx,p[1]+vy))

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if S[i//W][i%W] == "." and S[j//W][j%W] == ".":
            S_ = copy.deepcopy(S)
            ans = max(ans,bfs(S_,i//W,i%W,j//W,j%W))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
input = sys.stdin.readline
H,W= map(int,input().split())
input_maze = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if input_maze[i][j] ==".":
            queue = [[i,j,0]]#最初の△
            maze = copy.deepcopy(input_maze)
            while True:
                if len(queue) ==0:
                    tem_ans = point[2]
                    break
                point=queue.pop(0)#queueの先頭座標+何回移動したかの取得
                maze[point[0]][point[1]] = point[2] 
                if point[0] > 0 and maze[point[0]-1][point[1]]==".":#上
                    queue.append([point[0]-1,point[1],point[2]+1])
                if point[0] < len(maze)-1 and maze[point[0]+1][point[1]]==".":#下
                    queue.append([point[0]+1,point[1],point[2]+1])
                if point[1] > 0 and maze[point[0]][point[1]-1]==".":#左
                    queue.append([point[0],point[1]-1,point[2]+1])
                if point[1] < len(maze[point[0]])-1 and maze[point[0]][point[1]+1]=="." :#右
                    queue.append([point[0],point[1]+1,point[2]+1])
                
            ans = max(ans,tem_ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
input = sys.stdin.readline
H,W= map(int,input().split())
input_maze = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if input_maze[i][j] ==".":
            queue = list()#キュー
            queue.append([i,j,0])#最初の△
            maze = copy.deepcopy(input_maze)
            tem_ans = 0
            while True:
                if len(queue) ==0:
                    tem_ans = point[2]
                    break
                point=queue.pop(0)#queueの先頭座標+何回移動したかの取得
                maze[point[0]][point[1]] = point[2] 
                if point[0] > 0 and maze[point[0]-1][point[1]]==".":#上
                    queue.append([point[0]-1,point[1],point[2]+1])
                if point[0] < len(maze)-1 and maze[point[0]+1][point[1]]==".":#下
                    queue.append([point[0]+1,point[1],point[2]+1])
                if point[1] > 0 and maze[point[0]][point[1]-1]==".":#左
                    queue.append([point[0],point[1]-1,point[2]+1])
                if point[1] < len(maze[point[0]])-1 and maze[point[0]][point[1]+1]=="." :#右
                    queue.append([point[0],point[1]+1,point[2]+1])
                
            ans = max(ans,tem_ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
input = sys.stdin.readline
H,W= map(int,input().split())
input_maze = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if input_maze[i][j] ==".":
            queue = list()#キュー
            queue.append([i,j,0])#最初の△
            maze = copy.deepcopy(input_maze)
            tem_ans = 0
            while True:
                if len(queue) ==0:
                    break
                point=queue.pop(0)#queueの先頭座標+何回移動したかの取得
                maze[point[0]][point[1]] = point[2] 
                if point[0] > 0 and maze[point[0]-1][point[1]]==".":#上
                    queue.append([point[0]-1,point[1],point[2]+1])
                if point[0] < len(maze)-1 and maze[point[0]+1][point[1]]==".":#下
                    queue.append([point[0]+1,point[1],point[2]+1])
                if point[1] > 0 and maze[point[0]][point[1]-1]==".":#左
                    queue.append([point[0],point[1]-1,point[2]+1])
                if point[1] < len(maze[point[0]])-1 and maze[point[0]][point[1]+1]=="." :#右
                    queue.append([point[0],point[1]+1,point[2]+1])
                tem_ans = point[2]
            ans = max(ans,tem_ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
input = sys.stdin.readline
H,W= map(int,input().split())
input_maze = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if input_maze[i][j] ==".":
            queue = list()#キュー
            queue.append([i,j,0])#最初の△
            
            dis = 0
            maze = copy.deepcopy(input_maze)
            while True:
                if len(queue) ==0:
                    break
                point=queue.pop(0)#queueの先頭座標の取得
            
                ans = max(ans,point[2])

                maze[point[0]][point[1]] = point[2] 
                if point[0] > 0 and maze[point[0]-1][point[1]]==".":#上
                    queue.append([point[0]-1,point[1],point[2]+1])
                if point[0] < len(maze)-1 and maze[point[0]+1][point[1]]==".":#下
                    queue.append([point[0]+1,point[1],point[2]+1])
                if point[1] > 0 and maze[point[0]][point[1]-1]==".":#左
                    queue.append([point[0],point[1]-1,point[2]+1])
                if point[1] < len(maze[point[0]])-1 and maze[point[0]][point[1]+1]=="." :#右
                    queue.append([point[0],point[1]+1,point[2]+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy


H,W= map(int,input().split())
input_maze = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if input_maze[i][j] ==".":
            queue = list()#キュー
            queue.append([i,j,0])#最初の△
            dis = 0
            maze = copy.deepcopy(input_maze)
            while True:
                if len(queue) ==0:
                    break
                point=queue.pop(0)#queueの先頭座標の取得
            
                ans = max(ans,point[2])

                maze[point[0]][point[1]] = point[2] 
                if point[0] > 0 and maze[point[0]-1][point[1]]==".":#上
                    queue.append([point[0]-1,point[1],point[2]+1])
                if point[0] < len(maze)-1 and maze[point[0]+1][point[1]]==".":#下
                    queue.append([point[0]+1,point[1],point[2]+1])
                if point[1] > 0 and maze[point[0]][point[1]-1]==".":#左
                    queue.append([point[0],point[1]-1,point[2]+1])
                if point[1] < len(maze[point[0]])-1 and maze[point[0]][point[1]+1]=="." :#右
                    queue.append([point[0],point[1]+1,point[2]+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy



H,W= map(int,input().split())
input_maze = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if input_maze[i][j] ==".":
            queue = list()#キュー
            queue.append([i,j,0])#最初の△
            dis = 0
            maze = copy.deepcopy(input_maze)
            while True:
                if len(queue) ==0:
                    break
                point=queue.pop(0)#queueの先頭座標の取得
            
                ans = max(ans,point[2])

                maze[point[0]][point[1]] = point[2] 
                #print(numpy.array(maze))
                if point[0] > 0 and maze[point[0]-1][point[1]]==".":#上
                    queue.append([point[0]-1,point[1],point[2]+1])
                if point[0] < len(maze)-1 and maze[point[0]+1][point[1]]==".":#下
                    queue.append([point[0]+1,point[1],point[2]+1])
                if point[1] > 0 and maze[point[0]][point[1]-1]==".":#左
                    queue.append([point[0],point[1]-1,point[2]+1])
                if point[1] < len(maze[point[0]])-1 and maze[point[0]][point[1]+1]=="." :#右
                    queue.append([point[0],point[1]+1,point[2]+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def dfs_2d(H,W,M,start,goal):
    que = deque()
    que.append([start[0],start[1]])
    distance = [[-1 for i in range(W)] for j in range(H)]
    dxdy = [[1,0],[-1,0],[0,1],[0,-1]]##4方向

    distance[start[0]][start[1]] = 0

    flag = False
    
    while que:
        x,y = que.popleft()

        if x == goal[0] and y == goal[1]:
            return distance[goal[0]][goal[1]]
        
        for i,j in dxdy:
            dx = x + i
            dy = y + j
            if 0 <= dx <= H-1 and 0 <= dy <= W-1 and M[dx][dy] != "#":
                distance[dx][dy] = distance[x][y] + 1
                que.append([dx,dy])
    return -1

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(input())
    ans = 0
    for i in range(H):
        for j in range(W):
            for h in range(H):
                for k in range(W):
                    if M[i][j] != "#" and M[h][k] != "#":
                        start = [i,j]
                        goal = [h,k]
                        ans = max(ans,dfs_2d(H,W,M,start,goal))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def clear_maze(maze,sx,sy,gx,gy):
    # SからGまでの最短距離を計算する


    def calc_distance(maze,sx,sy,gx,gy):
        # mazeをリストに変換
        maze = maze.split()
        # Goalまでの距離としてはあり得ない数値を設定
        INF = 100000000

        field_x_length = len(maze[0])
        field_y_length = len(maze)

        # mazeと同じ配列構造ですべての箇所がINFで埋まっている二次元配列を作る
        # startからの距離をこのdistance配列に格納していく
        distance = []
        for i in range(field_y_length):
            distance.append([])
            for j in range(field_x_length):
                distance[i].append(INF)

        # queue配列を作り、ここに座標を格納する
        queue = []

        # queueの末尾にStart座標を入れる
        queue.insert(0, (sy, sx))

        # Startの座標距離は0に設定
        distance[sy][sx] = 0

        # Goalにつくまで以下ループ
        while True:
            # 最初に入れた要素を取り出す
            y, x = queue.pop()
            if x == gx and y == gy:
                break

            # 新しい座標(ny, nx)に現時点の座標から
            # (0, 1)(1, 0)(0, -1)(-1, 0)移動した値を代入  
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                # 移動先ny, nxが迷路の範囲内
                # かつ壁（maze配列が#）でなく、
                # かつ未到達（distance配列がINF）であるときに
                # 現時点の距離+1をdistance配列に格納する
                # 現時点の座標をqueue配列に格納する（再ループの時にその座標から始める）
                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1

        # Goalについたらループを抜け、Goalまでの距離を返す
        return distance[gy][gx]

    def main():
      return calc_distance(maze,sx,sy,gx,gy)   
    return main()
max_path = 0
maze = ""
H,W = (int(x) for x in input().split())
for i in range(H):
  maze += input()+"\n"

maze_li = maze.split()
for gy in range(H):
  for gx in range(W):
    if maze_li[gy][gx] == ".":
      for sy in range(H):
        for sx in range(W):
          if maze_li[sy][sx] == "." and (gy != sy or gx != sx):
            path = clear_maze(maze,sx,sy,gx,gy)
            if max_path < path:
              max_path = path
              
print(max_path)

Submission status: Time Limit Exceeded

Solution code:
import math
import time
from collections import deque
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def makemaze(H, W):
    maze = []
    for i in range(H):
        s = input()
        a = []
        for c in s:
            if c == ".":
                a.append(1000)
            if c == "#":
                a.append(9999)
        maze.append(a)
        #print(maze)
    return maze

def maxroot(maze, x, y, w, h):
    sn = 0
    if maze[y][x] == 9999:
        return 0

    maze = deepcopy(maze)
    maze[y][x] = 0
    que = deque()
    que.append((y, x))


    while que:
        xy = que.popleft()
        y = xy[0]
        x = xy[1]
        if maze[y][x] == 9999:
            continue

        minlist = []
        if x > 0:
            minlist.append((y, x-1))
        if y > 0:
            minlist.append((y-1, x))
        if x < w-1:
            minlist.append((y, x+1))
        if y < h-1:
            minlist.append((y+1, x))

        dd = min(maze[y][x] for y, x in minlist) + 1
        dd = min(dd, maze[y][x])
        maze[y][x] = dd

        for y, x in minlist:
            #if maze[y][x] != 9999 and maze[y][x] > dd+2:
            if maze[y][x] == 1000:
                que.append((y, x))
                sn += 1
            #print(sn)

    maxx = 0
    for line in maze:
        try:
            maxa = max([i for i in line if i < 1000])
        except:
            maxa = 0
        maxx = max(maxx, maxa)
    return maxx


def main():
    H, W = iip()
    maze = makemaze(H, W)

    maxx = 1
    for y in range(H):
        for x in range(W):
            maxx = max(maxx, maxroot(maze, x, y, W, H))
            pass

    print(maxx)
    #print(maxroot(maze, 0, 2, W, H))


main()

Submission status: Time Limit Exceeded

Solution code:
import math
import time
from collections import deque
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def makemaze(H, W):
    maze = []
    for i in range(H):
        s = input()
        a = []
        for c in s:
            if c == ".":
                a.append(1000)
            if c == "#":
                a.append(9999)
        maze.append(a)
        #print(maze)
    return maze

def maxroot(maze, x, y, w, h):
    maxx = 0
    if maze[y][x] == 9999:
        return 0

    maze = deepcopy(maze)
    maze[y][x] = 0
    que = deque()
    que.append((y, x))

    while que:
        xy = que.popleft()
        y = xy[0]
        x = xy[1]
        if maze[y][x] == 9999:
            continue

        minlist = []
        if x > 0:
            minlist.append((y, x-1))
        if y > 0:
            minlist.append((y-1, x))
        if x < w-1:
            minlist.append((y, x+1))
        if y < h-1:
            minlist.append((y+1, x))

        dd = min(maze[y][x] for y, x in minlist) + 1
        dd = min(dd, maze[y][x])
        maze[y][x] = dd
        maxx = max(dd, maxx)

        for y, x in minlist:
            if maze[y][x] != 9999 and maze[y][x] > dd+2:
                que.append((y, x))

        #if dd == 39:
        #    for i in range(20):
        #        print(maze[i])

    return maxx


def main():
    H, W = iip()
    maze = makemaze(H, W)

    maxx = 1
    for y in range(H):
        for x in range(W):
            maxx = max(maxx, maxroot(maze, x, y, W, H))
            pass

    print(maxx)
    #print(maxroot(maze, 0, 2, W, H))


main()

Submission status: Time Limit Exceeded

Solution code:
import math
import time
from collections import deque
from copy import deepcopy

t = time.time()
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def makemaze(H, W):
    maze = []
    for i in range(H):
        s = input()
        a = []
        for c in s:
            if c == ".":
                a.append(1000)
            if c == "#":
                a.append(9999)
        maze.append(a)
        #print(maze)
    return maze

def maxroot(maze, x, y, w, h):
    maxx = 0
    if maze[y][x] == 9999:
        return 0

    maze = deepcopy(maze)
    maze[y][x] = 0
    que = deque()
    que.append((y, x))

    while que:
        xy = que.popleft()
        y = xy[0]
        x = xy[1]
        if maze[y][x] == 9999:
            continue

        minlist = []
        if x > 0:
            minlist.append((y, x-1))
        if y > 0:
            minlist.append((y-1, x))
        if x < w-1:
            minlist.append((y, x+1))
        if y < h-1:
            minlist.append((y+1, x))

        dd = min(maze[y][x] for y, x in minlist) + 1
        dd = min(dd, maze[y][x])
        maze[y][x] = dd
        maxx = max(dd, maxx)

        for y, x in minlist:
            if maze[y][x] != 9999 and maze[y][x] > dd+1:
                que.append((y, x))

        #if dd == 39:
        #    for i in range(20):
        #        print(maze[i])

    return maxx


def main():
    H, W = iip()
    maze = makemaze(H, W)

    maxx = 1
    for y in range(H):
        for x in range(W):
            maxx = max(maxx, maxroot(maze, x, y, W, H))
            pass

    print(maxx)
    #print(maxroot(maze, 0, 2, W, H))


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.popleft()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
#             print(que)
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.pop()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
    s = s.replace(".", "0").replace("#", "1")
    s = list(map(int, list(s)))
    ss.append(s)
ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.pop()
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h, next_w] == 1:
                continue
            if dp[next_h, next_w] > dp[now_h, now_w] + 1:
                dp[next_h, next_w] = dp[now_h, now_w] + 1
                que.append((next_h, next_w))
    return dp

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh, sw] == 0:
            dp = find(sh, sw)
            score = np.max(dp[dp != 9999])
            if maximum < score:
                maximum = score

print(maximum)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [input() + "#" for _ in range(H)]
S.append("#" * (W + 1))
paths = [(h, w) for h in range(H) for w in range(W) if S[h][w] == "."]

ans = 0
todo = deque()
done = [[False] * W for _ in range(H)]
for sh, sw in paths:
    done[sh][sw] = True
    for gh, gw in paths:
        if done[gh][gw]:
            continue
        todo.append((0, sh, sw))
        pathed = [[False] * W for _ in range(H)]
        while todo:
            cnt, h, w = todo.popleft()
            cnt += 1
            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nh = h + dh
                nw = w + dw
                if nh == gh and nw == gw:
                    if ans < cnt:
                        ans = cnt
                    todo.clear()
                    break
                elif S[nh][nw] == "." and not pathed[nh][nw]:
                    todo.append((cnt, nh, nw))
            pathed[h][w] = True
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [input() + "#" for _ in range(H)]
S.append("#" * (W + 1))
paths = [(h, w) for h in range(H) for w in range(W) if S[h][w] == "."]

ans = 0
todo = deque()
for sh, sw in paths:
    for gh, gw in paths:
        if sh == gh and sw == gw:
            continue
        todo.append((0, sh, sw))
        pathed = [[False] * W for _ in range(H)]
        while todo:
            cnt, h, w = todo.popleft()
            cnt += 1
            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nh = h + dh
                nw = w + dw
                if nh == gh and nw == gw:
                    if ans < cnt:
                        ans = cnt
                    todo.clear()
                    break
                elif S[nh][nw] == "." and not pathed[nh][nw]:
                    todo.append((cnt, nh, nw))
            pathed[h][w] = True
print(ans)

Submission status: Time Limit Exceeded

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

def dfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]
ans = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == '#':
            continue
        for gy in range(H):
            for gx in range(W):
                if S[gy][gx] == '#' or (sy==gy and sx==sy):
                    continue
                ans = max(ans,dfs(sy,sx,gy,gx))
print(ans)

Submission status: Time Limit Exceeded

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

def dfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]
ans = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == '#':
            continue
        for gy in range(H):
            for gx in range(W):
                if S[gy][gx] == '#':
                    continue
                ans = max(ans,dfs(sy,sx,gy,gx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=-1
#print(S)
def bfs(sx,sy,gx,gy):
  #dx, dy 四方向に対応したベクトルのリスト
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  #P: (x, y)のキュー
  P=[]
  #d: スタートから各点までの最小距離の配列
  d=np.ones((H, W))*INF
  #スタート地点をキューに入れ、その点の距離を0にする
  P.append([sx, sy])
  d[sx,sy]=0
    
  #キューがからになるまでループ
  while len(P)>0:
    #キューの先頭を取り出す
    p=P.pop(0)
    #取り出してきた状態がゴールなら探索をやめる
    if (p[0]==gx and p[1]==gy):
      break
        
    #移動四方向をループ
    for i in range(4):
      #移動した後の点をnx, nyとする
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
            
      #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
      if 0<=nx and nx<H and 0<=ny and ny<W and S[nx, ny]!="#" and d[nx, ny]==INF:
        #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  #print(d)
  if d[gx,gy]!=INF:
    result=d[gx, gy]
  else:
    result=0
  return result
ans=0
Tlen=H*W
for i in range(Tlen):
  for j in range(i,Tlen):
    sx,sy=i%H, int(i//H)
    gx,gy=j%H, int(j//H)
    
    if S[sx,sy]=="#" or S[gx,gy]=="#":
      continue
    res=bfs(sx,sy,gx,gy)
    ans=max(ans, res)
"""
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="#" or S[gx,gy]=="#":
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
"""
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=np.inf
#print(S)
def bfs(sx,sy,gx,gy):
  #dx, dy 四方向に対応したベクトルのリスト
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  #P: (x, y)のキュー
  P=[]
  #d: スタートから各点までの最小距離の配列
  d=np.ones((H, W))*INF
  #スタート地点をキューに入れ、その点の距離を0にする
  P.append([sx, sy])
  d[sx,sy]=0
    
  #キューがからになるまでループ
  while len(P)>0:
    #キューの先頭を取り出す
    p=P.pop(0)
    #取り出してきた状態がゴールなら探索をやめる
    if (p[0]==gx and p[1]==gy):
      break
        
    #移動四方向をループ
    for i in range(4):
      #移動した後の点をnx, nyとする
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
            
      #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
      if 0<=nx and nx<H and 0<=ny and ny<W and S[nx, ny]!="#" and d[nx, ny]==INF:
        #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  #print(d)
  if d[gx,gy]!=INF:
    result=d[gx, gy]
  else:
    result=0
  return result
ans=0
Tlen=H*W
for i in range(Tlen):
  for j in range(i,Tlen):
    sx,sy=i%H, int(i//H)
    gx,gy=j%H, int(j//H)
    
    if S[sx,sy]=="#" or S[gx,gy]=="#":
      continue
    res=bfs(sx,sy,gx,gy)
    ans=max(ans, res)
"""
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="#" or S[gx,gy]=="#":
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
"""
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=np.inf
#print(S)
def bfs(sx,sy,gx,gy):
  #dx, dy 四方向に対応したベクトルのリスト
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  #P: (x, y)のキュー
  P=[]
  #d: スタートから各点までの最小距離の配列
  d=np.ones((H, W))*INF
  #スタート地点をキューに入れ、その点の距離を0にする
  P.append([sx, sy])
  d[sx,sy]=0
    
  #キューがからになるまでループ
  while len(P)>0:
    #キューの先頭を取り出す
    p=P.pop(0)
    #取り出してきた状態がゴールなら探索をやめる
    if (p[0]==gx and p[1]==gy):
      break
        
    #移動四方向をループ
    for i in range(4):
      #移動した後の点をnx, nyとする
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
            
      #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
      if 0<=nx and nx<H and 0<=ny and ny<W and S[nx, ny]!="#" and d[nx, ny]==INF:
        #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  #print(d)
  if d[gx,gy]!=INF:
    result=d[gx, gy]
  else:
    result=0
  return result
ans=0
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="#" or S[gx,gy]=="#":
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
print(int(ans))