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:
h,w = map(int,input().split())
from copy import deepcopy
from collections import deque
a = [list(input()) for l in range(h)]
c = [[None for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            c[i][j] = -1
ans = 0
g = deque()
for l in range(h):
    for k in range(w):
        b = deepcopy(c)
        if a[l][k] == '.':
            b[l][k] = 0
            g.append((l,k))
            while len(g)>0:
                i,j = g.popleft()
                dis = b[i][j] 
                for dx,dy in ((1,0),(0,1),(-1,0), (0,-1)):
                    newi = i + dx
                    newj = j +dy
                    if newi < 0 or newi > h-1 or newj < 0 or newj > w-1:
                        continue
                    if b[newi][newj] == -1:
                        b[newi][newj] = dis + 1
                        ans = max(ans,dis+1)
                        g.append((newi,newj))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

# 全通りのstart位置から探索する
start = []
for i in range(h):
    for j in range(w):
        if MAZE[i][j] == ".":
            start.append((i, j))


INF = 10**18


def bfs(start):
    i, j = start
    dist = [[INF] * w for _ in range(h)]
    dist[i][j] = 0
    next_v = deque([start])
    while next_v:
        i, j = next_v.popleft()
        direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in direction:
            x, y = i+di, j+dj
            if MAZE[x][y] == "#":
                continue
            if dist[x][y] <= dist[i][j] + 1:
                continue
            dist[x][y] = dist[i][j] + 1
            next_v.append((x, y))
    return dist


ans = 0
for ls1 in start:
    r = bfs(ls1)
    for ls2 in start:
        ans = max(ans, r[ls2[0]][ls2[1]])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]

def bfs(s):
    MAX = 0
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    goal = s
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for k,d in depth.items():
        if MAX < d:
            MAX = d
            goal = k

    return MAX, goal


for r in range(0,H):
    if "." in MAP[r]:
        start = [r, MAP[r].index(".")]

MAX, goal = bfs(tuple(start))
MAX, _ = bfs(tuple(goal))
print(MAX)
exit()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]
MAX = 0 

def bfs(s):
    global MAX
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for d in depth.values():
        MAX = max(MAX,d)


for i in range(0,H):
    for j in range(0,W):
        if MAP[i][j] == '.':
            bfs(tuple([i,j]))
print(MAX)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(tuple(map(str,input())))

move = [[0,1],[0,-1],[1,0],[-1,0]]
MAX = 0 

def bfs(s):
    global MAX
    stack = deque([])
    stack.append(tuple(s))
    depth =dict()
    depth[tuple(s)] = 0
    while stack:
        v = stack.popleft()
        for m in move:
            a = tuple([v[0]+m[0], v[1] + m[1]])
            if a[0] < H and a[0] >=  0 and a[1] < W and a[1] >= 0:
                if MAP[a[0]][a[1]] == '.' and not a in depth:
                    stack.append(a)
                    depth[a] = depth[v] + 1

    for d in depth.values():
        MAX = max(MAX,d)


for i in range(0,H):
    for j in range(0,W):
        if MAP[i][j] == '.':
            bfs(tuple([i,j]))

for i in range(0,W):
    for j in range(0,H):
        if MAP[j][i] == '.':
            bfs(tuple([j,i]))

print(MAX)

Submission status: Accepted

Solution code:
"""参考
@drken
2020年02月02日に更新
BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜
https://qiita.com/drken/items/996d80bcae64649a6580
"""
import numpy as np 
from copy import deepcopy,copy
from copy import copy
def Breadth_first_search(start,already_initial):#幅優先探索
    already=set()
    already =copy(already_initial)
    already.add(start)    
    now = start
    now_generation =copy(queue_dic[start]) #次に行けるところ
    next_preparation =set() #その世代の間、nextに行くために溜めておく
    count_generation=0
    while len(already) < (H+2)*(W+2):
        for now in now_generation:
            if now in already:          #今いるのが壁
                continue            #壁はalready入力すみ
            elif now_generation <= already:   #壁・alreadyに囲まれている
                already.add(now)
                continue
            else:
                #print(now,end=" ")
                already.add(now)
                next_preparation    |= queue_dic[now] 

        now_generation.clear()
        now_generation           |= next_preparation
        next_preparation.clear()
        count_generation +=1
    return count_generation 

# 初期入力

H,W = (int(x) for x in input().split())

map_np =np.full((H+2,W+2),"#",dtype=str) #グリッド初期化、壁で囲むので＋２
for i in range(1,H+1):
    S = input()
    S.strip()
    for j in range(1,W+1):
        map_np[i,j]=S[j-1]

# 構造ーつながり
queue_dic={(h,w):set()for h in range(1,H+1) for w in range(1,W+1)}
already_initial=set() #探索すみ座標の初期値
for h in range(H+2):
    for w in range(W+2):
        if map_np[h,w] ==".":
            if map_np[h+1,w] =="." :
                queue_dic[h,w].add((h+1  ,w  ))
            if map_np[h-1,w] =="." :
                queue_dic[h,w].add((h-1  ,w  ))
            if map_np[h,w+1] =="." :
                queue_dic[h,w].add((h    ,w+1))
            if map_np[h,w-1] =="." :
                queue_dic[h,w].add((h    ,w-1))
        else:
            already_initial.add((h,w)) #壁は行けない＝既に行った
grid_all =queue_dic.keys() #マップの全て
can_pass =grid_all - already_initial  #通過できるところ

#幅優先探索
distance_list =[] #各スタート場所ごとの距離
for start1 in can_pass:
    already1 =set()
    already1=copy(already_initial )
    #print(already_initial)  
    distance_from_start =Breadth_first_search(start1,already_initial)
    distance_list.append(distance_from_start)

print(max(distance_list))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    h, w = mi()
    maze = []
    maze.append(['#'] * (w + 2))
    for _ in range(h):
        maze.append(['#'] + li() + ['#'])
    maze.append(['#'] * (w + 2))

    # for line in maze:
    #     print(*line)


    def bfs(point_dist):
        'point から BFS を行い最も離れていた点との距離を返す'
        q = deque([point_dist])
        max_distance = 0
        while q:
            point, dist = q.popleft()
            i, j = point
            # 距離が最小であることは保証されるが各頂点からの共通の隣接頂点で距離が等しいものが重複登録されることはある
            if visited[i][j]:
                continue
            else:
                visited[i][j] = True
            max_distance = max(max_distance, dist)

            tmp = [(i-1, j), (i, j-1), (i, j+1), (i+1, j)]
            for elm in tmp:
                if not visited[elm[0]][elm[1]] and maze[elm[0]][elm[1]] == '.':
                    q.append([elm, dist+1])
        return max_distance



    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if maze[i][j] == '.':
                # print("{} {}".format(i, j))
                visited = [[False] * (w + 2) for _ in range(h + 2)]
                ans = max(ans, bfs([(i, j), 0]))
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

INF=1001001001

h,w=map(int,input().split())
maze=[]

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


def bfs(y,x):
  #global maze
  #print("y,x",y,x)
  dx=[1,0,-1,0]
  dy=[0,-1,0,1]
  dist=[[INF for i in range(w)] for j in range(h)]
  dist[y][x]=0
  que=deque()
  que.append([y,x])
  mxd=0
  while que:
    v,u=que.popleft()
    #print("v,u",v,u)
    for i in range(4):
      ny=v+dy[i]
      nx=u+dx[i]
      #print("ny,nx",ny,nx)
      if 0<=ny<h and 0<=nx<w and maze[ny][nx]=="." and dist[ny][nx]==INF:
        que.append([ny,nx])
        dist[ny][nx]=dist[v][u]+1
        mxd=max(mxd,dist[ny][nx])
  return mxd

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

Submission status: Accepted

Solution code:
#ライブラリインポート
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

def BFS(H, W, L, start):
	dist = [[INF for i in range(W)] for j in range(H)]
	sy, sx = start
	dist[sy][sx] = 0
	Q = queue.Queue()
	Q.put([sy, sx])
	while not Q.empty():
		y, x = Q.get()
		if y - 1 >= 0:
			if L[y - 1][x] == "." and dist[y - 1][x] > dist[y][x] + 1:
				dist[y - 1][x] = dist[y][x] + 1
				Q.put([y - 1, x])
		if y + 1 <= H - 1:
			if L[y + 1][x] == "." and dist[y + 1][x] > dist[y][x] + 1:
				dist[y + 1][x] = dist[y][x] + 1
				Q.put([y + 1, x])
		if x - 1 >= 0:
			if L[y][x - 1] == "." and dist[y][x - 1] > dist[y][x] + 1:
				dist[y][x - 1] = dist[y][x] + 1
				Q.put([y, x - 1])
		if x + 1 <= W - 1:
			if L[y][x + 1] == "." and dist[y][x + 1] > dist[y][x] + 1:
				dist[y][x + 1] = dist[y][x] + 1
				Q.put([y, x + 1])

	return dist

#処理内容
def main():
	H, W = getlist()
	L = []
	for i in range(H):
		l = list(input())
		L.append(l)

	ans = 0
	for i in range(H):
		for j in range(W):
			if L[i][j] == ".":
				BF = BFS(H, W, L, [i, j])
				for p in range(H):
					for q in range(W):
						if BF[p][q] != INF:
							ans = max(ans, BF[p][q])

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# Maze by warshall_floyd
# ワーシャルフロイド法


def solve(H, W, a):
    # print(a)
    inf = H*W**2
    d = [[inf]*(H*W) for _ in range(H*W)]
    for h in range(H):
        for w in range(W):
            if (a[h][w] == "0"):
                d[h*W+w][h*W+w] = 0
                if (w+1<W)and(a[h][w+1] == "0"):
                    d[h*W+w][h*W+w+1] = 1
                if (h+1<H)and(a[h+1][w] == "0"):
                    d[h*W+w][(h+1)*W+w] = 1
                if (w-1>=0)and(a[h][w-1] == "0"):
                    d[h*W+w][h*W+w-1] = 1
                if (h-1>=0)and(a[h-1][w] == "0"):
                    d[h*W+w][(h-1)*W+w] = 1
                
    # print(*d, sep='\n')

    for k in range(H*W):  # via k [k//W][k% W]
        for st in range(H*W):  # start from st
            for ed in range(H*W):  # go to ed
                d[st][ed] = min(d[st][ed], d[st][k]+d[k][ed])

    # print(*d, sep="\n")

    print(max(*map(lambda x: max([_ if _ != inf else 0 for _ in x ]), d)))
    return

if __name__ == '__main__':
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int

    a = [[_ for _ in next(tokens).replace(".","0").replace("#","1")] for _ in range(H)]  # type: "List[int]"
    solve(H, W, a)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# Maze by warshall_floyd
# ワーシャルフロイド法


def solve(H, W, a):
    # print(a)
    inf = H*W**2
    d = [[inf]*(H*W) for _ in range(H*W)]
    for h in range(H):
        for w in range(W):
            if (a[h][w] == "0"):
                d[h*W+w][h*W+w] = 0
                if (w+1<W)and(a[h][w+1] == "0"):
                    d[h*W+w][h*W+w+1] = 1
                if (h+1<H)and(a[h+1][w] == "0"):
                    d[h*W+w][(h+1)*W+w] = 1
                if (w-1>=0)and(a[h][w-1] == "0"):
                    d[h*W+w][h*W+w-1] = 1
                if (h-1>=0)and(a[h-1][w] == "0"):
                    d[h*W+w][(h-1)*W+w] = 1
                
    # print(*d, sep='\n')

    for k in range(H*W):  # via k [k//W][k% W]
        for st in range(H*W):  # start from st
            for ed in range(H*W):  # go to ed
                d[st][ed] = min(d[st][ed], d[st][k]+d[k][ed])

    # print(*d, sep="\n")

    print(max(*map(lambda x: max([_ if _ != inf else -1 for _ in x ]), d)))
    return

if __name__ == '__main__':
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int

    a = [[_ for _ in next(tokens).replace(".","0").replace("#","1")] for _ in range(H)]  # type: "List[int]"
    solve(H, W, a)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(sy,sx):
    m_dis=0
    
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    visited=[[-1]*yoko for i in range(tate)]
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        for dy,dx in move:
            my,mx=y+dy,x+dx
            if not(0<=my<tate) or not(0<=mx<yoko):
                continue
            if maze[my][mx]=="." and visited[my][mx]==-1:
                queue.append([my,mx])
                visited[my][mx]=visited[y][x]+1 # visitedは距離も兼ねてる
                m_dis=visited[my][mx]
        
    return m_dis

tate,yoko=map(int,input().split())
maze=[]
for i in range(tate):
    line=list(input())
    maze.append(line)
ans=0
for y in range(tate):
    for x in range(yoko):
        if maze[y][x]==".":
            ans=max(ans,bfs(y,x))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    from collections import deque
    dy,dx=[1,0,-1,0],[0,1,0,-1]
    def maze_init(grid,road_chr='.',wall_chr='#',start_chr=None,goal_chr=None):
        H,W=len(grid),len(grid[0])
        if isinstance(grid[0],str):
            grid=[list(row) for row in grid]
        S,G=None,None
        c=[[-1]*(W+2) for _ in range(H+2)]
        for i,row in enumerate(grid,1):
            for j,x in enumerate(row,1):
                if x==road_chr:
                    c[i][j]=0
                elif x==wall_chr:
                    c[i][j]=1
                elif x==start_chr:
                    S=(i,j)
                    c[i][j]=0
                elif x==goal_chr:
                    G=(i,j)
                    c[i][j]=0
        return c,S,G
    def maze_bfs(grid,start_coordinate,road_cost=1,wall_cost=None):
        d=[[INF]*len(grid[0]) for _ in range(len(grid))]
        que=deque()
        que.append((start_coordinate[0],start_coordinate[1]))
        d[start_coordinate[0]][start_coordinate[1]]=0
        while que:
            v=que.popleft()
            for k in range(4):
                nv=(v[0]+dy[k],v[1]+dx[k])
                if grid[nv[0]][nv[1]]==0:
                    if d[nv[0]][nv[1]]>d[v[0]][v[1]]+road_cost:
                        que.append(nv)
                        d[nv[0]][nv[1]]=d[v[0]][v[1]]+road_cost
                elif grid[nv[0]][nv[1]]==1 and wall_cost is not None:
                    if d[nv[0]][nv[1]]>d[v[0]][v[1]]+wall_cost:
                        que.append(nv)
                        d[nv[0]][nv[1]]=d[v[0]][v[1]]+wall_cost
        return d
    
    H,W=map(int,input().split())
    s=[list(input()) for _ in range(H)]
    
    grid,S,G=maze_init(s,road_chr='.',wall_chr='#',start_chr=None,goal_chr=None)
    
    ans=0
    for i in range(1,H+1):
        for j in range(1,W+1):
            d=maze_bfs(grid,(i,j),road_cost=1,wall_cost=None)
            for k in range(1,H+1):
                for l in range(1,W+1):
                    if grid[i][j]==grid[k][l]==0:
                        ans=max(ans,d[k][l])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def bfs(start):
    Q = deque()
    child = deque()
    Q.append(start)
    dist[start[1] - 1][start[0] - 1] = 0
    r = 0

    while Q:
        x, y = Q.popleft()
        x = x - 1
        y = y - 1

        for i in range(4):
            child.clear()
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] != -1:
                continue

            child.append((nx + 1, ny + 1))

            if len(child) > 0:
                for c in child:
                    dist[c[1] - 1][c[0] - 1] = dist[y][x] + 1
                    Q.append(c)

    for i in range(H):
        r = max(r, max(dist[i]))
        # print(dist[i])

    return r


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

for i in range(H):
    G[i] = list(input())

# dist = [[-1 for _ in range(W)] for _ in range(H)]
dx = [1, 0, -1, 0]  # 斜めも含むならその方向もプラス
dy = [0, 1, 0, -1]

res = 0
for i in range(H):
    for j in range(W):
        if G[i][j] != "#":
            # print("-----------(" + str(j + 1) + "," + str(i + 1) + ")")
            dist = [[-1 for _ in range(W)] for _ in range(H)]
            start = (j + 1, i + 1)
            res = max(res, bfs(start))

print(res)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
square = [list(input()) for i in range(h)]
def bfs(si, sj):
    INF = 100
    que = deque([(si, sj)])
    d = [[INF] * w for i in range(h)]
    d[si][sj] = 0
    move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while que:
        i, j = que.popleft()
        for mi, mj in move:
            ni, nj = i + mi, j + mj
            if 0 <= ni < h and 0 <= nj < w and square[ni][nj] == '.' and d[ni][nj] == INF:
                que.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

max_num = 0
for i in range(h):
    for j in range(w):
        if square[i][j] == '.':
            max_ij = bfs(i, j)
            max_num = max(max_num, max_ij)
print(max_num)

Submission status: Accepted

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

def bfs(y, x):
  q = deque([[y, x]])
  while q:
    y,x = q.popleft()

    for a, b in zip([1,0,-1,0], [0,1,0,-1]):
      if 0 <= y+a < H and 0 <= x+b < W:
        if maze[y+a][x+b] == "." and visted[y+a][x+b] == -1:
          visted[y+a][x+b] = visted[y][x] + 1
          q.append([y+a, x+b])
  return 0

maze = []
dots=[]
for h in range(H):
  maze.append(input())
  for w in range(W):
    if maze[-1][w] == ".":
      dots.append([h, w])

ans=0
for i in range(len(dots)):
  sy = dots[i][0]
  sx = dots[i][1]
  visted = [[-1] * W for _ in range(H)]
  visted[sy][sx]=0
  bfs(sy, sx)
  for g in dots[i+1:]:
    gy = g[0]
    gx = g[1]
    ans = max(ans, visted[gy][gx])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
import math

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

edges = defaultdict(list)
field = []

for _ in range(H):
    field.append(input())

weight = 1
for i in range(H):
    for j in range(W):
        if j + 1 < W and field[i][j] == '.' and field[i][j + 1] == '.':
            edges[W * i + j].append((W * i + j + 1, weight))
            edges[W * i + j + 1].append((W * i + j, weight))
        if i + 1 < H and field[i][j] == '.' and field[i + 1][j] == '.':
            edges[W * i + j].append((W * (i + 1) + j, weight))
            edges[W * (i + 1) + j].append((W * i + j, weight))


def dijkstra(s):
    que = []
    dist = [float('inf')] * (H * W)
    dist[s] = 0
    heapq.heappush(que, (0, s))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for i in range(len(edges[v])):
            e = edges[v][i]
            if dist[e[0]] > dist[v] + e[1]:
                dist[e[0]] = dist[v] + e[1]
                heapq.heappush(que, (dist[e[0]], e[0]))

    dist = [0 if d == float('inf') else d for d in dist]
    return dist


ans = 0
for i in range(H*W):
    ans = max(ans, max(dijkstra(i)))

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq
import math

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

edges = defaultdict(list)
field = []

for _ in range(H):
    field.append(input())

weight = 1
for i in range(H):
    for j in range(W):
        if j + 1 < W and field[i][j] == '.' and field[i][j + 1] == '.':
            edges[W * i + j].append((W * i + j + 1, weight))
            edges[W * i + j + 1].append((W * i + j, weight))
        if i + 1 < H and field[i][j] == '.' and field[i + 1][j] == '.':
            edges[W * i + j].append((W * (i + 1) + j, weight))
            edges[W * (i + 1) + j].append((W * i + j, weight))


def dijkstra(s):
    que = []
    dist = [float('inf')] * (H * W)
    dist[s] = 0
    heapq.heappush(que, (0, s))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for i in range(len(edges[v])):
            e = edges[v][i]
            if dist[e[0]] > dist[v] + e[1]:
                dist[e[0]] = dist[v] + e[1]
                heapq.heappush(que, (dist[e[0]], e[0]))

    dist = [0 if d == float('inf') else d for d in dist]
    return dist


ans = 0
for i in range(H*W):
    ans = max(ans, max(dijkstra(i)))

print(ans)

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    def bfs(S,s,h,w):
        dist = np.ones((h,w))*-1
        dist[s[0],s[1]]=0
        que = [s]
        while len(que)>0:
            v = que.pop(0)
            if v[0]+1<h:
                if S[v[0]+1][v[1]]=='.' and dist[v[0]+1][v[1]] == -1:
                    dist[v[0]+1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]+1,v[1]])
            if v[0]-1>-1:
                if S[v[0]-1][v[1]]=='.' and dist[v[0]-1][v[1]]==-1:
                    dist[v[0]-1][v[1]]=dist[v[0]][v[1]]+1
                    que.append([v[0]-1,v[1]])
            if v[1]+1<w:
                if S[v[0]][v[1]+1]=='.' and dist[v[0]][v[1]+1]==-1:
                    dist[v[0]][v[1]+1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]+1])
            if v[1]-1>-1:
                if S[v[0]][v[1]-1]=='.' and dist[v[0]][v[1]-1]==-1:
                    dist[v[0]][v[1]-1]=dist[v[0]][v[1]]+1
                    que.append([v[0],v[1]-1])
        return np.max(dist)

    h,w = map(int,input().split())
    S = []
    for i in range(h):
        S.append(input())
    m = 0
    spot = []
    for i in range(h):
        for j in range(w):
            spot.append([i,j])
    for i in range(len(spot)):
        s = spot[i]
        if S[s[0]][s[1]]=='#':
            continue
        d = bfs(S,s,h,w)
        if m<d:
            m = d
    print(int(m))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
square = [list(input()) for i in range(h)]
def bfs(si, sj):
    que = deque()
    que.append((si, sj))
    d = [[float('inf')] * w for i in range(h)]
    d[si][sj] = 0
    move = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while que:
        i, j = que.popleft()
        for mi, mj in move:
            ni, nj = i + mi, j + mj
            if 0 <= ni < h and 0 <= nj < w and square[ni][nj] != '#' and d[ni][nj] == float('inf'):
                que.append((ni, nj))
                d[ni][nj] = d[i][j] + 1
    return d[i][j]

max_num = 0
for i in range(h):
    for j in range(w):
        if square[i][j] == '.':
            max_ij = bfs(i, j)
            max_num = max(max_num, max_ij)
print(max_num)

Submission status: Accepted

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

maze=[]
for _ in range(h):
    temp=input()
    ary=[]
    for s in temp:
        ary.append(s)
    maze.append(ary)

"""
#深さ優先じゃよく考えたらダメやん
def DFS(yy,xx):
    global maze,h,w,maze_temp
    kyori=0
    for UDRL in [(0,1),(1,0),(-1,0),(0,-1)]:
        ny=UDRL[0]+yy
        nx=UDRL[1]+xx
        if 0<=ny<h and 0<=nx<w and maze_temp[ny][nx]==".":
            maze_temp[ny][nx]="#"
            kyori=max(kyori,DFS(ny,nx))
    #print(yy,xx,kyori+1)
    return kyori+1
"""

import queue
from collections import deque







import copy
#maze_temp=copy.deepcopy(maze)

result=0

for y in range(h):
    for x in range(w):
        fifo = deque([])
        if maze[y][x]==".":
            maze_temp=[[-1]*w for _ in range(h)]
            fifo.append([y,x])
            maze_temp[y][x]=0
            result_temp=0
            while len(fifo)>0:
                temp=fifo.popleft()
                yy=temp[0]
                xx=temp[1]
                for yyy,xxx in [(0,1),(1,0),(-1,0),(0,-1)]:
                    ny=yyy+yy
                    nx=xxx+xx
                    if 0<=ny<h and 0<=nx<w:
                        if maze[ny][nx]=="." and maze_temp[ny][nx]==-1:
                            maze_temp[ny][nx]=maze_temp[yy][xx]+1
                            result_temp=max(result_temp,maze_temp[ny][nx])
                            fifo.append([ny,nx])
                            #print(maze_temp)
            result=max(result_temp,result)
            #print(y,x)
            #print(maze_temp)
print(result)

Submission status: Accepted

Solution code:
def bfs_longest(x,y):
    queuex = [x]
    queuey = [y]
    queuedis = [0]
    ans = [0]
    dis = [[-1 for _ in range(w+2)]for k in range(h+2)]
    dis[x][y] = 0
    while(len(queuex)):
        nowx = queuex.pop(0)
        nowy = queuey.pop(0)
        nowdis = queuedis.pop(0)
        search = [[nowx+1,nowy],[nowx-1,nowy],[nowx,nowy+1],[nowx,nowy-1]]
        for i in range(len(search)):
            if dis[search[i][0]][search[i][1]] == -1:
                if maze[search[i][0]][search[i][1]] == ".":
                    queuex.append(search[i][0])
                    queuey.append(search[i][1])
                    queuedis.append(nowdis+1)
                    ans.append(nowdis+1)
                    dis[search[i][0]][search[i][1]] = nowdis+1
    return ans[-1]

h,w = map(int,input().split())
maze = [["#" for _ in range(w+2)]for p in range(h+2)]
anchor = []
for i in range(h):
    data = str(input())
    for j in range(w):
        maze[i+1][j+1] = data[j]
        if data[j] == ".":
            anchor.append([i+1,j+1])

answer = 0
for i in range(len(anchor)):
    answer = max(bfs_longest(anchor[i][0],anchor[i][1]),answer)
print(answer)