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 collections

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    s = input()
    a = []
    for j in range(w):
        a.append(s[j])
    maze.append(a)
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            ne = collections.deque()
            dist = [[0]*w for k in range(h)]
            checked = [[0]*w for k in range(h)]
            ne.append([i,j])
            while len(ne) != 0:
                cur = ne.popleft()
                checked[cur[0]][cur[1]] = 1
                for l in range(4):
                    t = cur[0]+dy_dx[l][0]
                    u = cur[1]+dy_dx[l][1]
                    if (0 <= t <= h-1) and (0 <= u <= w-1):
                        if checked[t][u] == 0:
                            if maze[t][u] == '.':
                                dist[t][u] = dist[cur[0]][cur[1]]+1
                                ne.append([t,u])
                                ans = max(ans,dist[t][u])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    s = input()
    a = []
    for j in range(w):
        a.append(s[j])
    maze.append(a)
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            next = collections.deque()
            dist = []
            checked = []
            curmax = 0
            for k in range(h):
                a = [0]*w
                b = [0]*w
                dist.append(a)
                checked.append(b)
            next.append([i,j])
            while len(next) != 0:
                cur = next.popleft()
                checked[cur[0]][cur[1]] = 1
                for l in range(4):
                    t = cur[0]+dy_dx[l][0]
                    u = cur[1]+dy_dx[l][1]
                    if (0 <= t <= h-1) and (0 <= u <= w-1):
                        if checked[t][u] == 0:
                            if maze[t][u] == '.':
                                dist[t][u] = dist[cur[0]][cur[1]]+1
                                next.append([t,u])
                                curmax = max(curmax,dist[t][u])
            ans = max(ans,curmax)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    s = input()
    a = []
    for j in range(w):
        a.append(s[j])
    maze.append(a)
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            next = collections.deque()
            dist = []
            checked = []
            curmax = 0
            for k in range(h):
                a = [0]*w
                b = [0]*w
                dist.append(a)
                checked.append(b)
            next.append([i,j])
            while len(next) != 0:
                cur = next.popleft()
                checked[cur[0]][cur[1]] = 1
                for l in range(4):
                    if (0 <= cur[0]+dy_dx[l][0] <= h-1) and (0 <= cur[1]+dy_dx[l][1] <= w-1):
                        if checked[cur[0]+dy_dx[l][0]][cur[1]+dy_dx[l][1]] == 0:
                            if maze[cur[0]+dy_dx[l][0]][cur[1]+dy_dx[l][1]] == '.':
                                dist[cur[0]+dy_dx[l][0]][cur[1]+dy_dx[l][1]] = dist[cur[0]][cur[1]]+1
                                next.append([cur[0]+dy_dx[l][0],cur[1]+dy_dx[l][1]])
                                curmax = max(curmax,dist[cur[0]+dy_dx[l][0]][cur[1]+dy_dx[l][1]])
            ans = max(ans,curmax)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def main():
    field_y_length,field_x_length =  map(int, input().split())
    maze = [input() for i in range(field_y_length)]

    INF = 10**8
    
    max_distance = 0

    def bfs(sx,sy,gx,gy):
        distance = [[INF for i in range(field_x_length)] for j in range(field_y_length)]
        queue = []

        queue.insert(0,(sx,sy))

        distance[sy][sx] = 0

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

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

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

                if (0 <= nx and nx < field_x_length and 0 <= ny):
                    if (ny < field_y_length and maze[ny][nx] != '#'):
                        if (distance[ny][nx] == INF):
                            queue.insert(0, (nx, ny))
                            distance[ny][nx] = distance[y][x] + 1
        
        return distance[gy][gx]

    for sx in range(field_x_length):
        for sy in range(field_y_length):
            if maze[sy][sx] == '#':
                continue
            for gx in range(field_x_length):
                for gy in range(field_y_length):
                    if maze[gy][gx] == '#' or (gx == sx and gy == sy):
                        continue
                    max_distance = max(max_distance,bfs(sx,sy,gx,gy))
    print(max_distance)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
board = [list(input()) for i in range(h)]

road = []

for i in range(h):
    for j in range(w):
        if board[i][j] == ".":
            road.append([i,j])


from heapq import heappop, heappush

def dfs(start, end):
    dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
    dist = [[float("inf")]*w for i in range(h)]
    #heap = [(0, *start)]
    heap = [(0, start[0], start[1])]
    while heap:
        c,x,y = heappop(heap)
        if dist[x][y] <= c:
            continue
        dist[x][y] = c
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == ".":
                heappush(heap, (c+1, nx, ny))
    return dist[end[0]][end[1]]


from itertools import combinations

ans = 0
for start, end in combinations(road, 2):
    #print(start, end)
    tmp = dfs(start, end)
    if tmp != float("inf"):
        ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
import itertools

[H, W] = map(int, input().rstrip().split(" "))
S = []


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

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

max_cost = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        que = deque()
        history = [ [-1 for w in range(W)] for h in range(H)]
        que.append([h, w])
        history[h][w] = 0
        current_max_cost = 0
        while len(que) != 0:
            [x, y] = que.pop()
            for i in range(4):
                newx = x + dx[i]
                newy = y + dy[i]
                if 0 <= newx and newx < H and 0 <= newy and newy < W and S[newx][newy] != "#" and (history[newx][newy] > history[x][y] + 1 or history[newx][newy] == -1):
                    history[newx][newy] = history[x][y] + 1
                    que.append([newx, newy])
        current_max_cost = max(list(itertools.chain.from_iterable(history)))
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)

Submission status: Time Limit Exceeded

Solution code:
import queue

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


def bfs(gy, gx):
    while not que.empty():
        pos = que.get()
        for y, x in zip(dy, dx):
            ty = pos[0] + y
            tx = pos[1] + x
            if ty < 0 or H <= ty:
                continue
            if tx < 0 or W <= tx:
                continue
            if visited[ty][tx]:
                continue
            if S[ty][tx] == "#":
                continue
            if ty == gy and tx == gx:
                # print(ty, tx)
                # print(pos[2] + 1)
                return pos[2] + 1
            que.put((ty, tx, pos[2] + 1))
            visited[ty][tx] = True
    return -1

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append([c for c in input()])
ans = 0
for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if sy == gy and sx == gx:
                    continue
                if S[sy][sx] == "#" or S[gy][gx] == "#":
                    continue
                visited = [[False for _ in range(W)] for _ in range(H)]
                visited[sy][sx] = True
                que = queue.Queue()
                que.put((sy, sx, 0))
                ans = max(ans, bfs(gy, gx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
height,width=map(int,input().split())

graph=[input() for _ in range(height)]

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()
            route[ny][nx] = nn

            for dx,dy in zip(dxs, dys):
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]!=-1:
                    continue
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

Submission status: Time Limit Exceeded

Solution code:
import queue
height,width=map(int,input().split())

graph=[input() for _ in range(height)]

diff=[[0,-1],[0,1],[-1,0],[1,0]]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()
            route[ny][nx] = nn

            for dx,dy in diff:
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]!=-1:
                    continue
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

Submission status: Time Limit Exceeded

Solution code:
import queue
height,width=map(int,input().split())

graph=[input() for _ in range(height)]

diff=[[0,-1],[0,1],[-1,0],[1,0]]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()
            route[ny][nx] = nn

            for dx,dy in diff:
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]>-1:
                    continue
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

Submission status: Time Limit Exceeded

Solution code:
import queue
height,width=map(int,input().split())

graph=[]
for _ in range(height):
    graph.append(input())

diff=[[0,-1],[0,1],[-1,0],[1,0]]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()
            route[ny][nx] = nn

            for dx,dy in diff:
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]>-1:
                    continue
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

Submission status: Time Limit Exceeded

Solution code:
import queue
height,width=map(int,input().split())

graph=[]
for _ in range(height):
    graph.append(input())

diff=[[0,-1],[0,1],[-1,0],[1,0]]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = [[-1]*width for _ in range(height)]

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            nx,ny,nn = q.get()
            route[ny][nx] = nn

            for dx,dy in diff:
                x = nx+dx
                y = ny+dy
                if   width<=x \
                  or height<=y \
                  or x < 0 \
                  or y < 0 \
                  or graph[y][x]=='#' \
                  or route[y][x]>-1:
                    continue
                q.put([x, y, nn+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

Submission status: Time Limit Exceeded

Solution code:
import queue
height,width=map(int,input().split())

graph=[]
for _ in range(height):
    s_row = input()
    row = []
    for s in s_row:
        row.append(s)
    graph.append(row)

diff=[[0,-1],[0,1],[-1,0],[1,0]]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = []
        for _ in range(height):
            route.append([-1]*width)

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

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

            route[now[1]][now[0]] = now[2]

            for dx,dy in diff:
                next_w = now[0]+dx
                next_h = now[1]+dy
                if   width<=next_w \
                  or height<=next_h \
                  or next_w < 0 \
                  or next_h < 0 \
                  or graph[next_h][next_w]=='#' \
                  or route[next_h][next_w]>-1:
                    continue
                q.put([next_w, next_h, now[2]+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

Submission status: Time Limit Exceeded

Solution code:
import queue
height,width=map(int,input().split())

graph=[]
for _ in range(height):
    s_row = input()
    row = []
    for s in s_row:
        row.append(s)
    graph.append(row)

diff=[[0,-1],[0,1],[-1,0],[1,0]]
max_step=[]
for h in range(height):
    for w in range(width):
        if graph[h][w]=='#':
            continue

        route = []
        for _ in range(height):
            route.append([-1]*width)

        # start x,y,経路数
        q = queue.Queue()
        q.put([w,h,0])

        while not q.empty():
            now = q.get()
            now_w = now[0]
            now_h = now[1]
            now_n = now[2]

            route[now_h][now_w] = now_n

            for dx,dy in diff:
                next_w = now_w+dx
                next_h = now_h+dy
                if   width<=next_w \
                  or height<=next_h \
                  or next_w < 0 \
                  or next_h < 0 \
                  or graph[next_h][next_w]=='#' \
                  or route[next_h][next_w]>-1:
                    continue
                q.put([next_w, next_h, now_n+1])
        
        max_step.append(max(max(step) for step in route))
        
print(max(max_step))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

field = [["."]*W for _ in range(H)]

for i in range(H):
    input2 = input()
    for j in range(W):
        field[i][j] = input2[j]

dist = 0

for a in range(H):
    for b in range(W):

        field_test = copy.deepcopy(field)

        if field_test[a][b] == ".":
            field_test[a][b] = 0
            
            for k in range(H * W):
                for i in range(H):
                    for j in range(W):
                         if field_test[i][j] == k:
                            try:
                                if 0 <= i + 1 <= H and 0 <= j <= W:
                                    if field_test[i + 1][j] == ".":
                                        field_test[i + 1][j] = k + 1
                                        dist = max(dist,k + 1)
                            except:
                                pass
                    
                            try:
                                if 0 <= i - 1 <= H and 0 <= j <= W:
                                    if field_test[i - 1][j] == ".":
                                        field_test[i - 1][j] = k + 1
                                        dist = max(dist,k + 1)
                            except:
                                pass
                    
                            try:
                                if 0 <= i <= H and 0 <= j + 1 <= W:
                                    if field_test[i][j + 1] == ".":
                                        field_test[i][j + 1] = k + 1
                                        dist = max(dist,k + 1)
                            except:
                                pass
                            
                            try:
                                if 0 <= i <= H and 0 <= j - 1 <= W:
                                    if field_test[i][j - 1] == ".":
                                        field_test[i][j - 1] = k + 1
                                        dist = max(dist,k + 1)
                            except:
                                pass


print(dist)

Submission status: Time Limit Exceeded

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = deque()
        q.append((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        while q:
            p = q.popleft()
            for dx, dy in zip(dxs, dys):
                field[p[1]][p[0]] = p[2]
                cand.append(p[2])
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                q.append((x, y, p[2] + 1))
print(max(cand))

Submission status: Time Limit Exceeded

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                field[p[1]][p[0]] = p[2]
                cand.append(p[2])
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                q.put((x, y, p[2] + 1))
print(max(cand))

Submission status: Time Limit Exceeded

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        if S[j][i] == '#':
            continue
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                field[p[1]][p[0]] = p[2]
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                q.put((x, y, p[2] + 1))
        cand.append(max([max(row) for row in field]))
print(max(cand))

Submission status: Time Limit Exceeded

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                if S[p[1]][p[0]] == '#':
                    break
                field[p[1]][p[0]] = p[2]
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                q.put((x, y, p[2] + 1))
        cand.append(max([max(row) for row in field]))
print(max(cand))

Submission status: Time Limit Exceeded

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

dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]
cand = []
for j in range(H):
    for i in range(W):
        q = queue.Queue()
        q.put((i, j, 0))
        field = [[-1] * W for _ in range(H)]
        while not q.empty():
            p = q.get()
            for dx, dy in zip(dxs, dys):
                if S[p[1]][p[0]] == '#':
                    continue
                field[p[1]][p[0]] = p[2]
                x, y = p[0] + dx, p[1] + dy
                if not (0 <= x < W) or not (0 <= y < H) or S[y][x] == '#' or field[y][x] != -1:
                    continue
                q.put((x, y, p[2] + 1))
        cand.append(max([max(row) for row in field]))
print(max(cand))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [list('#' * (W + 2))]
for _ in range(H):
    S.append(list('#' + input() + '#'))
S.append(list('#' * (W + 2)))

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

inf = float('inf')

N = W * H
l = [[inf for _ in range(N)] for _ in range(N)]

for w in range(1, W + 1):
    for h in range(1, H + 1):
        if S[h][w] != '#':
            l[(h - 1) * W + w - 1][(h - 1) * W + w - 1] = 0
            for x, y in zip(dx, dy):
                if S[h + y][w + x] != '#':
                    l[(h - 1) * W + w - 1][(h + y - 1) * W + w + x - 1] = 1

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

ans = -1

for i in range(N):
    for j in range(N):
        k = l[i][j]
        if k != inf:
            ans = max(ans, k)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

(h, w) = [int(i) for i in input().rstrip().split(" ")]
mapSrc = [input().rstrip() for i in range(h)]

map = [mapSrc[int(i/w)][i%w] for i in range(h*w)]
diff = [[401 for i in range(h * w)] for j in range(h * w)]


def isSame(r1, c1, r2, c2):
    if r1 != r2:
        return False
    if c1 != c2:
        return False
    return True


def isNear(r1, c1, r2, c2):
    if r1 == r2:
        if abs(c1 - c2) == 1:
            return True
    elif abs(r1 - r2) == 1:
        if c1 == c2:
            return True
    return False

for idx1 in range(h*w):
    if map[idx1] == "#":
        continue
    r1 = int(idx1/w)
    c1 = idx1 % w
    for idx2 in range(h*w):
        if map[idx2] == "#":
            continue
        r2 = int(idx2/w)
        c2 = idx2 % w
        for idx3 in range(idx2 + 1, h*w):
            if map[idx3] == "#":
                continue
            r3 = int(idx3/w)
            c3 = idx3 % w

            if idx2 == idx3:
                diff[idx2][idx3] = 0
            elif isNear(r2,c2,r3,c3):
                diff[idx2][idx3] = 1
                diff[idx3][idx2] = 1
            else:
                tmp = diff[idx2][idx1] + diff[idx1][idx3]
                if diff[idx2][idx3] > tmp:
                    diff[idx2][idx3] = tmp
                    diff[idx3][idx2] = tmp

ans = 0

for i in range(h*w):
    for j in range(i+1, h*w):
        num = diff[i][j]
        if num > h*w:
            continue
        ans = max(ans,num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

(h, w) = [int(i) for i in input().rstrip().split(" ")]
map = [input().rstrip() for i in range(h)]

diff = [[401 for i in range(h * w)] for j in range(h * w)]


def isSame(r1, c1, r2, c2):
    if r1 != r2:
        return False
    if c1 != c2:
        return False
    return True


def isNear(r1, c1, r2, c2):
    if r1 == r2:
        if abs(c1 - c2) == 1:
            return True
    elif abs(r1 - r2) == 1:
        if c1 == c2:
            return True
    return False



ans = 0

for r1 in range(h):
    for c1 in range(w):
        if map[r1][c1] == "#":
            continue
        idx1 = r1*w+c1
        for r2 in range(h):
            for c2 in range(w):
                if map[r2][c2] == "#":
                    continue
                idx2 = r2*w+c2
                for r3 in range(h):
                    for c3 in range(w):
                        if map[r3][c3] == "#":
                            continue
                        idx3 = r3*w+c3
                        if isSame(r2, c2, r3, c3):
                            diff[idx2][idx3] = 0
                        elif isNear(r2, c2, r3, c3):
                            diff[idx2][idx3] = 1
                        else:
                            tmp = diff[idx2][idx1] + diff[idx1][idx3]
                            if tmp < diff[idx2][idx3]:
                                diff[idx2][idx3] = tmp

for i in range(h*w):
    for j in range(i+1, h*w):
        num = diff[i][j]
        if num > h*w:
            continue
        ans = max(ans,num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

(h, w) = [int(i) for i in input().rstrip().split(" ")]
map = [input().rstrip() for i in range(h)]

index_map = [[i * w + j for j in range(w)] for i in range(h)]
diff = [[401 for i in range(h * w)] for j in range(h * w)]


def isSame(r1, c1, r2, c2):
    if r1 != r2:
        return False
    if c1 != c2:
        return False
    return True


def isNear(r1, c1, r2, c2):
    if r1 == r2:
        if abs(c1 - c2) == 1:
            return True
    elif abs(r1 - r2) == 1:
        if c1 == c2:
            return True
    return False


ans = 0

for r1 in range(h):
    for c1 in range(w):
        idx1 = index_map[r1][c1]
        for r2 in range(h):
            for c2 in range(w):
                if map[r2][c2] == "#":
                    continue
                idx2 = index_map[r2][c2]
                for r3 in range(h):
                    for c3 in range(w):
                        if map[r3][c3] == "#":
                            continue
                        idx3 = index_map[r3][c3]
                        if isSame(r2, c2, r3, c3):
                            diff[idx2][idx3] = 0
                        elif isNear(r2, c2, r3, c3):
                            diff[idx2][idx3] = 1
                        else:
                            tmp = diff[idx2][idx1] + diff[idx1][idx3]
                            if tmp < diff[idx2][idx3]:
                                diff[idx2][idx3] = tmp

for i in range(h*w):
    for j in range(i+1, h*w):
        num = diff[i][j]
        if num > h*w:
            continue
        ans = max(ans,num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

(h, w) = [int(i) for i in input().rstrip().split(" ")]
map = [input().rstrip() for i in range(h)]

index_map = [[i * w + j for j in range(w)] for i in range(h)]
rev_index_map = [(int(i / w), i % w) for i in range(h * w)]
diff = [[401 for i in range(h * w)] for j in range(h * w)]


def isSame(r1, c1, r2, c2):
    if r1 != r2:
        return False
    if c1 != c2:
        return False
    return True


def isNear(r1, c1, r2, c2):
    if r1 == r2:
        if abs(c1 - c2) == 1:
            return True
    elif abs(r1 - r2) == 1:
        if c1 == c2:
            return True
    return False


ans = 0

for idx1 in range(h * w):
    for idx2 in range(h * w):
        (r2, c2) = rev_index_map[idx2]
        if map[r2][c2] == "#":
            continue
        for idx3 in range(h * w):
            (r3, c3) = rev_index_map[idx3]
            if map[r3][c3] == "#":
                continue
            if isSame(r2, c2, r3, c3):
                diff[idx2][idx3] = 0
            elif isNear(r2, c2, r3, c3):
                diff[idx2][idx3] = 1
                diff[idx3][idx2] = 1
            else:
                tmp = diff[idx2][idx1] + diff[idx1][idx3]
                if diff[idx2][idx3] > tmp:
                    diff[idx2][idx3] = tmp
                    diff[idx3][idx2] = tmp

for i in range(h*w):
    for j in range(i+1, h*w):
        num = diff[i][j]
        if num > h*w:
            continue
        ans = max(ans,num)
print(ans)