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:
import copy

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

def BFS(q):
	flg = copy.deepcopy(S)
	while q != []:
		cx,cy,cd = q.pop(0)
		if flg[cx][cy] == "#":
			continue
		else:
			flg[cx][cy] = "#"
		nps = [[cx+1,cy],[cx-1,cy],[cx,cy+1],[cx,cy-1]]
		for nx,ny in nps:
			if 0 <= nx < H and 0 <= ny < W:
				if flg[nx][ny] != "#":
					q.append([nx,ny,cd+1])

	return cd

ans = 0

for sx in range(H):
	for sy in range(W):
		if S[sx][sy] == "#":
			continue
		else:
			ans = max(ans,BFS([[sx,sy,0]]))

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
direcion = [(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        que = deque([(j,i)])
        dist = [[0]*w for _ in range(h)]
        visited = [[0]*w for _ in range(h)]
        visited[i][j] = 1
        while que:
            j, i = que.popleft()
            for x,y in direcion:
                n_x,n_y = j+x,i+y
                if not 0 <= n_x < w: continue
                if not 0 <= n_y < h: continue
                if visited[n_y][n_x]: continue
                if s[n_y][n_x] == "#": continue
                visited[n_y][n_x] = 1
                dist[n_y][n_x] = dist[i][j] + 1
                que.append((n_x,n_y))
        ans = max(ans,max(max(row) for row in dist))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
def main():
    hw = list(map(int, input().split()))
    s = np.zeros((hw[0],hw[1]), dtype=int)
    validpoints = []
    for i in range(hw[0]):
        tmp = input()
        tm = [None]*hw[1]
        for j in range(hw[1]):
            if tmp[j] == '.':
                tm[j] = 0
                validpoints.append((i,j))
            elif tmp[j] == '#':
                tm[j] = 1
        s[i] = np.array(tm)

    ma = 0

    for i in validpoints:
        cost = breadth(s,i)
        if cost > ma:
            ma = cost
    print(ma)

def breadth(ss, start):
    q = deque()
    visited = np.array(ss)
    visited[start] = 1
    q.append({start})
    c = 0

    while not len(q) == 0:
        c += 1
        v = q.pop()
        tmpl = []
        for i in v:
            visited[i] = 1
            child = get_child_quad(ss, visited, i)
            tmpl.extend(child)
        tmps = set(tmpl)
        if len(tmps) > 0:
            for i in tmps:
                visited[i] = 1
            q.append(set(tmpl))

    return c-1

def get_child_quad(ss, visited, p):
    down = (p[0]+1,p[1])
    up = (p[0]-1,p[1])
    right = (p[0],p[1]+1)
    left = (p[0],p[1]-1)
    child = [down,up,right,left]
    return list(filter(lambda pp: 0 <= pp[0] < len(ss) and 0 <= pp[1] < len(ss[0]) and visited[pp[0],pp[1]] == 0, child))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
def main():
    hw = list(map(int, input().split()))
    s = np.zeros((hw[0],hw[1]), dtype=int)
    validpoints = []
    for i in range(hw[0]):
        tmp = input()
        tm = [None]*hw[1]
        for j in range(hw[1]):
            if tmp[j] == '.':
                tm[j] = 0
                validpoints.append((i,j))
            elif tmp[j] == '#':
                tm[j] = 1
        s[i] = np.array(tm)

    ma = 0
    # for i in validpoints:
    #     for j in validpoints:
    #         vis = np.array(s)
    #         cost = breadth(s,i,j,vis)
    #         if cost > ma:
    #             ma = cost
    for i in validpoints:
        cost = breadth(s,i)
        if cost > ma:
            ma = cost
    print(ma)

    # print(breadth(s,(2,0),(0,4)))
    # print(breadth(s,(0,0),(1,0)))

def breadth(ss, start):
    q = deque()
    visited = np.array(ss)
    visited[start] = 1
    q.append({start})
    c = 0

    while not len(q) == 0:
        c += 1
        v = q.pop()
        tmpl = []
        for i in v:
            visited[i] = 1
            child = get_child_quad(ss, visited, i)
            tmpl.extend(child)
        tmps = set(tmpl)
        if len(tmps) > 0:
            for i in tmps:
                visited[i] = 1
            q.append(set(tmpl))

    return c-1

def get_child_quad(ss, visited, p):
    down = (p[0]+1,p[1])
    up = (p[0]-1,p[1])
    right = (p[0],p[1]+1)
    left = (p[0],p[1]-1)
    child = [down,up,right,left]
    return list(filter(lambda pp: 0 <= pp[0] < len(ss) and 0 <= pp[1] < len(ss[0]) and visited[pp[0],pp[1]] == 0, child))

# def breadth(ss, start, goal, visited):
#     newvis = np.array(visited)
#     newvis[start] = 1
#     if start == goal:
#         return 0
#     down = (start[0]+1,start[1])
#     up = (start[0]-1,start[1])
#     right = (start[0],start[1]+1)
#     left = (start[0],start[1]-1)
#     child = [down,up,right,left]
#     child = list(filter(lambda i: 0 <= i[0] < len(ss) and 0 <= i[1] < len(ss[0]) and visited[i[0],i[1]] == 0, child))
#     if len(child) > 0:
#         mi = 99999
#         for i in child:
#             co = breadth(ss,i,goal,newvis)
#             if mi > co:
#                 mi = co
#         return 1+mi
#     else:
#         return 1
    

# def breadth(ss, start, goal):
#     q = deque()
#     visited = np.array(ss)
#     visited[start] = 1
#     q.append(start)
#     c = 0
#     while not len(q) == 0:
#         v = q.pop()
#         if v == goal:
#             break
#         down = (v[0]+1,v[1])
#         up = (v[0]-1,v[1])
#         right = (v[0],v[1]+1)
#         left = (v[0],v[1]-1)
#         child = [down,up,right,left]
#         child = list(filter(lambda i: 0 <= i[0] < len(ss) and 0 <= i[1] < len(ss[0]) and visited[i[0],i[1]] == 0, child))

#         if len(child) > 0:
#             for i in child:
#                 visited[i] = 1
#                 q.append(i)
#             c += 1
        
#     return c

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from collections import deque

def resolve():
    H, W = iim()

    M = [input() for i in range(H)]

    def search(y, x):
        q = []
        m = [[0]*W for i in range(H)]

        m[y][x] = 1
        q = deque([(y,x, 0)])
        ans = 0
        while q:
            y, x, k = q.popleft()
            ans = max(ans, k)
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                yy = y + i
                xx = x + j

                if 0 <= xx < W and 0 <= yy < H:
                    if M[yy][xx] == "." and m[yy][xx] == 0:
                        m[yy][xx] = 1
                        q.append((yy, xx, k+1))

        return ans

    ans = 0
    for y in range(H):
        for x in range(W):
            if M[y][x] == ".":
                ans = max(ans, search(y, x))
    print(ans)
if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

ans=0
dxy=[(0,1),(1,0),(0,-1),(-1,0)]
for y in range(h):
  for x in range(w):
    if S[y][x]=='#': continue
    q=deque([(x,y)])
    dist=[[0]*w for _ in range(h)]
    visited=[[0]*w for _ in range(h)]
    visited[y][x]=1
    while q:
      x,y=q.popleft()
      for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w: continue
        if not 0<=ny<h: continue
        if visited[ny][nx]: continue
        if S[ny][nx]=='#': continue
        visited[ny][nx]=1
        dist[ny][nx]=dist[y][x]+1
        q.append((nx,ny))
    ans = max(ans, max(max(row) for row in dist))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import numpy as np
import copy
from collections import deque

n, m = map(int, input().split())

# マス目と距離保存のための箱を作成
d = []
mas = []
for i in range(n):
    mas.extend(list(map(list, input().split())))
    d.append([float("nan")] * m)


def tansaku(sx, sy, d):
    local_d = copy.deepcopy(d)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    local_d[sx][sy] = 0
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        for i in range(4):
            # 移動4方向をループ
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and mas[nx][ny] != "#"
                and not local_d[nx][ny] == local_d[nx][ny]
            ):
                # 移動できるならキューに入れ，その点の距離を p からの距離 +1 で確定する．最後Nan判定
                que.append((nx, ny))
                local_d[nx][ny] = local_d[p[0]][p[1]] + 1
    d_max = int(np.nanmax(np.array(local_d)))
    return d_max


dis = 0
for i in range(n):
    for j in range(m):
        if mas[i][j] != "#":
            dis_i = tansaku(i, j, d)
            if dis_i > dis:
                dis = copy.copy(dis_i)

print(dis)

Submission status: Accepted

Solution code:
Y,X=map(int,input().split())
info=[]
for i in range(Y):
    line=list(input())
    info.append(line)
ans=0
def bfs(y,x):
    global nex
    global ok
    global visited
    if not((0<=y<Y) and (0<=x<X)):
        return
    if visited[y][x]==1 or info[y][x]=="#":
        return
    visited[y][x]=1
    ok+=1
    nex.append([y,x])
#各地点から幅優先探索をして、一番深いところにいけたら答え。
for i in range(Y):
    for j in range(X):
        if info[i][j]=="#":
            continue
        visited=[[0 for a in range(X)] for b in range(Y)] #訪れたことあるか
        visited[i][j]=1
        nex=[[i,j]]
        farthest=0 #一番遠い手数
        num=1 #次にスタートにする数
        while num>0:
            ok=0
            for k in range(num):
                bfs(nex[0][0]+1,nex[0][1])
                bfs(nex[0][0]-1,nex[0][1])
                bfs(nex[0][0],nex[0][1]+1)
                bfs(nex[0][0],nex[0][1]-1)
                del nex[0]
            if ok!=0:
                farthest+=1
            num=len(nex)
        if ans<farthest:
            ans=farthest
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h, w = map(int, input().split())
    maze = [tuple(input()) for _ in range(h)]
    # h,w = inpm()
    # maze = []
    # for _ in range(h):
    #     s = tuple(input())
    #     maze.append(s)
    ans = 0
    dx = (1,0,-1,0)
    dy = (0,1,0,-1)

    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '#':
                continue
            else:
                d = [[-1 for _ in [0]*w] for _ in [0]*h]
                que = deque()
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    (qx,qy) = que.popleft()
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx >= 0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append((nx,ny))
                ans = max(ans,M)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h, w = map(int, input().split())
    maze = [tuple(input()) for _ in range(h)]
    # h,w = inpm()
    # maze = []
    # for _ in range(h):
    #     s = tuple(input())
    #     maze.append(s)
    ans = 0
    dx = (1,0,-1,0)
    dy = (0,1,0,-1)

    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '#':
                continue
            else:
                d = [[-1 for _ in range(w)] for _ in range(h)]
                que = deque()
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    (qx,qy) = que.popleft()
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx >= 0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append((nx,ny))
                ans = max(ans,M)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h, w = map(int, input().split())
    maze = [tuple(input()) for _ in range(h)]
    # h,w = inpm()
    # maze = []
    # for _ in range(h):
    #     s = tuple(input())
    #     maze.append(s)
    ans = 0
    dx = (1,0,-1,0)
    dy = (0,1,0,-1)

    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '#':
                continue
            else:
                d = [[-1 for _ in range(w)] for _ in range(h)]
                que = deque()
                d[sx][sy] = 0
                que.append([sx,sy])
                M = 0
                while que:
                    [qx,qy] = que.popleft()
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append([nx,ny])
                ans = max(ans,M)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h, w = map(int, input().split())
    maze = [tuple(input()) for _ in range(h)]
    # h,w = inpm()
    # maze = []
    # for _ in range(h):
    #     s = tuple(input())
    #     maze.append(s)
    ans = 0
    dx = (1,0,-1,0)
    dy = (0,1,0,-1)

    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '#':
                continue
            else:
                d = [[-1 for _ in range(w)] for _ in range(h)]
                que = deque()
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    (qx,qy) = que.popleft()
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append([nx,ny])
                ans = max(ans,M)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h,w = inpm()
    maze = []
    for _ in range(h):
        s = tuple(input())
        maze.append(s)
    ans = 0
    dx = (1,0,-1,0)
    dy = (0,1,0,-1)

    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '#':
                continue
            else:
                d = [[-1 for _ in range(w)] for _ in range(h)]
                que = deque()
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    (qx,qy) = que.popleft()
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append([nx,ny])
                ans = max(ans,M)
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


h, w = map(int, input().split())
meiro = []
for i in range(h):
    line = input()
    meiro.append(line)


def bfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '#':
        return 0
    dist[y][x] = 0

    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = deque([])
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            todo.append([ny, nx, 1])

    while todo:
        y, x, d = todo.popleft()
        if meiro[y][x] == '#':
            continue
        if dist[y][x] != -1:
            continue

        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1:
                todo.append([ny, nx, d+1])

    res = 0
    for line in dist:
        res = max(max(line), res)

    return res


ans = []
for y in range(h):
    for x in range(w):
        ans.append(bfs(y, x))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque


h, w = map(int, input().split())
meiro = []
for i in range(h):
    line = input()
    meiro.append(line)


def bfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '#':
        return 0
    dist[y][x] = 0

    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = deque([])
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            todo.append([ny, nx, 1])

    while todo:
        y, x, d = todo.popleft()
        if meiro[y][x] == '#':
            continue
        if dist[y][x] != -1:
            continue

        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1 and dist[ny][nx] == -1:
                todo.append([ny, nx, d+1])

    res = 0
    for line in dist:
        res = max(max(line), res)

    return res


ans = []
for y in range(h):
    for x in range(w):
        ans.append(bfs(y, x))

print(max(ans))

Submission status: Accepted

Solution code:
import collections
h, w = map(int, input().split())
s = [[""]*(w+2)]
starts = []
for i in range(h):
    _s = list(input())
    _s.insert(0, "")
    _s.append("")
    s.append(_s)
    for j, __s in enumerate(_s):
        if __s == ".":
            starts.append([i+1, j])
s.append([""]*(w+2))

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

ans = 0
for _start in starts:
    dist = [[-1]*(w+2) for _ in range(h+2)]
    dist[_start[0]][_start[1]] = 0
    q = collections.deque([_start])

    # BFS
    while 0 < len(q):
        c = q.pop()
        for _dx, _dy in zip(dx, dy):
            x = c[0] + _dx
            y = c[1] + _dy
            if s[x][y] == "." and dist[x][y] == -1:
                dist[x][y] = dist[c[0]][c[1]] + 1
                q.appendleft([x, y])

    for _d in dist:
        ans = max(ans, max(_d))

print(ans)

Submission status: Accepted

Solution code:
import heapq
 
 
h, w = map(int, input().split())
meiro = []
for i in range(h):
    line = input()
    meiro.append(line)
 
 
def dfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '#':
        return 0
    dist[y][x] = 0
 
    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = []
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            if meiro[ny][nx] == '.':
                heapq.heappush(todo, [1, ny, nx])
 
    while todo:
        d, y, x = heapq.heappop(todo)
        if meiro[y][x] == '#':
            continue
        if dist[y][x] != -1:
                continue
 
        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1:
                if dist[ny][nx] == -1 and meiro[ny][nx] == '.':
                    heapq.heappush(todo, [d+1, ny, nx])
 
    res = 0
    for line in dist:
        res = max(max(line), res)
 
    return res
 
 
ans = []
for y in range(h):
    for x in range(w):
        ans.append(dfs(y, x))
 
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque


h, w = map(int, input().split())
graph = '#' * (w+2)
for _ in range(h):
    line = '#' + input() + '#'
    graph = graph + line

graph = graph + '#' * (w+2)


def bfs(x):
    if graph[x] == '#':
        return 0
    seen = [-1] * ((h+2)*(w+2))
    seen[x] = 0
    pattern = [-(w+2), -1, 1, w+2]
    todo = deque([])
    for delta in pattern:
        if graph[x+delta] == '.':
            todo.append([x+delta, 1])

    while todo:
        node, dist = todo.popleft()
        if seen[node] != -1:
            continue
        seen[node] = dist
        for delta in pattern:
            if graph[node+delta] == '.' and seen[node+delta] == -1:
                todo.append([node+delta, dist+1])

    return max(seen)


ans = []
for i in range((h+1)*(w+1)):
    ans.append(bfs(i))

print(max(ans))

Submission status: Accepted

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

INF = 1001001001
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

def update(i, j, x):
    global dist, s, q
    if(dist[i][j] != INF): return
    dist[i][j] = x
    q.append([i, j])

res = 0
for si in range(h):
    for sj in range(w):
        if(s[si][sj] == '#'): continue
        
        dist = [[INF for _ in range(w)] for _ in range(h)]
        q = deque()
        update(si, sj, 0)
        
        while(q):
            i, j = q.popleft()
            
            for idir, jdir in zip(di, dj):
                ni = i + idir
                nj = j + jdir
                
                if(ni<0 or ni>=h or nj<0 or nj>=w): continue
                if(s[ni][nj] == '#'): continue
                
                update(ni, nj, dist[i][j]+1)
        
        for i in range(h):
            for j in range(w):
                if(dist[i][j]==INF): continue
                res = max(res, dist[i][j])

print(res)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
H, W = map(int, input().split())
grid = [[1 if i == "." else 0 for i in input()] for _ in range(H)]

inf = 10**5
wf = np.ones((H*W, H*W), dtype=int)*inf
DX = (0, 1, 0, -1)
DY = (1, 0, -1, 0)

for i in range(H):
    for j in range(W):
        if not grid[i][j]:
            continue
        for dx, dy in zip(DX, DY):
            x = i + dx
            y = j + dy
            if x < 0 or x >= H or y < 0 or y >= W:  # 範囲外ならだめ
                continue
            if not grid[x][y]:  # 壁ならだめ
                continue
            orig = W * i + j
            to = orig + dx * W + dy
            wf[orig][to] = 1
            wf[to][orig] = 1

wf = floyd_warshall(wf)
wf[wf >= inf] = 0.
ans = int(wf.max())
print(ans)

Submission status: Accepted

Solution code:
import queue

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

for i in range(h):
	mazeRow = list(input())
	maze.append(mazeRow)
	
maxRootCnt = 0
#スタート→ゴール全探索（ま？）
for roop_h in range(h):
	for roop_w in range(w):
		if maze[roop_h][roop_w] == '#':
			continue

		isSearched =  [[0] * w for i in range(h)]
		isLevel =  [[0] * w for i in range(h)]
		nowTansakuCnt = 0

		q = queue.Queue()
		q.put([roop_h,roop_w])

		# 探索済マスセット
		isSearched[roop_h][roop_w] = 1
		isLevel[roop_h][roop_w] = 0
		while not q.empty():
			n= q.get()
			nowLevel = isLevel[n[0]][n[1]]
			if nowLevel > maxRootCnt:
				maxRootCnt = nowLevel
			#北
			if n[0] != 0:
				if maze[n[0] -1][n[1]] == '.' and isSearched[n[0] -1][n[1]] == 0:
					q.put([n[0]-1,n[1]])
					isSearched[n[0] -1][n[1]] = 1
					isLevel[n[0] -1][n[1]] = nowLevel + 1
			#南
			if n[0] != h-1:
				if maze[n[0] +1][n[1]] == '.' and isSearched[n[0]+1][n[1]] == 0:
					q.put([n[0]+1,n[1]])
					isSearched[n[0] +1][n[1]] = 1
					isLevel[n[0] +1][n[1]] = nowLevel + 1
				
			#西
			if n[1] != 0:
				if maze[n[0]][n[1]-1] == '.' and isSearched[n[0]][n[1]-1] == 0:
					q.put([n[0],n[1]-1])
					isSearched[n[0]][n[1]-1] = 1
					isLevel[n[0]][n[1]-1] = nowLevel + 1

			#東            
			if n[1] != w-1:
				if maze[n[0]][n[1]+1] == '.' and isSearched[n[0]][n[1]+1] == 0:
					q.put([n[0],n[1]+1])
					isSearched[n[0]][n[1]+1] = 1
					isLevel[n[0]][n[1]+1] = nowLevel + 1
				                    
print(maxRootCnt)

Submission status: Accepted

Solution code:
#d maze master

from collections import deque

def bfs(sx,sy):
    cnt=0
    INF=100100100
    #mazeのまわりを"#"で囲ったので
    dist=[[INF]*(w+2) for _ in range(h+2)]
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]

    que=deque([])
    que.append((sx,sy))
    dist[sx][sy]=0

    #while内でpopして空になったとき(最後の層)まで調べた
    while que:
        q=que.popleft()

        for i in range(4):
            next_x=q[0]+dx[i]
            next_y=q[1]+dy[i]

            if maze[next_x][next_y]!="#" and dist[next_x][next_y]==INF:
                que.append((next_x,next_y))
                dist[next_x][next_y]=dist[q[0]][q[1]]+1
                cnt=dist[next_x][next_y]
                #一番最後の層の距離に更新される
    return cnt

h,w=map(int,input().split())
maze=[]
ans=0
x=""
for i in range(w+2):
    x+="#"
maze.append(x)
for i in range(h):
    s=input()
    s='#'+s+'#'
    maze.append(s)
maze.append(x)
for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i][j]=="#":
            continue
        ans=max(ans,bfs(i,j))
print(ans)