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:
# 2020/01/12

from copy import deepcopy
import sys
from collections import deque

sys.setrecursionlimit(10**7)


def main():
    dr=[(-1,0),(0,-1),(0,1),(1,0)]

    h,w=map(int,input().split())
    g=[list('#')*(w+2)]
    for _ in range(h):
        g+=[['#']+list(input())+['#']]
    g+=[list('#')*(w+2)]


    def bfs(sx,sy,maze):
        res=0
        x,y=sx,sy
        maze[x][y]=0
        que=deque()
        que.append((x,y))

        while que:
            x,y=que.popleft()
            for dx,dy in dr:
                nx=dx+x
                ny=dy+y
                if maze[nx][ny]!='@':continue
                maze[nx][ny]=maze[x][y]+1
                que.append((nx,ny))
                res=max(res,maze[nx][ny])
        return res


    def find(mz):
        maze=deepcopy(mz)
        ret=0
        for i in range(1,h+1):
            for j in range(1,w+1):
                if maze[i][j]!='@':continue
                res=bfs(i,j,maze)
                ret=max(res,ret)
                maze=deepcopy(mz)

        return ret


    def mk_maze(sx,sy,maze):
        x,y=sx,sy
        maze[x][y]='@'
        que=deque()
        que.append((x,y))

        while que:
            x,y=que.popleft()
            g[x][y]='#'
            for dx,dy in dr:
                nx=dx+x
                ny=dy+y
                if g[nx][ny]=='#':continue
                maze[nx][ny]='@'
                que.append((nx,ny))
        return maze

    maze=[[0]*(w+2) for _ in range(h+2)]
    ans=0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if g[i][j]=='#':continue
            mz=mk_maze(i,j,maze)
            res=find(mz)
            ans=max(res,ans)
    print(res)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import sys

input = sys.stdin.readline

INF = float('inf')

def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for u in E[v]: dist[v][u] = 1
    for k in V:
        for i, j in product(V, repeat=2):
            temp = dist[i][k] + dist[k][j]
            if dist[i][j] > temp:
                dist[i][j] = temp
    for v in V:
        if dist[v][v] < 0: return None
    return dist

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))
dist = floyd_warshall(V, E)
ans = 0
for D in dist.values():
    ans = max(ans, max(D.values()))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

input = sys.stdin.readline


class Solution:
    def __init__(self):
        self.dp = {}

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

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

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

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

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

        kouho = []
        while not q.empty():
            pos, cnt = q.get()

            if len(kouho) > 0 and cnt >= min(kouho):
                return min(kouho)

            if (pos[0], pos[1], goal[0], goal[1]) in self.dp.keys():
                kouho.append(self.dp[(pos[0], pos[1], goal[0], goal[1])] + cnt)
                continue

            f = False
            for move in moving_range:
                i, j = pos[0] + move[0], pos[1] + move[1]
                if (i, j) == goal:
                    f = True
                    kouho.append(cnt + 1)
                if map[i][j] == ".":
                    q.put(((i, j), cnt + 1))
            if f:
                break

        return min(kouho)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
# sx, sy = map(int, input().split())
# gx, gy = map(int, input().split())
# sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
c = [input() for i in range(H)]
INF = 10**9
def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[gx][gy]

ans = -1
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                sx, sy = i, j
                gx, gy = k, l
                if c[sx][sy] == '#' or c[gx][gy] == '#':
                    continue
                if bfs() == INF:
                    continue
                ans = max(ans, bfs())
print(ans)

Submission status: Time Limit Exceeded

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


def f(v1, v2):
    m = []
    for i in range(H):
        m.append([None]*W)
    m[v1][v2] = 0

    flag = True
    while flag:
        flag = False
        for i in range(H):
            for j in range(W):
                if S[i][j] == '#':
                    continue
                elif m[i][j] == None:
                    flag = True
                    continue
                else:
                    cur = m[i][j]
                    u = i-1
                    if 0 <= u and S[u][j] == '.':
                        if m[u][j] is None:
                            m[u][j] = cur + 1
                        m[u][j] = min(m[u][j], cur+1)
                    d = i+1
                    if d <= H-1 and S[d][j] == '.':
                        if m[d][j] is None:
                            m[d][j] = cur + 1
                        m[d][j] = min(m[d][j], cur+1)
                    l = j-1
                    if 0 <= l and S[i][l] == '.':
                        if m[i][l] is None:
                            m[i][l] = cur + 1
                        m[i][l] = min(m[i][l], cur+1)
                    r = j+1
                    if r <= W-1 and S[i][r] == '.':
                        if m[i][r] is None:
                            m[i][r] = cur + 1
                        m[i][r] = min(m[i][r], cur+1)

    ans = 0
    for i in range(H):
        for j in range(W):
            if m[i][j] == None:
                continue
            else:
                ans = max(ans, m[i][j])
    return ans

r = -1
#　スタート位置
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        else:
            x = f(i, j)
            r = max(r, x)
            # print(x)
print(r)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
import numpy as np

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

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

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

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

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

print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = list(map(int, input().split()))

s = []
for i in range(h):
    line = input()
    s.append(line)

ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue

        for k in range(i, h):
            for l in range(w):
                if s[k][l] == '#' or i == k and j == l or k <= i and l <= j:
                    continue
                start = (i, j)
                goal = (k, l)
                d = [[1<<10 for x in range(w)] for y in range(h)]

                stack = deque([])
                stack.append((start[0], start[1]))
                d[start[0]][start[1]] = 0
                while stack:
                    y, x = stack.popleft()
                    if y == goal[0] and x == goal[1]:
                        break
                    if y > 0 and s[y-1][x] == '.' and d[y-1][x] > d[y][x]+1:
                        d[y-1][x] = d[y][x] + 1
                        stack.append((y-1, x))
                    if x < w-1 and s[y][x+1] == '.' and d[y][x+1] > d[y][x]+1:
                        d[y][x+1] = d[y][x] + 1
                        stack.append((y, x+1))
                    if y < h-1 and s[y+1][x] == '.' and d[y+1][x] > d[y][x]+1:
                        d[y+1][x] = d[y][x] + 1
                        stack.append((y+1, x))
                    if x > 0 and s[y][x-1] == '.' and d[y][x-1] > d[y][x]+1:
                        d[y][x-1] = d[y][x] + 1
                        stack.append((y, x-1))
                ans.append(d[goal[0]][goal[1]])
ans.sort()
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(maze, sx, sy, gx, gy, n, m):
    # すべての点を INF で初期化
    d = [[float("inf")] * 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()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動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] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


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
      for k in range(n):
        for h in range(m):
          gx = k
          gy = h
          bfs_list.append(bfs(maze, sx, sy, gx, gy, n, m))

list2 = [x for x in bfs_list if x !=  float("inf")]
print(max(list2))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import copy

h, w = map(int, input().split())

maze = [list("#"+input()+"#") for _ in range(h)]
res = [i for i in "#"*(w+2)]
maze.insert(0, res)
maze.append(res)




p = []
for y, l in enumerate(maze):
    for x, m in enumerate(l):
        if m == ".":
            p.append([y, x])


ans = []

for c in combinations(p, 2):
    sy, sx = c[0][0], c[0][1]
    gy, gx = c[1][0], c[1][1]

    temp_maze = copy.deepcopy(maze)
    temp_maze[sy][sx] = 0

    loc = [[sy, sx]]

    for k in range(1, (h+2)*(w+2)):
        next_loc = []
        for y, x in loc:
            for i, j in ([1,0], [-1,0], [0,1],[0,-1]):
                    if temp_maze[y+i][x+j] == '.':
                        temp_maze[y+i][x+j] = k
                        next_loc.append([y+i, x+j])
        loc = next_loc
        if [gy, gx] in loc:
            ans.append(k)
            

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

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

ans = 0


def bfs(x, y):
    global ans
    m = []
    for _ in range(H):
        m.append([-1] * W)

    q = deque()
    q.append([y, x, 0])

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        dj = j + 1
        if dj < H and m[dj][i] == -1 and S[dj][i] == ".":
            q.append([dj, i, v+1])
            if ans < v+1:
                ans = v+1
        dj = j - 1
        if 0 <= dj and m[dj][i] == -1 and S[dj][i] == ".":
            q.append([dj, i, v+1])
            if ans < v+1:
                ans = v+1
        di = i + 1
        if di < W and m[j][di] == -1 and S[j][di] == ".":
            q.append([j, di, v+1])
            if ans < v+1:
                ans = v+1
        di = i - 1
        if 0 <= di and m[j][di] == -1 and S[j][di] == ".":
            q.append([j, di, v+1])
            if ans < v+1:
                ans = v+1


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        bfs(i, j)
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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


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

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

    start = (2, 0)
    goal = (0, 4)
    costs = []
    for i in range(H):
        for j in range(W):
            start = (i, j)
            for i_g in range(i, H):
                for j_g in range(j, W):
                    goal = (i_g, j_g)
                    cost, done, barrier = init_maze(maze, H, W, start, goal)
                    cost, done, barrier = init_maze(maze, H, W, start, goal)
                    costs.append(bnf(maze, cost, done, barrier, goal, g))
    print(max(costs))

Submission status: Time Limit Exceeded

Solution code:
def A():
    c = input()
    print(chr(ord(c)+1))

def B():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    K = temp[1]
    M = temp[2]
    A = [int(k) for k in input().split()]
    ans = M*N - sum(A)
    if ans <= K:
        print(max(0, ans))
    else:
        print(-1)

from collections import defaultdict
def C():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    M = temp[1]
    penal = defaultdict(int)
    P = []
    S = []
    for i in range(M):
        temp = input().split()
        P.append(int(temp[0]))
        S.append(temp[1])
    ac_problems = set()

    for i in range(M-1, -1, -1):
        if P[i] not in ac_problems and S[i] == 'AC':
            ac_problems.add(P[i])
        elif P[i] in ac_problems:
            if S[i] == 'WA':
                penal[P[i]] += 1
            elif S[i] == 'AC':
                penal[P[i]] = 0
    
    print(len(ac_problems), sum(penal.values()))

def D():
    temp = [int(k) for k in input().split()]
    H = temp[0]
    W = temp[1]
    S = []
    for i in range(H):
        S.append(input())
    ans = 0
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    memo = [[0 for i in range(W)] for j in range(H)]
    def bfs(x, y):
        to_visit = [(x, y, 0)]
        visited = set()
        while to_visit:
            x, y, distance = to_visit[0]
            del to_visit[0]
            visited.add((x, y))
            memo[x][y] = max(distance, memo[x][y])
            for d in directions:
                if x+d[0] < H and x+d[0] >= 0:
                    if y+d[1] < W and y+d[1] >= 0:
                        if (x+d[0], y+d[1]) not in visited:
                            if S[x+d[0]][y+d[1]] == '.':
                                to_visit.append((x+d[0], y+d[1], distance+1))
        #print(memo)

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                bfs(i, j)
                
    #print(memo)
    for i in range(H):
        for j in range(W):
            if memo[i][j] < float('inf'):
                ans = max(ans, memo[i][j])

    print(ans)

D()

Submission status: Time Limit Exceeded

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


def calcstep(maze, s, g):
    h, w = len(maze), len(maze[0])
    maze[s[0]] = maze[s[0]][:s[1]] + 's' + maze[s[0]][s[1]+1:]
    maze[g[0]] = maze[g[0]][:g[1]] + 'g' + maze[g[0]][g[1]+1:]
    
    cost = np.zeros((h, w), dtype=int) + 500
    done = np.zeros((h, w), dtype=bool)
    barrier = np.zeros((h, w), dtype=bool)

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

    for i in range(h):
        maze[i] = list(maze[i])
        for j in range(w):
            if maze[i][j] == 's':
                start = (i, j)
                cost[i, j] = 0
                done[i, j] = True
            if maze[i][j] == 'g':
                goal = (i, j)
            if maze[i][j] == '#':
                barrier[i, j] = True

    for i in range(1, 500):

        done_next = maximum_filter(done, footprint=g) * ~done

        cost_next = minimum_filter(cost, footprint=g) * done_next
        cost_next[done_next] += 1
        cost[done_next] = cost_next[done_next]
        cost[barrier] = 500
        done[done_next] = done_next[done_next]
        done[barrier] = False

        if done[goal[0], goal[1]] == True:
            break
    return i



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


res = -1
for i in range(h):
    for j in range(w):
        if(maze[i][j] == '#'): continue
        
        for k in range(h):
            for l in range(w):
                if(maze[k][l] == '#'): continue
                if(i==k and j==l): continue
                tmpmaze = copy.deepcopy(maze)
                steps = calcstep(tmpmaze, [i, j], [k, l])
                if(steps > res):
                    res = steps
print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(x) for x in input().split(" ")]


class Node:
    def __init__(self, text, pos):
        self.text = text
        self.pos = pos
        self.next_nodes = []

    def add_next(self, node):
        self.next_nodes.append(node)


nodes = dict()
for i in range(H):
    for j, text in enumerate(input()):
        nodes[(i, j)] = Node(text, (i, j))


for i in range(H):
    for j in range(W):
        node = nodes[(i, j)]
        if node.text == "#":
            continue
        for pos in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:
            if 0 <= pos[0] <= H-1 and 0 <= pos[1] <= W-1 and nodes[pos].text == ".":
                node.add_next(nodes[pos])


def all_pats():
    pat = []
    for i in range(H):
        for j in range(W):
            pat.append((i, j))
    return pat


searched_res = dict()


def search(start, end):
    queue = []
    queue.append(start)
    count = dict()
    count[start.pos] = 0

    if (start ,end) in searched_res:
        return searched_res[(start, end)]

    while True:
        if not queue:
            break
        node = queue[0]
        searched_res[(start.pos, node.pos)] = count[node.pos]
        if node.pos == end:
            break
        queue = queue[1:]

        for next_node in node.next_nodes:
            if next_node.pos in count:
                continue
            count[next_node.pos] = count[node.pos] + 1
            queue.append(next_node)
    return count[end.pos]


total = []
searched = []
for start in all_pats():
    for end in all_pats():
        if (start, end) in searched:
            continue
        start_node = nodes[start]
        end_node = nodes[end]
        if start_node.text == "." and end_node.text == ".":
            res = search(start_node, end_node)
            total.append(res)
        searched.append((start, end))

print(max(total))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
int_max = 2 ** 63 - 1

def get_cost(start, end):
    return 1 if start == '.' and end == '.' else 2 ** 63 - 1


def warshall_floyd(n, ad_table):
    """
    ワーシャルフロイド法
    :param n: 頂点の数
    :param ad_table: 隣接行列
    """
    for k in range(n):            # 経由する頂点
        for i in range(n):        # 始点
            for j in range(n):    # 終点
                ad_table[i][j] = min(ad_table[i][j], ad_table[i][k] + ad_table[k][j])

    return ad_table


def main():

    H, W = map(int, input().split(' '))
    ad_table = [[int_max for _ in range(H*W)] for _ in range(H*W)]
    maze = []
    for _ in range(H):
        maze.append(input())

    for si in range(H):
        for sj in range(W):
            for ti in range(H):
                for tj in range(W):
                    if si == ti and sj == tj:
                        ad_table[(si*W)+sj][(ti*W)+tj] = 0
                    elif (abs(si - ti) == 1 and sj - tj == 0) or (si - ti == 0 and abs(sj - tj) == 1):
                        ad_table[(si*W)+sj][(ti*W)+tj] = get_cost(maze[si][sj], maze[ti][tj])

    res = warshall_floyd(H*W, ad_table)
    ans = -1
    for l in res:
        for n in l:
            if n != int_max and ans < n:
                ans = n
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
def calc_distance(maze,sx,sy,gx,gy):
        # mazeをリストに変換
        # Goalまでの距離としてはあり得ない数値を設定
        INF = 100000000

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

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

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

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

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

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

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

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

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

        # Goalについたらループを抜け、Goalまでの距離を返す
        return distance[gy][gx]
    
ans = 0
for i in range(H):
    sy = i
    for j in range(W):
        sx = j
        for k in range(H):
            gy = k
            for m in range(W):
                gx = m
        
            
                if maze[sy][sx] == "#" or maze[gy][gx] == "#" or ((sy == gy) and (gx == sx)):
                    pass
                else:
                    
                    score = calc_distance(maze,sx,sy,gx,gy)
                    ans = max(ans,score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def solve(maze, start, end):
  memo = []
  q = deque()
  q.append([start,[]])
  ans = 0
  while q:
    cur, path = q.popleft()
    if cur == end:
      ans = path
      break
    elif cur in memo:
      continue
    else:
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],copy.deepcopy(path)+[cur]])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
memo = [[False]*(W+2) for _ in range(H+2)]
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    for ey in range(sy, H+1):
      for ex in range(sx+1 if sy == ey else 1, W+1):
        if Maze[ey][ex] == "#" or memo[ey][ex]:
          continue
        P = solve(Maze, [sy, sx], [ey,ex])
        Ans = max(Ans, len(P))
        for p in P:
          memo[p[0]][p[1]] = True
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
# D
from collections import deque
import numpy as np
INF = float('inf')
h, w = map(int, input().split())
maps = []

for _ in range(h):
    lst = list(input())
    maps.append(lst)
maps = np.array(maps)

def bfs(start, maps, distance, height, width):
    d = deque()
    d.append(start)
    sx, sy = start
    distance[sx,sy] = 0
    
    while d:
        now = d.pop()
        nowx, nowy = now
        
        for i in range(0, 4):
            nx, ny = nowx + [1, 0, -1, 0][i], nowy + [0, 1, 0, -1][i]
            if (0<=nx<height)and(0<=ny<width):
                if (maps[nx,ny] == '.'):
                    if (distance[nx,ny] == -1) or \
                        (distance[nowx,nowy]+1<distance[nx,ny]):
                        d.append((nx, ny))
                        distance[nx,ny] = distance[nowx,nowy] + 1
    #print(distance)
    return distance.max()

cand = []
for sx in range(h):
    for sy in range(w):
        if maps[sx,sy] == '#':
            continue
        distance = np.full((h, w), -1)
        cand.append(bfs((sx, sy), maps, distance, h, w))
print(int(max(cand)))