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: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            continue
        else:
            dist=[[inf for _ in range(w)] for _ in range(h)]
            dist[i][j]=0
            que=deque([(i,j)])
            while que:
                si,sj=que.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<h and 0<=nj<w and S[ni][nj]!="#":
                        if dist[ni][nj]>dist[si][sj]+1:
                            dist[ni][nj]=dist[si][sj]+1
                            ans=max(ans,dist[si][sj]+1)
                            que.append((ni,nj))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0

for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            continue
        else:
            dist=[[inf for _ in range(w)] for _ in range(h)]
            dist[i][j]=0
            que=deque([(i,j)])
            while que:
                si,sj=que.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<=h-1 and 0<=nj<=w-1 and S[ni][nj]!="#":
                        if dist[ni][nj]>dist[si][sj]+1:
                            dist[ni][nj]=dist[si][sj]+1
                            ans=max(ans,dist[si][sj]+1)
                            que.append((ni,nj))

print(ans)

Submission status: Accepted

Solution code:
# 自力実装（Numpy使用）
import numpy as np
H, W = map(int, input().split())

M = np.ones((H+2,W+2),dtype=int)
for i in range(H):
  s = input()
  for j in range(W):
    M[i+1,j+1] = int(s[j] == "#")

ans = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if M[i,j] == 1:
      continue
    Q = [(i,j)]
    dist = np.ones_like(M,dtype=int)*(-1)
    dist[i,j] = 0
    while len(Q) > 0:
      x,y = Q.pop(0)
      for k,l in [(1,0),(-1,0),(0,1),(0,-1),]:
        if M[x+k,y+l] == 0 and dist[x+k,y+l] == -1:
          Q.append((x+k,y+l))
          dist[x+k,y+l] = 1 + dist[x,y]
    ans.append(dist.max())
    
print(max(ans))

Submission status: Accepted

Solution code:
import queue
import copy

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

def dist(m, x1, y1):
    q = queue.Queue()
    q.put((x1, y1, 0))
    checked=[[False for _ in range(w)] for __ in range(h)]
    checked[y1][x1] = True
    while not q.empty():
        x, y, count = q.get()
        if x > 0 and m[y][x-1] == "." and checked[y][x-1] == False:
            checked[y][x-1] = True
            q.put((x-1, y, count+1))
        if y > 0 and m[y-1][x] == "." and checked[y-1][x] == False:
            checked[y-1][x] = True
            q.put((x, y-1, count+1))
        if x < w-1 and m[y][x+1] == "." and checked[y][x+1] == False:
            checked[y][x+1] = True
            q.put((x+1, y, count+1))
        if y < h-1 and m[y+1][x] == "." and checked[y+1][x] == False:
            checked[y+1][x] = True
            q.put((x, y+1, count+1))
    return count

ans = 0
for i in range(h):
    for j in range(w):
        if l[i][j] == ".":
            ans = max(ans, dist(l, j, i))
print(ans)

Submission status: Accepted

Solution code:
h, w = [int(i) for i in input().split(' ')]

m = []
for i in range(h):
    m.append(input())

def valid(d):
    global h, w
    return 0 <= d[0] and d[0] < h and 0 <= d[1] and d[1] < w

def bfs(i, j):
    global m
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    index = 0
    q = [(i, j)]
    v = {(i, j): 0}
    while index < len(q):
        item = q[index]
        for d in dirs:
            new_item = (d[0] + item[0], d[1] + item[1])
            if valid(new_item) and m[new_item[0]][new_item[1]] == '.' and new_item not in v:
                v[new_item] = v[item] + 1
                q.append(new_item)
        index += 1
    return max(v.values())

answer = 0

for i in range(h):
    for j in range(w):
        if m[i][j] == '.':
            answer = max(answer, bfs(i, j))

print(answer)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
H+=2
W+=2
s="#"*W
for _ in range(H-2):
    s+="#"+input()+"#"
s+="#"*W

answer=[]

for i in range(W*H):
    if s[i]=="#":
        continue
    dist=[-1]*(W*H)
    q=deque([i])
    dist[i]=0
    while len(q)>0:
        x=q.popleft()
        for j in [-1,1,W,-W]:
            if s[x+j]=="." and dist[x+j]==-1:
                q.append(x+j)
                dist[x+j]=1+dist[x]
    answer.append(max(dist))
print(max(answer))

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
direc = [(-1,0), (0,-1), (1,0), (0,1)]
ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue

        dist = [[-1] * W for i in range(H)]
        dist[y][x] = 0
        que = deque([[y,x]])
        while que:
            nh, nw = que.pop()
            for dh, dw in direc:
                if nh + dh < 0 or nh + dh >= H:
                    continue
                elif nw + dw < 0 or nw + dw >= W:
                    continue
                elif S[nh + dh][nw + dw] == '#':
                    continue
                elif dist[nh + dh][nw + dw] != -1:
                    continue
                else:
                    dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                    que.appendleft([nh + dh, nw + dw])
        ans = max(ans, max([max(d) for d in dist]))
print(ans)

Submission status: Accepted

Solution code:
import collections

h, w = map(int, input().split())
s = [[""]*(w+2)]
for _ in range(h):
    _s = list(input())
    _s.insert(0, "")
    _s.append("")
    s.append(_s)
s.append([""]*(w+2))

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

ans = 0

for _h in range(1, h+1):
    for _w in range(1, w+1):
        if s[_h][_w] == "#":
            continue

        q = collections.deque([[_h, _w]])

        a = [[-1]*(w+2) for _ in range(h+2)]
        a[_h][_w] = 0

        while 0 < len(q):
            cx, cy = q.pop()
            for _dx, _dy in zip(dx, dy):
                x = cx + _dx
                y = cy + _dy

                if s[x][y] == "." and a[x][y] == -1:
                    a[x][y] = a[cx][cy] + 1
                    q.appendleft([x, y])

        for _a in a:
            ans = max(ans, max(_a))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
H += 2
W += 2
maze = '#' * W
for _ in range(H-2):
  maze += '#' + input() + '#'
maze += '#' * W
 
def bfs(root):
  if maze[root] == '#':
    return -1
  dist = [-1] * (H*W)
  dist[root] = 0
  q = deque([root])
  while q:
    x = q.popleft()
    for d in [1, -1, W, -W]:
      if maze[x+d] == '.' and dist[x+d] == -1:
        q.append(x+d)
        dist[x+d] = dist[x] + 1
  return max(dist)
 
ans = max(bfs(i) for i in range(H*W))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [[0 if c == '#' else 1 for c in input()] for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == 0:
            continue
        costs = [[-1 for _ in range(w)] for _ in range(h)]
        costs[i][j] = 0
        q = deque([(i, j)])
        while q:
            y, x = q.popleft()
            for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                nx, ny = x + dx, y + dy
                if (0 <= nx < w) and (0 <= ny < h) and maze[ny][nx] and costs[ny][nx] == -1:
                    costs[ny][nx] = costs[y][x] + 1
                    q.append((ny, nx))
        for row in costs:
            ans = max(ans, max(row))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

def bfs(s,x, y):
    
    INF=400
    DX = [1, 0, -1, 0]
    DY = [0, 1, 0, -1]
    
    que = deque()
    res = 0
    dist = [[INF for _ in range(W)] for _ in range(H)]
 
    que.append((x, y))
    dist[x][y] = 0
    while que:
        x, y = que.pop()
        res = max(res, dist[x][y])
 
        for i in range(4):
            dx, dy = x + DX[i], y + DY[i]
 
            if dx < 0 or dx >= H or dy < 0 or dy >= W:
                continue
            if s[dx][dy] == "#":
                continue
 
            if dist[dx][dy] == INF:
                dist[dx][dy] = dist[x][y] + 1
                que.appendleft((dx, dy))
    return res

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

S = [list(input()) for _ in range(H)]

ans = 0
for x, y in product(range(H), range(W)):
  if S[x][y] == "#":
    continue
  ans = max(ans, bfs(S,x, y))
print(ans)

Submission status: Accepted

Solution code:
def main(h,w,s):
    maxStep = 0
    #開始地点を全探索
    for y in range(h):
        for x in range(w):
            #壁ならスキップ
            if s[y][x] == "#":
                continue
            #道ならBFSを実行し、最大値を更新
            else:
                st = [x,y]
                maxStep = max(maxStep, bfs(st,h,w,s))
    return maxStep

#stからBFSを行い、最大ステップ数を返す
def bfs(st,h,w,s):
    #初期化
    maxStep = 0
    seen = [[-1]*w for _ in range(h)]
    seen[st[1]][st[0]] = 0
    todo = [st]
    mov = [(1,0),(-1,0),(0,1),(0,-1)]
    #キューが空でない限り処理
    while len(todo) > 0:
        #キューから値を取り出す
        x,y = todo.pop(0)
        #上下左右の探索
        for m in mov:
            nx = x + m[0]
            ny = y + m[1]
            #範囲外(地図の外)ならスキップ
            if nx < 0 or (w-1) < nx or ny < 0 or (h-1) < ny:
                continue
            #未探索かつ道ならキューに追加しステップ数更新
            if seen[ny][nx] == -1 and s[ny][nx] == ".":
                todo.append([nx,ny])
                seen[ny][nx] = seen[y][x] + 1
                maxStep = max(maxStep, seen[ny][nx])
    return maxStep

h,w = map(int,input().split())
s = list(list(input()) for _ in range(h))
print(main(h,w,s))

Submission status: Accepted

Solution code:
import itertools

import copy
    
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
ab.append(list('#'*w))
mx = 0

for i in range(h):
    for j in range(w):
        if ab[i][j] == '.':
            dp = [[0 for a in range(w)] for b in range(h)]
            step = [[i, j]]

            while len(step) > 0:
                y, x = step.pop(0)
                if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
                    step.append([y+1, x])
                    dp[y+1][x] = dp[y][x] + 1
                if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
                    step.append([y, x+1])
                    dp[y][x+1] = dp[y][x] + 1
                if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
                    step.append([y-1, x])
                    dp[y-1][x] = dp[y][x] + 1
                if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
                    step.append([y, x-1])
                    dp[y][x-1] = dp[y][x] + 1
            dp[i][j] = 0
            mx = max([mx, max(list(itertools.chain.from_iterable(dp)))])

print(mx)

Submission status: Accepted

Solution code:
import sys
import socket
from heapq import heappush, heappop

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('d2.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def dijkstra(a, s):
  i0, j0 = s

  debug = i0 == 1 and j0 == 2

  H = len(a)
  W = len(a[0])
  inf = 1000
  d = [[inf]*W for i in range(H)]
  d[i0][j0] = 0
  q = []
  item = (0, i0, j0)
  heappush(q, item)
  for i in range(H):
    for j in range(W):
      if a[i][j] == '#':
        continue
      v = 0 if (i, j) == s else inf
      item = (v, i, j)
      # heappush(q, item)
  
  # print('q:', q)

  while q != []:
    v, i, j = heappop(q)
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
    for k in range(4):
      ii = i + di[k]
      jj = j + dj[k]
      if not (0 <= ii < H and 0 <= jj < W):
        continue
      if a[ii][jj] == '#':
        continue
      
      # if debug:
      #   print(' ', i, j, ii, jj, d, d[i][j] + 1, d[ii][jj])

      if d[i][j] + 1 < d[ii][jj]:
        d[ii][jj] = d[i][j] + 1
        item = (d[i][j] + 1, ii, jj)
        heappush(q, item)
      # print('  ',  d[ii][jj])  
  return d


def main():
    H, W = read_int_list()
    a = [read_str() for i in range(H)]
    res = 0
    for i in range(H):
      for j in range(W):
        if a[i][j] == '#':
          continue
        s = (i, j)
        d = dijkstra(a, s)
        
        # print('  d:', d)
        # break

        for k in range(H):
          for l in range(W):
            if a[k][l] == '#':
              continue
            if d[k][l] > res:
              res = d[k][l]

    print(res)


def bfs(a, s):
  i0, j0 = s
  H = len(a)
  W = len(a[0])
  inf = 1000
  d = [[inf]*W for i in range(H)]
  d[i0][j0] = 0

  state = [[0] * W for i in range(H)]
  q = []
  q.append(s)
  state[i0][j0] = 1
  while q != []:
    u = q.pop(0)
    i, j = u
    state[i][j] = 2
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
    for k in range(4):
      ii = i + di[k]
      jj = j + dj[k]
      if not (0 <= ii < H and 0 <= jj < W):
        continue
      if a[ii][jj] == '#':
        continue

      # if d[i][j] + 1 < d[ii][jj]:
      if state[ii][jj] == 0:
        d[ii][jj] = d[i][j] + 1
        q.append((ii, jj))
        state[ii][jj] = 1


  return d


def main2():
    H, W = read_int_list()
    a = [read_str() for i in range(H)]
    res = 0
    for i in range(H):
      for j in range(W):
        if a[i][j] == '#':
          continue
        s = (i, j)
        d = bfs(a, s)
        
        # print('  d:', d)
        # break

        for k in range(H):
          for l in range(W):
            if a[k][l] == '#':
              continue
            if d[k][l] > res:
              res = d[k][l]

    print(res)

main2()

Submission status: Accepted

Solution code:
import sys
import socket
from heapq import heappush, heappop

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def dijkstra(a, s):
  i0, j0 = s

  debug = i0 == 1 and j0 == 2

  H = len(a)
  W = len(a[0])
  inf = 1000
  d = [[inf]*W for i in range(H)]
  d[i0][j0] = 0
  q = []
  item = (0, i0, j0)
  heappush(q, item)
  for i in range(H):
    for j in range(W):
      if a[i][j] == '#':
        continue
      v = 0 if (i, j) == s else inf
      item = (v, i, j)
      # heappush(q, item)
  
  # print('q:', q)

  while q != []:
    v, i, j = heappop(q)
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
    for k in range(4):
      ii = i + di[k]
      jj = j + dj[k]
      if not (0 <= ii < H and 0 <= jj < W):
        continue
      if a[ii][jj] == '#':
        continue
      
      # if debug:
      #   print(' ', i, j, ii, jj, d, d[i][j] + 1, d[ii][jj])

      if d[i][j] + 1 < d[ii][jj]:
        d[ii][jj] = d[i][j] + 1
        item = (d[i][j] + 1, ii, jj)
        heappush(q, item)
      # print('  ',  d[ii][jj])  
  return d


def main():
    H, W = read_int_list()
    a = [read_str() for i in range(H)]
    res = 0
    for i in range(H):
      for j in range(W):
        if a[i][j] == '#':
          continue
        s = (i, j)
        d = dijkstra(a, s)
        
        # print('  d:', d)
        # break

        for k in range(H):
          for l in range(W):
            if a[k][l] == '#':
              continue
            if d[k][l] > res:
              res = d[k][l]

    print(res)


main()

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from collections import deque

def solve(x,y):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    start = [x, y]
    dist = [[10**3]*w for i in range(h)]
    dist[y][x] = 0
    Q = deque()
    Q.append(start)
    mx = 0

    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==10**3:
                    Q.append([nx, ny])
                    dist[ny][nx] = dist[p[1]][p[0]] + 1
                    if mx < dist[ny][nx]:
                        mx=dist[ny][nx]
    return mx

ans=0
for i in range(h):
    for j in range(w):
        if l[i][j]=="#":
            continue

        res=solve(j,i)
        if res > ans:
            ans=res

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(x, y):
    Max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    start = [x, y]
    distance = [[41]*W for i in range(H)]
    distance[y][x] = 0
    Q = deque()
    Q.append(start)

    while len(Q) != 0:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            
            if 0 <= nx < W and 0 <= ny < H:
                if Maze[ny][nx]=="." and distance[ny][nx]==41:
                    Q.append([nx, ny])
                    distance[ny][nx] = distance[p[1]][p[0]] + 1
    
    for i in range(H):
        for j in range(W):
            if distance[i][j]!=41 and  distance[i][j] > Max:
                Max = distance[i][j]
    return Max

H, W = map(int, input().split())
Maze = [None]*H
for i in range(H):
    Maze[i] = list(input())

MaxDistance = 0
for i in range(H):
    for j in range(W):
        if Maze[i][j] == ".":
            d = bfs(j, i)
            if d > MaxDistance:
                MaxDistance = d


print(MaxDistance)

Submission status: Accepted

Solution code:
def clear_maze(sx, sy, maze):

    INF=-10**9
    global cnt
    cnt=0
    distance = [[INF for i in range(w+1)] for j in range(h+1)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        global cnt
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]


                if (0 <= nx and  0 <= ny  and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))

                    distance[nx][ny] = distance[x][y] + 1
                    if cnt<distance[nx][ny]:
                        cnt=distance[nx][ny]
        return cnt
    return bfs()


h,w = map(int, input().split())
maze=[list(input()) for i in range(h)]
t=[[0]*w for i in range(h)]

for i in range(h):
    maze[i]=['#']+maze[i]+['#']
maze=[['#' for i in range(w+2)]]+maze+[['#' for i in range(w+2)]]

ans=0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if maze[i][j] == '#':
            continue
        v = (clear_maze(i, j, maze))

        if ans <= v:
            ans = v
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import chain

H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
max_d = 400


def bfs(start):
    queue = deque()
    queue.append(start)

    distance = [[max_d] * W for _ in range(H)]
    sx, sy = start
    distance[sx][sy] = 0

    while len(queue) > 0:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if nx >= 0 and nx < H and ny >= 0 and ny < W and maze[nx][ny] == '.' and distance[nx][ny] == max_d:
                queue.append((nx, ny))
                distance[nx][ny] = distance[x][y] + 1

    return max(filter(lambda d: d != max_d, chain.from_iterable(distance)))


ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            ans = max(ans, bfs((i, j)))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs(sty, stx):
    visited = [[-1]*W for _ in range(H)]
    q = deque()
    visited[sty][stx] = 0
    q.append((sty, stx, 0))


    def is_ok(y, x):
        if not 0 <= y <= H - 1:
            return False
        if not 0 <= x <= W - 1:
            return False
        if visited[y][x] != -1:
            return False
        if maze[y][x] == '#':
            return False
        return True


    while q:
        y, x, lv = q.popleft()
        for i in (-1, 1):
            if is_ok(y+i, x):
                visited[y+i][x] = lv+1
                q.append((y+i, x, lv+1))
            if is_ok(y, x+i):
                visited[y][x+i] = lv + 1
                q.append((y, x+i, lv+1))

    return max(max(r) for r in visited)

res = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            res = max(res, bfs(i, j))

print(res)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import chain
h, w = (int(x) for x in input().split())
s = []
for _ in range(h):
    s.append(list(input()))
dx = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        d = [[0] * w for i in range(h)]
        for k, sh in enumerate(s):
            for l, sw in enumerate(sh):
                if sw == '#':
                    d[k][l] = -1
                else:
                    d[k][l] = float('inf')
        que = deque()
        que.append([i, j])
        d[i][j] = 0
        while len(que) > 0:
            qx, qy = que.popleft()
            for x, y in dx:
                nx, ny = qx + x, qy + y
                if 0 <= nx and nx < h and 0 <= ny and ny < w and d[nx][ny] == float('inf'):
                    que.append([nx, ny]) 
                    d[nx][ny] = d[qx][qy] + 1
        ans.append(max(chain.from_iterable(d)))
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
c = [input() for _ in range(h)]
ans = -1

def bfs(sx, sy):
    que = deque([[sy, sx]])
    d = [[-1] * w for _ in range(h)]
    d[sy][sx] = 0
    res = 0
    while que:
        y, x = que.popleft()
        res = max(res, d[y][x])
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            nx, ny = x+i, y+j
            if 0 <= nx and nx < w and 0 <= ny and ny < h and d[ny][nx] == -1 and c[ny][nx] != "#":
                nx_, ny_ = nx-i, ny-j
                d[ny][nx] = d[ny_][nx_] + 1
                que.append([ny, nx])
    return res

for i_ in range(h):
    for j_ in range(w):
        if c[i_][j_] != "#":
            ans = max(ans, bfs( j_, i_))

print(ans)

Submission status: Accepted

Solution code:
def get_neighbors(S, i):
    n = []
    if S[i]:
        if i >= W: #First row
            if S[i-W]:
                n += [i-W]
        if i < (H-1)*W:
            if S[i+W]:
                n += [i+W]
        if i % W > 0:
            if S[i-1]:
                n += [i-1]
        if i % W < W-1:
            if S[i+1]:
                n += [i+1]
    return n

import numpy as np
H, W = map(int, raw_input().split())
S = np.empty(H*W, bool)

for i in xrange(H):
    S[i*W:(i+1)*W] = map(lambda x: x==".", raw_input())
    
NR = sum(S) # Number of road cube
NE = [] # The neighbors
for i in xrange(H*W):
    NE += [get_neighbors(S, i)]

M = np.zeros([H*W, H*W], int)
# init
for i,n in enumerate(NE):
    for j in n:
        M[i,j] = 1
        
# find road
I = np.sum(M != 0)
Count = 2

while I < NR *NR:
    a = []
    for i,n in enumerate(NE):
        for j in n:
            a = np.logical_and(M[i] == 0, M[j] == Count-1)
            M[i][a] = Count
    I = np.sum(M != 0)
    Count += 1

np.fill_diagonal(M, 0)
print(M.max())

Submission status: Accepted

Solution code:
H,W = [int(i) for i in input().split()]
maze = [list(input()) for _ in range(H)]
dica = [[-1] * W for _ in range(H)]
import collections
from collections import deque
import numpy as np
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = -1
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            dic = [k[:] for k in dica]
            que = deque()
            que.append([i,j])
            dic[i][j] = 0
            while len(que) != 0:
                k = que.popleft()
                x = k[0]
                y = k[1]
                for l in range(4):
                    nx = x + dx[l]
                    ny = y + dy[l]
                    if nx < 0 or ny < 0 or nx >= H or ny >= W:
                        continue
                    if maze[nx][ny] == "#":
                        continue
                    if dic[nx][ny] != -1:
                        continue
                    dic[nx][ny] = dic[x][y] + 1
                    que.append([nx,ny])
            arr = np.array(dic)
            M = np.amax(arr)
            if M > ans:
                ans = M
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
l = []
for i in range(h):
    s = list(input())
    l.append(s)
q = deque()
s = [[1,0],[0,1],[-1,0],[0,-1]]
def aaa(i,j,h,w):
    if i >= 0 and i <= h-1 and j >= 0 and j <= w-1:
        return True
    else:
        return False
ans = []
for i in range(h):
    for j in range(w):
        if l[i][j] == ".":
            rl = [[-1 for i in range(w)] for j in range(h)]
            rl[i][j] = 0
            q.append([i,j])
            while len(q) > 0:
                a,b = deque.popleft(q)
                for x in s:
                    if aaa(a+x[0],b+x[1],h,w):
                        if l[a+x[0]][b+x[1]] == ".":
                            if rl[a+x[0]][b+x[1]] >= 0:
                                rl[a+x[0]][b+x[1]] = min(rl[a+x[0]][b+x[1]],rl[a][b]+1)
                            else:
                                rl[a+x[0]][b+x[1]] = rl[a][b]+1
                                q.append([a+x[0],b+x[1]])
            for y in range(h):
                ans.append(max(rl[y]))
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product


#幅優先探索
def bfs(s,x, y):
    
    INF=400
    #周囲の探索に必要
    DX = [1, 0, -1, 0]
    DY = [0, 1, 0, -1]
    
    que = deque() #キュー（配列と同じ：前後からの取り出しの高速化が可能）
    res = 0
    dist = [[INF for _ in range(W)] for _ in range(H)]
 
    que.append((x, y))
    dist[x][y] = 0
    while que:
        x, y = que.pop()
        res = max(res, dist[x][y])
 
        for i in range(4):
            dx, dy = x + DX[i], y + DY[i]
 
            if dx < 0 or dx >= H or dy < 0 or dy >= W:
                continue
            if s[dx][dy] == "#":
                continue
 
            if dist[dx][dy] == 400:
                dist[dx][dy] = dist[x][y] + 1
                que.appendleft((dx, dy))
    return res
 
if __name__=="__main__":
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]


    #全部のスタート地点でbfsを行い、その時の最大を取得
    #product　デカルト積　二つの配列の全ての組み合わせを返す
    ans = 0
    for x, y in product(range(H), range(W)):
        if S[x][y] == "#":
            continue
        ans = max(ans, bfs(S,x, y))
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

move=((1,0),(-1,0),(0,1),(0,-1))

def bfs(i,j): # 幅優先探索、マス i,j から始まる時の最長経路
    if S[i][j] == '#': # そのマスが壁ならスタート地点にならないのでパス
        return 0
    
    visited=[[0]*w for _ in range(h)] # 探索済のリスト
    visited[i][j]=1 # 最初のマスは探索済へ
    
    que=deque([(i,j,0)]) # キューの作成（queueは待ち行列）
    
    while len(que)>0:
        ci,cj,d = que.popleft() #キューの左側から取り出してキューから削除

        for mi,mj in move: #moveで定義したそれぞれの動きについて
            ni,nj = ci+mi,cj+mj # 移動先の座標をni,njとしている。
            if 0 <= ni < h and 0 <= nj < w and visited[ni][nj]==0:
                if S[ni][nj] == '.':
                    visited[ni][nj] = 1
                    que.append((ni, nj, d+1))
    return d
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int,input().split())
maze = []
ans = 0
dy_dx = [[0,1],[1,0],[0,-1],[-1,0]]
for i in range(h):
    maze.append(input())
flag = True
check = '.'*w
for i in range(h):
    if maze[i] != check:
        flag = False
        break
if flag:
    print(h+w-2)
else:
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                ne = deque([[i,j]])
                dist = [[0]*w for k in range(h)]
                checked = [[0]*w for k in range(h)]
                while len(ne) != 0:
                    cur = ne.popleft()
                    checked[cur[0]][cur[1]] = 1
                    for l in range(4):
                        t = cur[0]+dy_dx[l][0]
                        u = cur[1]+dy_dx[l][1]
                        if (0 <= t <= h-1) and (0 <= u <= w-1):
                            if checked[t][u] == 0:
                                if maze[t][u] == '.':
                                    dist[t][u] = dist[cur[0]][cur[1]]+1
                                    ne.append([t,u])
                                    ans = max(ans,dist[t][u])
    print(ans)