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
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    #root=[[-1 for i in range(h*w)] for i in range(h*w)]
    root=[0]*(h*w)
    for i in range(h*w):
        root[i]=[-1]*(h*w)
    ina=[i for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=deque()
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                toVis.append(i)
                dist[i]=dist[now]+1
        while len(toVis)>0:
            now=toVis.popleft()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.append(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
n=h*w
inf=10**6
field=[]
for i in range(h):
    field.append(input())
dist=[[inf]*n for i in range(n)]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":continue
        if j+1<w and field[i][j+1]!="#":
            dist[i*w+j][i*w+j+1]=1
            dist[i*w+j+1][i*w+j]=1
        if i+1<h and field[i+1][j]!="#":
            dist[i*w+j][(i+1)*w+j]=1
            dist[(i+1)*w+j][i*w+j]=1
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if dist[i][j]==inf:
            continue
        ans=max(ans,dist[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    #root=[[-1 for i in range(h*w)] for i in range(h*w)]
    root=[0]*(h*w)
    for i in range(h*w):
        root[i]=[-1]*(h*w)
    ina=[i for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=queue.Queue()
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                toVis.put(i)
                dist[i]=dist[now]+1
        while toVis.empty()!=True:
            now=toVis.get()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.put(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    root=numpy.array([[-1 for i in range(h*w)] for i in range(h*w)])
    ina=numpy.array([i for i in range(h*w)])
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=queue.Queue()
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                toVis.put(i)
                dist[i]=dist[now]+1
        while toVis.empty()!=True:
            now=toVis.get()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.put(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    root=[[-1 for i in range(h*w)] for i in range(h*w)]
    ina=[i for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in ina:
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=queue.Queue()
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                toVis.put(i)
                dist[i]=dist[now]+1
        while toVis.empty()!=True:
            now=toVis.get()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.put(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    root=[[-1 for i in range(h*w)] for i in range(h*w)]
    ina=[0]*(h*w)
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=queue.Queue()
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                toVis.put(i)
                dist[i]=dist[now]+1
        while toVis.empty()!=True:
            now=toVis.get()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.put(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    root=[[-1 for i in range(h*w)] for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    max=0
    hw=h*w
    for start in range(hw):
        dist=[-1]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=queue.Queue()
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                toVis.put(i)
                dist[i]=dist[now]+1
        while toVis.empty()!=True:
            now=toVis.get()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.put(i)
                    dist[i]=le+1
        #print("s:",start,"g:",goal,"len",dist[goal])
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    h,w=map(int,input().split())
    maze=[]
    for i in range(h):
        row=input()
        maze.append(row)
    #print(maze)
    root=[[-1 for i in range(h*w)] for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            if maze[i][j]==".":
                now=w*i+j
                hidari=w*i+j-1
                migi=w*i+j+1
                ue=w*(i-1)+j
                sita=w*(i+1)+j
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                now=w*i+j
                now=w*i+j
                hidari=w*i+j-1
                migi=w*i+j+1
                ue=w*(i-1)+j
                sita=w*(i+1)+j
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    for start in range(h*w):
        dist=[-1]*(h*w)
        now=start
        dist[start]=0
        visted=[0]*(h*w)
        toVis=queue.Queue()
        visted[now]=1
        for i in range(h*w):
            if root[now][i]!=-1:
                toVis.put(i)
                dist[i]=dist[now]+1
        while toVis.empty()!=True:
            now=toVis.get()
            visted[now]=1
            for i in range(h*w):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.put(i)
                    dist[i]=dist[now]+1
        #print("s:",start,"g:",goal,"len",dist[goal])
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w=map(int,input().split())
maze=[]
def func(n):
    if n=="#":
        return -1
    else:
        return 0


for i in range(h):
    row=input()
    maze.append(row)
#print(maze)
root=[[-1 for i in range(h*w)] for i in range(h*w)]
for i in range(h):
    for j in range(w):
       # print(maze[i][j])
        if maze[i][j]==".":
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if j>0:
                if maze[i][j-1]!="#":
                    root[now][hidari]=0
            if i+1<h:
                if maze[i+1][j]!="#":
                    root[now][sita]=0
            if j+1<w:
                if maze[i][j+1]!="#":
                    root[now][migi]=0
            if 0<i:
                if maze[i-1][j]!="#":
                    root[now][ue]=0
        else:
            now=w*i+j
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if j>0:
                root[now][hidari]=-1
            if i+1<h:
                root[now][sita]=-1
            if j+1<w:
                root[now][migi]=-1
            if 0<i:
                root[now][ue]=-1
#print(root)
max=0
for start in range(h*w):
    dist=[-1]*(h*w)
    now=start
    dist[start]=0
    visted=[0]*(h*w)
    toVis=queue.Queue()
    visted[now]=1
    for i in range(h*w):
        if root[now][i]!=-1:
            toVis.put(i)
            dist[i]=dist[now]+1
    while toVis.empty()!=True:
        now=toVis.get()
        visted[now]=1
        for i in range(h*w):
            if root[now][i]!=-1 and visted[i]!=1:
                toVis.put(i)
                dist[i]=dist[now]+1
    #print("s:",start,"g:",goal,"len",dist[goal])
    farest=dist[now]
    if max<farest:
        max=farest
print(max)

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w=map(int,input().split())
maze=[]
def func(n):
    if n=="#":
        return -1
    else:
        return 0


for i in range(h):
    row=input()
    maze.append(row)
#print(maze)
root=[[-1 for i in range(h*w)] for i in range(h*w)]
for i in range(h):
    for j in range(w):
       # print(maze[i][j])
        if maze[i][j]==".":
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if j>0:
                if maze[i][j-1]!="#":
                    root[now][hidari]=0
            if i+1<h:
                if maze[i+1][j]!="#":
                    root[now][sita]=0
            if j+1<w:
                if maze[i][j+1]!="#":
                    root[now][migi]=0
            if 0<i:
                if maze[i-1][j]!="#":
                    root[now][ue]=0
        else:
            now=w*i+j
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if j>0:
                root[now][hidari]=-1
            if i+1<h:
                root[now][sita]=-1
            if j+1<w:
                root[now][migi]=-1
            if 0<i:
                root[now][ue]=-1
#print(root)
max=0
for start in range(h*w):
    for goal in range(h*w):
        
        if start==goal:
            continue
        dist=[-1]*(h*w)
        now=start
        dist[start]=0
        visted=[0]*(h*w)
        toVis=queue.Queue()
        visted[now]=1
        for i in range(h*w):
            if root[now][i]!=-1:
                toVis.put(i)
                dist[i]=dist[now]+1
        while toVis.empty()!=True and now!=goal:
            now=toVis.get()
            
            visted[now]=1
            for i in range(h*w):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.put(i)
                    dist[i]=dist[now]+1
        #print("s:",start,"g:",goal,"len",dist[goal])
        if max<dist[goal]:
            max=dist[goal]
print(max)

Submission status: Time Limit Exceeded

Solution code:
import sys

# import re
# import math
# import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
# import copy
# import heapq
# import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    h, w = ns()
    mat = [list(sys.stdin.readline()) for _ in range(h)]

    def bfs(x, y):
        arrived_mat = [[False for i in range(w)] for j in range(h)]

        que = queue.Queue()
        que.put((x, y, 1))
        arrived_mat[y][x] = True
        res = 0

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

        while que.qsize() > 0:
            xi, yi, cnt = que.get()
            arrived_mat[yi][xi] = True

            for dx, dy in direc:
                next_x = xi + dx
                next_y = yi + dy
                if -1 < next_x < w and -1 < next_y < h:
                    if mat[next_y][next_x] == "." and arrived_mat[next_y][next_x] != True:
                        que.put((next_x, next_y, cnt + 1))
                        res = max(res, cnt + 1)

        return res

    ans = 0
    for y in range(h):
        for x in range(w):
            if mat[y][x] == ".":
                ans = max(ans, bfs(x, y) - 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    def bfs(i,j):
        que = collections.deque([[i,j,0]])
        footprint = [[-1 for _ in range(W)] for _ in range(H)]

        while len(que) >=1:
            a, b, c = que.popleft()
            footprint[a][b] = c

            if a != 0:
                if footprint[a-1][b] == -1 and grid[a-1][b] == '.':
                    que.append([a-1, b, c+1])
            if a != H-1:
                if footprint[a+1][b] == -1 and grid[a+1][b] == '.':
                    que.append([a+1, b, c+1])
            if b != 0:
                if footprint[a][b-1] == -1 and grid[a][b-1] == '.':
                    que.append([a, b-1, c+1])
            if b != W-1:
                if footprint[a][b+1] == -1 and grid[a][b+1] == '.':
                    que.append([a, b+1, c+1])

        # print(footprint)
        return max([max(item) for item in footprint])

    res = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                res = max(res, bfs(i,j))
            if res == H+W-2:
                break
        if res == H+W-2:
                break
    
    print(res)
        


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

    def bfs(i,j):
        que = collections.deque([[i,j,0]])
        footprint = [[-1 for _ in range(W)] for _ in range(H)]

        while len(que) >=1:
            a, b, c = que.popleft()
            footprint[a][b] = c

            if a != 0:
                if footprint[a-1][b] == -1 and grid[a-1][b] == '.':
                    que.append([a-1, b, c+1])
            if a != H-1:
                if footprint[a+1][b] == -1 and grid[a+1][b] == '.':
                    que.append([a+1, b, c+1])
            if b != 0:
                if footprint[a][b-1] == -1 and grid[a][b-1] == '.':
                    que.append([a, b-1, c+1])
            if b != W-1:
                if footprint[a][b+1] == -1 and grid[a][b+1] == '.':
                    que.append([a, b+1, c+1])

        # print(footprint)
        return max([max(item) for item in footprint])

    res = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                res = max(res, bfs(i,j))
    
    print(res)
        


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

def bfs(maze,h,w,sx,sy,gx,gy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    return maze[gy][gx]
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '#':
      continue
    for gi in range(H):
      for gj in range(W):
        if maze[gi][gj] == '#' or (si == gi and sj == gj):
          continue
        copymaze = copy.deepcopy(maze)
        res =  int(bfs(copymaze,H,W,sj,si,gj,gi))
        max_dist = max(max_dist,res)

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
h, w = map(int, input().split())
maze = [input() for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
 
# BFSでは、同じステップ数のノードを先に全探索するので、訪問済みフラグはグローバル共有しても大丈夫
 
max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        while True:
            if len(plan) == 0:
                break
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            visited[y][x] = True
            if step > largest_step:
                largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if next_x == -1 or next_x == w or next_y == -1 or next_y == h:
                    continue
                if maze[next_y][next_x] == "#":
                    continue
                # 訪問済みでないかチェック
                if visited[next_y][next_x]:
                    continue
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        if largest_step > max_step:
            max_step = largest_step
 
print(max_step)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys

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


def get_shortest_steps(S_inner, visited, i_inner, j_inner, steps):
    if i_inner == -1 or i_inner == h or j_inner == -1 or j_inner == w:
        return sys.maxsize
    if visited[i_inner * 20 + j_inner]:
        return sys.maxsize
    if S_inner[i_inner][j_inner] == "#":
        return sys.maxsize
    visited[i_inner * 20 + j_inner] = True
    if shortest_steps_map[i_inner * 20 + j_inner] > steps:
        shortest_steps_map[i_inner * 20 + j_inner] = steps
    get_shortest_steps(S_inner, copy.copy(visited), i_inner + 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner + 1, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner - 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner - 1, steps + 1)
    return


result = -1
for i_outer in range(h):
    for j_outer in range(w):
        visited_outer = [False] * (h * 20 + w + 1)
        shortest_steps_map = [500] * (h * 20 + w + 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer, j_outer, 0)

        for i in range(len(shortest_steps_map)):
            if shortest_steps_map[i] == 500:
                shortest_steps_map[i] = 0

        if max(shortest_steps_map) > result:
            result = max(shortest_steps_map)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from collections import deque

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

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        distance = [[-1] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        distance[i][j] = step
        while True:
            if len(plan) == 0:
                break
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            visited[y][x] = True
            distance[i][j] = step
            # if step > largest_step:
            #     largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        # if largest_step > max_step:
        #     max_step = largest_step
        max_step = max(max_step, np.max(np.array(distance)))

print(max_step)