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 sys
from queue import Queue


def get_costs(S):
    costs = [[0 for w in range(len(S[0]))] for h in range(len(S))]
    for h in range(len(S)):
        for w in range(len(S[0])):
            if S[h][w] == '#':
                costs[h][w] = -1
    return costs


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_h in range(H):
        for start_w in range(W):
            costs = get_costs(S)
            queue = Queue()
            queue.put((start_h, start_w, 1))
            cost = 1
            while not queue.empty():
                (y, x, c) = queue.get()
                if not (0 <= y < len(costs) and 0 <= x < len(costs[0])):
                    continue
                if costs[y][x] != 0:
                    continue
                # print("({},{}): {}".format(y, x, c))
                costs[y][x] = c
                cost = c
                queue.put((y - 1, x, c + 1))
                queue.put((y, x + 1, c + 1))
                queue.put((y + 1, x, c + 1))
                queue.put((y, x - 1, c + 1))
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
#A = [list(map(str,input().split())) for i in range(H)]
A = [list(input()) for i in range(H)]

from queue import Queue

dj = [1, 0, -1, 0]
di = [0, 1, 0, -1]

sum_sharp = sum([A[i].count('#') for i in range(H)])

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        d_max = 0
        q_i = Queue()
        q_j = Queue()
        D = [[-1]*W for i in range(H)]
        #flag = [[0]*W for i in range(H)]
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            q_i.put(s_i)
            q_j.put(s_j)
            #while sum(map(sum, flag)) != W*H - sum_sharp:
            while flag < W*H - sum_sharp:
                i = q_i.get()
                j = q_j.get()
                #flag[i][j] =1
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '#' or (D[ni][nj]>=0 and D[ni][nj]<D[i][j]+1):
                    #if ni<0 or ni>=H or nj<0 or nj>=W:
                        continue
                    #elif A[ni][nj]== '#' or D[ni][nj] < D[i][j]+1:
                        #flag[ni][nj] = 1
                        #continue
                    else:
                        if D[ni][nj] == -1:
                            flag += 1
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        q_i.put(ni)
                        q_j.put(nj)
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
#A = [list(map(str,input().split())) for i in range(H)]
A = [list(input()) for i in range(H)]

from queue import Queue

dj = [1, 0, -1, 0]
di = [0, 1, 0, -1]

sum_sharp = sum([A[i].count('#') for i in range(H)])

fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        d_max = 0
        q_i = Queue()
        q_j = Queue()
        D = [[401]*W for i in range(H)]
        #flag = [[0]*W for i in range(H)]
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            q_i.put(s_i)
            q_j.put(s_j)
            #while sum(map(sum, flag)) != W*H - sum_sharp:
            while flag < W*H - sum_sharp:
                i = q_i.get()
                j = q_j.get()
                #flag[i][j] =1
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '#' or D[ni][nj] < D[i][j]+1:
                    #if ni<0 or ni>=H or nj<0 or nj>=W:
                        continue
                    #elif A[ni][nj]== '#' or D[ni][nj] < D[i][j]+1:
                        #flag[ni][nj] = 1
                        #continue
                    else:
                        if D[ni][nj] == 401:
                            flag += 1
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        q_i.put(ni)
                        q_j.put(nj)
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
#A = [list(map(str,input().split())) for i in range(H)]
A = [list(input()) for i in range(H)]
#print(A)
from queue import Queue

#q_i = Queue()
#q_j = Queue()

#D = [[401]*W for i in range(H)]
#flag = [[0]*W for i in range(H)]

dj = [1, 0, -1, 0]
di = [0, 1, 0, -1]

fin_d_max = 0

for s_i in range(H):
    for s_j in range(W):
        #print(s_i, s_j, '\n')
        d_max = 0
        q_i = Queue()
        q_j = Queue()
        D = [[401]*W for i in range(H)]
        flag = [[0]*W for i in range(H)]
        #print(sum(D))

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            q_i.put(s_i)
            q_j.put(s_j)
            while sum(map(sum, flag)) != W*H:
                i = q_i.get()
                j = q_j.get()
                #print(i, j)
                flag[i][j] =1
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    if ni<0 or ni>=H or nj<0 or nj>=W:
                        continue
                    elif A[ni][nj]== '#' or D[ni][nj] < D[i][j]+1:
                        flag[ni][nj] = 1
                        continue
                    else:
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        q_i.put(ni)
                        q_j.put(nj)
                        #print(ni, nj)
                #print(sum(map(sum, flag)))
        #print(D, '\n', '\n')
        #d_max = max(d_max, max(max(D)))
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

V = list(product(range(H), range(W)))

INF = len(V)
dp = dict(product(product(V, V), [INF]))

for v in V:
    dp[v, v] = 0

for v in V:
    x, y = v
    if S[x][y] == '.':
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            xn = x + dx
            yn = y + dy
            if 0 <= xn < H and 0 <= yn < W and S[xn][yn] == '.':
                vn = (xn, yn)
                dp[v, vn] = 1

for k in V:
    for i in V:
        for j in V:
            if dp[i, j] > dp[i, k] + dp[k, j]:
                dp[i, j] = dp[i, k] + dp[k, j]

result = 0
for v in V:
    for w in V:
        if dp[v, w] != INF:
            result = max(result, dp[v, w])

print(result)

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(['...', '...', '...']), 4)

    def test_2(self):
        self.assertEqual(think(['...#.', '.#.#.', '.#...']), 10)


def solve():
    maze = read()
    result = think(maze)
    write(result)


def read():
    h, w = read_int(2)
    maze = []
    for _ in range(h):
        maze.append(read_line(n=w))
    return maze


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(maze):
    wall = '#'
    h, w = get_height_and_width_of(maze)
    longest_path_length = 0

    for y in range(h):
        for x in range(w):
            if maze[y][x] == wall:
                continue
            longest_path_length = max(longest_path_length, search(maze, x, y, wall))

    return longest_path_length


def write(result):
    print(result)


def get_height_and_width_of(maze):
    return len(maze), len(maze[0])


def search(maze, x, y, wall):
    h, w = get_height_and_width_of(maze)
    inf = h * w + 1

    dp = prepare_dp_table(h, w, inf)
    dfs(maze, dp, w, h, x, y, 0, wall)

    return get_longest_path_length(dp, inf)


def prepare_dp_table(h, w, inf):
    return [[inf for _ in range(w)] for _ in range(h)]


def dfs(maze, dp, w, h, x, y, distance, wall):
    if dp[y][x] < distance:
        return
    dp[y][x] = distance

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

    for dx, dy in diff_xy:
        nx, ny = x + dx, y + dy
        if not in_range(w, h, nx, ny):
            continue
        if maze[ny][nx] == wall:
            continue
        if dp[ny][nx] <= distance + 1:
            continue
        dfs(maze, dp, w, h, nx, ny, distance + 1, wall)


def in_range(w, h, x, y):
    return 0 <= x < w and 0 <= y < h


def get_longest_path_length(dp_table, inf):
    h, w = get_height_and_width_of(dp_table)
    longest_path_length = 0
    for y in range(h):
        for x in range(w):
            if dp_table[y][x] == inf:
                continue
            longest_path_length = max(longest_path_length, dp_table[y][x])
    return longest_path_length


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

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

s = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    ll = input()

    for j in range(w):
        if ll[j] == '.':
            s[i][j] = 0
        else:
            s[i][j] = 1

g = [[0 for i in range(w * h)] for j in range(w * h)]
for t in range(h * w):
    y = t // w
    x = t % w

    left = x - 1
    right = x + 1
    up = y - 1
    down = y + 1

    #print('x, y', x, y)

    if s[y][x] == 0:
        if left >= 0:
            if s[y][left] == 0:
                g[t][t - 1] = 1
                g[t - 1][t] = 1
        #print(right, w, s)
        if right < w:
            if s[y][right] == 0:
                g[t][t + 1] = 1
                g[t + 1][t] = 1
        if up >= 0:
            if s[up][x] == 0:
                g[t][t - w] = 1
                g[t - w][t] = 1
        if down < h:
            if s[down][x] == 0:
                g[t][t + w] = 1
                g[t + w][t] = 1

#print(g)

d = [[float('inf') for i in range(w * h)] for j in range(w * h)]
for i in range(w * h):
    for j in range(w * h):
        if g[i][j] != 0:
            d[i][j] = g[i][j]
        if i == j:
            d[i][j] = 0
            

for k in range(w * h):
    for i in range(w * h):
        for j in range(w * h):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

dd = 0
for i in range(w * h):
    for j in range(w * h):
        if d[i][j] != float('inf'):
            if dd < d[i][j]:
                dd = d[i][j]
print(dd)

Submission status: Time Limit Exceeded

Solution code:
import queue

max = 0

tmp = []
tmp = list(map(int, input().split()))

w = tmp.pop()
h = tmp.pop()

maze = [["." for i in range(w)] for j in range(h)]
flag = [[False for i in range(w)] for j in range(h)]

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

xq = queue.Queue()
yq = queue.Queue()
lq = queue.Queue()
    
for i in range(w):
    for j in range(h):

        flag = [[False for i in range(w)] for j in range(h)]
        #        print("{} {} {}".format(j,i, maze[j][i]))
        # start をqueueにいれる
        if maze[j][i]==".":
            xq.put(i)
            yq.put(j)
            lq.put(0)
            flag[j][i]=True

        while not xq.empty():
            x = xq.get() #現在地 x
            y = yq.get() #現在地 y
            l = lq.get() #距離 l

            if max < l:
                max = l
            

            #行ける方向をチェックしてqueueにつむ、訪問済みにする
            #行ける方向 = 上下左右隣接、
            # なおかつ、壁じゃない、迷路の外じゃない、すでに訪問済みじゃない

            # チェックするのは4方向
            if ((x-1) >= 0 ):
                if (flag[y][x-1]==False) and (maze[y][x-1])==".":
                    xq.put(x-1)
                    yq.put(y)
                    lq.put(l+1)
                    flag[y][x-1]=True
                
            if ((x+1) < w ):
#                print("{} {} {}".format(x, y, l))
#                print(maze[x][y])
                if flag[y][x+1]==False and maze[y][x+1]==".":
                    xq.put(x+1)
                    yq.put(y)
                    lq.put(l+1)
                    flag[y][x+1]=True
                
            if ((y-1) >= 0):
                if flag[y-1][x]==False and maze[y-1][x]==".":
                    xq.put(x)
                    yq.put(y-1)
                    lq.put(l+1)
                    flag[y-1][x]=True

            if ((y+1) < h):
#                print("{} {} {}".format(x, y, l))
#                print(maze[x][y])
                if flag[y+1][x]==False and maze[y+1][x]==".":
                    xq.put(x)
                    yq.put(y+1)
                    lq.put(l+1)
                    flag[y+1][x]=True
                

print(max)

Submission status: Time Limit Exceeded

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

s = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    ll = input()

    for j in range(w):
        if ll[j] == '.':
            s[i][j] = 0
        else:
            s[i][j] = 1

g = [[0 for i in range(w * h)] for j in range(w * h)]
for t in range(h * w):
    y = t // w
    x = t % w

    left = x - 1
    right = x + 1
    up = y - 1
    down = y + 1

    #print('x, y', x, y)

    if s[y][x] == 0:
        if left >= 0:
            if s[y][left] == 0:
                g[t][t - 1] = 1
                g[t - 1][t] = 1
        #print(right, w, s)
        if right < w:
            if s[y][right] == 0:
                g[t][t + 1] = 1
                g[t + 1][t] = 1
        if up >= 0:
            if s[up][x] == 0:
                g[t][t - w] = 1
                g[t - w][t] = 1
        if down < h:
            if s[down][x] == 0:
                g[t][t + w] = 1
                g[t + w][t] = 1

#print(g)

d = [[float('inf') for i in range(w * h)] for j in range(w * h)]
for i in range(w * h):
    for j in range(w * h):
        if g[i][j] != 0:
            d[i][j] = g[i][j]
        if i == j:
            d[i][j] = 0
            

for k in range(w * h):
    for i in range(w * h):
        for j in range(w * h):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]

for i in range(w * h):
    for j in range(w * h):
        if d[i][j] == float('inf'):
            d[i][j] = -1
#print(d)
dd = [max(i) for i in d]
print(max(dd))

Submission status: Time Limit Exceeded

Solution code:
import copy
h, w = map(int ,input().split())
maze = []
for i in range(h):
    maze.append(list(input()))
step = copy.deepcopy(maze)

def bfs(sx,sy,gx,gy):
    for i in range(h):
        for j in range(w):
            step[i][j] = 0
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    que = []
    que.append([sx,sy])

    while(len(que) != 0):
        x, y = que[0][0], que[0][1]
        que.remove(que[0])
        if(x == gx and y == gy):
            return step[gy][gx]
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if(0 <= nx < w and 0 <= ny < h):
                if(step[ny][nx] == 0 and maze[ny][nx] != "#"):
                    step[ny][nx] = step[y][x] + 1
                    que.append([nx, ny])
    
ans = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                if(maze[i][j] == "." and maze[k][l] == "."):
                    ans = max(ans, bfs(j, i, l, k))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
H,W=map(int,input().rstrip().split())
maze=[list(input().rstrip()) for i in range(H)]
def resolve():
    seen=[[0 for i in range(W)] for j in range(H)]
    ans=0
    for i in range(H):
        for j in range(W):
            for k in range(H):
                for l in range(W):
                    if maze[i][j]=="#" or maze[k][l]=="#":
                        continue
                    maze[k][l]=1#end
                    buf=bfs(maze,seen,i,j)
                    ans=max(ans,buf)

                    seen=[[0 for i in range(W)] for j in range(H)]
                    maze[k][l]="."
    print(ans)
    
def bfs(maze, seen, sh, sw):
    stack = deque([[sh, sw]])
    seen[sh][sw] = 1
    expandcount=0#今のdepthに展開されたノードを親ノードとしたときの子ノードの数
    expanded=-1#今のdepthに展開されたノード数
    popcount=0#popした数
    depth=0#ルートからの深さ
    while stack:
        h, w = stack.popleft()
        popcount+=1
        if maze[h][w] == 1:
            return depth
        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  seen[new_h][new_w] == 0:#未発見
                seen[new_h][new_w] = 1#発見済みにする
                stack.append([new_h, new_w])#隣接を探索予定に
                expandcount+=1
        
        if popcount==expanded or expanded==-1:#同一のdepthは探索済み、下のdepthの探索に移る
            expanded=expandcount
            popcount=0
            expandcount=0
            depth+=1
    
"""
    for i in range(H):
        for j in range(W):
            if(S[i][j]=="#"):
                for dir in range(4):
                    nx=j+dx[dir]
                    ny=i+dy[dir]

                    if(nx<0 or nx>=W):
                        continue
                    if(ny<0 or ny>=H):
                        continue

                    if(S[i][j]==S[ny][nx]):
                        break
                else:
                    print("No")
                    return
    print("Yes")
"""
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
...
..."""
        output = """4"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3 5
...#.
.#.#.
.#..."""
        output = """10"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#input
H, W = map(int, input().split())
S = [list(str(input())) for i in range(H)]

#output
import numpy as np
INF = -1
dp = np.full((H, W), INF)

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

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

        while len(q):
            x, y = q.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + dx[i], y + dy[i]

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

L = []
for h1 in range(H):
    for h2 in range(H):
        for w1 in range(W):
            for w2 in range(W):
                if S[h1][w1] != "#" and S[h2][w2] != "#":
                    dp = np.full((H, W), INF)
                    p = clear_maze(h1, w1, h2, w2, S)
                    if p != INF:
                        L.append(p)
print(int(max(L)))

Submission status: Time Limit Exceeded

Solution code:
import queue

D = ((0, 1), (1, 0), (0, -1), (-1, 0))

def bfs(M, s, g):

    if s == g:
        return 0

    q = queue.Queue()
    q.put((s[0], s[1], 0))

    while not q.empty():
        cur = q.get()

        for d in D:
            x = cur[0] + d[0]
            y = cur[1] + d[1]
            if M[y][x] != '#':
                if (x, y) == g:
                    return cur[2] + 1
                else: 
                    q.put((x, y, cur[2]+1))

    return 20*20+1

H, W = map(int, input().split())
S = [None]*(H+2)

S[0] = '#' * (W + 2)
for h in range(1, H+1):
    S[h] = '#' + input() + '#'
S[-1] = '#' * (W + 2)

ans = 0
for sy in range(1, H+1):
    for sx in range(1, W+1):
        if S[sy][sx] != '#':
            for gy in range(sy, H+1):
                for gx in range(1, W+1):
                    if S[gy][gx] != '#' and not (sy == gy and gx < sx):
                        ans = max(ans, bfs(S, (sx, sy), (gx, gy)))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def make_noreplace_comb(list):
    res=[]
    for i in range(len(list)-1):
        for j in range(i+1,len(list)):
            res.append([list[i],list[j]])
    return res

def Maze_Breadth(Maze,start_goal):

    h=len(Maze)
    w=len(Maze[0])
    #ここに距離も格納
    footprints=[[-1 for i in range(w)] for j in range(h)]

    que=[start_goal[0]]

    distance=0
    while True:
        Que=[]

        for pos in que:
            
            footprints[pos[0]][pos[1]]=distance

            if pos[0]==start_goal[1][0] and pos[1]==start_goal[1][1]:
                
                break

            if not pos[0]==0:
                if Maze[pos[0]-1][pos[1]]=="." and footprints[pos[0]-1][pos[1]]==-1:
                    Que.append([pos[0]-1,pos[1]])
            
            if not pos[0]==h-1:
                if Maze[pos[0]+1][pos[1]]=="." and footprints[pos[0]+1][pos[1]]==-1:
                    Que.append([pos[0]+1,pos[1]])

            if not pos[1]==0:
                if Maze[pos[0]][pos[1]-1]=="." and footprints[pos[0]][pos[1]-1]==-1:
                    Que.append([pos[0],pos[1]-1])
            
            if not pos[1]==w-1:
                if Maze[pos[0]][pos[1]+1]=="." and footprints[pos[0]][pos[1]+1]==-1:
                    Que.append([pos[0],pos[1]+1])
        que=Que
        distance+=1

        if len(Que)==0:
            break
    return footprints[start_goal[1][0]][start_goal[1][1]]

N,M=input().split(" ")

N=int(N)
M=int(M)

H,W=N,M

Ss=[]

for i in range(H):
    S=input()
    Ss.append([S[i] for i in range(len(S))])

road_coords=[]

for i in range(H):
    for j in range(W):
        if Ss[i][j]==".":
            road_coords.append([i,j])

patterns=make_noreplace_comb(road_coords)

ans=0
max_pattern=None
for s_g in patterns:
    temp=Maze_Breadth(Ss,s_g)
    if temp>ans:
        ans=temp
        max_pattern=s_g

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
# (sx, sy) から 全点への最短距離を求める
# 辿り着けないと INF
def bfs(maze, sx, sy, n, m):
    # すべての点を 0 で初期化
    d = [[0] * m for i in range(n)]
 
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
 
    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
 
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
 
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
 
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#":
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
 
    return max(max(d))
 
 
n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
 
#print(maze)
 
bfs_list = [0]
 
for i in range(n):
  for j in range(m):
    # スタートとゴールの座標を探す
      sx = i
      sy = j
      bfs_list.append(bfs(maze, sx, sy, n, m))
 
print(max(bfs_list))

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w=map(int,input().split())
    s=[]
    for i in range(h):
        ss=input()
        s.extend(ss)
    mat = [[float("INF")] * (h*w) for i in range(h*w)]
    for i,a in enumerate(s):
        if a == '.':
            mat[i][i] = 0
            makemat(i,mat,h,w,s)
    # mtemp = mat
    # for i , a in enumerate(mat):
    #     print(a)
    for i,a in enumerate(s):
        if a == '.':

            caldist(mat,w*h)
            break
    ans = 0
    # print(mat)
    # for i, a in enumerate(mat):
    #     print(a)
    #     ans = max(ans, max(a))
    print(calans(mat))
def calans(m):
    temp = 0
    for i,w in enumerate(m):
        for j, s in enumerate(w):
            if s != float("INF"):
                temp = max(temp,s)
    return temp
# 隣接行列m作成
def makemat(i,m,h,w,s):

    if (i % w) + 1 != w:
        if s[i+1] == '.':
            j = i+1
            m[i][j] = 1
            m[j][i] = 1
        # else:
        #     j = i+1
        #     m[i][j] = float('INF')
        #     m[j][i] = float('INF')
    if (i % w)  != 0:
        if s[i-1] == '.':
            j = i-1
            m[i][j] = 1
            m[j][i] = 1
        # else:
        #     j = i-1
        #     m[i][j] = float('INF')
        #     m[j][i] = float('INF')
    if i > w:
        if s[i-w] == '.':
            j=i-w
            m[i][j] = 1
            m[j][i] = 1
        # else:
        #     j = i-w
        #     m[i][j] = float('INF')
        #     m[j][i] = float('INF')
    if i < h*w - w:
        if s[i+w] == '.':
            j=i+w
            m[i][j] = 1
            m[j][i] = 1
        # else:
        #     j = i+w
        #     m[i][j] = float('INF')
        #     m[j][i] = float('INF')

def caldist(m,l):
    for i in range(l):
        for j in range(l):
            for k in range(l):
                m[j][k] = min(m[j][k],m[j][i]+m[i][k])


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

mass.append(['#']*(W+2))
for i in range(H):
  mass.append(['#'] + [ x for x in input()] + ['#'])
mass.append(['#']*(W+2))

def find_next(mass, x, y):
  return [ (p,q) for p,q in [(x + 1, y),(x - 1, y), (x, y + 1),(x, y - 1)] if mass[p][q] == '.' ] 
  

def find_all(mass):
  for i in range(1,H+1):
    for j in range(1,W+1):
      if mass[i][j] == '.':
        yield (i,j)

def search(mass, x,y, tx, ty):
  open_list = []
  closed_list = set()
 
  open_list.append((x,y,0))
  min_level = -1 
 
  while len(open_list) > 0:
    sx, sy, level = open_list.pop(0)
    closed_list.add((sx, sy))
    if sx == tx and sy == ty:
      if min_level == -1:
         min_level = level
      elif min_level > level:
         min_level = level
      continue
    nexts = find_next(mass, sx, sy)
    for x in nexts:
      if x not in closed_list:
        open_list.append((x[0], x[1], level+1))
  return min_level

searched = set()

M = [ x for x in find_all(mass)]
min = 0
for x in M:
  for y in M:
    if y[0] == x[0] and y[1] == x[1]:
      continue
    if tuple(sorted([x,y])) in searched:
      continue
    r = search(mass, x[0], x[1], y[0], y[1])
    if r > min:
      min = r
    searched.add(tuple(sorted([x,y])))
print(min)

Submission status: Time Limit Exceeded

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

mass.append(['#']*(W+2))
for i in range(H):
  mass.append(['#'] + [ x for x in input()] + ['#'])
mass.append(['#']*(W+2))

def find_next(mass, x, y):
  return [ (p,q) for p,q in [(x + 1, y),(x - 1, y), (x, y + 1),(x, y - 1)] if mass[p][q] == '.' ] 
  

def find_all(mass):
  for i in range(1,H+1):
    for j in range(1,W+1):
      if mass[i][j] == '.':
        yield (i,j)

def search(mass, x,y, tx, ty):
  open_list = []
  closed_list = set()
 
  open_list.append((x,y,0))
  min_level = -1 
 
  while len(open_list) > 0:
    sx, sy, level = open_list.pop(0)
    closed_list.add((sx, sy))
    if sx == tx and sy == ty:
      if min_level == -1:
         min_level = level
      elif min_level > level:
         min_level = level
      continue
    nexts = find_next(mass, sx, sy)
    for x in nexts:
      if x not in closed_list:
        open_list.append((x[0], x[1], level+1))
  return min_level


#print(search(mass, 1, 3, 3, 3))
#exit(0)
M = [ x for x in find_all(mass)]
min = 0
for x in M:
  for y in M:
    if y[0] == x[0] and y[1] == x[1]:
      continue
    r = search(mass, x[0], x[1], y[0], y[1])
    if r > min:
      min = r

print(min)

Submission status: Time Limit Exceeded

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

def bfs(a, b):
	Q = [[a, b, 0]]
	d_lst = [[4000 for _ in range(W)] for _ in range(H)]
	while Q:
		cur = Q.pop(0)
		y, x, d = cur[0], cur[1], cur[2]
		if S[y][x] == "#": continue
		d_lst[y][x] = min(d_lst[y][x], d)
		
		if x > 0 and d + 1 < d_lst[y][x - 1] and S[y][x - 1] == ".":
			Q.append([y, x - 1, d + 1])
		if x < W - 1 and d + 1 < d_lst[y][x + 1] and S[y][x + 1] == ".":
			Q.append([y, x + 1, d + 1])
		if y > 0 and d + 1 < d_lst[y - 1][x] and S[y - 1][x] == ".":
			Q.append([y - 1, x, d + 1])
		if y < H - 1 and d + 1 < d_lst[y + 1][x] and S[y + 1][x] == ".":
			Q.append([y + 1, x, d + 1])
	
	ans = 0
	for i in range(H):
		for j in range(W):
			if S[i][j] == "#": continue
			ans = max(ans, d_lst[i][j])
	return ans
		

for i in range(H):
	tmp = list(map(str, input()))
	S.append(tmp)
	
res = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == "#": continue
		res = max(res, bfs(i, j))
		
print(res)