Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
# H（縦マス） W（横マス）
# 3 5
# ...#.
# .#.#.
# .#...  → ループ内では S[i][j] で表す

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

S = [list(input()) for i in range(H)]
# Sは元の地図

T = [[0 for i in range(W)] for j in range(H)]
# Tはそれぞれの位置からの最大距離を示す（まず0、このあと距離を埋めていく）

for i in range(H):  
  for j in range(W):
    # このループ内で点[i][j]からの最大距離を求める
    # 0 <= i <= H-1
    # 0 <= j <= W-1
    
    if S[i][j] == "#":
      continue
    # もし点[i][j]が壁ならループを終了し次の点を調べる
    
    U = [[999 for i in range(W)] for j in range(H)]
    U[i][j] = 0
    # 点[i][j]から各点までの距離をUで表す（まず999で初期化）
    # ただし点[i][j]は0で自明
    
    queue = []
    if 0 <= i <= H-1 and 0 <= j-1 <= W-1:
      if S[i][j-1] == ".":
        queue.append([i, j-1])
    if 0 <= i <= H-1 and 0 <= j+1 <= W-1:
      if S[i][j+1] == ".":
        queue.append([i, j+1])
    if 0 <= i-1 <= H-1 and 0 <= j <= W-1:
      if S[i-1][j] == ".":
        queue.append([i-1, j])
    if 0 <= i+1 <= H-1 and 0 <= j <= W-1:
      if S[i+1][j] == ".":
        queue.append([i+1, j])
    # 最初の点の周辺をqueueに追加

    while queue != []:
      
      [qi, qj] = queue.pop(0) # queueの先頭を取得して削除

      kyori = []
      if 0 <= qi <= H-1 and 0 <= qj-1 <= W-1:
        kyori.append(U[qi][qj-1])
        if U[qi][qj-1] == 999 and S[qi][qj-1] == ".":
          queue.append([qi, qj-1])
      if 0 <= qi <= H-1 and 0 <= qj+1 <= W-1:
        kyori.append(U[qi][qj+1])
        if U[qi][qj+1] == 999 and S[qi][qj+1] == ".":
          queue.append([qi, qj+1])
      if 0 <= qi-1 <= H-1 and 0 <= qj <= W-1:
        kyori.append(U[qi-1][qj])
        if U[qi-1][qj] == 999 and S[qi-1][qj] == ".":
          queue.append([qi-1, qj])
      if 0 <= qi+1 <= H-1 and 0 <= qj <= W-1:
        kyori.append(U[qi+1][qj])
        if U[qi+1][qj] == 999 and S[qi+1][qj] == ".":
          queue.append([qi+1, qj])
      U[qi][qj] = min(kyori) + 1
      # queueの先頭から最初の点[i][j]までの距離をUに代入      
      # queueの先頭に隣接する点のうち、まだ考慮していない分をqueueに追加

    # 点[i][j]からの最大の距離をTに代入する（開始）
    for k in range(H):
      for l in range(W):
        if S[k][l] == "#":
          U[k][l] = 0
        if T[i][j] < U[k][l]:
          T[i][j] = U[k][l]
    # 点[i][j]からの最大の距離をTに代入する（終了）

# ここまででTが全て埋まる

maxkyori = 0
for i in range(H):
  for j in range(W):
    if maxkyori < T[i][j]:
      maxkyori = T[i][j]

print(maxkyori)

Submission status: Time Limit Exceeded

Solution code:
# H（縦マス） W（横マス）
# 3 5
# ...#.
# .#.#.
# .#...  → ループ内では S[i][j] で表す

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

S = [list(input()) for i in range(H)]
# Sは元の地図

T = [[0 for i in range(W)] for j in range(H)]
# Tはそれぞれの位置からの最大距離を示す（まず0、このあと距離を埋めていく）

for i in range(H):  
  for j in range(W):
    # このループ内で点[i][j]からの最大距離を求める
    # 0 <= i <= H-1
    # 0 <= j <= W-1
    
    if S[i][j] == "#":
      continue
    # もし点[i][j]が壁ならループを終了し次の点を調べる
    
    U = [[999 for i in range(W)] for j in range(H)]
    U[i][j] = 0
    # 点[i][j]から各点までの距離をUで表す（まず999で初期化）
    # ただし点[i][j]は0で自明
    
    queue = []
    if 0 <= i <= H-1 and 0 <= j-1 <= W-1:
      if S[i][j-1] == ".":
        queue.append([i, j-1])
    if 0 <= i <= H-1 and 0 <= j+1 <= W-1:
      if S[i][j+1] == ".":
        queue.append([i, j+1])
    if 0 <= i-1 <= H-1 and 0 <= j <= W-1:
      if S[i-1][j] == ".":
        queue.append([i-1, j])
    if 0 <= i+1 <= H-1 and 0 <= j <= W-1:
      if S[i+1][j] == ".":
        queue.append([i+1, j])
    # 最初の点の周辺をqueueに追加

    while queue != []:
      
      [qi, qj] = queue.pop(0) # queueの先頭を取得して削除

      kyori = []
      if 0 <= qi <= H-1 and 0 <= qj-1 <= W-1:
        kyori.append(U[qi][qj-1])
      if 0 <= qi <= H-1 and 0 <= qj+1 <= W-1:
        kyori.append(U[qi][qj+1])
      if 0 <= qi-1 <= H-1 and 0 <= qj <= W-1:
        kyori.append(U[qi-1][qj])
      if 0 <= qi+1 <= H-1 and 0 <= qj <= W-1:
        kyori.append(U[qi+1][qj])
      U[qi][qj] = min(kyori) + 1
      # queueの先頭から最初の点[i][j]までの距離をUに代入
      
      if 0 <= qi <= H-1 and 0 <= qj-1 <= W-1:
        if U[qi][qj-1] == 999 and S[qi][qj-1] == ".":
          queue.append([qi, qj-1])
      if 0 <= qi <= H-1 and 0 <= qj+1 <= W-1:
        if U[qi][qj+1] == 999 and S[qi][qj+1] == ".":
          queue.append([qi, qj+1])
      if 0 <= qi-1 <= H-1 and 0 <= qj <= W-1:
        if U[qi-1][qj] == 999 and S[qi-1][qj] == ".":
          queue.append([qi-1, qj])
      if 0 <= qi+1 <= H-1 and 0 <= qj <= W-1:
        if U[qi+1][qj] == 999 and S[qi+1][qj] == ".":
          queue.append([qi+1, qj])
      # queueの先頭に隣接する点のうち、まだ考慮していない分をqueueに追加

    # 点[i][j]からの最大の距離をTに代入する（開始）
    for k in range(H):
      for l in range(W):
        if S[k][l] == "#":
          U[k][l] = 0
        if T[i][j] < U[k][l]:
          T[i][j] = U[k][l]
    # 点[i][j]からの最大の距離をTに代入する（終了）

# ここまででTが全て埋まる

maxkyori = 0
for i in range(H):
  for j in range(W):
    if maxkyori < T[i][j]:
      maxkyori = T[i][j]

print(maxkyori)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def BFS(x,y):
    dist = 1
    visited = deque()
    visited.append((x,y))
    destination = deque()
    search = [(1,0),(-1,0),(0,1),(0,-1)]
    for (dx,dy) in search:
        if maze[y+dy][x+dx] == ".":
            destination.append((x+dx,y+dy))
    same_dist = len(destination)
    moved = 0
    x = destination[0][0]
    y = destination[0][1]
    while destination:
        visited.append((x,y))
        destination.popleft()
        for (dx,dy) in search:
            if maze[y+dy][x+dx] == ".":
                if (x+dx,y+dy) not in destination and (x+dx,y+dy) not in visited:
                    destination.append((x+dx,y+dy))
        if len(destination) >= 1:
            x = destination[0][0]
            y = destination[0][1]
            moved += 1
            if moved == same_dist:
                dist += 1
                moved = 0
                same_dist = len(destination)
    return dist

H,W = map(int,input().split())
maze = [list("#"*(W+2))] + [list("#" + input() + "#") for i in range(H)] + [list("#"*(W+2))]
ans = 0

for y in range(1,H+1):
    for x in range(1,W+1):
        if maze[y][x] == ".":
            ans = max(ans,BFS(x,y))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import queue
inf = 1000
di = [-1,0,1,0]
dj = [0,-1,0,1]
ans = 0
def update(i,j,x,f):
    if f[i][j] != inf:
        f[i][j] = x
h,w = [int(x) for x in input().split(" ")]
field = []
for i in range(h):
    field.append(input())
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            continue
        q = queue.Queue()
        f = [[inf for k in range(w)] for l in range(h)]
        q.put([i,j])
        while not q.empty():
            i2,j2 = q.get()
            for m in range(4):
                ni=i2+di[m]
                nj=j2+dj[m]
                if ni<0 or ni>=h or nj<0 or nj>=w:
                    continue
                update(ni,nj,1,f)
                q.put([ni,nj])
        for i in range(h):
            for j in range(w):
                ans = max(ans, f[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def bfs(cells, x, y):
    ops = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    h = len(cells)
    w = len(cells[0])
    q = [(x, y, 0)]
    result = 0
    passed = set()
    while q:
        x, y, val = q.pop(0)
        passed.add((x, y))
        for dx, dy in ops:
            new_x, new_y, new_val = x + dx, y + dy, val + 1
            if ((new_x, new_y) in passed or not 0 <= new_x <= w - 1
                    or not 0 <= new_y <= h - 1 or cells[new_y][new_x] == '#'):
                continue
            result = max(result, new_val)
            q.append((new_x, new_y, val + 1))
    return result


def main():
    """
    1. 適当なルートをスタート地点として最短距離を求める。
    2. 1のルートで通ったセルを覗いて別の道から最短距離を求める
    3. 2の途中で1.で通ったセルに出会ったらそこで探索を中断し、1の結果を足す。
    """

    h, w = map(int, input().split(' '))
    cells = []
    for _ in range(h):
        row = list(input())
        cells.append(row)

    m = 0
    for y, row in enumerate(cells):
        for x, cell in enumerate(row):
            if cell == '.':
                m = max(m, bfs(cells, x, y))
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
    #print(xytuple)
  return mlength


#X = str(input()).split()
HW = str(input()).split()
H = int(HW[0])
W = int(HW[1])
S = [[0 for i in range(W)] for j in range(H)]
# SS = [[INF]*(W*H)]*(W*H)
mlength = 0


for i in range(H):
  temp = str(input())
  for j in range(W):
    #print(i,j)
    S[i][j]=temp[j]


for i in range(H):
  for j in range(W):
    if(S[i][j] != "#"):
      TS = copy.deepcopy(S)
      mlength = max(mlength, bfs(TS, i, j, H, W))
    #print(S)

print(mlength);

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
import Queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = Queue.Queue()
  xytuple = (x, y, 0)
  q.put(xytuple)


  while not q.empty():
    xytuple = q.get()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in xrange(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        mlength = max(mlength, xytuple[2] +1)
        q.put(temptuple)
  
  return mlength


#X = str(raw_input()).split()
HW = str(raw_input()).split()
H = int(HW[0])
W = int(HW[1])
S = [[0 for i in xrange(W)] for j in xrange(H)]
# SS = [[INF]*(W*H)]*(W*H)
mlength = 0


for i in xrange(H):
  temp = str(raw_input())
  for j in xrange(W):
    #print(i,j)
    S[i][j]=temp[j]


for i in xrange(H):
  for j in xrange(W):
    if(S[i][j] != "#"):
      TS = copy.deepcopy(S)
      mlength = max(mlength, bfs(TS, i, j, H, W))
    # print(S)

print(mlength);

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 1000000000
h,w = map(int, input().split())
maze = [list(input()) for _ in range(h)]

def bfs(sx, sy, gx, gy):
    ds = [[1,0], [-1,0], [0,1], [0,-1]]
    visited = [[False for _ in range(h)] for _ in range(w)]
    distance = [[INF for _ in range(h)] for _ in range(w)]
    q = deque([[sx, sy]])
    distance[sx][sy] = 0

    while q:
        x, y = q.popleft()
        if visited[x][y]: continue
        visited[x][y] = True
        #print('-----', x, y)
        for dx, dy in ds:
            nx = x+dx
            ny = y+dy
            if (nx >= 0) and (nx <= w-1) and (ny >= 0) and (ny <= h-1):
                #print(nx, ny)
                if maze[ny][nx] != '#':
                    q.append([nx, ny])
                    distance[nx][ny] = min(distance[nx][ny], distance[x][y] + 1)
    return distance[gx][gy]

count = 0
for s_x in range(w):
    for s_y in range(h):
        if maze[s_y][s_x] == '.':
            for g_x in range(w):
                for g_y in range(h):
                    if (maze[g_y][g_x] == '.' and ((s_x != g_x) or (s_y != g_y))):
                        #print(s_x, s_y, g_x, g_y)
                        ans = bfs(s_x, s_y, g_x, g_y)
                        #print(ans)
                        if ans != INF and ans > count:
                            count = ans

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=[int(i) for i in input().split()]
# c=[[i for i in input().split()] for _ in range(h)]
C=list(input() for _ in range(H))
C=list(list(i) for i in C) #visited_listを用いずに壁にしていく方法ではリスト化が必要

def bfs(maze,s1,s2,g1,g2):
    for y in range(H):
        for x in range(W):
            if maze[y][x]!='#':
                maze[y][x]=10**9

    maze[s1][s2]=0
    que=deque([[s1,s2]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if nexty >= 0 and nexty < H and nextx >= 0 and nextx < W:
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    return maze[g1][g2]

ans=0
for s1,c_w in enumerate(C):
    for s2,c in enumerate(c_w):
        if C[s1][s2]!="#":
            for g1,c_w in enumerate(C):
                for g2,c in enumerate(c_w):
                    if C[g1][g2]!="#":
                        temp=bfs(C,s1,s2,g1,g2)
                        ans=max(temp,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
''' 
INF = float('inf')
MOD = 10 ** 9 + 7
'''
## ここは１つにまとめれる
# dy = (0, -1, 0, 1)
# dx = (1, 0, -1, 0)
d=[(1,0),(0,1),(-1,0),(0,-1)]

    
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for _ in range(H)]
        if M[i][j] == '.':
            Ma = 0
            q.append((i, j))
            dist[i][j] = 0
            while q:
                cx,cy = q.popleft()
                for nx,ny in d:
                    x ,y= cx+nx,cy+ny
                    ''' ここの処理がをnotにしてわかりやすく
                    if x<0 or y<0 or x>=H or y>=W or dist[x][y]>0:
                        continue
                    '''
                    '''
                    if 0<= x < H and 0<= y < W and dist[x][y]<=0:
                    '''
                    if 0<= x < H and 0<= y < W and M[x][y] == ".":
                        dist[x][y]=dist[cx][cy]+1
                        Ma = max(Ma,dist[x][y])
                        q.append((x,y))
            Max_list.append(Ma)

print(max(Max_list))

Submission status: Time Limit Exceeded

Solution code:
import queue

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

que = queue.Queue()
class stgo:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.depth = 0
y_dist = (0, 0, -1, +1)
x_dist = (-1, +1, 0, 0)
g_y = 0
g_x = 0

def bfs():
    dist = [[-1] * (w) for i in range(h)]
    maxdepth = 0
    while not que.empty():
        now = que.get()
        y = now.y
        x = now.x
        depth = now.depth
        dist[now.y][now.x] = depth
        maxdepth = max(maxdepth, depth)

        for z in range(4):
            next = stgo()
            next.y = y + y_dist[z]
            next.x = x + x_dist[z]
            next.depth = depth + 1

            if next.y >= 0 and next.y <= h - 1 and next.x >= 0 and next.x <= w - 1 and s[next.y][next.x] == "." and dist[next.y][next.x] == -1:
                que.put(next)
    return maxdepth

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            start = stgo()
            start.x = j
            start.y = i
            start.depth = 0
            que.put(start)
            ans = max(ans,bfs())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
sys.setrecursionlimit(1000000)

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

que = queue.Queue()
class stgo:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.depth = 0
y_dist = (0, 0, -1, +1)
x_dist = (-1, +1, 0, 0)
g_y = 0
g_x = 0

def bfs():
    dist = [[-1] * (w) for i in range(h)]
    maxdepth = 0
    while not que.empty():
        now = que.get()
        y = now.y
        x = now.x
        depth = now.depth
        dist[now.y][now.x] = depth
        maxdepth = max(maxdepth, depth)

        for z in range(4):
            next = stgo()
            next.y = y + y_dist[z]
            next.x = x + x_dist[z]
            next.depth = depth + 1

            if next.y >= 0 and next.y <= h - 1 and next.x >= 0 and next.x <= w - 1 and s[next.y][next.x] == "." and dist[next.y][next.x] == -1:
                que.put(next)
    return maxdepth

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            start = stgo()
            start.x = j
            start.y = i
            start.depth = 0
            que.put(start)
            ans = max(ans,bfs())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
sys.setrecursionlimit(1000000)

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

que = queue.Queue()
class stgo:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.depth = 0
y_dist = (0, 0, -1, +1)
x_dist = (-1, +1, 0, 0)
g_y = 0
g_x = 0

def bfs():
    dist = [[-1] * (w) for i in range(h)]
    maxdepth = 0
    while not que.empty():
        now = que.get()
        y = now.y
        x = now.x
        depth = now.depth
        dist[now.y][now.x] = depth
        maxdepth = max(maxdepth, depth)

        for z in range(4):
            next = stgo()
            next.y = y + y_dist[z]
            next.x = x + x_dist[z]
            next.depth = depth + 1

            if next.y >= 0 and next.y <= h - 1 and next.x >= 0 and next.x <= w - 1 and s[next.y][next.x] == "." and dist[next.y][next.x] == -1:
                que.put(next)
    return maxdepth

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            start = stgo()
            start.x = j
            start.y = i
            start.depth = 0
            que.put(start)
            ans = max(ans,bfs())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
import sys
sys.setrecursionlimit(1000000)

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

que = queue.Queue()
class stgo:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.depth = 0
y_dist = (0, 0, -1, +1)
x_dist = (-1, +1, 0, 0)
g_y = 0
g_x = 0

def bfs():
    dist = copy.deepcopy(s)
    maxdepth = 0
    while not que.empty():
        now = que.get()
        y = now.y
        x = now.x
        depth = now.depth
        dist[y][x] = depth

        for z in range(4):
            next = stgo()
            next.y = y + y_dist[z]
            next.x = x + x_dist[z]
            next.depth = depth + 1

            if next.y >= 0 and next.y <= h - 1 and next.x >= 0 and next.x <= w - 1 and dist[next.y][next.x] == "." and dist[next.y][next.x] != "#":
                que.put(next)
        maxdepth = max(dist[y][x],maxdepth)
    return maxdepth

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            start = stgo()
            start.x = j
            start.y = i
            start.depth = 0
            que.put(start)
            ans = max(ans,bfs())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(n, d):
    for i in range(n):
        di = d[i]
        for j in range(n):
            dj = d[j]
            for k in range(n):
                t = dj[i] + di[k]
                if t < dj[k]:
                    dj[k] = t


INF = float('inf')

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

N = H * W
d = [[INF] * N for _ in range(N)]
for k in range(N):
    d[k][k] = 0

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        if y - 1 >= 0 and S[y - 1][x] != '#':
            d[y * W + x][(y - 1) * W + x] = 1
        if y + 1 < H and S[y + 1][x] != '#':
            d[y * W + x][(y + 1) * W + x] = 1
        if x - 1 >= 0 and S[y][x - 1] != '#':
            d[y * W + x][y * W + x - 1] = 1
        if x + 1 < W and S[y][x + 1] != '#':
            d[y * W + x][y * W + x + 1] = 1

warshall_floyd(N, d)

result = 0 
for i in range(N):
    for j in range(N):
        if d[i][j] != INF and d[i][j] > result:
            result = d[i][j]

print(result)

Submission status: Time Limit Exceeded

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

def BFS(a,b,atlas):
  times = 0
  queue = [[a, b]]
  old_queue = []
  while True:
    new_queue = []
    changed = False
    for x, y in queue:
      if x+1 < H:
        if atlas[x+1][y] != "#" and not [x+1, y] in old_queue:
          new_queue.append([x+1, y])
          old_queue.append([x+1, y])
          changed = True
      if x-1 >= 0:
        if atlas[x-1][y] != "#" and not [x-1, y] in old_queue:
          new_queue.append([x-1, y])
          old_queue.append([x-1, y])
          changed = True
      if y+1 < W:
        if atlas[x][y+1] != "#" and not [x, y+1] in old_queue:
          new_queue.append([x, y+1])
          old_queue.append([x, y+1])
          changed = True
      if y-1 >= 0:
        if atlas[x][y-1] != "#" and not [x, y-1] in old_queue:
          new_queue.append([x, y-1])
          old_queue.append([x, y-1])
          changed = True
    queue = new_queue
    if not changed:
      continue
    times += 1
  return times
 
TIMES = 0
for j in range(H):
  for k in range(W):
    if Atlas[j][k] == "#":
      continue
    new_TIMES = BFS(j, k, Atlas)
    if new_TIMES > TIMES:
      TIMES = new_TIMES
      
print(TIMES)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

h, w = list(map(int, input().split()))
s = []
for i in range(h):
    s.append(input().strip())

ans = 0
for i in range(h):
    for j in range(w):
        start = s[i][j]
        if start == "#":
            continue
        else:
            visited = [[False for _ in range(w)] for _ in range(h)]
            visited[i][j] = True
            queue = Queue()
            queue.put((i, j, 0))

            while 0 < queue.qsize():
                now = queue.get()
                visited[now[0]][now[1]] = True
                ans = max(ans, now[2])

                if (now[0] <= (h - 2)) and (s[now[0] + 1][now[1]] == ".") and not visited[now[0] + 1][now[1]]:
                    queue.put(((now[0] + 1), now[1], (now[2] + 1)))
                if (now[1] <= (w - 2)) and (s[now[0]][now[1] + 1] == ".") and not visited[now[0]][now[1] + 1]:
                    queue.put((now[0], (now[1] + 1), (now[2] + 1)))
                if (1 <= now[0]) and (s[now[0] - 1][now[1]] == ".") and not visited[now[0] - 1][now[1]]:
                    queue.put(((now[0] - 1), now[1], (now[2] + 1)))
                if (1 <= now[1]) and (s[now[0]][now[1] - 1] == ".") and not visited[now[0]][now[1] - 1]:
                    queue.put((now[0], (now[1] - 1), (now[2] + 1)))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

h, w = list(map(int, input().split()))
s = []
for i in range(h):
    s.append(input().strip())

ans = 0
for i in range(h):
    for j in range(w):
        start = s[i][j]
        if start == "#":
            continue
        else:
            visited = [[False for k in range(w)] for l in range(h)]
            queue = Queue()
            queue.put((i, j, 0))

            while 0 < queue.qsize():
                now = queue.get()
                visited[now[0]][now[1]] = True
                ans = max(ans, now[2])

                if (now[0] <= (h - 2)):
                    if (s[now[0] + 1][now[1]] == ".") and not visited[now[0] + 1][now[1]]:
                        queue.put(((now[0] + 1), now[1], (now[2] + 1)))
                if (now[1] <= (w - 2)):
                    if (s[now[0]][now[1] + 1] == ".") and not visited[now[0]][now[1] + 1]:
                        queue.put((now[0], (now[1] + 1), (now[2] + 1)))
                if (1 <= now[0]):
                    if (s[now[0] - 1][now[1]] == ".") and not visited[now[0] - 1][now[1]]:
                        queue.put(((now[0] - 1), now[1], (now[2] + 1)))
                if (1 <= now[1]):
                    if (s[now[0]][now[1] - 1] == ".") and not visited[now[0]][now[1] - 1]:
                        queue.put((now[0], (now[1] - 1), (now[2] + 1)))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 7
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque()
    q.append((i,j))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] < dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

def main():
    anss = 0
    for i in range(h+2):
        for j in range(w+2):
            if A[i][j] == "#":
                continue
            anss = max(anss,bfs(i,j))
    print(anss)
            
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque()
    q.append((i,j))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] < dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

def main():
    anss = 0
    for i in range(h+2):
        for j in range(w+2):
            if A[i][j] == "#":
                continue
            anss = max(anss,bfs(i,j))
    print(anss)
            
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque([[i,j]])
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] < dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append([hh+k,ww+l])

    return ans

def main():
    anss = 0
    for i in range(h+2):
        for j in range(w+2):
            if A[i][j] == "#":
                continue
            anss = max(anss,bfs(i,j))
    print(anss)
            
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque([[i,j]])
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] < dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            q.append([hh+k,ww+l])
    ans = 0
    for k in range(h+2):
        for l in range(w+2):
            if dist[k][l] == inf:
                continue
            ans = max(ans,dist[k][l])

    return ans

def main():
    anss = 0
    for i in range(h+2):
        for j in range(w+2):
            if A[i][j] == "#":
                continue
            anss = max(anss,bfs(i,j))
    print(anss)
            
main()