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
import copy

digtmp = [[0, 1], [1, 0], [0, -1], [-1, 0]]

def bfs(maze, s, g):
    que = deque([s])
    maze[s[0]][s[1]] = 0
    for _ in range(pow(10, 3)):
        fr = que.popleft()
        for d in digtmp:
            to = [fr[0] + d[0], fr[1] + d[1]]
            if maze[to[0]][to[1]] == '.':
                maze[to[0]][to[1]] = maze[fr[0]][fr[1]] + 1
                que.append(to)
        if maze[g[0]][g[1]] != '.':
            break
        if len(que) == 0:
            break
    ans = maze[g[0]][g[1]]
    return ans

def main():
    H, W = map(int, input().split())
    grid = []; road = []
    grid.append(['#']*(W+2))
    for i in range(H):
        tmp = list(input())
        for j in range(W):
            if tmp[j] == '.':
                road.append([i+1, j+1])
        grid.append(['#'] + tmp + ['#'])
    grid.append(['#']*(W+2))
    
    ans = 1
    for i in range(len(road)):
        for j in range(i+1, len(road)):
            maze = copy.deepcopy(grid)
            ans = max(ans, bfs(maze, road[i], road[j]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def bfs(field, sx, sy, gx, gy, seen):
    queue = deque([(sx, sy)])
    seen[sx][sy] += 1
    
    while queue:
        x, y = queue.popleft()
        if (x, y) == (gx, gy):
            return seen[x][y]

        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            nx = x + dx
            ny = y + dy
            
            if seen[nx][ny] == -1 and field[nx][ny] != "#":
                seen[nx][ny] = seen[x][y] + 1
                queue.append((nx, ny))


def main():
    H,W = map(int, readline().split())
    c = ["#" * (W + 2)]
    for _ in range(H):
        c.append("#" + readline().strip() + "#")
    c.append("#" * (W + 2))

    ans = 0
    for sx in range(1,H+1):
        for sy in range(1,W+1):
            if c[sx][sy] == "#":
                continue
            for gx in range(sx,H+1):
                for gy in range(1,W+1):
                    if c[gx][gy] == "#":
                        continue
                    seen = [[-1] * (W + 2) for i in range(H+2)]
                    dist = bfs(c, sx, sy, gx, gy, seen)
                    ans = max(ans, dist)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def bfs(field, sx, sy, gx, gy, seen):
    queue = deque([(sx, sy)])
    seen[sx][sy] += 1
    
    while queue:
        x, y = queue.popleft()
        if (x, y) == (gx, gy):
            return seen[x][y]

        for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            nx = x + dx
            ny = y + dy
            
            if seen[nx][ny] == -1 and field[nx][ny] != "#":
                seen[nx][ny] = seen[x][y] + 1
                queue.append((nx, ny))


def main():
    H,W = map(int, readline().split())
    c = ["#" * (W + 2)]
    for _ in range(H):
        c.append("#" + readline().strip() + "#")
    c.append("#" * (W + 2))

    ans = 0
    for sx in range(1,H+1):
        for sy in range(1,W+1):
            if c[sx][sy] == "#":
                continue
            for gx in range(1,H+1):
                for gy in range(1,W+1):
                    if (gx, gy) == (sx, sy):
                        continue
                    if c[gx][gy] == "#":
                        continue
                    seen = [[-1] * (W + 2) for i in range(H+2)]
                    dist = bfs(c, sx, sy, gx, gy, seen)
                    ans = max(ans, dist)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(maze, sy, sx, gy, gx, H, W):
    """
    maze>>迷路
    visited>>探索済み
    sy, sx>>スタート地点
    gy, gx>>ゴール地点
    """
    queue = deque([[sy, sx]])
    visited = [[-1]*W for _ in range(H)]
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k

            if new_y < 0 or H -1 < new_y or new_x < 0 or W -1 < new_x:
                continue
            elif maze[new_y][new_x] != '#' and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])


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

answer_list = []
for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if maze[sy][sx] != '#' and maze[gy][gx] != '#':
                    answer_list.append(bfs(maze, sy, sx, gy, gx, H, W))

print(max(answer_list))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

n, m = map(int, input().split(" "))
t = [ [-1] * m for i in range(n) ]

NG='#'
OK='.'

ok_list = []
for i in range(n):
    for j,s in enumerate(input()):
        t[i][j] = s
        if s == OK:
            ok_list.append( (i, j ) )


def depth(t, src, dest):
    q = collections.deque()
    deadlist = { src: 0 }
    q.append( (src[0], src[1], 0) )

    while len(q) != 0:
        x, y, cost = q.popleft()
        for _x, _y in [(x+1, y), (x-1,y), (x,y+1),(x,y-1)]:
            if ((_x,_y) not in deadlist ) and \
                ( 0 <= _x < n) and (0 <= _y < m) and t[_x][_y] == OK:
                deadlist[(_x, _y)] = cost+1
                q.append((_x, _y, cost+1))

    return deadlist.get(dest, -1)


ans = 0
for src, dest in itertools.combinations(ok_list, 2):
    tmp = depth(t, src, dest)
    if ans < tmp:
        ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

ans = 0
INF = 20 * 20 + 1
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[INF] * w for _ in range(h)] 
            cnt[j][i] = 0
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    by += y
                    bx += x 
                    if 0 <= by < h and 0 <= bx < w:
                        if maze[by][bx] == "#": continue
                        ct = cnt[y][x] + 1
                        if ct > cnt[by][bx]: continue 
                        q += [(by,bx)] 
                        cnt[by][bx] = ct
                        ans = max(ans, cnt[by][bx])


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

ans = 0
INF = 1e10
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[INF] * w for _ in range(h)] 
            cnt[j][i] = 0
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    by += y
                    bx += x 
                    if 0 <= by < h and 0 <= bx < w:
                        if maze[by][bx] == "#": continue
                        ct = cnt[y][x] + 1
                        if ct > cnt[by][bx]: continue 
                        q += [(by,bx)] 
                        cnt[by][bx] = ct
                        ans = max(ans, cnt[by][bx])


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

ans = 0
INF = 1e100
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[INF] * w for _ in range(h)] 
            cnt[j][i] = 0
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    by += y
                    bx += x 
                    if 0 <= by < h and 0 <= bx < w:
                        if maze[by][bx] == "#": continue
                        ct = cnt[y][x] + 1
                        if ct > cnt[by][bx]: continue 
                        q += [(by,bx)] 
                        cnt[by][bx] = ct
                        ans = max(ans, cnt[by][bx])


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  while queue:
    y, x = queue.popleft()
    if [y, x] == [gy, gx]:
      return visited[y][x]
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if new_y >= H or new_y < 0 or new_x >= W or new_x < 0:
        continue
      elif maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        visited[new_y][new_x] = visited[y][x] + 1
        queue.append([new_y, new_x])

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
ans = 0
for sy in range(H):
  for sx in range(W):
    for gy in range(H):
      for gx in range(W):
        visited = [[-1]*W for j in range(H)]
        res = bfs(maze, visited, sy, sx, gy, gx)
        if res != None:
          ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
 
H, W = map(int, input().split())
field_s = []
 
# フィールドを作る
for h in range(H + 2):
    field_s.append(["#"] * (W + 2))
    if 1 <= h <= (H):
        field_s[h][1:-1] = list(map(str, input().rstrip()))
 
# 動き方のセットを準備
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
 
# スタートとゴールの座標の組み合わせを作成
sg = []
for y in range(H + 2):
    for x in range(W + 2):
        if field_s[y][x] == ".":
            sg.append([y, x])
 
# 答え
ans = 0
 
# スタートとゴールの座標を組み合わせてぐるぐる
for s in sg:
    for g in sg:
 
        # startとgoalの座標が同じならスキップ
        if s == g:
            continue
 
        # fieldの初期化
        field = copy.deepcopy(field_s)
 
        # startをキューに追加
        que = deque([s])
 
        # startの距離は0に
        field[s[0]][s[1]] = 0
 
        # キューに何かがある限り探索を続ける
        while que:
            c = que.popleft()
 
            # 今の距離
            dist = field[c[0]][c[1]]
 
            # 動いた先が「.」なら、距離を記録してキューに追加
            for m in moves:
                my = c[0] + m[0]
                mx = c[1] + m[1]
 
                if field[my][mx] == ".":
                    field[my][mx] = dist + 1
                    que.append([my, mx])
                else:
                    continue
 
                # もしゴールに到達していたらansを差し替えてbreak
                if [my, mx] == g:
                    ans = max(ans, field[my][mx])
                    break
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque
from itertools import combinations

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

# フィールドを作る
for h in range(H + 2):
    field_s.append(["#"] * (W + 2))
    if 1 <= h <= (H):
        field_s[h][1:-1] = list(map(str, input().rstrip()))

#　動き方のセットを準備
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

# スタートとゴールの座標の組み合わせを作成
sg = []
for y in range(H + 2):
    for x in range(W + 2):
        if field_s[y][x] == ".":
            sg.append([y, x])

# 答え
ans = 0

# スタートとゴールの座標を組み合わせてぐるぐる
for s, g in list(combinations(sg, 2)):

    # startとgoalの座標が同じならスキップ
    if s == g:
        continue

    # fieldの初期化
    field = copy.deepcopy(field_s)

    # startをキューに追加
    que = deque([s])

    # startの距離は0に
    field[s[0]][s[1]] = 0

    # キューに何かがある限り探索を続ける
    while que:
        c = que.popleft()

        # 今の距離
        dist = field[c[0]][c[1]]

        # 動いた先が「.」なら、距離を記録してキューに追加
        for m in moves:
            my = c[0] + m[0]
            mx = c[1] + m[1]

            if field[my][mx] == ".":
                field[my][mx] = dist + 1
                que.append([my, mx])
            else:
                continue

            # もしゴールに到達していたらansを差し替えてbreak
            if [my, mx] == g:
                ans = max(ans, field[my][mx])
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

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

# フィールドを作る
for h in range(H + 2):
    field_s.append(["#"] * (W + 2))
    if 1 <= h <= (H):
        field_s[h][1:-1] = list(map(str, input().rstrip()))

#　動き方のセットを準備
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

# スタートとゴールの座標の組み合わせを作成
sg = []
for y in range(H + 2):
    for x in range(W + 2):
        if field_s[y][x] == ".":
            sg.append([y, x])

# 答え
ans = 0

# スタートとゴールの座標を組み合わせてぐるぐる
for s in sg:
    for g in sg:

        # startとgoalの座標が同じならスキップ
        if s == g:
            continue

        # fieldの初期化
        field = copy.deepcopy(field_s)

        # startをキューに追加
        que = deque([s])

        # startの距離は0に
        field[s[0]][s[1]] = 0

        # キューに何かがある限り探索を続ける
        while que:
            c = que.popleft()

            # 今の距離
            dist = field[c[0]][c[1]]

            # 動いた先が「.」なら、距離を記録してキューに追加
            for m in moves:
                my = c[0] + m[0]
                mx = c[1] + m[1]

                if field[my][mx] == ".":
                    field[my][mx] = dist + 1
                    que.append([my, mx])
                else:
                    continue

                # もしゴールに到達していたらansを差し替えてbreak
                if [my, mx] == g:
                    ans = max(ans, field[my][mx])
                    break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(s, visited, sy, sx, gy, gx):

    queue = deque([sy, sx])
    visited[sy][sx] = 0 

    while queue:
        
        y = queue.popleft()
        x = queue.popleft()
        

        if [y, x] == [gy, gx]:
            return visited[y][x]
        
        for (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            
            new_y = y + i
            new_x = x + j

            if (0 <= new_y < h) and (0 <= new_x < w):

                if s[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                        
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append(new_y)
                    queue.append(new_x)


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

position = []
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            position.append([i, j])

position_set = []
a = len(position)
for i in range(a):
    for j in range(a):
        position_set.append(position[i] + position[j])

ans =[]
for i in position_set:
    visited = [[-1]*w for _ in range(h)] 
    ans.append(bfs(s, visited, i[0], i[1], i[2], i[3]))


print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

h,w = nm()

s = []

for y in range(h):
  s.append([_ for _ in input()])



def bfs(sx,sy,gx,gy,route):
  xx=[1,-1,0,0]
  yy=[0,0,1,-1]
  
  if sx == gx and sy == gy:
    return 0
  
  mn = 9999
  for i in range(4):
    nx = sx + xx[i]
    ny = sy + yy[i]
    
    if 0 <= nx < w and 0 <= ny < h:
      if s[ny][nx] == '.':
        if (nx,ny) not in route:
          mn = min(mn,bfs(nx,ny,gx,gy,route+[(nx,ny)]))
  return mn+1

mx = 0

for sx in range(w):
  for sy in range(h):
    for gx in range(w):
      for gy in range(h):
        if s[sy][sx] == '.' and s[gy][gx] == '.':
          b = bfs(sx,sy,gx,gy,[])
          if b < h*w:
            mx = max(mx,b)

print(mx)

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

h,w = nm()

s = []

for y in range(h):
  s.append([_ for _ in input()])



def bfs(sx,sy,gx,gy,route):
  xx=[1,-1,0,0]
  yy=[0,0,1,-1]
  
  if sx == gx and sy == gy:
    return 0
  
  mn = 9999
  for i in range(4):
    nx = sx + xx[i]
    ny = sy + yy[i]
    
    if 0 <= nx < w and 0 <= ny < h:
      if s[ny][nx] == '.':
        if (nx,ny) not in route:
          mn = min(mn,bfs(nx,ny,gx,gy,route+[(nx,ny)]))
  return mn+1

mx = 0

for sx in range(w):
  for sy in range(h):
    for gx in range(w):
      for gy in range(h):
        if s[sy][sx] == '.' and s[gy][gx] == '.':
          b = bfs(sx,sy,gx,gy,[])
          if b < h*w:
            mx = max(mx,b)

print(mx)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append(["#" * W])
for h in range(H-2):
  grid.append(["#" + input() + "#"])
grid.append(["#" * W])

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    m_grid = 0
    if grid[h][0][w]=="#": continue

    dist = [[INF]*W for i in range(H)]
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      m_grid = max(d_v, m_grid)
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][0][n_w]=="#": continue
        d_n = d_v + 1
        if d_n > dist[n_h][n_w]:
          continue

        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))
        m_grid = max(d_n, m_grid)

    
    ans = max(ans, m_grid)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append(["#" * W])
for h in range(H-2):
  grid.append(["#" + input() + "#"])
grid.append(["#" * W])

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    
    if grid[h][0][w]=="#": continue

    dist = [[INF]*W for i in range(H)]
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][0][n_w]=="#": continue
        d_n = d_v + 1
        if d_n > dist[n_h][n_w]:
          continue
        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))

    new_dist =[]
    for l in dist:
      new_dist.append([x for x in l if x < INF])
    LL = [max(l) if len(l)>0 else 0 for l in new_dist]
    ans = max(ans, max(LL))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append(["#" * W])
for h in range(H-2):
  grid.append(["#" + input() + "#"])
grid.append(["#" * W])

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    
    if grid[h][0][w]=="#": continue

    dist = [[INF]*W for i in range(H)]
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][0][n_w]=="#": continue
        d_n = d_v + 1
        if d_n > dist[n_h][n_w]:
          continue
        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))

    new_dist =[]
    for l in dist:
      new_dist.append([x for x in l if x < INF])
    LL = [max(l) if len(l)>0 else 0 for l in new_dist]
    ans = max(ans, max(LL))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append("#" * W)
for h in range(H-2):
  grid.append("#" + input() + "#")
grid.append("#" * W)

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    
    if grid[h][w]=="#": continue

    dist = np.array([[INF]*W for i in range(H)])
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][n_w]=="#": continue
        d_v = dist[v_h][v_w]
        d_n = d_v + 1
        if (dist[n_h][n_w] == -1) & (d_n > dist[n_h][n_w]):
          continue
        
        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))


    
      dist_m = max(x for x in dist.flatten() if x < INF)
      ans = max(ans, dist_m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append("#" * W)
for h in range(H-2):
  grid.append("#" + input() + "#")
grid.append("#" * W)

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    
    if grid[h][w]=="#": continue

    dist = np.array([[INF]*W for i in range(H)])
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][n_w]=="#": continue
        d_n = d_v + 1
        if d_n > dist[n_h][n_w]:
          continue
        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))


    
      dist_m = max(x for x in dist.flatten() if x < INF)
      ans = max(ans, dist_m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append(["#" * W])
for h in range(H-2):
  grid.append(["#" + input() + "#"])
grid.append(["#" * W])

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    
    if grid[h][0][w]=="#": continue

    dist = [[INF]*W for i in range(H)]
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][0][n_w]=="#": continue
        d_n = d_v + 1
        if d_n > dist[n_h][n_w]:
          continue
        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))

      new_dist =[]
      for l in dist:
        new_dist.append([x for x in l if x < INF])
      #print(new_dist)
      LL = [max(l) if len(l)>0 else 0 for l in new_dist]
      #print(LL)
      ans = max(ans, max(LL))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h,w=map(int,input().split())
    hw=h*w
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        #row=input()
        r_append(input())
    #print(maze)
    #root=[[-1 for i in range(h*w)] for i in range(h*w)]
    root=[0]*(hw)
    ina=[0]*hw
    for i in range(hw):
        root[i]=[-1]*(hw)
        ina[i]=[i]
    
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=deque()
        tv_append=toVis.append
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                tv_append(i)
                dist[i]=dist[now]+1
        while len(toVis)>0:
            now=toVis.popleft()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    tv_append(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        #row=input()
        r_append(input())
    #print(maze)
    #root=[[-1 for i in range(h*w)] for i in range(h*w)]
    root=[0]*(h*w)
    for i in range(h*w):
        root[i]=[-1]*(h*w)
    ina=[i for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=deque()
        tv_append=toVis.append
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                tv_append(i)
                dist[i]=dist[now]+1
        while len(toVis)>0:
            now=toVis.popleft()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    tv_append(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    #root=[[-1 for i in range(h*w)] for i in range(h*w)]
    root=[0]*(h*w)
    for i in range(h*w):
        root[i]=[-1]*(h*w)
    ina=[i for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=deque()
        tv_append=toVis.append
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                tv_append(i)
                dist[i]=dist[now]+1
        while len(toVis)>0:
            now=toVis.popleft()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    tv_append(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()