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
 
def ngoin(bo,now):
    return 0 <= now[0] and now[0] < len(bo) and 0 <= now[1] and now[1] < len(bo[0])
 
def minido(bo,si,sj):
    tb = [[False for i in range(len(bo[0]))] for j in range(len(bo))]
    q = queue.Queue()
    q.put([si,sj,0])
    ret = 0
    while not q.empty():
        now = q.get()
        ret = now[2]
        if tb[now[0]][now[1]]:
            continue
        tb[now[0]][now[1]] = True
        tb[now[0]][now[1]] = True
        if ngoin(bo,[now[0]-1,now[1]]):
            if bo[now[0]-1][now[1]]:
                q.put([now[0]-1,now[1],now[2]+1])
        if ngoin(bo,[now[0],now[1]+1]):
            if bo[now[0]][now[1]+1]:
                q.put([now[0],now[1]+1,now[2]+1])
        if ngoin(bo,[now[0]+1,now[1]]):
            if bo[now[0]+1][now[1]]:
                q.put([now[0]+1,now[1],now[2]+1])
        if ngoin(bo,[now[0],now[1]-1]):
            if bo[now[0]][now[1]-1]:
                q.put([now[0],now[1]-1,now[2]+1])
    return ret
            
 
h,w = map(int,input().split())
bo = [[True if x == '.' else False for x in input()] for i in range(h)]
grap = [[float('inf') for i in range(h*w)] for j in range(h*w)]
ans = 0
for i in range(h*w):
    grap[i][i] = 0
for si in range(h):
    for sj in range(w):
        if not bo[si][sj]:
            continue
        ans = max(ans,minido(bo,si,sj)-1)
                
print(ans)

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 permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd


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

def bfs(maze, visited, sy, sx, gy, gx, H, W):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if new_y < 0 or new_y >= H or new_x < 0 or new_x >= W:
                continue
            elif maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

def main():
    H, W = MAP()
    s = [list(input()) for _ in range(H)]
    ans = 0
    lis = []
    for i in range(H):
        for j in range(W):
            if s[i][j] != '#':
                lis.append([i,j])
    for (x,y) in combinations(lis, 2):
        sh = x[0]
        sw = x[1]
        gh = y[0]
        gw = y[1]

        visited = [[-1]*W for _ in range(H)]
        ans = max(ans,bfs(s, visited, sh, sw, gh, gw, H, W))

    print(ans)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

def judge1(masu,h,w):
    if (masu[0]>=0)&(masu[0]<h)&(masu[1]>=0)&(masu[1]<w):
        return True
    else:
        return False
    
def judge2(masu,s):
    if s[masu[0]][masu[1]] == '.':
        return True
    else:
        return False
    
def tsugi(i,j,h,w,s2):
    ans=[]
    for masu in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
        if judge1(masu,h,w):
            if judge2(masu,s2):
                ans.append(masu)
    return ans
    


def solve(i,j,s,h,w):
    ma = 0
    s2 = copy.deepcopy(s)
    if s2[i][j]=='.':
        s2[i][j]='#'
        nex = tsugi(i,j,h,w,s2)
        flag=1
        while len(nex)!=0 :
            ma+=1
            #flag= 0
            nex2=[]
            for n in nex:
                nex2[len(nex2):] = tsugi(n[0],n[1],h,w,s2)
                s2[n[0]][n[1]]='#'
            nex = nex2
    return ma


h,w=map(int,input().split())
s = []
ma = 0
for i in range(h):
    s.append(list(input()))
for i in range(h):
    for j in range(w):
        ans = solve(i,j,s,h,w)
        ma = max(ma,ans)
print(ma)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
    l = []
    for i in range(len(S)):
      for j in range(i+1, len(G)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!='#':
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                if nexty == G[j][0] and nextx == G[j][1]:
                  break
                que.append([nexty,nextx])
        l.append(maze1[G[j][0]][G[j][1]])
    print(max(l))
bfs()

Submission status: Time Limit Exceeded

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

d_max = 0


def bfs(sx,sy,gx,gy):
    d = [[float("inf")] * w for i in range(h)]

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

    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    if d[gx][gy] == float("inf"):
        return 0
    else:
        return d[gx][gy]

for i in range(h*w):
    for k in range(i+1,h*w):
        jj = i%w
        ii = i//w
        ll = k%w
        kk = k//w
        if s[ii][jj] == '.' and s[kk][ll] == '.':
            d_min = bfs(ii,jj,kk,ll)
            if d_max < d_min:
                d_max = d_min
print(d_max)

Submission status: Time Limit Exceeded

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

def Maze_Master(y, x, c):
    if y < 0 or y > h-1 or x < 0 or x > w-1 or m[y][x] != 0 and m[y][x] < c or s[y][x] == "#":
        pass
    else:
        m[y][x] = c
        c += 1
        Maze_Master(y+1, x, c)
        Maze_Master(y-1, x, c)
        Maze_Master(y, x+1, c)
        Maze_Master(y, x-1, c)
    return m
    
a = 0
for y in range(h):
    for x in range(w):
        m = [[0]*w for _ in range(h)]
        ans = Maze_Master(y, x, 1)
        l = []
        for i in ans:
            l.append(max(i))
        b = max(l)
        a = max(a, b)

print(a-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
from scipy.ndimage.filters import minimum_filter, maximum_filter

def init_maze(maze, H, W, start, goal):
    cost = np.zeros((H, W), dtype=int) + 999
    done = np.zeros((H, W), dtype=bool)
    barrier = np.zeros((H, W), dtype=bool)
    for i in range(H):
        for j in range(W):
            if (i, j) == start:
                # start = (i, j)
                cost[i, j] = 0
                done[i, j] = True
            if (i, j) == goal:
                pass
                # goal = (i, j)
            if maze[i][j] == '#':
                barrier[i,j] = True
    return cost, done, barrier

def bnf(maze, cost, done, barrier, goal, g):
    for i in range(1, 999):
        done_next = maximum_filter(done, footprint=g) * ~done

        cost_next = minimum_filter(cost, footprint=g) * done_next
        cost_next[done_next] += 1

        cost[done_next] = cost_next[done_next]
        cost[barrier] = 999

        done[done_next] = done_next[done_next]
        done[barrier] = False

        if done[goal[0], goal[1]] == True:
            return max(cost_next[done_next])
            break
    return 0


if __name__ == '__main__':
    H, W = [ int(x) for x in stdin.readline().rstrip().split() ]
    maze = []
    for i in range(H):
        maze.append(stdin.readline().rstrip())

    index = []
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                index.append((i, j))

    g = np.array([
        [0,1,0],
        [1,1,1],
        [0,1,0]
    ])

    costs = []
    for idx_start in index:
        start = idx_start
        for idx_goal in index:
            goal = idx_goal
            cost, done, barrier = init_maze(maze, H, W, start, goal)
            cost, done, barrier = init_maze(maze, H, W, start, goal)
            costs.append(bnf(maze, cost, done, barrier, goal, g))
    print(max(costs))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def calc_dist(s, start_i, start_j, goal_i, goal_j, h, w):
    from collections import deque

    result = 0
    d = deque()
    d.append((start_i, start_j))
    dist = [[0 for _ in range(w)] for _ in range(h)]
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[start_i][start_j] = True
    dxy = [(1, 0), (-1, 0), (0, -1), (0, 1)]

    while d:
        hd, wd = d.popleft()

        for dx, dy in dxy:
            nx = wd + dx
            ny = hd + dy

            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue

            if s[ny][nx] == '#':
                continue

            if visited[ny][nx]:
                continue

            visited[ny][nx] = True
            dist[ny][nx] = dist[hd][wd] + 1
            d.append((ny, nx))
            result = max(result, dist[ny][nx])

            if nx == goal_j and ny == goal_i:
                return result

    return result


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    ans = 0

    for start_i in range(h):
        for start_j in range(w):
            for goal_i in range(h):
                for goal_j in range(w):
                    if s[start_i][start_j] == '#':
                        continue

                    if s[goal_i][goal_j] == '#':
                        continue

                    ans = max(ans, calc_dist(s, start_i, start_j, goal_i, goal_j, h, w))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right, bisect_left
from itertools import groupby, permutations, combinations
from fractions import gcd
import numpy as np
from sys import stdin, stderr
from collections import deque


def lcm(x, y):
    return (x * y) // gcd(x, y)


def movement_max(start_h, start_w, maze):
    H, W = len(maze), len(maze[0])
    score = []
    unvisited = deque()
    visited = []
    # unvisited.add(start_h + start_w*100)
    for h in range(H):
        score.append([1000] * W)
        visited.append([False] * W)
        # for w in range(W):
        #     if maze[h][w] == "#":
        #         visited.add(h + w*100)
    score[start_h][start_w] = 0
    unvisited.append([start_h, start_w])
    ret = 0
    while len(unvisited) > 0:
        h, w = unvisited.popleft()
        # hw = unvisited.pop()
        # h = hw % 100
        # w = hw // 100
        # visited.add(hw)
        visited[h][w] = True
        if maze[h][w] == "#":
            continue
        s = score[h][w] + 1
        if h > 0:
            score[h-1][w] = min(s, score[h-1][w])
            if not visited[h-1][w]:
                unvisited.append([h-1, w])
            # if (h-1 + w*100) not in visited:
            #     unvisited.add(h-1 + w*100)

        if h < H - 1:
            score[h+1][w] = min(s, score[h+1][w])
            if not visited[h+1][w]:
                unvisited.append([h+1, w])
            # if (h+1 + w*100) not in visited:
            #     unvisited.add(h+1 + w*100)
        if w > 0:
            score[h][w-1] = min(s, score[h][w-1])
            if not visited[h][w-1]:
                unvisited.append([h, w-1])
            # if (h + (w-1)*100) not in visited:
            #     unvisited.add(h + (w-1)*100)
        if w < W - 1:
            score[h][w+1] = min(s, score[h][w+1])
            if not visited[h][w+1]:
                unvisited.append([h, w+1])
            # if (h + (w+1)*100) not in visited:
            #     unvisited.add(h + (w+1)*100)
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                continue
            ret = max(score[h][w], ret)
    return ret


def main():
    H, W = [int(x) for x in input().split()]
    maze = [""] * H
    score = []
    for i in range(H):
        maze[i] = input()
        score.append([-1] * W)
    result = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                continue
            # score[h][w] = movement_max(h, w, maze)
            result = max(result, movement_max(h, w, maze))
            # print(result)
        # print(score[h])
    return result


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right, bisect_left
from itertools import groupby, permutations, combinations
from fractions import gcd
import numpy as np
from sys import stdin, stderr
from collections import deque


def lcm(x, y):
    return (x * y) // gcd(x, y)


def movement_max(start_h, start_w, maze):
    H, W = len(maze), len(maze[0])
    score = []
    unvisited = deque()
    visited = []
    # unvisited.add(start_h + start_w*100)
    for h in range(H):
        score.append([1000] * W)
        visited.append([False] * W)
        # for w in range(W):
        #     if maze[h][w] == "#":
        #         visited.add(h + w*100)
    score[start_h][start_w] = 0
    unvisited.append([start_h, start_w])
    ret = 0
    while len(unvisited) > 0:
        h, w = unvisited.popleft()
        # hw = unvisited.pop()
        # h = hw % 100
        # w = hw // 100
        # visited.add(hw)
        visited[h][w] = True
        if maze[h][w] == "#":
            continue
        s = score[h][w] + 1
        if h > 0:
            score[h-1][w] = min(s, score[h-1][w])
            if not visited[h-1][w]:
                unvisited.append([h-1, w])
            # if (h-1 + w*100) not in visited:
            #     unvisited.add(h-1 + w*100)

        if h < H - 1:
            score[h+1][w] = min(s, score[h+1][w])
            if not visited[h+1][w]:
                unvisited.append([h+1, w])
            # if (h+1 + w*100) not in visited:
            #     unvisited.add(h+1 + w*100)
        if w > 0:
            score[h][w-1] = min(s, score[h][w-1])
            if not visited[h][w-1]:
                unvisited.append([h, w-1])
            # if (h + (w-1)*100) not in visited:
            #     unvisited.add(h + (w-1)*100)
        if w < W - 1:
            score[h][w+1] = min(s, score[h][w+1])
            if not visited[h][w+1]:
                unvisited.append([h, w+1])
            # if (h + (w+1)*100) not in visited:
            #     unvisited.add(h + (w+1)*100)
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                continue
            ret = max(score[h][w], ret)
    return ret


def main():
    H, W = [int(x) for x in input().split()]
    maze = [""] * H
    score = []
    for i in range(H):
        maze[i] = input()
        score.append([-1] * W)
    result = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                continue
            score[h][w] = movement_max(h, w, maze)
            result = max(result, movement_max(h, w, maze))
            # print(result)
        # print(score[h])
    return result


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

input = sys.stdin.readline


class Solution:
    def main(self):
        H, W = map(int, input().split())
        S = [list(input().rstrip()) for _ in range(H)]

        for i in range(H):
            S[i] = ["#"] + S[i] + ["#"]
        S = [["#"] * (W + 2)] + S + [["#"] * (W + 2)]

        already = set()
        ans = 0
        for i in range(1, H + 1):
            for j in range(1, W + 1):
                if S[i][j] == "#":
                    continue
                for n in range(1, H + 1):
                    for m in range(1, W + 1):
                        if S[n][m] == "#" or (i, j) == (n, m) or (i, j, n, m) in already:
                            continue
                        v = self.min_move(S, (i, j), (n, m))
                        already.add((i, j, n, m))
                        already.add((n, m, i, j))
                        ans = max(ans, v)
        print(ans)

    def min_move(self, map, start, goal):
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))

        q = queue.Queue()
        q.put((start, 0))

        while not q.empty():
            pos, cnt = q.get()
            for move in moving_range:
                i, j = pos[0] + move[0], pos[1] + move[1]
                if (i, j) == goal:
                    return cnt + 1
                if map[i][j] == ".":
                    q.put(((i, j), cnt + 1))


# Run main
if __name__ == '__main__':
    Solution().main()

Submission status: Time Limit Exceeded

Solution code:

H, W = [int(i) for i in input().split()]
SSS = [[10000000000000 for i in range(W+2)]]
for i in range(H):
    buff = "#"+input()+"#"
    SSS.append([0 if i=="." else 10000000000000 for i in buff])
SSS.append([10000000000000 for i in range(W+2)])

def routetable(x0,y0):
    table = [[10000000 for i in range(W+2)] for j in range(H+2)]
    for i in range(H+2):
        for j in range(W+2):
            if SSS[i][j]==10000000000000:
                table[i][j]=SSS[i][j]
    table[x0][y0]=1

    
    while True:
        detector = 0
        for i in range(1,H+1):
            for j in range(1,W+1):
                if table[i][j]==10000000: detector += 1
                if table[i-1][j]!=10000000000000: table[i-1][j]=min(table[i][j]+1,table[i-1][j])
                if table[i+1][j]!=10000000000000: table[i+1][j]=min(table[i][j]+1,table[i+1][j])
                if table[i][j-1]!=10000000000000: table[i][j-1]=min(table[i][j]+1,table[i][j-1])
                if table[i][j+1]!=10000000000000: table[i][j+1]=min(table[i][j]+1,table[i][j+1])
        if detector==0:
            break
    """
    print("\n")
    for t in table:
        print(t)
    """
    maxroute = 0
    for i in range(H+2):
        for j in range(W+2):
            if table[i][j]!=10000000000000:
                maxroute = max(maxroute,table[i][j])
    return(maxroute-1)


ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if SSS[i][j]!=10000000000000:
            ans = max(ans,routetable(i,j))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def calc_dist(s, start_i, start_j, goal_i, goal_j, h, w):
    from collections import deque

    result = 0
    d = deque()
    d.append((start_i, start_j))
    dist = [[0 for _ in range(w)] for _ in range(h)]
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[start_i][start_j] = True
    dxy = [(1, 0), (-1, 0), (0, -1), (0, 1)]

    while d:
        hd, wd = d.popleft()

        for dx, dy in dxy:
            nx = wd + dx
            ny = hd + dy

            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue

            if s[ny][nx] == '#':
                continue

            if visited[ny][nx]:
                continue

            visited[ny][nx] = True
            dist[ny][nx] = dist[hd][wd] + 1
            d.append((ny, nx))

            if nx == goal_j and ny == goal_i:
                for i in range(h):
                    for j in range(w):
                        result = max(result, dist[i][j])

                return result

    return result


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    ans = 0

    for start_i in range(h):
        for start_j in range(w):
            for goal_i in range(h):
                for goal_j in range(w):
                    if s[start_i][start_j] == '#':
                        continue

                    if s[goal_i][goal_j] == '#':
                        continue

                    ans = max(ans, calc_dist(s, start_i, start_j, goal_i, goal_j, h, w))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
maze = []
pad = ' ' * (W+2)
maze.append(pad)
for i in range(H):
  m = input()
  maze.append(' ' + m + ' ')
maze.append(pad)
  
def bfs(maze, x,y, score):
    queue = [(x,y,0)]
    visited = {}
    while queue:
      x,y,s = queue.pop(0)
      if maze[x][y] != '.':
        continue
      visited[(x,y)] = s
      if (x+1,y) not in visited:
        queue.append((x+1,y,s+1))
      if (x-1,y) not in visited:
        queue.append((x-1,y,s+1))
      if (x,y+1) not in visited:
        queue.append((x,y+1,s+1))
      if (x,y-1) not in visited:
        queue.append((x,y-1,s+1))
    return max(visited.values())
  
ans = -1
for h in range(1,H+1):
  for w in range(1,W+1):
    now = maze[h][w]
    if now == '#':
      continue
    count = 0
    if maze[h-1][w] == '.':
      count+=1
    if maze[h+1][w] == '.':
      count+=1
    if maze[h][w-1] == '.':
      count+=1
    if maze[h][w+1] == '.':
      count+=1
    if count > 2:
      continue
    a = bfs(maze,h,w,0)
    if a > ans:
      ans = a
print(ans)

Submission status: Time Limit Exceeded

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

def Maze_Master(y, x, c):
    if y < 0 or y > h-1 or x < 0 or x > w-1 or m[y][x] != 0 and m[y][x] < c or s[y][x] == "#":
        pass
    else:
        m[y][x] = c
        c += 1
        Maze_Master(y+1, x, c)
        Maze_Master(y-1, x, c)
        Maze_Master(y, x+1, c)
        Maze_Master(y, x-1, c)
    return m
    
a = 0
for y in range(h):
    for x in range(w):
        m = [[0]*w for _ in range(h)]
        ans = Maze_Master(x, y, 1)
        l = []
        for i in ans:
            l.append(max(i))
        b = max(l)
        a = max(a, b)

print(a-1)

Submission status: Time Limit Exceeded

Solution code:
import copy

H,W = map(int,input().split())

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

#print(S)
inf = 10 ** 3
data = [[[[inf for i in range(W+2)] for j in range(H+2)] for k in range(W+2)] for l in range(H+2)]

for i in range(1,H+1):
    for j in range(1,W+1):
        data[i][j][i][j] = 0

for m in range((H+2)*(W+2)//2):
    data_ = copy.copy(data)
    for i in range(1,H+1):
      for j in range(1,W+1):
        for k in range(1,H+1):
            for l in range(1,W+1):
                if S[i][j] == "#" or S[k][l] == "#":
                    continue
                data_[i][j][k][l] = min(data[i][j][k][l],data[i][j][k+1][l]+1,data[i][j][k-1][l]+1,data[i][j][k][l+1]+1,data[i][j][k][l-1]+1)

x = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        for k in range(1,H+1):
            for l in range(1,W+1):
                if x < data_[i][j][k][l] and data_[i][j][k][l] != inf:
                    x = data_[i][j][k][l]

print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw, gh, gw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        # ゴールの条件
        if h == gh and w == gw:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                   continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    stack.append([new_h, new_w])
    
    return visited[gh][gw]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if maze[sh][sw] != "#" and maze[gh][gw] != "#" and vd[sh][sw][gh][gw] == 0 and vd[gh][gw][sh][sw] == 0 and not (gh == sh and gw == sw):
                        if ans >= 1 and (abs(sh - gh) + abs(sw - gw) <= 1):
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                        else:
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                            visited = [[-1] * W for _ in range(H)]
                            step_cnt = bfs(maze, visited, sh, sw, gh, gw)
                            ans = max(ans, step_cnt)
    print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
import numpy as np

H,W = list(map(int,input().split()))

maze = []
maze.append(["#" for i in range(W+2)])
for i in range(H):
    maze.append(list(input()))
    maze[i+1].insert(0,"#")
    maze[i+1].append("#")
maze.append(["#" for i in range(W+2)])

distance_template = np.array([[-1 for i in range(W+2)] for i in range(H+2)])

ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        cnt = 0
        for k in range(0, 4):
            nx, ny = i + [1, 0, -1, 0][k], j + [0, 1, 0, -1][k]
            if maze[nx][ny] != "#":
                cnt+=1
                if cnt == 3:
                    continue
        if maze[i][j] != "#":
            startx,starty = i,j
            distance = copy.deepcopy(distance_template)
            distance[startx][starty] = 0
            Q = queue.Queue()
            Q.put((startx, starty))
            while not Q.empty():
                x,y = Q.get()
                for k in range(0, 4):
                    nx, ny = x + [1, 0, -1, 0][k], y + [0, 1, 0, -1][k]
                    if (maze[nx][ny] != "#" and distance[nx][ny] == -1):
                        Q.put((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1
            maxdistance = np.unravel_index(np.argmax(distance), distance.shape)
            if ans < distance[maxdistance[0]][maxdistance[1]]:
                ans = distance[maxdistance[0]][maxdistance[1]]
print(ans)

Submission status: Time Limit Exceeded

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

move = [[0 for i in range(W)]for i in range(H)]

S = ["#" for i in range(H)]

M = 0

for i in range(H):
    S[i] = input()





def keisoku(sx,sy,ex,ey):
    global W
    global H
    end = False

    count = 1

    kyori = [[-1 for i in range(W)]for i in range(H)]
    kyori[ey][ex] == 0
    if ey < H-1:
        
        if S[ey+1][ex] == ".":
            kyori[ey+1][ex] = 1
    if ey >= 1:
        if S[ey-1][ex] == ".":
            kyori[ey-1][ex] = 1
    if ex < W -1:
            
        if S[ey][ex+1] == ".":
            kyori[ey][ex+1] = 1
    if ex >= 1:
        if S[ey][ex-1] == ".":
            kyori[ey][ex-1] = 1

    while(not end):
        for x in range(W):
            for y in range(H):
                if kyori[y][x] == count:
                    
                    if y < H -1:
                            
                        if S[y+1][x] == ".":
                            kyori[y+1][x] = count +1
                    if y >= 1:
                            
                        if S[y-1][x] == ".":
                            kyori[y-1][x] = count +1
                    if x < W -1:
                            
                        if S[y][x+1] == ".":
                            kyori[y][x+1] = count +1

                    if x >= 1:
                            
                        if S[y][x-1] == ".":
                            kyori[y][x-1] = count +1

        
        if kyori[sy][sx] != -1:
            end = True
        count += 1
    
    return kyori[sy][sx]
                    
for sx in range(W):
    for sy in range(H):
        for ex in range(W):
            for ey in range(H):
                if S[sy][sx] == "#" or S[ey][ex] == "#" or (sx == ex and sy == ey):
                    continue

                newmax = keisoku(sx,sy,ex,ey)
                if newmax > M:
                    M = newmax 

print(M)