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:
# 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)]
    f[h][w] = True
    max_d = 0
    while q.qsize() > 0:
        h, w, d = q.get()
        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))
                    f[h+dh][w+dw] = True
    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: Accepted

Solution code:
import copy
import collections
import sys


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


def bfs(sx, sy):
    # 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()
        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  # d[gx][gy]


inf = -1
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
        cand.append([h1, w1])
for c in cand:
    res = bfs(*c)
    memo.append(max(sum(res, [])))
print(max(memo))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from queue import Queue
h, w = map(int, input().split())
s = [input() for _ in range(h)]

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

ans = 0
for sx in range(h):
    for sy in range(w):
        if s[sx][sy] == "#":
            continue

        q = Queue()
        q.put((sx, sy))
        dist = [[10 ** 9] * w for _ in range(h)]
        dist[sx][sy] = 0
        while not q.empty():
            cx, cy = q.get()
            for k in range(4):
                tx = cx + dx[k]
                ty = cy + dy[k]
                if not (0 <= tx < h and 0 <= ty < w and s[tx][ty] == "."):
                    continue
                if dist[tx][ty] > dist[cx][cy] + 1:
                    dist[tx][ty] = dist[cx][cy] + 1
                    q.put((tx, ty))

        for tx in range(h):
            for ty in range(w):
                if s[tx][ty] == ".":
                    ans = max(ans, dist[tx][ty])

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

M = [str(input()) for _ in range(h)]
M = ['#'*w] + M + ['#'*w]
M = ['#'+c+'#' for c in M]

from collections import deque
ans = 0
for sy in range(1, h+1):
    for sx in range(1, w+1):
        if M[sy][sx] == '#':
            continue
        q = deque()
        q.append((sy, sx))
        visit = [[-1]*(w+2) for _ in range(h+2)]
        visit[sy][sx] = 0
        while q:
            y, x = q.popleft()
            for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
                ny, nx = y+dy, x+dx
                if visit[ny][nx] == -1 and M[ny][nx] != '#':
                    visit[ny][nx] = visit[y][x]+1
                    q.append((ny, nx))
        ans = max(ans, max(max(row) for row in visit))
print(ans)

Submission status: Accepted

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

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

def max_distance(i,j):
    not_visit = [[-1]*W for i in range(H)]
    not_visit[i][j] = 0
    stack = [(i,j)]

    while stack != []:
        y,x = stack.pop(0)
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and S[y+dy[i]][x+dx[i]] != "#" and not_visit[y+dy[i]][x+dx[i]] == -1:
                not_visit[y+dy[i]][x+dx[i]] =  not_visit[y][x] + 1
                stack.append((y+dy[i],x+dx[i]))
    
    return not_visit[y][x]

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            ans = max(ans,max_distance(i,j))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
INF = 1000000

def bfs(sx, sy):
    reached = [[INF for _ in range(w)] for _ in range(h)]
    reached[sx][sy] = 0
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    d = deque()
    d.append([sx, sy])

    while d:
        x, y = d.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx > h - 1 or ny < 0 or ny > w - 1 or  maze[nx][ny] == "#" or reached[nx][ny] != INF:
                continue
            d.append([nx, ny])
            reached[nx][ny] = reached[x][y] + 1
    gl = 0
    for i in range(h):
        for j in range(w):
            if reached[i][j] != INF:
                gl = max(gl, reached[i][j])
    return gl
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:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = ''.join(['#']*(W+2))
S[-1] = ''.join(['#']*(W+2))
for i in range(1,H+1):
  S[i] = '#'+input()+'#'

maxd = 0
import queue
dy = [1,0,-1,0]
dx = [0,1,0,-1]
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]=='.':
      visited = [[False]*(W+2) for _ in range(H+2)]
      q = queue.Queue()
      visited[h][w] = True
      q.put([h,w,0])
      while not q.empty():
        a,b,c = q.get()
        #print(a,b,c)
        for i in range(4):
          y,x = a+dy[i], b+dx[i]
          if S[y][x]=='.' and visited[y][x]==False:
            q.put([y,x,c+1])
            visited[y][x]=True
      maxd = max(maxd,c)
print(maxd)

Submission status: Accepted

Solution code:
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
 
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
  for w in range(W):
    if maze[h][w]=='#':
      numcount+=1
      n+=1
      continue
    if h>0 and maze[h-1][w]=='.':
      edge[n].add(n-W)
    if h<H-1 and maze[h+1][w]=='.':
      edge[n].add(n+W)
    if w>0 and maze[h][w-1]=='.':
      edge[n].add(n-1)
    if w<W-1 and maze[h][w+1]=='.':
      edge[n].add(n+1)
    n+=1

def dfs(start):
  reach=[start]
  distance=[-1 for _ in range(H*W)]
  distance[n]=0
  while reach:
    _from=reach.pop(0)
    for _to in edge[_from]:
      if not(_to in reach) and distance[_to]==-1:
        reach.append(_to)
        distance[_to]=distance[_from]+1
  return(max(distance))
 
n=0
ans=set()
for h in range(H):
  for w in range(W):
    if maze[h][w]=='.':
      ans.add(dfs(n))
    n+=1
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
 
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
 
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
  for w in range(W):
    if maze[h][w]=='#':
      numcount+=1
      n+=1
      continue
    if h>0 and maze[h-1][w]=='.':
      edge[n].add(n-W)
    if h<H-1 and maze[h+1][w]=='.':
      edge[n].add(n+W)
    if w>0 and maze[h][w-1]=='.':
      edge[n].add(n-1)
    if w<W-1 and maze[h][w+1]=='.':
      edge[n].add(n+1)
    n+=1

def dfs(start):
  reach=deque([start])
  distance=[-1 for _ in range(H*W)]
  distance[n]=0
  while reach:
    _from=reach.popleft()
    for _to in edge[_from]:
      if not(_to in reach) and distance[_to]==-1:
        reach.append(_to)
        distance[_to]=distance[_from]+1
  return(max(distance))
 
n=0
ans=set()
for h in range(H):
  for w in range(W):
    if maze[h][w]=='.':
      ans.add(dfs(n))
    n+=1
print(max(ans))

Submission status: Accepted

Solution code:
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]

point=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
  for w in range(W):
    if maze[h][w]=='#':
      numcount+=1
      n+=1
      continue
    if h>0 and maze[h-1][w]=='.':
      point[n].add(n-W)
    if h<H-1 and maze[h+1][w]=='.':
      point[n].add(n+W)
    if w>0 and maze[h][w-1]=='.':
      point[n].add(n-1)
    if w<W-1 and maze[h][w+1]=='.':
      point[n].add(n+1)
    n+=1

def dfs(num):
  reach=[num]
  check=[-1 for _ in range(H*W)]
  check[num]=0
  while reach:
    v=reach.pop(0)
    for e in point[v]:
      if not(e in reach) and check[e]==-1:
        reach.append(e)
        check[e]=check[v]+1
  return(max(check))

n=0
ans=set()
for h in range(H):
  for w in range(W):
    if maze[h][w]=='.':
      ans.add(dfs(n))
    n+=1
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int,input().split())
s = [input() for _ in range(h)]
result = []
for xx in range(h):
    for yy in range(w):
        if s[xx][yy]==".":
            visit = [[-1 for _ in range(w)] for __ in range(h)]
            visit[xx][yy] = 0

            q = deque([[xx,yy]])
            while q:
                x, y = q.popleft()
                for i in [-1, 1]:
                    if 0 <= x+i and x+i < h:
                        if s[x+i][y] != "#" and visit[x+i][y] < 0:
                            visit[x+i][y] = visit[x][y]+1
                            q.append([x+i, y])
                    if 0 <= y+i and y+i < w:
                        if s[x][y+i] != "#" and visit[x][y+i] < 0:
                            visit[x][y+i] = visit[x][y]+1
                            q.append([x, y+i])
            result.append(max([max(i) for i in visit]))
print(max(result))

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
h, w = map(int,input().split())
s = [input() for _ in range(h)]
result = []
for xx in range(h):
    for yy in range(w):
        if s[xx][yy]==".":
            visit = np.array([np.array([-1 for _ in range(w)]) for __ in range(h)])
            visit[xx][yy] = 0

            q = deque([[xx,yy]])
            while q:
                x, y = q.popleft()
                for i in [-1, 1]:
                    if 0 <= x+i and x+i < h:
                        if s[x+i][y] != "#" and visit[x+i][y] < 0:
                            visit[x+i][y] = visit[x][y]+1
                            q.append([x+i, y])
                    if 0 <= y+i and y+i < w:
                        if s[x][y+i] != "#" and visit[x][y+i] < 0:
                            visit[x][y+i] = visit[x][y]+1
                            q.append([x, y+i])
            result.append(max(visit.flatten()))
print(max(result))

Submission status: Accepted

Solution code:
from collections import deque

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


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

#print(maze)

def bfs(x,y):
    seen = [[False for _ in range(w)] for _ in range(h)]
    dist = [[False for _ in range(w)] for _ in range(h)]
    
    if(maze[y][x] == "#"):
        return [[0]]
    
    dist[y][x] = 0
    d = deque()
    d.append(x + w*y)
    #print(d)
    while d:
        #print(d)
        base = d.popleft()
        #print(base)
        xx = base%w
        yy = base//w
        #print(*seen,sep='\n')
        #print("-------")
        if(seen[yy][xx] == True):
            continue
        else:
            seen[yy][xx] = True
        
        for px,py in [(-1,0),(1,0),(0,-1),(0,1)]:
            #print(xx+px,yy+py)
            if (0<= xx+px < w and 0<= yy+py < h):
                if(maze[yy+py][xx+px] == "." and seen[yy+py][xx+px] == False):
                    d.append(xx+px+(yy+py)*w)
                    dist[yy+py][xx+px] = dist[yy][xx] + 1
    
    return dist

#result = bfs(0,2)  

#print(*result,sep ="\n")
ans = 0
for j in range(h):
    for k in range(w):
        res = 0
        result = bfs(k,j)
        for i in result:
            res = max(max(i),res)
        ans = max(ans,res)
        


print(ans)

Submission status: Accepted

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)
      newMaze[h][w] = '#'
      # 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:
          # 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] == '.':
              newMaze[y][x] = '#'
              newSpots.append([y, x])
      if res < count:
        res = count
print(res-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
ans = 0

def bfs(sx, sy):
    INF = 1000000
    reached = [[INF for _ in range(w)] for _ in range(h)]
    reached[sx][sy] = 0
    d = deque()
    d.append([sx, sy])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while d:
        x, y = d.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if next_x < 0 or next_x > h - 1 or next_y < 0 or next_y > w - 1:
                continue
            if maze[next_x][next_y] == "#":
                continue
            if reached[next_x][next_y] != INF:
                continue
            d.append([next_x, next_y])
            reached[next_x][next_y] = reached[x][y] + 1
    gl = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                gl = max(gl, reached[i][j])    
    return gl

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            res = bfs(i, j)
            ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
import copy
h, w = map(int, input().split())
field = []

for i in range(h):
    field.append(list(input()))

d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = 0

for start_y in range(h):
    for start_x in range(w):
        if field[start_y][start_x] == "#":
            continue

        new_field = copy.deepcopy(field)
        next_pos = [(start_y, start_x)]
        cnt = 0
        new_field[start_y][start_x] = 0
        
        while True:
            next_pos_cand = []
            cnt += 1
            for y, x in next_pos:
                for dy, dx in d:
                    if 0 <= y + dy < h and 0 <= x + dx < w:
                        if new_field[y + dy][x + dx] == ".":
                            next_pos_cand.append((y + dy, x + dx))
                            new_field[y + dy][x + dx] = cnt
            next_pos = next_pos_cand

            if len(next_pos) == 0:
                ans = max(ans, cnt - 1)
                break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy
 
def bfs(pos,map):
      while pos:
        x,y,depth=pos.popleft()
        if map[x][y]=="#":
            continue
        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: Accepted

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

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

    def bfs(x,y):
        dist=[[-1]*w  for _ in range(h)]
        seen=[[False]*w for _ in range(h)]
        stk=[(x,y,0)]
        while stk:
            px,py,dst=stk.pop(0)
            if seen[px][py]:
                continue
            seen[px][py]=True
            
            if s[px][py]=='#':
                dist[px][py]=0
                continue
            
            for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
                if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                    continue
                else:
                    stk.append((px+x,py+y,dst+1))
            dist[px][py]=dst
        ans=0
    
        for i in range(h):
            ans=max(max(dist[i]),ans)
        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: Accepted

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



H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
que = deque()
ans  = -1
for sx in range(W):
    for sy in range(H): # スタート地点のループ
        if C[sy][sx]  == "#":
            continue
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        que.append((sy,sx))
        dist[sy][sx] = 0
        while que:
            y,x = que.popleft()
            for temp in go:
                gx,gy = temp
                nx = x + gx
                ny = y + gy
                if 0<= nx < W and 0<= ny < H and C[ny][nx] != "#":
                    if dist[ny][nx] == -1: # ここの更新にminはいらない(幅優先なので自明に最短距離を進む)
                        dist[ny][nx] = dist[y][x] + 1
                        que.append( (ny,nx))
        for temp in dist:
            cand = max(temp)
            ans = max(ans,cand)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
H,W = [int(x) for x in stdin.readline().rstrip().split()]
grid = [input() for i in range(H)]

visited = [[False for i in range(W)] for i in range(H)]
visit_p = deque()
ans = 0

for h,i in enumerate(grid):
    for w, j in enumerate(i):
        if j != "#":
            visited[h][w] = True
            visit_p.append((h, w, 0))
        while visit_p:
            nh,nw,num = visit_p.popleft()
            
            for dh,dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                if not (0 <= nh+dh < H) or not (0 <= nw+dw < W):
                    # 範囲外
                    continue

                if visited[nh+dh][nw+dw] or grid[nh+dh][nw+dw] == '#':
                    # 壁または訪問済み
                    continue

                visit_p.append((nh+dh,nw+dw,num+1))
                visited[nh+dh][nw+dw] = True
                ans = max(ans,num+1)
        visited = [[False for i in range(W)] for i in range(H)]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
H,W = [int(x) for x in stdin.readline().rstrip().split()]
grid = [input() for i in range(H)]

visited = [[False for i in range(W)] for i in range(H)]
visit_p = deque()
ans = 0

search_p = []
for h,i in enumerate(grid):
    for w, j in enumerate(i):
        if j != "#":
            search_p.append((h, w, 0))

for p in search_p:
    visited[p[0]][p[1]] = True
    visit_p.append(p)
    while visit_p:
        nh,nw,num = visit_p.popleft()

        for dh,dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            if not (0 <= nh+dh < H) or not (0 <= nw+dw < W):
                # 範囲外
                continue

            if visited[nh+dh][nw+dw] or grid[nh+dh][nw+dw] == '#':
                # 壁または訪問済み
                continue

            visit_p.append((nh+dh,nw+dw,num+1))
            visited[nh+dh][nw+dw] = True
            ans = max(ans,num+1)
    visited = [[False for i in range(W)] for i in range(H)]
print(ans)

Submission status: Accepted

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:
  d = [[9999999]*(W+2) for _ in range(H+2)]
  # キューを作成して初期ノード(root)を入れる
  q = deque()
  q.append(start_node)
  d[start_node[0]][start_node[1]] = 0
  res = 0 

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

Submission status: Accepted

Solution code:
from collections import deque

INF = float("inf")

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),]

nodes = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if data[i][j] == ".":
      nodes.append((i,j))

FARTHEST = 0

for start_node in nodes:
  i = start_node[0]
  j = start_node[1]
  d = [[INF]*(W+2) for i in range(H+2)]
  d[i][j] = 0
  q = deque([(i,j)])
  res = 0
  while q:
    x,y = q.popleft()
    nd = d[x][y]+1
    for o in offsets:
      nx, ny = x+o[0], y+o[1]
      if data[nx][ny] == "#":
        continue
      if nd < d[nx][ny]:
        d[nx][ny] = nd
        q.append((nx,ny))
        res = nd
  if res > FARTHEST:
    FARTHEST = res

print(FARTHEST)

Submission status: Accepted

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

from collections import deque

H,W = map(int,readline().split())
H += 2; W += 2
grid = '#' * W
for _ in range(H-2):
    grid += '#' + readline().rstrip().decode() + '#'
grid += '#' * W


def bfs(start):
    inf = 10**9
    dist = [inf] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1,1,W,-W):
            w = v + move
            if grid[w] == '#':
                continue
            if dist[w] > dv + 1:
                dist[w] = dv + 1
                q.append(w)
    return max(x for x in dist if x != inf)


print(max(bfs(v) for v in range(H*W) if grid[v] != '#'))

Submission status: Accepted

Solution code:
# .....
# ..#.#
# ..#..
from collections import deque

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

point=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
  for w in range(W):
    if maze[h][w]=='#':
      numcount+=1
      n+=1
      continue
    if h>0 and maze[h-1][w]=='.':
      point[n].add(n-W)
    if h<H-1 and maze[h+1][w]=='.':
      point[n].add(n+W)
    if w>0 and maze[h][w-1]=='.':
      point[n].add(n-1)
    if w<W-1 and maze[h][w+1]=='.':
      point[n].add(n+1)
    n+=1
#print(point)
def dfs(n):
  reach=deque([n])
  check=[-1 for _ in range(H*W)]
  check[n]=0
  while reach:
    v=reach.popleft()
    for e in point[v]:
      if not(e in reach) and check[e]==-1:
        reach.append(e)
        check[e]=check[v]+1
  return(max(check))

n=0
ans=set()
for h in range(H):
  for w in range(W):
    if maze[h][w]=='.':
      ans.add(dfs(n))
    n+=1
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
s = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]
ans = 0

for y in range(1, H+1):
    for x in range(1, W+1):
        if s[y][x] == '#':
            continue
        visited = [[0]*(W+2) for _ in range(H+2)]
        visited[y][x] = 1
        max_s = 0
        dq = deque([(y, x, 0)])

        while dq:
            cy, cx, steps = dq.popleft()
            if steps > max_s:
                max_s = steps
            steps += 1

            for dy, dx in ((cy+1, cx), (cy-1, cx), (cy, cx+1), (cy, cx-1)):
                if s[dy][dx] == '#' or visited[dy][dx]:
                    continue
                visited[dy][dx] = 1
                dq.append((dy, dx, steps))

        ans = max(ans, max_s)

print(ans)

Submission status: Accepted

Solution code:
import math 
import bisect
import heapq
from collections import deque

h,w=map(int,input().split())
M=[]
M=[input() for _ in range(h)]
 
def bfs(x,y):
    dist=[[-1]*w  for _ in range(h)]
    seen=[[False]*w for _ in range(h)]
    stk=[(x,y,0)]
    while stk:
        px,py,dst=stk.pop(0)
        if seen[px][py]:
            continue
        seen[px][py]=True
        
        if M[px][py]=='#':
            dist[px][py]=0
            continue
        
        for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
            if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                continue
            else:
                stk.append((px+x,py+y,dst+1))
        dist[px][py]=dst
    ans=0
 
    for i in range(h):
        ans=max(max(dist[i]),ans)
    return ans
ans = 0
for i in range(h):
    for j in range(w):
        if M[i][j]=='#':
            continue
        ans=max(bfs(i,j),ans)
print(ans)

Submission status: Accepted

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("#")


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:
        i = q1.popleft()
        j = q2.popleft()
        r = depth[i][j] + 1
        if j != w - 1:
            if mass[i][j + 1] != wall and not visited[i][j + 1]:
                q1.append(i)
                q2.append(j+1)
                visited[i][j + 1] = True
                depth[i][j + 1] += r
        if j != 0:
            if mass[i][j - 1] != wall and not visited[i][j - 1]:
                q1.append(i)
                q2.append(j - 1)
                visited[i][j - 1] = True
                depth[i][j - 1] += r
        if i != 0:
            if mass[i - 1][j] != wall and not visited[i - 1][j]:
                q1.append(i-1)
                q2.append(j)
                visited[i - 1][j] = True
                depth[i - 1][j] += r
        if i != h - 1:
            if mass[i + 1][j] != wall and not visited[i + 1][j]:
                q1.append(i + 1)
                q2.append(j)
                visited[i + 1][j] = True
                depth[i + 1][j] += r
    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: Accepted

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])
    visited[s][t] = True
    while q1:
        i = q1.popleft()
        j = q2.popleft()
        r = depth[i][j] + 1
        if j != w - 1:
            if mass[i][j + 1] != wall and not visited[i][j + 1]:
                q1.append(i)
                q2.append(j+1)
                visited[i][j + 1] = True
                depth[i][j + 1] += r
        if j != 0:
            if mass[i][j - 1] != wall and not visited[i][j - 1]:
                q1.append(i)
                q2.append(j - 1)
                visited[i][j - 1] = True
                depth[i][j - 1] += r
        if i != 0:
            if mass[i - 1][j] != wall and not visited[i - 1][j]:
                q1.append(i-1)
                q2.append(j)
                visited[i - 1][j] = True
                depth[i - 1][j] += r
        if i != h - 1:
            if mass[i + 1][j] != wall and not visited[i + 1][j]:
                q1.append(i + 1)
                q2.append(j)
                visited[i + 1][j] = True
                depth[i + 1][j] += r
    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: Accepted

Solution code:
h,w=map(int,input().split())
M=[]


M=[input() for _ in range(h)]

def bfs(x,y):
    dist=[[-1]*w  for _ in range(h)]
    seen=[[False]*w for _ in range(h)]
    stk=[(x,y,0)]
    while stk:
        px,py,dst=stk.pop(0)
        if seen[px][py]:
            continue
        seen[px][py]=True
        
        if M[px][py]=='#':
            dist[px][py]=0
            continue
        
        for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
            if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                continue
            else:
                stk.append((px+x,py+y,dst+1))
        dist[px][py]=dst
    ans=0

    for i in range(h):
        ans=max(max(dist[i]),ans)
    return ans

ans=0
for i in range(h):
    for j in range(w):
        if M[i][j]=='#':
            continue
        ans=max(bfs(i,j),ans)

print(ans)