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()))
maze = ['#' * (w + 2)] + ['#{}#'.format(input()) for i in range(h)] + ['#' * (w + 2)]
directions = [[0, -1], [-1, 0], [1, 0], [0, 1]]
queue = deque()
answer = 0

for start_x in range(1, h + 1):
    for start_y in range(1, w + 1):
        if maze[start_x][start_y] == '.':
            distance = [[-1] * (w + 2) for i in range(h + 2)]
            distance[start_x][start_y] = 0
            queue.append([start_x, start_y])
            while queue:
                x, y = queue.popleft()
                for direction in directions:
                    next_x, next_y = x + direction[0], y + direction[1]
                    if maze[next_x][next_y] == '.' and distance[next_x][next_y] == -1:
                        distance[next_x][next_y] = distance[x][y] + 1
                        queue.append([next_x, next_y])
                        answer = max(answer, distance[next_x][next_y])

print(answer)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, sy, sx):
    visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    dist = 0
    
    while queue:
        y, x = queue.popleft()
        for j, k in ([1,0], [-1,0], [0,1], [0,-1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                dist = max(dist, visited[new_y][new_x])
    return(dist)

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

ans=0

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
# stdin = open("testdata.txt", "r")

def input():
	return stdin.readline().strip()

from collections import defaultdict, deque

R, C = map(int, input().split())

grid = [None]*R

for i in range(R):
	temp = input()
	grid[i] = temp

def get_neighs(r, c):
	is_valid = lambda x, y: 0 <= x < R and 0 <= y < C and grid[x][y]=='.'
	dr = [-1, 0, 1, 0]
	dc = [0, 1, 0, -1]
	return [(r+dr[i], c+dc[i]) for i in range(4) if is_valid(r+dr[i], c+dc[i])]


def get_max(r0, c0):
	visited = {(r0, c0),}
	dq = deque()
	dq.append((r0, c0, 0))
	max_steps = 0
	while dq:
		r, c, steps = dq.popleft()
		max_steps = max(max_steps, steps)
		for _r, _c in get_neighs(r, c):
			if (_r, _c) not in visited:
				dq.append((_r, _c, steps+1))
				visited.add((_r, _c))
	return max_steps

ans = 0
for r in range(R):
	for c in range(C):
		if grid[r][c]=='.':
			ans = max(get_max(r, c), ans)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def bfs(que):
  if len(que) > 0:
    nh, nw = que[0]
    que.pop(0)
    for dh, dw in directions:
      ##枠外
      if not ((0 <= nh+dh < H)and(0 <= nw+dw < W)):
        continue
      ##壁
      if G[nh+dh][nw+dw] == '#':
      	continue
   	  ##探索済み
      if dist[nh+dh][nw+dw] != -1:
      	continue
      dist[nh+dh][nw+dw] = dist[nh][nw]+1
      que.append([nh+dh, nw+dw])
    nh += dh
    nw += dw
    bfs(que)

    
      
ans_list = []
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]
directions = [[0,1],[1,0],[0,-1],[-1,0]] #right, down, left, up

for nh in range(H):
  for nw in range(W):
    if G[nh][nw] == '#':
      continue
    dist = [[-1] * W for i in range(H)]
    que = [[nh,nw]] # start pos in this tine
    dist[nh][nw] = 0
    bfs(que)
    ans = np.max(dist)
    ans_list.append(ans)
      
print(max(ans_list))

Submission status: Accepted

Solution code:
from collections import deque


def find_farthest(adj, start):
    distance = [float("inf")] * len(adj)
    q = deque([(start, 0)])
    while len(q):
        cur, d = q.popleft()
        if distance[cur] <= d:
            continue
        distance[cur] = d
        for nxt in adj[cur]:
            if distance[nxt] > d+1:
                q.append((nxt, d+1))
    ret = 0
    for i, d in enumerate(distance):
        if d != float("inf"):
            ret = max(ret, d)
    return ret


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    adj = [set() for _ in range(H*W)]
    start = None
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                continue
            if i >= 1 and S[i-1][j] == ".":
                adj[i*W+j].add((i-1)*W+j)
                adj[(i-1)*W+j].add(i*W+j)
            if j >= 1 and S[i][j-1] == ".":
                adj[i*W+j].add(i*W+(j-1))
                adj[i*W+(j-1)].add(i*W+j)
            start = i*W+j
    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                ans = max(ans, find_farthest(adj, i*W+j))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

h, w = map(int, input().split())
s = ["#{}#".format(input()) for _ in range(h)]
h += 2
w += 2

s = ["#" * w] + s + ["#" * w]

# 最終的な最大値
res_opt = -2

# 各ループ開始
for h_i in range(h):
  for w_i in range(w):
    if s[h_i][w_i] != '#':
      # BFS開始
      visited = [ [-1] * w for _ in range(h) ]
      visited[h_i][w_i] = 0
      queue = deque([(h_i, w_i)])
      
      while queue:
        y, x = queue.popleft()
        
        # 上下4マスに対して
        opt = 0
        for i in range(4):
          
          dx, dy = dis_x[i], dis_y[i]
          if s[y+dy][x+dx] == '.' and visited[y+dy][x+dx] == -1:
            visited[y+dy][x+dx] = visited[y][x] + 1
            opt = max(opt, visited[y+dy][x+dx])
            queue.append((y+dy, x+dx))
        res_opt = max(res_opt, opt)

print(res_opt)

Submission status: Accepted

Solution code:
from collections import deque
 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
INF = 10**15

answer = 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 # 始点を定義
      queue = deque([(i, j)]) # 始点を"先入れ先出し"の配列に入れる
      
      while queue:
      # BFS
      # * 計算量 O(4HW:辺の数)
        si, sj = queue.popleft() 
        # "先入れ先出し"
        # * ⇔後入れ先出し。DFS
        #   si, sj = stack.pop()
        
        for ni, nj in [(si + 1, sj), (si - 1, sj), (si, sj + 1), (si, sj - 1)]:
        # 経路に重みがない場合、BFSでは先に入れた方がそのマスに対する最短経路になる...☆
        # * DFSを使用すると更新の必要があり、
        #   計算量が(4HW*HW:辺の数×グリッドの数) -> TLE
        # ** 木だと経路は1つしかないため、BFSもDFSも計算量は同じ
        #    グラフでは基本的にBFS推奨[要出典]
        # * 経路に重みがある場合も更新の必要があり、計算量はO(4HW*HW)
        # ** Dijkstra法を使えば、計算量はO(4HW+HWlogHW)
        #    O(E + VlogV): E -> Edge, V -> Vertex
          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
              queue.append((ni, nj))
          # ☆より、最短経路をとるマスからの隣接が次の最短経路の候補となる
          # すでに最短経路を取っているものは排除
              
      max_dist = 0
      for ii in range(H):
        for jj in range(W):
          if dist[ii][jj] != INF:
            max_dist = max(max_dist, dist[ii][jj])
      answer = max(max_dist, answer)
      # 添え字被りに注意
      
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
#H...高さ、W...幅
H, W = map(int, input().split())

#G...迷路データ　H行連続取得
G = [list(input()) for i in range(H)]

#方向を準備 0...右、1...下、2...左、3...上
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]

ans = 0
for sh in range(H):
    for sw in range(W):
        #通れないマスはスタートになりえない
        if G[sh][sw] == '#':
            #continue...次のswに進める
            continue
        
        #BFS
        #H行W列の-1を準備
        dist = [[-1] * W for i in range(H)]
        #今いる場所を0とする
        dist[sh][sw] = 0
        #要素がsh, swの2つのキュー型変数を用意する
        que = deque([[sh, sw]])
        
        #queの中にデータが有ればtrue, なければfalseが返る
        #つまり、中にデータが有る限りwhileが回る。
        while que:
            #popは右から取り出す
            nh, nw = que.pop()
            
            
            for dh, dw in directions:
                #迷路からはみ出す = not 中にいる. 中にいる= 現在地＋移動量が、0以上、H-1,W-1以下
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue
                    
                #移動先が通れないマス=#
                if G[nh + dh][nw + dw] == '#':
                    continue
                    
                #探索済み
                if dist[nh + dh][nw + dw] != -1:
                    continue
                
                #移動先の数字を出発地＋１にする
                dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                #queの左側に「移動先」を追加
                que.appendleft([nh + dh, nw + dw])
                
                                
        ans = max(ans, max([max(d) for d in dist]))
print(ans)

Submission status: Accepted

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

def bfs(sw,sh):
    res = 0
    dw = [-1,1,0,0]
    dh = [0,0,1,-1]
    dist = [[-1 for _ in range(h)] for _ in range(w)]
    dist[sw][sh] = 0
    queue = deque()
    queue.append((sw,sh))
    while len(queue) != 0:
        cw,ch = queue.popleft()
        for i in range(4):
            nw,nh = cw + dw[i], ch + dh[i]
            if not (0<= nw < w and 0 <= nh < h): continue
            if path[nw][nh] == "#": continue
            if dist[nw][nh] != -1: continue
            dist[nw][nh] = dist[cw][ch] + 1
            queue.append((nw,nh))
            res = max(res, dist[nw][nh])
    return res

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

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
s = [input() for _ in range(h)]
ans = 0

def bfs(sh,sw):
    dh = (1,-1,0,0)
    dw = (0,0,1,-1)
    dist = [[-1 for _ in range(w)] for _ in range(h)]
    queue = deque()
    queue.append((sh,sw))
    dist[sh][sw] = 0
    while len(queue) != 0:
        ch,cw = queue.popleft()
        for i in range(4):
            nh,nw = ch+dh[i],cw+dw[i]
            if not (0 <= nh <= h-1 and 0 <= nw <= w-1): continue
            if s[nh][nw] == "#": continue
            if dist[nh][nw] != -1: continue
            queue.append((nh,nw))
            dist[nh][nw] = dist[ch][cw]+1
    return dist[ch][cw]

for sh in range(h):
    for sw in range(w):
        if s[sh][sw] == "#":
            continue
        ans = max(ans,bfs(sh,sw))
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
INF = 10**15

answer = 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 # 始点を定義
      stack = deque([(i, j)]) # 始点を"先入れ先出し"の配列に入れる
      
      while stack:
      # BFS
      # * 計算量 O(4HW:辺の数)
        si, sj = stack.popleft() 
        # "先入れ先出し"
        # * ⇔後入れ後出し。DFS
        #   si, sj = stack.pop()
        
        for ni, nj in [(si + 1, sj), (si - 1, sj), (si, sj + 1), (si, sj - 1)]:
        # 経路に重みがない場合、BFSでは先に入れた方がそのマスに対する最短経路になる...☆
        # * DFSを使用すると更新の必要があり、
        #    計算量が(4HW*HW:辺の数×グリッドの数)->TLE
        # ** 木だと経路は1つしかないため、BFSもDFSも計算量は同じ
        #     グラフでは基本的にBFS推奨[要出典]
        # * 経路に重みがある場合も更新の必要があり、計算量はO(4HW*HW)
        # ** Dijkstra法を使えば、計算量はO(4HW+HWlogHW)
        #     O(E + VlogV): E -> Edge, V -> Vertex
          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
              stack.append((ni, nj))
          # ☆より、最短経路をとるマスからの隣接が次の最短経路の候補となる
          # すでに最短経路を取っているものは排除
              
              
      max_dist = 0
      for ii in range(H):
        for jj in range(W):
          if dist[ii][jj] != INF:
            max_dist = max(max_dist, dist[ii][jj])
      answer = max(max_dist, answer)
      # * 添え字被りに注意
      
print(answer)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
h, w = map(int, input().split())
maze = [input() for _ in range(h)]
dest = [(1, 0), (-1, 0), (0, 1), (0, -1)]
score = 0

for sx, sy in product(range(w), range(h)):
  if maze[sy][sx] == '#':
    continue
  r = [[-1] * w for _ in range(h)]
  r[sy][sx] = 0
  queue = deque([(sx, sy)])
  while queue:
    x, y = queue.popleft()
    for dx, dy in dest:
      nx, ny = x + dx, y + dy
      if not (0 <= nx < w and 0 <= ny < h):
        continue
      if maze[ny][nx] == '#' or r[ny][nx] != -1:
        continue
      r[ny][nx] = r[y][x] + 1
      queue.append((nx, ny))
      score = max(score, r[ny][nx])
print(score)

Submission status: Accepted

Solution code:
import queue
dx=[1,0,-1,0]
dy=[0,1,0,-1]
H,W=map(int,input().split())
S=[]
for h in range(H):
  S.append(input())

def bfs(s):
  dist = [[-1]*W for _ in range(H)]
  
  h,w = s
  dist[h][w]=0
  que = queue.Queue()
  que.put(s)
  
  while not(que.empty()):
    h,w = que.get()
    for d in range(4):
      nh = h + dx[d]
      nw = w + dy[d]
      if nh<0 or H<=nh or nw<0 or W<=nw:
        continue
      if S[nh][nw]=="#":
        continue
      if dist[nh][nw]==-1:
        dist[nh][nw]=dist[h][w]+1
        que.put([nh,nw])
  return dist[h][w]

ans = 0
for h in range(H):
  for w in range(W):
    if S[h][w]==".":
      ans = max(ans,bfs([h,w]))
print(ans)

Submission status: Accepted

Solution code:
#q:グラフ探索済み格納キュー n:キューの次探索インデックス l:キュー内の次格納インデックス
def bfs_len_max(ind,graph,q_num):
    distance_arr=[0 if i==ind  else -1 for i in range(len(graph))]
    q=[-1 for _ in range(q_num)]
    q[0]=ind
    l=1
    n=0
    while len(q)>l:
        for i in graph[ind]:
            if distance_arr[i]==-1:
                distance_arr[i]=distance_arr[ind]+1
                q[l]=i
                l+=1
        #print(n)
        #print("elapsed q:",q)
        #print("elapsed distance:",distance_arr)
        #print()
        n+=1
        ind=q[n]


    return distance_arr
    

n,m=list(map(int,input().split()))
maze=[]
for i in range(n):
    tmp=input()
    maze.append([k for k in tmp])
#move=[[0 for _ in range(m)] for _ in range(n)]
#print(move)


q_num=0
graph=[[] for _ in range(n*m)]
for i in range(n):
    for j in range(m):
        if maze[i][j]=="#":
            continue
        ind=i*m+j
        q_num+=1
        #move[i][j]=ind
        if i!=0:
            if maze[i-1][j]!="#":
                graph[ind].append((i-1)*m+j)
        if i!=n-1:
            if maze[i+1][j]!="#":
                graph[ind].append((i+1)*m+j)
        if j!=0:
            if maze[i][j-1]!="#":
                graph[ind].append(i*m+j-1)

        if j!=m-1:
            if maze[i][j+1]!="#":
                graph[ind].append(i*m+j+1)
#print(graph)
ans=0
for s in range(m*n):
    if len(graph[s])==0:
        continue
    #print("ind:",s)
    tmp=bfs_len_max(s,graph,q_num)
    #print("res:",tmp)
    ans=max(ans,max(tmp))
    #print("\n\n\n\n")
print(ans)

Submission status: Accepted

Solution code:
import copy
from collections import deque

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

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

maze=[[-1 for j in range(w+2)] for i in range(h+2)]

#banpei
for i in range(h):
    for j in range(w):
        if input_maze[i][j]=='.':
            maze[i+1][j+1]=0
        else:
            maze[i+1][j+1]=-1

#print(maze)

max_route=0
direction=[[1,0],[-1,0],[0,1],[0,-1]]
for i in range(h):
    for j in range(w):
        copy_maze=copy.deepcopy(maze)
        start=[i+1,j+1]
        que=deque([])
        if maze[start[0]][start[1]]==0:
            copy_maze[start[0]][start[1]]=-1
            for d in direction:
                if copy_maze[start[0]+d[0]][start[1]+d[1]]==0:
                    que.append([start[0]+d[0],start[1]+d[1]])
                    copy_maze[start[0]+d[0]][start[1]+d[1]]=1
                    if max_route<1:
                    	max_route=1
            while len(que)>0:
                tmp=que.popleft()
                for d in direction:
                    if copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]==0:
                        que.append([tmp[0]+d[0],tmp[1]+d[1]])
                        copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]=copy_maze[tmp[0]][tmp[1]]+1
                        if max_route<copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]:
                            max_route=copy_maze[tmp[0]+d[0]][tmp[1]+d[1]]

                
print(max_route)

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int, input().split())
fields = []
for i in range(H):
    fields.append(list(input()))
# print(fields)

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

ans = 0
for i1 in range(H):
    for j1 in range(W):
        if fields[i1][j1] == "#":continue
        s = (i1,j1)
        # 探索
        q = deque([])
        q.append(s)
        used = [[-1]*W for i in range(H)]
        used[i1][j1] = 0
        while len(q) > 0:
            h,w = q.popleft()
            for dh,dw in mvs:
                if 0 <= h+dh < H and 0 <= w+dw < W:
                    if used[h+dh][w+dw]==-1 and fields[h+dh][w+dw]==".":
                        q.append((h+dh,w+dw))
                        used[h+dh][w+dw] = used[h][w] + 1
        for i in range(H):
            for j in range(W):
                ans = max(ans, used[i][j])
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import numpy as np
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]
h, w = na()
g = [[1]*(w+2)]
for _ in range(h):
    g += [[1] + [1 if s=="#" else 0 for s in ns()] +[1]]
g += [[1]*(w+2)]
inf = 10**9
def bfs(sx, sy):
    dist = [[inf]*(w+2) for _ in range(h+2)] 
    dist[sx][sy] = 0
    que = deque([[sx, sy]])
    used = set([(sx, sy)])
    while que:
        x, y = que.popleft()
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x+i, y+j
            if (nx, ny) in used:
                continue
            used.add((nx, ny))
            if g[nx][ny]==0:
                dist[nx][ny] = dist[x][y] + 1
                que.append([nx, ny])
    res = 0
    for i in range(h+2):
        for j in range(w+2):
            if g[i][j] == 1:
                dist[i][j] = 0
    return dist


ans = 0
for sx in range(1,h+1):
    for sy in range(1, w+1):
        if g[sx][sy]==0:
            #print(bfs(sx, sy))
            res = np.max(np.array(bfs(sx, sy)))
            ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

h, w = na()
g = [[1]*(w+2)]
for _ in range(h):
    g += [[1] + [1 if s=="#" else 0 for s in ns()] +[1]]
g += [[1]*(w+2)]
inf = 10**9
def bfs(sx, sy):
    dist = [[inf]*(w+2) for _ in range(h+2)] 
    dist[sx][sy] = 0
    que = deque([[sx, sy]])
    used = set([(sx, sy)])
    while que:
        x, y = que.popleft()
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x+i, y+j
            if (nx, ny) in used:
                continue
            used.add((nx, ny))
            if g[nx][ny]==0:
                dist[nx][ny] = dist[x][y] + 1
                que.append([nx, ny])
    res = 0
    for i in range(h+2):
        for j in range(w+2):
            if g[i][j] == 0:
                res = max(res, dist[i][j])

    return res


ans = 0
for sx in range(1,h+1):
    for sy in range(1, w+1):
        if g[sx][sy]==0:  
            ans = max(ans, bfs(sx, sy))
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())

maze = [["."for i in range(W)] for j in range(H)]

for h in range(H):
    ret = input()
    for i, x in enumerate(ret):
        if x == "#":
            maze[h][i] = "#"
        # else: # == "."
        #     maze[h][i] = True

# print(maze)

def bfs(maze, y, x):
    q = [[y, x]]
    res = 0
    dist = [[-1] * W for j in range(H)]
    dist[y][x] = 0
    while len(q) > 0:
        yy, xx = q[0]
        res = max(res, dist[yy][xx])
        q.pop(0)
        for dy, dx in [[1,0], [0,1], [-1,0], [0,-1]]:
            ny = yy + dy
            nx = xx + dx
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue
            if maze[ny][nx] == '#':
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[yy][xx] + 1
                q.append([ny, nx])
    return res

res_max = 0
for j in range(H):
    for i in range(W):
        if maze[j][i] == '#':
            continue
        res_max = max(res_max, bfs(maze, j, i))
print(res_max)

Submission status: Accepted

Solution code:
def bfs():
      global flag
      if len(que)==0:
         flag=False
      else:
         now=que.popleft()
         now_step=steps[now[0]][now[1]]
         for dx,dy in (0,-1),(1,0),(0,1),(-1,0):
            ny=now[0]+dy
            nx=now[1]+dx
            if 0<=ny<=H-1 and 0<=nx<=W-1:
               if maze[ny][nx]==".":
                  if ([ny,nx] in que)==False:
                     maze[ny][nx]="A"
                     que.append([ny,nx])
                     steps[ny][nx]=now_step+1
               else:
                  pass

import copy
from collections import deque

H,W=map(int,input().split())
maze=[]
for i in range(H):
   S=input()
   S=[c for c in S]
   maze.append(S)

maze_copy=copy.deepcopy(maze)
max_step=0

for s_i in range(H):
   for s_j in range(W):
      if maze[s_i][s_j]=="#":
         continue
            
      maze=copy.deepcopy(maze_copy)
      maze[s_i][s_j]="S"
      que=deque([[s_i,s_j]])
      steps=[[-1]*W for c in range(H)]
      steps[s_i][s_j]=0
      flag=True

      while(flag):
         bfs()

      toriaezu_max=0
      for i in range(H):
         toriaezu_max=max(toriaezu_max,max(steps[i]))
      max_step=max(max_step,toriaezu_max)

print(max_step)

Submission status: Accepted

Solution code:
from collections import deque

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

def bps(si,sj):
    distance=[[-1]*W for j in range(H)]
    distance[si][sj]=0
    deq=deque([[si,sj]])
    fdis=0
    while deq:
        i,j=deq.popleft()
        for dir_i,dir_j in [(-1,0),(1,0),(0,-1),(0,1)]:
            if 0<=i+dir_i<H and 0<=j+dir_j<W and distance[i+dir_i][j+dir_j]==-1 and Map[i+dir_i][j+dir_j]==".":
                distance[i+dir_i][j+dir_j]=fdis=distance[i][j]+1
                deq.append([i+dir_i,j+dir_j])
    return fdis

bestMapDistance=0
for i in range(H):
    for j in range(W):
        if Map[i][j]==".":
            bestMapDistance=max(bps(i,j),bestMapDistance)

print(bestMapDistance)

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):
    if S[i][j] == '#':
        return 0

    visited = [[False] * W for _ in range(H)]
    visited[i][j] = True
    que = deque([(i, j, 0)])

    while que:
        ci, cj, d = que.popleft()

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
                continue
            if S[ni][nj] == '.':
                visited[ni][nj] = True
                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:
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

from collections import deque

h, w = na()
s = [ns() for i in range(h)]
maze = [[s[i][j] for j in range(w)] for i in range(h)]
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

def bfs(sx, sy):
    q = deque()
    inf = 1 << 60
    d = [[inf for i in range(w)] for i in range(h)]
    d[sy][sx] = 0
    q.append((sx, sy))
    mx = 0
    while len(q):
        p = q.popleft()
        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]
            if 0 <= nx and nx < w and 0 <= ny and ny < h and maze[ny][nx] != '#' and d[ny][nx] == inf:
                q.append((nx, ny))
                update = d[p[1]][p[0]] + 1
                d[ny][nx] = update
                mx = max(mx, update)
    return mx

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

print(ans)

Submission status: Accepted

Solution code:
# D - Maze Master
def bfs(source: int):
    queue = [source]
    dist = {source: 0}
    while queue:
        x = queue.pop(0)
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] == "." and nx not in dist:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist.values())


def main():
    global W, maze
    H, W = map(int, input().split())
    H, W = H + 2, W + 2
    maze = "#" * W
    for _ in range(H - 2):
        maze += "#" + input().rstrip() + "#"
    maze += "#" * W
    ans = max(bfs(i) for i, c in enumerate(maze) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Maze Master
from collections import deque


def bfs(start: int):
    queue = deque([start])
    dist = [0] * (H * W)
    dist[start] = 1
    while queue:
        x = queue.popleft()
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] == "." and not dist[nx]:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist) - 1


def main():
    global H, W, maze
    H, W = map(int, input().split())
    H, W = H + 2, W + 2
    maze = "#" * W
    for _ in range(H - 2):
        maze += "#" + input().rstrip() + "#"
    maze += "#" * W
    ans = max(bfs(i) for i, c in enumerate(maze) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Maze Master
from collections import deque


def bfs(start: int):
    queue = deque([start])
    dist = {start: 0}
    while queue:
        x = queue.popleft()
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] == "." and nx not in dist:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist.values())


def main():
    global W, maze
    H, W = map(int, input().split())
    H, W = H + 2, W + 2
    maze = "#" * W
    for _ in range(H - 2):
        maze += "#" + input().rstrip() + "#"
    maze += "#" * W
    ans = max(bfs(i) for i, x in enumerate(maze) if x == ".")
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Maze Master
from collections import deque


def bfs(start: int):
    queue = deque([start])
    dist = {start: 0}
    while queue:
        x = queue.popleft()
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] and nx not in dist:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist.values())


def main():
    global W, maze
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    maze = [False] * W  # flatten S and put sentinels
    for s in S:
        maze += [False] + [c == "." for c in s] + [False]
    maze += [False] * W
    ans = max(bfs(i) for i, x in enumerate(maze) if x)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Maze Master
from collections import deque


def bfs(start: int):
    queue = deque([start])
    dist = {start: 0}
    while queue:
        x = queue.popleft()
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] and nx not in dist:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist.values())


def main():
    global H, W, maze
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    maze = [0] * W  # flatten S and put sentinels
    for s in S:
        maze += [0] + [c == "." for c in s] + [0]
    maze += [0] * W
    ans = max(bfs(i) for i, x in enumerate(maze) if x)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Maze Master
from collections import deque

MOD = 10 ** 9 + 7
dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]


def bfs(sx: int, sy: int):
    queue = deque([(sx, sy)])
    dist = {sx * MOD + sy: 0}
    while queue:
        x, y = queue.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if S[nx][ny] == ".":
                if nx * MOD + ny not in dist:
                    dist[nx * MOD + ny] = dist[x * MOD + y] + 1
                    queue.append((nx, ny))
    return max(dist.values())


def main():
    global S
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    S = ["#" * W] + ["#" + s + "#" for s in S] + ["#" * W]  # put sentinels
    ans = max(bfs(i, j) for i, s in enumerate(S) for j, c in enumerate(s) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()