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:
h, w = map(int, input().split())
S = [0 for i in range(h)]
P = []

for i in range(h):
    S[i] = input()
    for j in range(len(S[i])):
        if S[i][j] == '.':
            P.append([i, j])
        else:
            pass

MV = [[-1, 0], [1, 0], [0, -1], [0, 1]]   #Move Vectol
ans = 0
def print_field(L:list):
    for i in range(len(L)):
        print(L[i])
    
def try_move(ch:int, cw:int, M:list):
    if 0 <= ch and ch < h and 0 <= cw and cw < w:
        if M[ch][cw] == '.':
            return True
        else:
            pass
    else:
        pass
    return False

def search_root(ch:int, cw:int, time:int, M:list):
    global md
    #print('time = ', time)
    if ch == gh and cw == gw:
        #print('gtime = ',time)
        if time < md:
            md = time
        else:
            pass
    else:
        for i in range(4):
            if try_move(ch+MV[i][0], cw+MV[i][1], M) == True:
                R = M[:]
                R[ch+MV[i][0]] = R[ch+MV[i][0]][0:cw+MV[i][1]] + '〇' + R[ch+MV[i][0]][cw+MV[i][1]+1:]
                #print_field(R)
                search_root(ch+MV[i][0], cw+MV[i][1], time+1, R)
            else:
                pass

ans = 0
for i in range(len(P)):
    for j in range(i+1, len(P)):
        md = h*w
        F = S[:]
        sh, sw = P[i]
        gh, gw = P[j]
        search_root(sh, sw, 0, F)
        if ans < md:
            ans = md
        else:
            pass
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 114514191981036436433-4
h,w = map(int,input().split())

c = [[] for _ in range(h)]
for i in range(h):
    c[i] = input()
            
dx = [1,0,-1,0]
dy = [0,1,0,-1]

ans = 0
for i in range(h):
    for j in range(w):
        for l in range(h):
            for m in range(w):
                if c[i][j] == "#" or c[l][m] == "#":
                    continue
                if i == l and j == m:
                    continue
                    
                d = [[INF for i in range(w)] for j in range(h)]
                
                sx,sy = j,i
                gx,gy = m,l
                
                d[sy][sx] = 0
                que = deque([[sy,sx]])

                while que:
                    y,x = que.popleft()

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

                        if 0<=nx and nx<w and 0<=ny and ny<h and c[y][x] != '#':
                            if d[ny][nx] > d[y][x] + 1:
                                d[ny][nx]=d[y][x] + 1
                                que.append([ny,nx])
                                
                if d[gy][gx] != INF:         
                    ans = max(d[gy][gx],ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
from copy import deepcopy

    
H, W = map(int, input().split())
S = [['#'] * (W + 2)]
cnt = []
Checked = [[0 for _ in range(W+2)] for _ in range(H+2)]


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

for start_h in range(1, H+1):
    for start_w in range(1, W+1):
        if S[start_h][start_w] == '#':
            continue
        for goal_h in range(1, H+1):
            for goal_w in range(1, W+1):
                if S[goal_h][goal_w] == '#':
                    continue
                if start_h == goal_h or start_w == goal_w:
                    cnt.append(abs(start_h - goal_h) + abs(start_w - goal_w))
                    continue
                    
                q = deque([[start_h, start_w]])
                checked = deepcopy(Checked)
                c = 0
                tmp = []
                while q:
                    h, w = q.popleft()
                    if checked[h][w]:
                        continue
                    checked[h][w] = 1
                    if h == goal_h and w == goal_w:
                        cnt.append(c)
                        break
                        
                    for dw, dh in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                        next_h, next_w = h + dh, w + dw
                        if S[next_h][next_w] == '#':
                            continue
                        if [next_h, next_w] in tmp or checked[next_h][next_w]:
                            continue
                        tmp.append([next_h, next_w])
                    if not q:
                        q.extend(tmp)
                        tmp = []
                        c += 1

print(max(cnt))

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
from copy import deepcopy

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


for _ in range(H):
    S.append([i for i in input()])
    
for start_h in range(H):
    for start_w in range(W):
        if S[start_h][start_w] == '#':
            continue
        for goal_h in range(H):
            for goal_w in range(W):
                if S[goal_h][goal_w] == '#':
                    continue
                if start_h == goal_h or start_w == goal_w:
                    cnt.append(abs(start_h - goal_h) + abs(start_w - goal_w))
                    continue
                    
                q = deque([[start_h, start_w]])
                checked = deepcopy(Checked)
                c = 0
                tmp = []
                while q:
                    h, w = q.popleft()
                    if checked[h][w]:
                        continue
                    checked[h][w] = 1
                    if h == goal_h and w == goal_w:
                        cnt.append(c)
                        break
                        
                    for dw, dh in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                        next_h, next_w = h + dh, w + dw
                        if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                            continue
                        if S[next_h][next_w] == '#':
                            continue
                        if [next_h, next_w] in tmp or checked[next_h][next_w]:
                            continue
                        tmp.append([next_h, next_w])
                    if not q:
                        q.extend(tmp)
                        tmp = []
                        c += 1

print(max(cnt))

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
from copy import deepcopy

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


for _ in range(H):
    S.append([i for i in input()])
    
for start_h in range(H):
    for start_w in range(W):
        if S[start_h][start_w] == '#':
            continue
        for goal_h in range(H):
            for goal_w in range(W):
                if S[goal_h][goal_w] == '#':
                    continue
                if start_h == goal_h or start_w == goal_w:
                    cnt.append(abs(start_h - goal_h) + abs(start_w - goal_w))
                    continue
                    
                q = [[start_h, start_w]]
                checked = deepcopy(Checked)
                c = 0
                tmp = []
                while q:
                    h, w = q.pop(0)
                    if checked[h][w]:
                        continue
                    checked[h][w] = 1
                    if h == goal_h and w == goal_w:
                        cnt.append(c)
                        break
                        
                    for dw, dh in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                        next_h, next_w = h + dh, w + dw
                        if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                            continue
                        if S[next_h][next_w] == '#':
                            continue
                        if [next_h, next_w] in tmp or checked[next_h][next_w]:
                            continue
                        tmp.append([next_h, next_w])
                    if not q:
                        q.extend(tmp)
                        tmp = []
                        c += 1

print(max(cnt))

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

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


for _ in range(H):
    S.append([i for i in input()])
    
for start_h in range(H):
    for start_w in range(W):
        if S[start_h][start_w] == '#':
            continue
        for goal_h in range(H):
            for goal_w in range(W):
                if S[goal_h][goal_w] == '#':
                    continue
                if start_h == goal_h or start_w == goal_w:
                    cnt.append(abs(start_h - goal_h) + abs(start_w - goal_w))
                    continue
                    
                q = [[start_h, start_w]]
                checked = []
                c = 0
                tmp = []
                while q:
                    h, w = q.pop(0)
                    if [h, w] in checked:
                        continue
                    checked.append([h, w])
                    if h == goal_h and w == goal_w:
                        cnt.append(c)
                        break
                        
                    for dw, dh in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                        next_h, next_w = h + dh, w + dw
                        if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                            continue
                        if S[next_h][next_w] == '#':
                            continue
                        if [next_h, next_w] in tmp or [next_h, next_w] in checked:
                            continue
                        tmp.append([next_h, next_w])
                    if not q:
                        q.extend(tmp)
                        tmp = []
                        c += 1

print(max(cnt))

Submission status: Time Limit Exceeded

Solution code:
import copy


def bfs(x, y, goal_h, goal_w, c, s):
    if x < 0 or y < 0 or x >= H or y >= W or s[x][y] == '#':
        return 10000
    if x == goal_h and y == goal_w:
        return c
    s[x][y] = '#'
    return min([bfs(next_x, next_y,goal_h, goal_w, c+1, copy.deepcopy(s))
                for next_x, next_y in ([x+1, y], [x-1, y], [x, y+1], [x, y-1])])
    
H, W = map(int, input().split())
S = []
cnt = []


for _ in range(H):
    S.append([i for i in input()])
    
for start_h in range(H):
    for start_w in range(W):
        if S[start_h][start_w] == '#':
            continue
        for goal_h in range(H):
            for goal_w in range(W):
                if S[goal_h][goal_w] == '#':
                    continue
                if start_h == goal_h or start_w == goal_w:
                    cnt.append(abs(start_h - goal_h) + abs(start_w - goal_w))
                    continue
                c = 0
                s = copy.deepcopy(S)
                s[start_h][start_w], s[goal_h][goal_w] = 'S', 'G'
                cnt.append(bfs(start_h, start_w, goal_h, goal_w, c, s))

print(max(cnt))

Submission status: Time Limit Exceeded

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

graph = [[float('inf')]*H*W for _ in range(H*W)]
nv = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for h in range(H):
    for w in range(W):
        if S[h][w]=='.':
            for nx, ny in nv:
                if H <= h+nx or h+nx < 0 or W <= w+ny or w+ny < 0:
                    continue
                if S[h+nx][w+ny]=='.':
                    graph[W*h+w][W*(h+nx)+(w+ny)] = 1

for k in range(H*W):
    for i in range(H*W):
        for j in range(H*W):
            graph[i][i]=0
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        if graph[i][j] != float('inf'):
            ans = max(ans, graph[i][j])
print(ans)

Submission status: Time Limit Exceeded

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

graph = [[float('inf')]*H*W for _ in range(H*W)]
for i in range(H*W):
    graph[i][i]=0
nv = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for h in range(H):
    for w in range(W):
        if S[h][w]=='.':
            for nx, ny in nv:
                if H <= h+nx or h+nx < 0 or W <= w+ny or w+ny < 0:
                    continue
                if S[h+nx][w+ny]=='.':
                    graph[W*h+w][W*(h+nx)+(w+ny)] = 1
                    graph[W*(h+nx)+(w+ny)][W*h+w] = 1

for k in range(H*W):
    for i in range(H*W):
        for j in range(H*W):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        if graph[i][j] != float('inf'):
            ans = max(ans, graph[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
from itertools import product
h, w = map(int, input().split())
maze = []
max_d = 0
for i in range(h):
    maze.append(input())
for i, j in product(range(h), range(w)):
    if maze[i][j] == '#':
        continue
    s = (i, j)
    for k, l in product(range(h), range(w)):
        if maze[k][l] == '#':
            continue
        g = (k, l)
        pathes = [[s]]
        while pathes:
            path = pathes.pop(0)
            a, b = path[-1]
            for point in [(0, 1), (1, 0), (0, -1),(-1, 0)]:
                di, dj = point
                if a + di >= 0 and a + di < h and b + dj >= 0 and b + dj < w and (a+di, b+dj) not in path and maze[a+di][b+dj]=='.':
                    copy_path = copy(path)
                    copy_path.append((a + di, b + dj))
                    pathes.append(copy_path)
                if (a + di, b + dj) == g:
                    max_d = max(max_d, len(copy_path)-1)
                    pathes = None
                    break
print(max_d)

Submission status: Time Limit Exceeded

Solution code:
import collections

H, W = map(int, input().split(" "))
mp = []
for _ in range(H):
    mp.append(input().strip())


def bfs(sh, sw, mp):
    que = collections.deque()
    que.append((sh, sw, 0))
    dist = [[float('inf') for _ in range(W)] for _ in range(H)]

    while len(que) > 0:
        h, w, d = que.popleft()
        dist[h][w] = d
        for (dh, dw) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if h + dh < 0 or w + dw < 0 or h + dh >= H or w + dw >= W:
                continue
            if mp[h + dh][w + dw] == '#' or dist[h + dh][w + dw] != float('inf'):
                continue
            que.append((h + dh, w + dw, d + 1))
    return dist


for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            tmp_dist = bfs(h, w, mp)
            sh = h; sw = w;
            break

for h in range(H):
    for w in range(W):
        if mp[h][w] == '.' and tmp_dist[h][w] >= tmp_dist[sh][sw]:
            sh = h
            sw = w

dist = bfs(sh, sw, mp)
ans = 1
for h in range(H):
    for w in range(W):
        if mp[h][w] == '.':
            ans = max(ans, dist[h][w])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
from itertools import*
from copy import*
n,m=map(int,input().split())

grid=[list("#"*(m+2))]+[list("#"+input()+"#")for i in range(n)]+[list("#"*(m+2))]

#print(grid)

start=[]
for i in range(1,n+1):
    for j in range(1,m+1):
        start.append((i,j))

ans=0
for s,g in combinations(start,2):
    G=deepcopy(grid)
    if G[s[0]][s[1]]!="#":
        G[s[0]][s[1]]=0
    else:
        continue
    if G[g[0]][g[1]]=="#":
        continue
    Q=deque([s])
    while Q:
        y,x=Q.pop()
        for my,mx in (-1,0),(1,0),(0,-1),(0,1):
            if G[y+my][x+mx]==".":
                G[y+my][x+mx]=G[y][x]+1
                Q.appendleft((y+my,x+mx))
    
    if type(G[g[0]][g[1]])!=str:
        if ans<G[g[0]][g[1]]:
            ans=G[g[0]][g[1]]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

maze = []
for _ in range(H):
    maze.append(list(input()))

def dfs(i, j, path):
    global ans
    if i == end[0] and j == end[1]:
        # print(path)
        ans = min(ans, path)
        return 

    for dx, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        x = i + dx
        y = j + dj
        if 0 <= x < H and 0 <= y < W and maze[x][y] == "." :
            if (x, y) not in seen:
                seen.add((x, y))
                dfs(x, y, path+1)
                seen.discard((x, y))   
    return

res = []
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][j] == ".":
                    ans = float("inf")
                    seen = set()
                    seen.add((i, j))
                    end = (k, l)
                    dfs(i, j, 0)
                    if ans != float("inf"):
                        res.append(ans)
                    # res = max(res, ans if ans != float("inf") else 0)

print(max(res))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

'''
3 5
...#.
.#.#.
.#...
'''

import sys
from collections import deque

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = na()
# data = [ns() for _ in range(H)]

data = [list("#" * (W + 2))]
# 周りを'#'で埋めておく
for _ in range(H):
    data.append(["#"] + list(input()) + ["#"])
data += [list("#" * (W + 2))]


def bfs(h, w):
    dist = [[-1] * (W+2) for _ in range(H+2)]
    q = deque()

    max_dist = 0
    dist[h][w] = 0
    q.append((h, w, 0))

    # while len(q) > 0:
    while len(q) > 0:
        h, w, val = q.popleft()

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if data[h_new][w_new] == '.' and dist[h_new][w_new] == -1:
                q.append((h_new, w_new, val+1))
                dist[h][w] = val + 1
                max_dist = max(max_dist, val + 1)

    return max_dist


ans = 0
for h in range(H+2):
    for w in range(W+2):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

'''
3 5
...#.
.#.#.
.#...
'''

import sys
from collections import deque

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = na()
# data = [ns() for _ in range(H)]

data = [list("#" * (W + 2))]
# 周りを'#'で埋めておく
for _ in range(H):
    data.append(["#"] + list(input()) + ["#"])
data += [list("#" * (W + 2))]


def judge(h, w, dist):
    if data[h][w] == '#' or dist[h][w] > -1:
        return False
    else:
        return True


def bfs(h, w):
    dist = [[-1] * (W+2) for i in range(H+2)]
    q = deque()

    max_dist = 0
    dist[h][w] = 0
    q.append((h, w, 0))

    # while len(q) > 0:
    while len(q) > 0:
        h, w, val = q.popleft()
        dist[h][w] = val
        max_dist = max(max_dist, val)

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if data[h_new][w_new] == '.' and dist[h_new][w_new] == -1:
                q.append((h_new, w_new, val+1))

    return max_dist


ans = 0
for h in range(H+2):
    for w in range(W+2):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

'''
3 5
...#.
.#.#.
.#...
'''

import sys
# from collections import deque
import queue


stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = na()
# data = [ns() for _ in range(H)]

data = [list("#" * (W + 2))]
# 周りを'#'で埋めておく
for _ in range(H):
    data.append(["#"] + list(input()) + ["#"])
data += [list("#" * (W + 2))]


def judge(h, w, dist):
    if data[h][w] == '#' or dist[h][w] > -1:
        return False
    else:
        return True


def bfs(h, w):
    dist = [[-1] * (W+2) for i in range(H+2)]
    # q = deque()
    q = queue.Queue()

    max_dist = 0
    dist[h][w] = 0
    # q.append((h, w, 0))
    q.put((h, w, 0))

    # while len(q) > 0:
    while not q.empty():
        # h, w, val = q.popleft()
        h, w, val = q.get()
        dist[h][w] = val
        max_dist = max(max_dist, val)

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if judge(h_new, w_new, dist):
                q.put((h_new, w_new, val+1))

    return max_dist


ans = 0
for h in range(H+2):
    for w in range(W+2):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

'''
3 5
...#.
.#.#.
.#...
'''

import sys
# from collections import deque
import queue


stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = na()
# H, W = map(int, input().split())
data = [ns() for _ in range(H)]

# data = [None] * H
# for i in range(H):
#     data[i] = input()


def judge(h, w, dist):
    if (h < 0) or (h >= H) or (w < 0) or (w >= W):
        return False
    if data[h][w] == '#' or dist[h][w] > -1:
        return False
    else:
        return True


def bfs(h, w):
    dist = [[-1] * W for i in range(H)]
    # q = deque()
    q = queue.Queue()

    max_dist = 0
    dist[h][w] = 0
    # q.append((h, w, 0))
    q.put((h, w, 0))

    # while len(q) > 0:
    while not q.empty():
        # h, w, val = q.popleft()
        h, w, val = q.get()
        dist[h][w] = val
        max_dist = max(max_dist, val)

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if judge(h_new, w_new, dist):
                q.put((h_new, w_new, val+1))

    return max_dist


ans = 0
for h in range(H):
    for w in range(W):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

'''
3 5
...#.
.#.#.
.#...
'''


# from collections import deque
import queue

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

data = [None] * H
for i in range(H):
    data[i] = input()


def judge(h, w, dist):
    if (h < 0) or (h >= H) or (w < 0) or (w >= W):
        return False
    if data[h][w] == '#' or dist[h][w] > -1:
        return False
    else:
        return True


def bfs(h, w):
    dist = [[-1] * W for i in range(H)]
    # q = deque()
    q = queue.Queue()

    max_dist = 0
    dist[h][w] = 0
    # q.append((h, w, 0))
    q.put((h, w, 0))

    # while len(q) > 0:
    while not q.empty():
        # h, w, val = q.popleft()
        h, w, val = q.get()
        dist[h][w] = val
        max_dist = max(max_dist, val)

        m = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for dx, dy in m:
            h_new, w_new = h + dx, w + dy
            if judge(h_new, w_new, dist):
                q.put((h_new, w_new, val+1))

    return max_dist


ans = 0
for h in range(H):
    for w in range(W):
        if data[h][w] == '.':
            res = bfs(h, w)
            if ans < res:
                ans = res

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)
# BFSなのでdeque / queue使う・・・微妙に1つだけTLE残る

# 全ての地点から全ての地点への最短経路を求める

# from collections import deque
import queue

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

data = [None] * H
for i in range(H):
    data[i] = input()


def judge(h, w, dist):
    if (h < 0) or (h >= H) or (w < 0) or (w >= W):
        return False
    if data[h][w] == '#' or dist[h][w] > -1:
        return False
    else:
        return True


def bfs(h, w):
    dist = [[-1] * W for i in range(H)]
    # q = deque()
    q = queue.Queue()

    max_dist = 0
    dist[h][w] = 0
    # q.append((h, w, 0))
    q.put((h, w, 0))

    # while len(q) > 0:
    while not q.empty():
        # h, w, val = q.popleft()
        h, w, val = q.get()
        dist[h][w] = val
        max_dist = max(max_dist, val)

        if judge(h+1, w, dist):
            q.put((h+1, w, val+1))
        if judge(h-1, w, dist):
            q.put((h-1, w, val+1))
        if judge(h, w+1, dist):
            q.put((h, w+1, val+1))
        if judge(h, w-1, dist):
            q.put((h, w-1, val+1))

    return max_dist


ans = 0
for h in range(H):
    for w in range(W):
        if data[h][w] == '.':
            res = bfs(h, w)
            ans = max(ans, res)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D

# BFSで各点から到達可能な最も遠いところを探索する
# 1回探索はO(HW)なのでO(HHWW)?
# BFSなのでdeque / queue使う

# from collections import deque
import queue

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

data = [None] * H
for i in range(H):
    data[i] = input()


def judge(h, w, dist):
    if (h >=0) and (h < H) and (w >= 0) and (w < W):
        if data[h][w] == '.' and dist[h][w] == -1:
            return True
        else:
            return False
    return False


def bfs(h, w):
    dist = [[-1] * W for i in range(H)]
    # q = deque()
    q = queue.Queue()

    max_dist = 0
    dist[h][w] = 0
    # q.append((h, w, 0))
    q.put((h, w, 0))

    # while len(q) > 0:
    while not q.empty():
        # h, w, val = q.popleft()
        h, w, val = q.get()
        dist[h][w] = val
        max_dist = max(max_dist, val)

        if judge(h+1, w, dist):
            q.put((h+1, w, val+1))
        if judge(h-1, w, dist):
            q.put((h-1, w, val+1))
        if judge(h, w+1, dist):
            q.put((h, w+1, val+1))
        if judge(h, w-1, dist):
            q.put((h, w-1, val+1))

    return max_dist


ans = 0
for h in range(H):
    for w in range(W):
        if data[h][w] == '.':
            res = bfs(h, w)
            # print(h, w, res)
            ans = max(ans, res)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D

from collections import deque

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

data = [None] * H
for i in range(H):
    data[i] = input()
# print(data)

def judge(h, w, dist):
    if (h >=0) and (h < H) and (w >= 0) and (w < W):
        if data[h][w] == '.' and dist[h][w] == -1:
            return True
        else:
            return False
    return False


def bfs(h, w):
    dist = [[-1] * W for i in range(H)]
    q = deque()

    max_dist = 0
    dist[h][w] = 0
    q.append((h, w, 0))

    while len(q) > 0:
        h, w, val = q.popleft()
        dist[h][w] = val
        max_dist = max(max_dist, val)

        if judge(h+1, w, dist):
            q.append((h+1, w, val+1))
        if judge(h-1, w, dist):
            q.append((h-1, w, val+1))
        if judge(h, w+1, dist):
            q.append((h, w+1, val+1))
        if judge(h, w-1, dist):
            q.append((h, w-1, val+1))

    return max_dist


ans = 0
for h in range(H):
    for w in range(W):
        if data[h][w] == '.':
            res = bfs(h, w)
            # print(h, w, res)
            ans = max(ans, res)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def main():
	H, W = (int(x) for x in input().split())
	S = [[] for x in range(H)]

	for i in range(H):
		S[i] = [x for x in input()]

	# 隣接行列の作成
	inf = 1000000

	nodes = []
	for i in range(H):
		for j in range(W):
			if S[i][j] == ".":
				nodes.append([i, j])
	
	g = [[inf for j in range(len(nodes))] for i in range(len(nodes))]
	for i in range(len(nodes)):
		for j in range(len(nodes)):
			if   nodes[i][0] == nodes[j][0] and nodes[i][1] == nodes[j][1]:
				g[i][j] = 0
			elif abs(nodes[i][0]-nodes[j][0]) + abs(nodes[i][1]-nodes[j][1]) == 1:
				g[i][j] = 1

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

	for i in range(len(g[0])):
		for j in range(len(g[0])):
			if max < g[i][j]:
				max = g[i][j]
                
	print(max)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(input())
nodes = []
nodedict = {}
for r in range(H):
    for c in range(W):
        if maze[r][c] == '.':
            node_id = len(nodes)
            nodedict[(r,c)] = node_id
            nodes.append((r,c))
N = len(nodes)
INF = H*W+100
dist = [[INF] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

def connect(r1, c1, r2, c2):
    n1 = nodedict[(r1, c1)]
    n2 = nodedict[(r2, c2)]
    dist[n1][n2] = 1
    dist[n2][n1] = 1

def solve():
    for i in range(N):
        r, c = nodes[i]
        if r > 0 and maze[r-1][c] == '.': connect(r, c, r-1, c)
        if r < H-1 and maze[r+1][c] == '.': connect(r, c, r+1, c)
        if c > 0 and maze[r][c-1] == '.': connect(r, c, r, c-1)
        if c < W-1 and maze[r][c+1] == '.': connect(r, c, r, c+1)

    # Warshall Floyd
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    maxd = 0
    di, dj = None, None
    for i in range(N):
        for j in range(N):
            d = dist[i][j]
            if d < INF and maxd < d:
                maxd = d
                di = nodes[i]
                dj = nodes[j]
    return maxd  #, di, dj


print(solve())