Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=np.inf
#print(S)
def bfs(sx,sy,gx,gy):
  #dx, dy 四方向に対応したベクトルのリスト
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  #P: (x, y)のキュー
  P=[]
  #d: スタートから各点までの最小距離の配列
  d=np.ones((H, W))*INF
  #スタート地点をキューに入れ、その点の距離を0にする
  P.append([sx, sy])
  d[sx,sy]=0
    
  #キューがからになるまでループ
  while len(P)>0:
    #キューの先頭を取り出す
    p=P.pop(0)
    #取り出してきた状態がゴールなら探索をやめる
    if (p[0]==gx and p[1]==gy):
      break
        
    #移動四方向をループ
    for i in range(4):
      #移動した後の点をnx, nyとする
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
            
      #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
      if 0<=nx and nx<H and 0<=ny and ny<W and S[nx, ny]!="#" and d[nx, ny]==INF:
        #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  #print(d)
  return d[gx, gy]
ans=0
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="#" or S[gx,gy]=="#":
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
print(int(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 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())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

ans = []
for sy in range(1,h+1) :
  for sx in range(1+w+1):
    c = (sy-1)*w+sx
    for gy in range(c//w+1,h+1) :
      for gx in range(1,w+1) :
        if maze[sy][sx] == '#' or maze[gy][gx] == '#' :
          continue
        visited = [[-1]*(w+2) for _ in range(h+2)]
        ans.append(bfs(maze, visited, sy, sx, gy, gx))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
edge = []
S = [list(input()) for i in range(H)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] != "#" :
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return max(dist)

ans = 0
for i in range(H*W) :
    if S[i//W][i%W] != "#" :
        dist = [-1 for _ in range(H*W)]
        ans = max(ans, bfs(i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
G = [[0]*(H*W) for _ in range(H*W)]
edge = []
S = [list(input()) for i in range(H)]
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] == "#" :
        continue
    else :
        if h > 1 and S[h-1][w] == "." :
            j = (h-1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if h < H-1 and S[h+1][w] == "." :
            j = (h+1)*W + w
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w > 1 and S[h][w-1] == "." :
            j = h*W + w-1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1
        if w < W-1 and S[h][w+1] == "." :
            j = h*W + w+1
            edge.append([i, j])
            G[i][j] = G[j][i] = 1

def bfs(s) :
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for i in range(H*W) :
            if G[now][i] == 1 :
                if dist[i] != -1 :
                    continue
                else :
                    dist[i] = dist[now] + 1
                    q.append(i)
    return max(dist)

ans = 0
for i in range(H*W) :
    dist = [-1 for _ in range(H*W)]
    ans = max(ans, bfs(i))

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 < 0 or new_y >= h or new_x < 0 or new_x >= w :
        continue
      if 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 = [input() for i in range(h)]

ans = 0
for i in range(0,h) :
  for j in range(0,w):
    for k in range(0,h) :
      for l in range(0,w) :
        sy = i ; sx = j
        gy = k ; gx = l
        if maze[sy][sx] == '#' or maze[gy][gx] == '#' :
          continue
        visited = [[-1]*w for _ in range(h)]
        temp = bfs(maze, visited, sy, sx, gy, gx)
        if ans < temp :
          ans = temp

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 < 0 or new_y >= h or new_x < 0 or new_x >= w :
        continue
      if 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 = [input() for i in range(h)]

ans = []
for i in range(0,h) :
  for j in range(0,w):
    for k in range(0,h) :
      for l in range(0,w) :
        sy = i ; sx = j
        gy = k ; gx = l
        if maze[sy][sx] == '#' or maze[gy][gx] == '#' :
          continue
        visited = [[-1]*w for _ in range(h)]
        ans.append(bfs(maze, visited, sy, sx, gy, gx))

print(max(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 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())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

ans = []
for i in range(1,h+1) :
  for j in range(1+w+1):
    for k in range(1,h+1) :
      for l in range(1,w+1) :
        sy = i ; sx = j
        gy = k ; gx = l
        if maze[sy][sx] == '#' or maze[gy][gx] == '#' :
          continue
        visited = [[-1]*(w+2) for _ in range(h+2)]
        ans.append(bfs(maze, visited, sy, sx, gy, gx))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

def bfs(sy,sx,gy,gx):
    res = [[-1]*(w) for i in range(h)]
    res[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    while q:
        z = q.popleft()
        if z[0]==gy and z[1]==gx:
            break
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny = z[0] + dy
            nx = z[1] + dx
            if 0<=ny<h and 0<=nx<w and m[ny][nx]=="." and res[ny][nx]==-1:
                q.append([ny,nx])
                res[ny][nx] = res[z[0]][z[1]] + 1
    return res[gy][gx]

ans = -1
for i in range(h):
    for j in range(w):
        for ii in range(h):
            for jj in range(w):
                if i==ii and j==jj:
                    continue
                if (m[i][j]=="." and m[ii][jj]=="."):
                    xxx = bfs(i,j,ii,jj)
                    if xxx != -1:
                        if xxx > ans:
                            ans = xxx
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

def bfs(sy,sx,gy,gx):
    res = [[-1]*(w) for i in range(h)]
    res[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    while q:
        z = q.popleft()
        if z[0]==gy and z[1]==gx:
            break
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny = z[0] + dy
            nx = z[1] + dx
            if 0<=ny<h and 0<=nx<w and m[ny][nx]=="." and res[ny][nx]==-1:
                q.append([ny,nx])
                res[ny][nx] = res[z[0]][z[1]] + 1
    return res[gy][gx]

ans = []
for i in range(h):
    for j in range(w):
        for ii in range(h):
            for jj in range(w):
                if i==ii and j==jj:
                    continue
                if (m[i][j]=="." and m[ii][jj]=="."):
                    xxx = bfs(i,j,ii,jj)
                    if xxx != -1:
                        ans.append(xxx)

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
x = 0
y = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]


for _ in range(H):
    MAP.append(list(input()))

def bfs(A,B):
    que = queue.Queue()
    d = [[INF for i in range(W)] for j in range(H)]
    que.put(A)
    d[A[x]][A[y]] = 0
    
    while que:
        p = que.get()
        if p == B:
            break
        for i in range(4):
            nx = p[x] + dx[i]
            ny = p[y] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] != "#" and d[nx][ny] == INF:
                que.put([nx,ny])
                d[nx][ny] = d[p[x]][p[y]] + 1
    
    return d[B[x]][B[y]]

print(bfs([0,0],[H-1,0]),bfs([0,0],[0,W-1]),bfs([0,0],[H-1,W-1]),bfs([H-1,0],[0,W-1]),bfs([H-1,0],[H-1,W]),bfs([0,W-1],[H-1,W-1]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import queue

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

def bfs(h, w):
    q = queue.Queue()
    q.put((h, w, 0))
    f = [[False] * W for _ in range(H)]
    max_d = 0
    while q.qsize() > 0:
        h, w, d = q.get()
        f[h][w] = True
        max_d = max(max_d, d)
        for dh, dw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if h + dh >= 0 and h + dh < H and w + dw >= 0 and w + dw < W:
                if f[h+dh][w+dw] == False and m[h+dh][w+dw] == '.':
                    q.put((h+dh, w+dw, d+1))
    return max_d    

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

Submission status: Time Limit Exceeded

Solution code:
import copy
import collections
import sys


def input():
    return sys.stdin.readline()[:-1]


def bfs(sx, sy, gx, gy):
    # sx,sy := スタートの座標
    # gx,gy := ゴールの座標
    que = collections.deque()
    que.append([sx, sy])
    d = [[inf]*W for _ in range(H)]
    d[sx][sy] = 0
    s = copy.copy(field)
    while (len(que) > 0):
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and s[nx][ny] != "#" and d[nx][ny] == inf):
                que.append([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]


inf = float('inf')
H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
d = [[inf]*W for _ in range(H)]

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

cand = []
memo = []

for h1 in range(H):
    for w1 in range(W):
        if field[h1][w1] == '#':
            continue
        for h2 in range(H):
            for w2 in range(W):
                if field[h2][w2] == '#':
                    continue
                if h1 == h2 and w1 == w2:
                    continue
                cand.append([h1, w1, h2, w2])
for c in cand:
    res = bfs(*c)
    if res != float('inf'):
        memo.append(res)
print(max(memo))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
H, W = map(int, input().split())
spots = []
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
maze = []
for h in range(H):
  line = list(input())
  maze.append(line)
res = 0
for h in range(H):
  for w in range(W):
    if maze[h][w] == '.':
      newMaze = deepcopy(maze)
      # print(j, i)
      # for line in newMaze:
      #   print(line)
      # print()
      newSpots = [[h, w]]
      count = 0
      while True:
        spots = newSpots
        newSpots = []
        # print(count)
        # for line in newMaze:
        #   print(line)
        # print()
        if 0 < len(spots):
          count += 1
        else:
          break
        for pos in spots:
          newMaze[pos[0]][pos[1]] = '#'
          # if j == 5 and i == 4:
          #   for line in newMaze:
          #     print(line)
          #   print()
          for d in dirs:
            x = d[1] + pos[1]
            y = d[0] + pos[0]
            if 0 <= x < W and 0 <= y < H and newMaze[y][x] == '.':
              newSpots.append([y, x])
      if res < count:
        res = count
print(res-1)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
H, W = map(int, input().split())
spots = []
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
maze = []
for h in range(H):
  line = list(input())
  maze.append(line)
res = 0

for h in range(H):
  for w in range(W):
    if maze[h][w] == '.':
      newMaze = deepcopy(maze)
      # print(j, i)
      # for line in newMaze:
      #   print(line)
      # print()
      newSpots = [[h, w]]
      count = 0
      while True:
        spots = newSpots
        newSpots = []
        # print(count)
        # for line in newMaze:
        #   print(line)
        # print()
        if 0 < len(spots):
          count += 1
        else:
          break
        for pos in spots:
          newMaze[pos[0]][pos[1]] = '#'
          if res < count:
            res = count
          # if j == 5 and i == 4:
          #   for line in newMaze:
          #     print(line)
          #   print()
          for d in dirs:
            x = d[1] + pos[1]
            y = d[0] + pos[0]
            if 0 <= x < W and 0 <= y < H and newMaze[y][x] == '.':
              nextPos = newMaze[y][x]
              newSpots.append([y, x])
      if res < count:
        res = count
print(res-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy
def bfs(pos,map):
      while pos:
        x,y,depth=pos.popleft()
        map[x][y]="#"
        if map[x-1][y]!="#":
          pos.append([x-1,y,depth+1])
        if map[x+1][y]!="#":
          pos.append([x+1,y,depth+1])
        if map[x][y+1]!="#":
          pos.append([x,y+1,depth+1])
        if map[x][y-1]!="#":
          pos.append([x,y-1,depth+1])
      return depth
H,W=map(int,input().split())
ans=0
fence=["#"]*(W+2)
field=[fence]
for _ in range(H):
  L=list(input())
  field.append(["#"]+L+["#"])
field.append(fence)
for i in range(1,H+1):
  for j in range(1,W+1):
    if field[i][j]==".": 
      pos=deque([[i,j,0]])
      depth=bfs(pos,deepcopy(field))
      if ans<depth:
        ans=depth
print(ans)

Submission status: Time Limit Exceeded

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

def main():        
    h,w=map(int,input().split())
    s=[[]*w for _ in range(h)]
    for i in range(h):
        s[i]=list(input())
    chk=deque()
    d=[[0,1],[0,-1],[1,0],[-1,0]]

    def bfs(x,y):
        ans,dist=0,0
        a=[[-1]*w for _ in range(h)]
        chk=[(x,y,0)]
        a[x][y]=0
        while chk:
            x,y,dist=chk.pop(0)
            bx,by=x,y
            a[x][y]=dist
            for dx,dy in d:
                x=dx+bx
                y=dy+by
                if x>=0 and y>=0 and x<=h-1 and y<=w-1:
                    if s[x][y]=='.' and a[x][y]==-1:
                        chk.append((x,y,dist+1))
            ans=max(ans,dist)
        return ans
    
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            ans=max(ans,bfs(i,j))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():        
    h,w=map(int,input().split())
    s=[[]*w for _ in range(h)]
    for i in range(h):
        s[i]=list(input())
    chk=deque()
    d=[[0,1],[0,-1],[1,0],[-1,0]]

    def bfs(x,y):
        ans,dist=0,0
        a=[[-1]*w for _ in range(h)]
        chk=[(x,y,0)]
        a[x][y]=0
        while chk:
            x,y,dist=chk.pop(0)
            bx,by=x,y
            a[x][y]=dist
            for dx,dy in d:
                x=dx+bx
                y=dy+by
                if x>=0 and y>=0 and x<=h-1 and y<=w-1:
                    if s[x][y]=='.' and a[x][y]==-1:
                        chk.append([x,y,dist+1])
        ans=0
        for i in range(h):
                ans=max(ans,max(a[i]))
        return ans
    
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            ans=max(ans,bfs(i,j))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():        
    h,w=map(int,input().split())
    s=[[]*w for _ in range(h)]
    for i in range(h):
        s[i]=list(input())
    chk=deque()
    d=[[0,1],[0,-1],[1,0],[-1,0]]

    def bfs(x,y):
        ans,dist=0,0
        a=[[-1]*w for _ in range(h)]
        chk.append([x,y,0])
        a[x][y]=0
        while chk:
            x,y,dist=chk.popleft()
            bx,by=x,y
            a[x][y]=dist
            for dx,dy in d:
                x=dx+bx
                y=dy+by
                if x>=0 and y>=0 and x<=h-1 and y<=w-1:
                    if s[x][y]=='.' and a[x][y]==-1:
                        chk.append([x,y,dist+1])
        ans=0
        for i in range(h):
                ans=max(ans,max(a[i]))
        return ans
    
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            ans=max(ans,bfs(i,j))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():        
    h,w=map(int,input().split())
    s=[[]*w for _ in range(h)]
    for i in range(h):
        s[i]=list(input())
    chk=deque()
    d=[[0,1],[0,-1],[1,0],[-1,0]]

    def bfs(x,y):
        ans,dist=0,0
        a=[[-1]*w for _ in range(h)]
        chk.append([x,y,0])
        a[x][y]=0
        while chk:
            x,y,dist=chk.popleft()
            bx,by=x,y
            a[x][y]=dist
            for dx,dy in d:
                x=dx+bx
                y=dy+by
                if x>=0 and y>=0 and x<=h-1 and y<=w-1:
                    if s[x][y]=='.' and a[x][y]==-1:
                        chk.append([x,y,dist+1])
        ans=0
        for i in range(h):
            for j in range(w):
                ans=max(ans,a[i][j])
        return ans
    
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            ans=max(ans,bfs(i,j))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

N = H*W

data = ["#" * (W+2)]
for i in range(H):
  data.append("#"+input()+"#")
data.append("#" * (W+2))

offsets = [(0,1),(0,-1),(1,0),(-1,0),]

tree = {}
for i in range(1,H+1):
  for j in range(1,W+1):
    if data[i][j] != ".":
      pass
    else:
      tree[(i,j)] = []
      for o in offsets:
        i_ = i+o[0]
        j_ = j+o[1]
        if data[i_][j_] == "." :
          tree[(i,j)].append((i_,j_))

nodes = list(tree.keys())
  
FARTHEST = 0

for start_node in nodes:
  flag = set()
  # キューを作成して初期ノード(root)を入れる
  q = deque()
  q.append((start_node,0))
  farthest = None

  # キューが空になるまで繰り返す
  while len(q) > 0:
      # キューの先頭（左端）からnodeを取り出す
      data = q.popleft()
      node = data[0]
      distance = data[1]
      if node is not None:
          farthest = (node,distance)
          flag.add(node)
          childs = tree[node]
          for child in childs:
            if child not in flag:
              q.append((child,distance+1))

      if FARTHEST < farthest[1]:
        FARTHEST = farthest[1]

print(FARTHEST)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import fractions
from functools import reduce
stdin = sys.stdin

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

from collections import deque


def bfs(sx, sy, gx, gy, H, W):
    d = [[-1 for i in range(W)] for j in range(H)]

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

    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            #print(nx, ny)
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != "#" and d[ny][nx] == -1:
                que.append((ny, nx))
                #print(p[0], p[1], ny, nx)
                d[ny][nx] = d[p[0]][p[1]] + 1
    return d[gy][gx]


H, W = na()
ans = 0
maze = [input() for i in range(H)]
fin = []
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        for gy in range(H):
            for gx in range(W):
                if maze[gy][gx] == '#':
                    continue
                if (gx, gy, sx, sy) in fin:
                    continue
                else:
                    #print(sx, sy, gx, gy)
                    fin.append((sx, sy, gx, gy))
                    ans = max(ans, bfs(sx, sy, gx, gy, H, W))
                    #print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import fractions
from functools import reduce
stdin = sys.stdin

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

from collections import deque


def bfs(sx, sy, gx, gy, H, W):
    d = [[-1 for i in range(W)] for j in range(H)]

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

    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            #print(nx, ny)
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != "#" and d[ny][nx] == -1:
                que.append((ny, nx))
                #print(p[0], p[1], ny, nx)
                d[ny][nx] = d[p[0]][p[1]] + 1
    return d[gy][gx]


H, W = na()
ans = 0
maze = [input() for i in range(H)]
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        for gy in range(H):
            for gx in range(W):
                if maze[gy][gx] == '#':
                    continue
                #print(sx, sy, gx, gy)
                ans = max(ans, bfs(sx, sy, gx, gy, H, W))
                #print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx or ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall or visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = depth[x][y] + 1
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[False] * w for _ in range(h)]
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] = True

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx or ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall or visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = depth[x][y] + 1
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")

dr = np.array([[0, 1], [0, -1], [1, 0], [-1, 0]])


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        dr_i = dr + [x, y]
        for nx, ny in dr_i:
            if nx < 0 or h - 1 < nx or ny < 0 or w - 1 < ny:
                continue      
          
            if mass[nx][ny] == wall or visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = depth[x][y] + 1

    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")

dr = np.array([[0, 1], [0, -1], [1, 0], [-1, 0]])


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        dr_i = dr + [x, y]
        for nx, ny in dr_i:
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = depth[x][y] + 1

    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [[ord(i) for i in input()] for _ in range(h)]
wall = ord("#")

dr = np.array([[0, 1], [0, -1], [1, 0], [-1, 0]])


def bfs(s, t):
    if mass[s][t] == wall:
        return 0
    visited = [[False] * w for _ in range(h)]
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    visited[s][t] = True
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] = True
        for nx, ny in dr + [x, y]:
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == wall:
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = depth[x][y] + 1

    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))