Problem:


Score : 400 points

Problem Statement

Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.

The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is #, and a "road" square if S_{ij} is ..

From a road square, you can move to a horizontally or vertically adjacent road square.

You cannot move out of the maze, move to a wall square, or move diagonally.

Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.

Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.

In this situation, find the maximum possible number of moves Aoki has to make.

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

Any road square can be reached from any road square in zero or more moves.

Input

Input is given from Standard Input in the following format:

H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

Output

Print the maximum possible number of moves Aoki has to make.

Sample Input 1

3 3
...
...
...

Sample Output 1

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Sample Input 2

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

Sample Output 2

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque


h, w = map(int, input().split())
ls = []  # [[0, 0, 0, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 0, 0]]
for _ in range(h):
    ls1 = []
    s = input()
    for i in range(w):
        if s[i] == '.':
            ls1.append(0)
        else:
            ls1.append(1)
    ls.append(ls1)

def trans(a, b):
    return a * w + b

ls2 = [[] for _ in range(h * w)]


for i in range(h):
    for j in range(w):
        # check ij
        if ls[i][j] == 1:
            continue

        if 0 <= i < h and 0 <= j - 1 < w and ls[i][j - 1] == 0:
            ls2[trans(i, j)].append(trans(i, j - 1))
            #print(ls2)
        if 0 <= i + 1 < h and 0 <= j < w and ls[i + 1][j] == 0:
            ls2[trans(i, j)].append(trans(i + 1, j))
            #print(ls2)
        if 0 <= i - 1 < h and 0 <= j < w and ls[i - 1][j] == 0:
            ls2[trans(i, j)].append(trans(i - 1, j))
            #print(ls2)
        if 0 <= i < h and 0 <= j + 1 < w and ls[i][j + 1] == 0:
            ls2[trans(i, j)].append(trans(i, j + 1))

#print(ls2)


def route(i, j):
    if i == j:
        return 0
    count = 1
    ss = deque(ls2[i])
    next = deque()
    now = i
    explored = [i]
    while True:
        #print(now, i, j)
        if not ss:
            count +=1
            ss = next
            next = deque()
        now =ss.popleft()
        if now in explored:
            continue
        if now == j:
            #print(count)
            return count
        else:
            next.extend(ls2[now])


ls3 = [0] * (h * w)


for i in range(h * w):
    if ls2[i] == []:
        continue
    count = 0
    for j in range(h * w):
        if ls2[j] == []:
            continue
        else:
            count = max( count, route(i, j))
    ls3[i] = count

print(max(ls3))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid

    def pos(self, x, y):
        return y * (self.w + 2) + x + 1

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]

        d = [[INF for i in range(self.size)] for j in range(self.size)]
        for i in range(self.size):
            d[i][i] = 0

        for i in range(1, self.h + 1):
            for j in range(1, self.w + 1):
                # pass # ここから何か書いてね
                cx, cy = j, i
                if grid[cy][cx] == "#":
                    continue
                cur = grid[cy][cx]
                for mv in move:
                    dx, dy = mv
                    nx, ny = cx + dx, cy + dy
                    if grid[ny][nx] == ".":
                        d[self.pos(cx, cy)][self.pos(nx, ny)] = 1

        d = warshall_floyd(d, self.size)
        ans = 0
        for dd in d:
            for ddd in dd:
                if ddd != INF:
                    ans = max(ans, ddd)


        print(ans)


def solve():
    h, w = getList()
    G = TwoDimGrid(h, w)
    G.search()
    return



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Time Limit Exceeded

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

for r in range(H):
  maze.append(list(input()))
maxVisit = 0
for row in maze:
  for road in row:
    if (road == "."):
      maxVisit += 1
# do bfs for each point and record maximum steps...
def findMaxBFS(start):
  # initialize BFS
  visitedCount = 1
  visitedPoints = []
  for r in range(H):
    visitedPoints.append([])
    for c in range(W):
      if (r == start[0]) and (c == start[1]):
        visitedPoints[r].append("Y")
      else:
        visitedPoints[r].append("N")
  points = [start]
  directions = [[0,1], [0,-1], [1,0], [-1,0]]
  steps = 0
  # BFS starts
  while (visitedCount < maxVisit):
    steps += 1
    nextPoints = []
    for p in points:
      for d in directions:
        nextP = [p[0]+d[0], p[1]+d[1]]
        #check nextP is inside the maze
        if (0<=nextP[0] and nextP[0]<H) and (0<=nextP[1] and nextP[1]<W):
          road = maze[nextP[0]][nextP[1]]
          #check nextP is walkable = stone
          if (road == "."):
            # check if nextP is already visisted
            if (visitedPoints[nextP[0]][nextP[1]] == "N"):
              nextPoints.append(nextP)
              visitedCount += 1
              visitedPoints[nextP[0]][nextP[1]] = "Y" 
    points = nextPoints
  # BFS ended
  # return max step
  return steps

max_steps = []
for r in range(H):
  for c in range(W):
    max_steps.append(findMaxBFS([r,c]))
print(max(max_steps))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    H, W = map(int, input().split())
    S_lsit = [input() for i in range(H)]

    INF = 401

    node_list = []
    for i in range(H):
        node_list += [(i, j) for j in range(W)]

    dist_table = [[INF for j in range(H*W)] for i in range(H*W)]
    for i in range(H*W):
        dist_table[i][i] = 0
    #print(dist_table)

    path_list = [[] for i in range(H*W)]
    for k in range(H*W):
        node = node_list[k]
        i, j = node[0], node[1]
        if i >= 1 and S_lsit[i-1][j] == ".":
            path_list[k].append((i-1)*W + j)
        if i <= H-2 and S_lsit[i+1][j] == ".":
            path_list[k].append((i+1)*W + j)
        if j >= 1 and S_lsit[i][j-1] == ".":
            path_list[k].append(i*W + j-1)
        if j <= W-2 and S_lsit[i][j+1] == ".":
            path_list[k].append(i*W + j+1)
        for next_node in path_list[k]:
            dist_table[k][next_node] = 1
    #print(path_list)

    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                dist_table[i][j] = min(
                    dist_table[i][j],
                    dist_table[i][k] + dist_table[k][j]
                )
    #print(dist_table)

    max_dist = 0
    for i in range(H*W):
        if S_lsit[i//W][i%W] == ".":
            for j in range(H*W):
                if S_lsit[j//W][j%W] == ".":
                    max_dist = max(max_dist, dist_table[i][j])
    print(max_dist)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    field = "#"*(W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#"*(W+2)

    INF = 10**9
    cost = [INF]*len(field)
    move = [-1, 1, -(W+2), W+2]
    def bfs(s):
        q = deque()

        cost[s] = 0
        q.append(s)

        while q:
            now = q.popleft()
            now_cost = cost[now]
            for dx in move:
                nv = now + dx

                if field[nv] == "#" or cost[nv] < INF:
                    continue
                else:
                    cost[nv] = now_cost + 1
                    q.append(nv)
    
    ans = 0
    s_flag = False
    for si in range(H):
        for sj in range(W):
            s_flag = False
            for gi in range(H):
                if s_flag:
                    break
                for gj in range(W):
                    start = (si+1)*(W+2)+sj+1
                    goal = (gi+1)*(W+2)+gj+1
                    if field[start] == "#":
                        s_flag = True
                        break
                    if field[goal] == "#":
                        continue
                    if start == goal:
                        continue
                    cost = [INF] * len(field)
                    bfs(start)
                    ans = max(ans, cost[goal])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    field = "#"*(W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#"*(W+2)

    INF = 10**9
    cost = [INF]*len(field)
    move = [-1, 1, -(W+2), W+2]
    def bfs(s):
        q = deque()

        cost[s] = 0
        q.append(s)

        while q:
            now = q.popleft()
            now_cost = cost[now]
            for dx in move:
                nv = now + dx

                if field[nv] == "#" or cost[nv] < INF:
                    continue
                else:
                    cost[nv] = now_cost + 1
                    q.append(nv)
    
    ans = 0
    for si in range(H):
        for sj in range(W):
            for gi in range(H):
                for gj in range(W):
                    start = (si+1)*(W+2)+sj+1
                    goal = (gi+1)*(W+2)+gj+1
                    if start == goal or "#" in [field[start], field[goal]]:
                        continue
                    cost = [INF] * len(field)
                    bfs(start)
                    ans = max(ans, cost[goal])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    dd = 0, 1, 0, -1

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

    def dist(sr, sc, gr, gc):
        if G[sr][sc] == '#' or G[gr][gc] == '#':
            return -1

        memo = [[-1] * W for _ in range(H)]

        dq = deque()
        dq.append((sr, sc, 0))
        while dq:
            r, c, d = dq.popleft()
            if r == gr and c == gc:
                return d

            nd = d + 1
            for i in range(4):
                nr = r + dd[i]
                nc = c + dd[i ^ 1]
                if not (0 <= nr < H and 0 <= nc < W):
                    continue
                if ~memo[nr][nc]:
                    continue
                if G[nr][nc] == '#':
                    continue
                dq.append((nr, nc, nd))
                memo[nr][nc] = nd

        return -1

    ans = 0
    for sr in range(H):
        for sc in range(W):
            for gr in range(H):
                for gc in range(W):
                    ans = max(ans, dist(sr, sc, gr, gc))

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Time Limit Exceeded

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    is_visited[start[0]][start[1]] = float('inf')
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      # is_visited[now_h][now_w] = 1
      is_visited[now_h][now_w] = float('inf')
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (is_visited[next_h][next_w] == float('inf')) or \
           M[next_h][next_w] == '#':
           # (dist[next_h][next_w] != float('inf')) or \
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      # is_visited[now_h][now_w] = 1
      is_visited[now_h][now_w] = float('inf')
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (is_visited[next_h][next_w] == float('inf')) or \
           M[next_h][next_w] == '#':
           # (dist[next_h][next_w] != float('inf')) or \
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (is_visited[next_h][next_w] == 1) or \
           M[next_h][next_w] == '#':
           # (dist[next_h][next_w] != float('inf')) or \
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           is_visited[next_h][next_w] or \
           M[next_h][next_w] == '#':
           # (dist[next_h][next_w] != float('inf')) or \
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           is_visited[next_h][next_w] or \
           M[next_h][next_w] == '#':
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

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

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start, goal):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0
    # is_visited = set()
    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      # is_visited.add((now_h, now_w))
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        # if ((next_h, next_w) in is_visited) or not(0 <= next_h < H) or not(0 <= next_w < W):
        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           is_visited[next_h][next_w] or \
           M[next_h][next_w] == '#':
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        if goal == (next_h, next_w):
          return dist[next_h][next_w]
        q.append((next_h, next_w))

  all_ = []
  for h in range(H):
    for w in range(W):
      all_.append((h, w))

  max_ = 0
  for start, goal in itertools.combinations(all_, 2):
    if M[start[0]][start[1]] == '.' and M[goal[0]][goal[1]] == '.':
      max_ = max(max_, bfs(start, goal))

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

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


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

  M = [input()[:-1] for _ in range(H)]

  def bfs(start, goal):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0
    is_visited = set()
    q = deque([start])
    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      is_visited.add((now_h, now_w))
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if ((next_h, next_w) in is_visited) or not(0 <= next_h < H) or not(0 <= next_w < W):
          continue

        if M[next_h][next_w] == '#':
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        if goal == (next_h, next_w):
          return dist[next_h][next_w]
        q.append((next_h, next_w))

  all_ = []
  for h in range(H):
    for w in range(W):
      all_.append((h, w))

  max_ = 0
  for start, goal in itertools.combinations(all_, 2):
    if M[start[0]][start[1]] == '.' and M[goal[0]][goal[1]] == '.':
      max_ = max(max_, bfs(start, goal))

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Time Limit Exceeded

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

for ix in range(H):
    S.append(list(input()))

DMX = 500
dp = [[10**9 for _ in range(DMX)] for __ in range(DMX)]

def tid(x,y):
    return x*W+y

for i in range(DMX):
    dp[i][i] = 0

D = ((1,0), (0,1), (-1,0), (0, -1))
for ix in range(H):
    for jy in range(W):
        if S[ix][jy] == '#':
            continue
        for dx, dy in D:
            nx = ix + dx
            ny = jy + dy

            if nx < 0 or ny < 0 or nx >= H or ny >= W or S[nx][ny] == '#':
                continue

            dp[tid(ix,jy)][tid(nx, ny)] = 1
            dp[tid(nx,ny)][tid(ix, jy)] = 1

# Floyd-Warshall
V = H * W
for v in range(V):
    for i in range(V):
        for j in range(V):
            t = dp[i][v] + dp[v][j]
            if dp[i][j] > t:
                dp[i][j] = t

ans = 0
for x in range(H):
    for y in range(W):
        if S[x][y] == '#':
            continue
        for x2 in range(H):
            for y2 in range(W):
                if S[x2][y2] == '#':
                    continue
                t = dp[tid(x,y)][tid(x2,y2)]
                if t > ans:
                    ans = t

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product, combinations

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

points = [(y, x) for y, x in product(range(H), range(W)) if maze[y][x] == '.']

ans = 0
for (sy, sx), (gy, gx) in combinations(points, r=2):
    checked = set()
    queue = deque()
    queue.append((sy, sx, 0))
    while queue:
        y, x, cost = queue.popleft()
        checked.add((y, x))
        if (y, x) == (gy, gx):
            ans = max(ans, cost)
            break

        for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
            if not 0 <= ny < H:
                continue
            if not 0 <= nx < W:
                continue
            if (ny, nx) in checked:
                continue
            if maze[ny][nx] == '#':
                continue
            queue.append((ny, nx, cost + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys

sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy
import queue
from collections import deque


def minload(data_copy, high_i, width_i, high_j, width_j, high, width):
    data = deepcopy(data_copy)
    count = 0
    now_point = set()
    now_point.add((high_i, width_i))
    next_point = set()
    goal = [high_j, width_j]
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    while 1:
        for now_i, now_j in now_point:
            data[now_i][now_j] = count
            for move_i, move_j in move:
                next_i, next_j = now_i + move_i, now_j + move_j
                if next_i < 0 or next_i >= high or next_j < 0 or next_j >= width:
                    continue
                if data[next_i][next_j] != ".":
                    continue
                # data[next_i][next_j] = count
                next_point.add((next_i, next_j))

        if data[goal[0]][goal[1]] != ".":
            break
        now_point = next_point
        next_point = set()
        count += 1

    # print(data)

    return data[goal[0]][goal[1]]



def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    ans = 0

    for high_i in range(high):
        for width_i in range(width):
            for high_j in range(high):
                for width_j in range(width):
                    # print(high_i, width_i, high_j, width_j)
                    if high_i <= high_j and width_i <= width_j:
                        continue
                    if data[high_i][width_i] == data[high_j][width_j] == ".":
                        ans = max(ans, minload(data, high_i, width_i, high_j, width_j, high, width))
                        # print(ans, data)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys

sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy
import queue
from collections import deque


def minload(data_copy, high_i, width_i, high_j, width_j, high, width):
    data = deepcopy(data_copy)
    count = 0
    now_point = set()
    now_point.add((high_i, width_i))
    next_point = set()
    goal = [high_j, width_j]
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]

    while 1:
        for now_i, now_j in now_point:
            data[now_i][now_j] = count
            for move_i, move_j in move:
                next_i, next_j = now_i + move_i, now_j + move_j
                if next_i < 0 or next_i >= high or next_j < 0 or next_j >= width:
                    continue
                if data[next_i][next_j] != ".":
                    continue
                # data[next_i][next_j] = count
                next_point.add((next_i, next_j))

        if data[goal[0]][goal[1]] != ".":
            break
        now_point = next_point
        next_point = set()
        count += 1

    # print(data)

    return data[goal[0]][goal[1]]



def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    ans = 0

    for high_i in range(high):
        for width_i in range(width):
            for high_j in range(high):
                for width_j in range(width):
                    # print(high_i, width_i, high_j, width_j)
                    if data[high_i][width_i] == data[high_j][width_j] == ".":
                        ans = max(ans, minload(data, high_i, width_i, high_j, width_j, high, width))
                        # print(ans, data)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
field = ''
for i in range(H):
    field += input()
field += '#' * W

def bfs(s):
    noreach = [1] * (H * W)
    for _ in range(W):
        noreach.append(0)
    q = deque()
    q.append((s, 0))
    while q:
        p, c = q.popleft()
        noreach[p] = 0
        if (field[p - W] == '.') and noreach[p - W]:
            q.append((p - W, c + 1))
        if (field[p + W] == '.') and noreach[p + W]:
            q.append((p + W, c + 1))
        if (field[p - 1] == '.') and noreach[p - 1] and p % W != 0:
            q.append((p - 1, c + 1))
        if (field[p + 1] == '.') and noreach[p + 1] and p % W != W - 1:
            q.append((p + 1, c + 1))
    return c

ans = -1
for s in range(H * W):
    if field[s] == '.':
        ans = max(ans, bfs(s))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

def num_to_coo(p):
    h, w = divmod(p, W)
    h += 1
    w += 1
    return h, w

def bfs(s):
    noreach = [1] * (H * W)
    for _ in range(W):
        noreach.append(0)
    q = deque()
    q.append((s, 0))
    while q:
        p, c = q.popleft()
        noreach[p] = 0
        h, w = num_to_coo(p)
        if (field[h - 1][w] == '.') and noreach[p - W]:
            q.append((p - W, c + 1))
        if (field[h + 1][w] == '.') and noreach[p + W]:
            q.append((p + W, c + 1))
        if (field[h][w - 1] == '.') and noreach[p - 1]:
            q.append((p - 1, c + 1))
        if (field[h][w + 1] == '.') and noreach[p + 1]:
            q.append((p + 1, c + 1))
    return c

ans = -1
for s in range(H * W):
    h, w = num_to_coo(s)
    if field[h][w] == '.':
        ans = max(ans, bfs(s))
print(ans)