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

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                dist[y][x]=d
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
maze=[]

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [[999999]*w for _ in range(h)]
            
            dq = deque()
            y=i
            x=j
            d=0
            
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                dist[y][x]=d
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
maze=[]

for _ in range(h):
    maze.append(input())

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [[999999]*w for _ in range(h)]
            
            dq = deque()
            y=i
            x=j
            d=0
            
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                dist[y][x]=d
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h)):
                        if(dist[y+m[1]][x+m[0]] > d+1):
                            if(maze[y+m[1]][x+m[0]] == "."):
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

H,W=mint()
s=[input() for _ in range(H)]
n=dict()
k=0
for i in range(H):
    for j in range(W):
        if s[i][j]=='.':
            n[(i,j)]=k
            k+=1
N=len(n)

def solve(s,g):
    if s==g:
        return 0
    q=deque([s])
    res=[-1]*N
    res[n[s]]=0
    while True:
        i,j=q.popleft()
        for x in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if x in n and res[n[x]]<0:
                res[n[x]]=res[n[(i,j)]]+1
                if x==g:
                    return res[n[x]]
                q.append(x)
ans=0
for s in n:
    for g in n:
        ans=max(ans,solve(s,g))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(maze,H, W, S, G):
    next_set = set()
    next_set.add(S)
    seen = [[False]*W for _ in range(H)]
    n = 0
    while True:
        curr_ = list(next_set)
        next_set = set()
        for h, w in curr_:
            if (h, w) == G:
                return n
            if seen[h][w]:
                continue

            seen[h][w] = True
            for x in maze[h][w]:
                next_set.add(x)
        n += 1
    
    return print('error')

# 入力
H, W = list(map(int, input().split()))
maze = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False


# mazeに移動可能移動可能なマスを記録
for h in range(H):
    for w in range(W):
        if maze[h][w] == False:
            continue
        for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if 0 <= nh < H and 0<= nw < W:
                if maze[nh][nw] != False:
                    maze[h][w].append((nh, nw))
        # print(maze)
# print(maze)
ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        S = (i//W, i%W)
        G = (j//W, j%W)
        if maze[S[0]][S[1]] and maze[G[0]][G[1]]:
            ans = max(ans, solve(maze, H, W, S, G))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(maze,H, W, S, G):
    next_set = set()
    next_set.add(S)
    seen = [[False]*W for _ in range(H)]
    n = 0
    while True:
        curr_ = list(next_set)
        next_set = set()
        for h, w in curr_:
            if (h, w) == G:
                return n
            if seen[h][w]:
                continue

            seen[h][w] == True
            for x in maze[h][w]:
                next_set.add(x)
        n += 1
    
    return print('error')

# 入力
H, W = list(map(int, input().split()))
maze = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False


# mazeに移動可能移動可能なマスを記録
for h in range(H):
    for w in range(W):
        if maze[h][w] == False:
            continue
        for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if 0 <= nh < H and 0<= nw < W:
                if maze[nh][nw] != False:
                    maze[h][w].append((nh, nw))
        # print(maze)
# print(maze)
ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        S = (i//W, i%W)
        G = (j//W, j%W)
        if maze[S[0]][S[1]] and maze[G[0]][G[1]]:
            ans = max(ans, solve(maze, H, W, S, G))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(maze,H, W, S, G):
    next_ = [S]
    seen = [[False]*W for _ in range(H)]
    n = 0
    while True:
        curr_ = next_[:]
        next_ = []
        for h, w in curr_:
            if (h, w) == G:
                return n
            if seen[h][w]:
                continue

            seen[h][w] == True
            next_ += maze[h][w]
        n += 1
    
    return print('error')

# 入力
H, W = list(map(int, input().split()))
maze = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False


# mazeに移動可能移動可能なマスを記録
for h in range(H):
    for w in range(W):
        if maze[h][w] == False:
            continue
        for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if 0 <= nh < H and 0<= nw < W:
                if maze[nh][nw] != False:
                    maze[h][w].append((nh, nw))
        # print(maze)
# print(maze)
ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        S = (i//W, i%W)
        G = (j//W, j%W)
        if maze[S[0]][S[1]] and maze[G[0]][G[1]]:
            ans = max(ans, solve(maze, H, W, S, G))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(maze,H, W, S, G):
    next_ = [S]
    seen = [[False]*W for _ in range(H)]
    n = 0
    while True:
        curr_ = next_[:]
        next_ = []
        for x in curr_:
            if seen[x[0]][x[1]]:
                continue
            seen[x[0]][x[1]] == True
            if x == G:
                return n
            move_to = [(x[0]+1, x[1]), (x[0], x[1]+1), (x[0]-1, x[1]), (x[0], x[1]-1)] 
            for m in move_to:
                h, w = m
                if 0 <= h < H and 0<= w < W:
                    if maze[h][w]:
                        next_.append(m)
        n += 1
    
    return print('error')

H, W = list(map(int, input().split()))
maze = [[True]*W for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False

ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        S = (i//W, i%W)
        G = (j//W, j%W)
        if maze[S[0]][S[1]] and maze[G[0]][G[1]]:
            ans = max(ans, solve(maze, H, W, S, G))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(maze,H, W, S, G):
    next_set = set()
    next_set.add(S)
    seen = [[False]*W for _ in range(H)]
    n = 0
    while True:
        curr_set = list(next_set)
        next_set = set()
        for x in curr_set:
            seen[x[0]][x[1]] == True
            if x == G:
                return n
            move_to = [(x[0]+1, x[1]), (x[0], x[1]+1), (x[0]-1, x[1]), (x[0], x[1]-1)] 
            for m in move_to:
                h, w = m
                if 0 <= h < H and 0<= w < W:
                    if maze[h][w] and seen[h][w] == False:
                        next_set.add(m)
        n += 1
    
    return print('error')

H, W = list(map(int, input().split()))
maze = [[True]*W for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False

ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        S = (i//W, i%W)
        G = (j//W, j%W)
        if maze[S[0]][S[1]] and maze[G[0]][G[1]]:
            ans = max(ans, solve(maze, H, W, S, G))

print(ans)

Submission status: Time Limit Exceeded

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

def bfs(maze, sy, sx, gy, gx):
    visited = [[-1]*W for j in range(H)]
    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 0 <= new_y < H and 0 <= new_x < W:
                if 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])
ma=0
for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if maze[sy][sx] == "." and maze[gy][gx] == ".":
                    if bfs(maze,sy,sx,gy,gx) is not None:
                        ma = max(bfs(maze, sy, sx, gy, gx),ma)
print(ma)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            q = deque([(i, j, 0)])
            v = [[0] * w for _ in range(h)]
            while q:
                ii, jj, cnt = q.popleft()
                v[ii][jj] = 1
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and v[ii + 1][jj] == 0:
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and v[ii][jj + 1] == 0:
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and v[ii - 1][jj] == 0:
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and v[ii][jj - 1] == 0:
                    q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from typing import List
 
 
def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = input()
        g.append(r)
    print(mm(h, w, g))
 
 
def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            q = deque([(i, j, 0)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((ii, jj))
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
    return ret
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            q = deque([(i, j, 0)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((ii, jj))
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = [input() for _ in range(h)]
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            q = deque([(i, j, 0)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((ii, jj))
                ret = max(ret, cnt)
                for d_ii, d_jj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    n_ii = ii + d_ii
                    n_jj = jj + d_jj
                    if n_ii >= h or n_jj >= w or n_ii < 0 or n_jj < 0:
                        continue
                    if g[n_ii][n_jj] == '#' or (n_ii, n_jj) in v:
                        continue
                    q.append((n_ii, n_jj, cnt + 1))
                # n_ii =
                # # ↓
                # if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                #     q.append((ii + 1, jj, cnt + 1))
                # # →
                # if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                #     q.append((ii, jj + 1, cnt + 1))
                # # ↑
                # if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                #     q.append((ii - 1, jj, cnt + 1))
                # # ←
                # if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                #     q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = [input() for _ in range(h)]
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            cnt = 0
            q = deque([(i, j, cnt)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((ii, jj))
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            cnt = 0
            q = deque([(i, j, cnt)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((ii, jj))
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            cnt = 0
            q = deque([(i, j, cnt)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((20 * ii + jj))
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (20 * (ii + 1) + jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (20 * ii + (jj + 1)) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (20 * (ii - 1) + jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (20 * ii + (jj - 1)) not in v:
                    q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
h, w = map(int,input().split())

maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for j in s:
    if j == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

def bfs(start):
  maze2 = copy.deepcopy(maze)
  #print(maze2)
  pos = [start]
  max_depth = 0
  while len(pos):
    x, y, depth = pos.pop(0)
    max_depth = max(depth, max_depth)
    
    maze2[x][y] = 2
    if maze2[x-1][y] < 2:
      pos.append([x-1,y,depth + 1])
    if maze2[x+1][y] < 2:
      pos.append([x+1,y,depth + 1])
    if maze2[x][y-1] < 2:
      pos.append([x,y-1,depth +1])
    if maze2[x][y+1] < 2:
      pos.append([x,y+1,depth +1])
  return max_depth

ans = 0
for i in range(h):
  for j in range(w):
      start = [i+1,j+1,0]
      if maze[i+1][j+1] != 9:
        #print(bfs(start))
      	ans =max(ans,bfs(start))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = list(map(int, raw_input().split()))
grid = [raw_input() for _ in range(h)]

ans = 0

for startx in range(w):
    for starty in range(h):
        for endx in range(w):
            for endy in range(h):
                if grid[starty][startx] == "#" or grid[endy][endx] == "#":
                    continue

                dist = [[10000]*w for _ in range(h)]
                dist[starty][startx] = 0

                q = deque([(startx, starty)])

                while q:
                    curx, cury = q.popleft()
                    if (curx, cury) == (endx, endy):
                        break

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

                    for xo, yo in adj:
                        x, y = curx + xo, cury + yo

                        if x < 0 or x >= w or y < 0 or y >= h:
                            continue
                        if grid[y][x] == "#":
                            continue

                        newDist = dist[cury][curx] + 1
                        if newDist < dist[y][x]:
                            dist[y][x] = newDist
                            q.append((x, y))

                ans = max(ans, dist[endy][endx])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy as np

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
dir4 = [[-1,0],[1,0],[0,-1],[0,1]]


def solveMaze(s, g):
    q = queue.Queue()
    q.put([s[0],s[1],0])
    times = [[999999999 for j in range(W)] for i in range(H)]

    while not q.empty():
        now = q.get()
        for i in range(4):
            nextH = now[0] + int(dir4[i][0])
            nextW = now[1] + int(dir4[i][1])
            time = now[2] + 1
            g0 = g[0]
            g1 = g[1]

            if nextH == g[0] and nextW == g[1]:
                return time

            if nextH < 0 or nextH >= H or nextW < 0 or nextW >=W or maze[nextH][nextW] == "#" or times[nextH][nextW] <= time:
                continue
            else:
                times[nextH][nextW] = time
                q.put([nextH, nextW, time])

    return -1


ans = 0

for sH in range(H):
    for sW in range(W):
        if maze[sH][sW] == ".":
            for gH in range(H):
                for gW in range(W):
                    if maze[gH][gW] == ".":
                        if sH != gH or sW != gW:
                            ans = max(ans, solveMaze([sH, sW], [gH, gW]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
q=collections.deque()
h,w=map(int,input().split())
S=[]
for _ in range(h):
    s=input()
    S.append(s)
went=[[0]*w for _ in range(h)]
l=[]
def walk(x,y):
    if x<=h-2:
        if S[x+1][y]=='.' and (x+1,y)!=(ih,iw) and went[x+1][y]==0 or went[x+1][y]>went[x][y]+1:
            went[x+1][y]=went[x][y]+1
            q.append((x+1,y))
    if y<=w-2:
        if S[x][y+1]=='.' and (x,y+1)!=(ih,iw) and went[x][y+1]==0 or went[x][y+1]>went[x][y]+1:
            went[x][y+1]=went[x][y]+1
            q.append((x,y+1))
    if y>=1:
        if S[x][y-1]=='.' and (x,y-1)!=(ih,iw) and went[x][y-1]==0 or went[x][y-1]>went[x][y]+1:
            went[x][y-1]=went[x][y]+1
            q.append((x,y-1))
    if x>=1:
        if S[x-1][y]=='.' and (x-1,y)!=(ih,iw) and went[x-1][y]==0 or went[x-1][y]>went[x][y]+1:
            went[x-1][y]=went[x][y]+1
            q.append((x-1,y))
        
for ih in range(h):
    for iw in range(w):
        if S[ih][iw]=='.':
            went=[[0]*w for _ in range(h)]
            q.append((ih,iw))
            while q:
                (a,b)=q.pop()
                walk(a,b)
            
            ll=[]
            for i in range(h):
                ll.append(max(went[i]))
            l.append(max(ll))
            
print(max(l))

Submission status: Time Limit Exceeded

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

S = [["#"] * (W + 2) for i in range(H + 2)]
for i in range(H):
    s = input()
    for j in range(W):
        S[i + 1][j + 1] = s[j]
#print(S)

g = H * W

d = [[float("INF")] * g for i in range(g)]
for i in range(g):
    d[i][i] = 0

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if S[i][j] == ".":
            p = (i - 1)*W + (j - 1)
            if S[i][j+1] == ".":
                d[p][p + 1] = 1
            if S[i][j-1] == ".":
                d[p][p - 1] = 1
            if S[i+1][j] == ".":
                d[p][p + W] = 1
            if S[i-1][j] == ".":
                d[p][p - W] = 1

for k in range(g):
    for i in range(g):
        for j in range(g):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0

for i in range(g):
    for j in range(g):
        if d[i][j] != float("INF"):
            ans = max(ans, d[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections # deque, Counter
# import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
# import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # Python3.5以前 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # Python3.6以降
# --------------------------------------------------------------

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

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

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

cnt = 0

for j in range(H):
    for k in range(W):
        for l in range(H):
            for m in range(W):
                if maze[j][k]=='#' or maze[l][m]=='#':
                    continue
                else:
                    sy = j
                    sx = k
                    gy = l
                    gx = m

                    seen = [[-1 for _ in range(W)] for _ in range(H)]
                    seen[sy][sx] = 0

                    que  = collections.deque()  # 発見済未訪問な頂点
                    que.append([sy,sx])

                    while(len(que)!=0):
                        p = que.popleft()
                        for i in range(4):
                            ny = p[0] + dy[i]
                            nx = p[1] + dx[i]
                            if (ny >= 0 and nx >=0 and ny < H and nx < W and seen[ny][nx] == -1 and maze[ny][nx] != '#'):
                                seen[ny][nx] = seen[p[0]][p[1]] + 1
                                que.append([ny,nx])

                    cnt = max(cnt, seen[gy][gx])

print(cnt)