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:
def main():
    import sys
    readline = sys.stdin.buffer.readline

    from collections import deque

    h, w = map(int, readline().split())
    s = [readline().rstrip().decode('utf-8') for _ in range(h)]

    l = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                l.append((i, j))
    dire = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque()
    ans = 0
    for hh, ww in l:
        q.appendleft((hh, ww, 0))
        c = [[0]*w for _ in range(h)]
        while q:
            ha, wa, ca = q.pop()
            if c[ha][wa] == 0:
                c[ha][wa] = 1
                ans = max(ans, ca)
                for dh, dw in dire:
                    hdh, wdw = ha+dh, wa+dw
                    if 0 <= hdh < h and 0 <= wdw < w:
                        if s[hdh][wdw] == '.' and c[hdh][wdw] == 0:
                            q.appendleft((hdh, wdw, ca+1))
    print(ans)

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.buffer.readline

    from collections import deque

    h, w = map(int, readline().split())
    s = ['#'*(w+2)] + ['#' + readline().rstrip().decode('utf-8') + '#' for _ in range(h)] + ['#'*(w+2)]

    l = []
    for i in range(h+2):
        for j in range(w+2):
            if s[i][j] == '.':
                l.append((i, j))
    dire = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque()
    ans = 0
    for hh, ww in l:
        q.appendleft((hh, ww, 0))
        c = [[0]*(w+2) for _ in range(h+2)]
        while q:
            ha, wa, ca = q.pop()
            if c[ha][wa] == 0:
                c[ha][wa] = 1
                ans = max(ans, ca)
                for dh, dw in dire:
                    hdh, wdw = ha+dh, wa+dw
                    if s[hdh][wdw] == '.' and c[hdh][wdw] == 0:
                        q.appendleft((hdh, wdw, ca+1))
    print(ans)

main()

Submission status: Accepted

Solution code:
def main():
	H, W = [int(x) for x in input().split(" ")]
	S = []
	S.append(["X"] * (W + 2))
	h = 0
	w = 0
	for i in range(H):
		row = list(input())
		S.append(["X"] + row + ["X"])
		if not h and not w and row.count(".") > 0:
			h = i + 1
			w = row.index(".") + 1
	S.append(["X"] * (W + 2))

	ans = []
	for i in range(H):
		for j in range(W):
			ans.append(BFS(S, i + 1, j + 1, H + 2, W + 2))
	print(max(ans))

def BFS(M, i, j, H, W):
	if M[i][j] != ".":
		return 0
	to_visit = [{"row": i, "col": j, "step": 0}]
	checked = [[0] * W for x in range(H)]
	checked[i][j] = 1
	z = [[0] * W for x in range(H)]
	while len(to_visit):
		visiting = to_visit.pop(0)
		r0 = visiting["row"]
		c0 = visiting["col"]
		s0 = visiting["step"]
		z[r0][c0] = s0
		for d in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
			r = r0 + d[0]
			c = c0 + d[1]
			s = s0 + 1
			if checked[r][c] == 0 and M[r][c] == ".":
				to_visit.append({"row": r, "col": c, "step": s})
				checked[r][c] = 1
	a = 0
	for i in range(len(z)):
		for j in range(len(z[i])):
			if a < z[i][j]:
				a = z[i][j]
	return a

main()

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    H,W = i_map()
    dy_dx=[[1,0],[0,1],[-1,0],[0,-1]]
    rc=[input() for i in range(H)]
    ans = 0

    for sy in range(H):
        for sx in range(W):
            if rc[sy][sx] == "#":
                continue
            dist=[[-1 for _ in range(W)] for _ in range(H)]
            dist[sy][sx] = 0
            d=deque()
            d.append([sx,sy])
            while d:
                nx, ny = d.popleft()
                for dy,dx in dy_dx:
                    y,x = ny+dy,nx+dx
                    if 0<=y<H and 0<=x<W and rc[y][x] != "#" and dist[y][x] == -1:
                        dist[y][x] = dist[ny][nx] + 1
                        d.append([x,y])
            ans = max(ans, max(list(itertools.chain.from_iterable(dist))))
    print(ans)


if __name__=="__main__":
    main()

Submission status: Accepted

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

maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for j in s:
    if j == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

def bfs(start):
  maze2 = copy.deepcopy(maze)
  #print(maze2)
  pos = [start]
  max_depth = 0
  maze2[start[0]][start[1]] = 2
  while len(pos):
    x, y, depth = pos.pop(0)
    max_depth = max(depth, max_depth)
    
    if maze2[x-1][y] < 2:
      pos.append([x-1,y,depth + 1])
      maze2[x-1][y] = 2
    if maze2[x+1][y] < 2:
      pos.append([x+1,y,depth + 1])
      maze2[x+1][y] = 2
    if maze2[x][y-1] < 2:
      pos.append([x,y-1,depth +1])
      maze2[x][y-1] = 2
    if maze2[x][y+1] < 2:
      pos.append([x,y+1,depth +1])
      maze2[x][y+1] = 2
  return max_depth

ans = 0
for i in range(h):
  for j in range(w):
      start = [i+1,j+1,0]
      maze2 = maze
      if maze[i+1][j+1] != 9:
        #print(bfs(start))
        ans = max(ans,bfs(start))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

sl = []
flag = False
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            sl.append([i, j])

q = deque()
dire = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = 0
for sh, sw in sl:
    c = [[0]*w for _ in range(h)]
    q.append((sh, sw, 0))
    while q:
        ph, pw, k = q.pop()
        if c[ph][pw] == 0:
            ans = max(ans, k)
            c[ph][pw] = 1
            for dh, dw in dire:
                hdh, wdw = ph+dh, pw+dw
                if 0 <= hdh < h and 0 <= wdw < w and c[hdh][wdw] == 0:
                    if s[hdh][wdw] == '.':
                        q.appendleft((hdh, wdw, k+1))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 0

for startx in range(w):
    for starty in range(h):
        if grid[starty][startx] == "#":
            continue

        dist = [[10000]*w for _ in range(h)]
        dist[starty][startx] = 0
        maxDist = 0

        q = deque([(startx, starty)])

        while q:
            curx, cury = q.popleft()

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

            for xo, yo in adj:
                x, y = curx + xo, cury + yo

                if x < 0 or x >= w or y < 0 or y >= h:
                    continue
                if grid[y][x] == "#":
                    continue

                newDist = dist[cury][curx] + 1
                if newDist < dist[y][x]:
                    dist[y][x] = newDist
                    q.append((x, y))

                    maxDist = max(maxDist, newDist)

        ans = max(ans, maxDist)

print(ans)

Submission status: Accepted

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

def bfs(start):
    already = {}
    queue = []
    counter = 0
    queue.append((start[0], start[1], 0))
    already[start] = True
    max_depth = 0
    while counter < len(queue):
        y, x, depth = queue[counter]
        if depth > max_depth:
            max_depth = depth
        for move in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            new_y = y + move[0]
            new_x = x + move[1]
            if new_y >= 0 \
            and new_y < H \
            and new_x >= 0 \
            and new_x < W \
            and S[new_y][new_x] == '.' \
            and (new_y, new_x) not in already:
                already[(new_y, new_x)] = True
                queue.append((new_y, new_x, depth+1))
        counter += 1
    return max_depth

answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        depth = bfs((i, j))
        if answer < depth:
            answer = depth
print(answer)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import copy
from collections import deque

def yn(b):
    print("Yes" if b==1 else "No")
    return

def sagasu(h,w,mp,sh,sw):
    d = deque()
    x=sw
    y=sh
    d.append([y,x,0])
    while len(d)>0:
        y,x,cnt=d.popleft()
        if mp[y][x]==-2 or mp[y][x] > cnt:
            mp[y][x]=cnt
            nxt=[[y-1,x],[y+1,x],[y,x-1],[y,x+1]]
            for nx in nxt:
                y2=nx[0]
                x2=nx[1]
                if y2 < 0:
                    continue
                if y2 >= h:
                    continue
                if x2 < 0:
                    continue
                if x2 >= w:
                    continue
                if mp[y2][x2] == -2 or mp[y2][x2] > cnt:
                    d.append([y2,x2,cnt+1])
    ret=-1
    for y in range(h):
        for x in range(w):
            ret=max(ret,mp[y][x])
    return ret
def resolve():
    readline=sys.stdin.readline

    h,w=map(int, readline().rstrip().split())

    mp=[[0 for i in range(w)] for j in range(h)]
    for y in range(h):
        ss=readline().rstrip()
        for x in range(w):
            if ss[x]=="#":
                mp[y][x]=-1 #kabe
            else:
                mp[y][x]=-2 #miti
    ans=0
    for y in range(h):
        for x in range(w):
            if mp[y][x]==-2:
                mp2=copy.deepcopy(mp)
                n=sagasu(h,w,mp2,y,x)
                ans=max(ans,n)
    print(ans)
    
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
import queue
import numpy as np

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


def solveMaze(s):
    q = queue.Queue()
    q.put([s[0],s[1],0])
    times = [[999999999 for j in range(W)] for i in range(H)]
    tmpAns = 0
    times[s[0]][s[1]] = 0
    while not q.empty():
        now = q.get()
        tmpAns = max(tmpAns, now[2])
        for i in range(4):
            nextH = now[0] + int(dir4[i][0])
            nextW = now[1] + int(dir4[i][1])
            nextTime = now[2] + 1

            if nextH < 0 or nextH >= H or nextW < 0 or nextW >=W or maze[nextH][nextW] == "#" or times[nextH][nextW] <= nextTime:
                continue
            else:
                times[nextH][nextW] = nextTime
                q.put([nextH, nextW, nextTime])

    return tmpAns


ans = 0

for sH in range(H):
    for sW in range(W):
        if maze[sH][sW] == ".":
            ans = max(ans, solveMaze([sH, sW]))

print(ans)

Submission status: Accepted

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

inf=1000000000
field=[]
for i in range(H):
  row=list(input())
  for j in range(len(row)):
    if row[j]=='#':row[j]=-1
    else:row[j]=inf
  field.append(row)
ans=inf

def isIn(x,y):
  if x<0 or x>=W:return False
  if y<0 or y>=H:return False
  return True
vector=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]==-1:continue
    l=deque([[j,i]])
    f=copy.deepcopy(field)
    f[i][j]=0
    tmp=0
    #print('--start--')
    while l:
      x,y=l.popleft()
      #print(x,y)
      #i,jを訪問
      for v in vector:
        if not isIn(x+v[1],y+v[0]):continue
        if f[y+v[0]][x+v[1]]<=tmp:continue
        f[y+v[0]][x+v[1]]=f[y][x]+1
        l.append([x+v[1],y+v[0]])
        tmp=max(f[y+v[0]][x+v[1]],tmp)
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy

H,W=map(int,input().split())
S=[[x for x in input()] for _ in range(H)]
start_list=[]
length=[[-1]*W for _ in range(H)]
ans=0

for i in range(H):
  for j in range(W):
    if S[i][j]=='.':
      start_list.append((i,j))

for start in start_list:
  h,w=start
  d=deque([(h,w)])
  T=copy.deepcopy(S)
  L=copy.deepcopy(length)
  L[h][w]=0
  T[h][w]='#'
  while d:
    h,w=d.popleft()
    
    if h-1>=0 and T[h-1][w]=='.':
      d.append((h-1,w))
      L[h-1][w]=L[h][w]+1
      T[h-1][w]='#'
      ans=max(ans,L[h-1][w])
      
    if h+1<=H-1 and T[h+1][w]=='.':
      d.append((h+1,w))
      L[h+1][w]=L[h][w]+1
      T[h+1][w]='#'
      ans=max(ans,L[h+1][w])
      
    if w-1>=0 and T[h][w-1]=='.':
      d.append((h,w-1))
      L[h][w-1]=L[h][w]+1
      T[h][w-1]='#'
      ans=max(ans,L[h][w-1])
      
    if w+1<=W-1 and T[h][w+1]=='.':
      d.append((h,w+1))
      L[h][w+1]=L[h][w]+1
      T[h][w+1]='#'
      ans=max(ans,L[h][w+1])

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
m=[]
for i in range(h):
  m.append(list(map(lambda x:int(x=="#"),list(input())))+[1,1])
m+=[[1 for i in range(w+2)]]*2
mx=0
d=[(1,0),(-1,0),(0,1),(0,-1)]
for x in range(h):
  for y in range(w):
        if m[x][y]:
          continue
        s=[(x,y)]
        c=-1
        v=[[0 for i in range(w)] for i in range(h)]
        v[x][y]=1
        while s:
          ns=[]
          for i in s:
            for j in d:
              if m[i[0]+j[0]][i[1]+j[1]] or v[i[0]+j[0]][i[1]+j[1]]:
                continue
              v[i[0]+j[0]][i[1]+j[1]]=1
              ns.append((i[0]+j[0],i[1]+j[1]))
          s=ns
          c+=1
        mx=max(mx,c)
print(mx)

Submission status: Accepted

Solution code:
from copy import deepcopy  

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
ans = 0
queue = [[1,0],[-1,0],[0,1],[0,-1]]

def now(n,s):
    t = []
    for i in queue:
        j = n[0] + i[0]
        k = n[1] + i[1]
        if 0 <= j < H and 0 <= k < W:
            if s[j][k] == ".":
                t.append([j,k])
                s[j][k] = "#"
    return [t,s]
        

def bfs(trust, a, s):
    t = []
    for i in trust:
        tt, s = now(i,s)
        t += tt
    if len(t) == 0:
        return a
    else:
        a = a + 1
        return bfs(t, a, s)


for i in range(H):
    for j in range(W):
        s = deepcopy(S)
        if S[i][j] == ".":
            s[i][j] = "#"
            ans = max(ans, bfs([[i,j]], 0, s))
print(ans)

Submission status: Accepted

Solution code:
from queue import deque

H, W = map(int,input().split())
S = list(list(input()) for _ in range(H))
ans = 0

for h in range(H):
  for w in range(W):
    if S[h][w] == ".":
      D = [[-1] * W for _ in range(H)]
      D[h][w] = 0
      Q = deque()
      Q.append((h, w))
      
      while Q:
        y, x = Q.popleft()

        for i, j in (1, 0), (-1, 0), (0, 1), (0, -1):
          y2, x2 = y + i, x + j

          if 0 <= y2 < H and 0 <= x2 < W and S[y2][x2] == "." and D[y2][x2] == -1:
            Q.append((y2, x2))
            D[y2][x2] = D[y][x] + 1

      for i in range(H): ans = max(ans, max(D[i]))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans = 0

for a in range(h):
    for b in range(w):
        if maze[a][b] == ".":
            DQ = deque([(a, b)])
            visit = [[-1] * w for _ in range(h)]
            visit[a][b] = 0
            tmp = 0
            while DQ:
                px, py = DQ.popleft()
                for i in range(4):
                    nx = px + dx[i]
                    ny = py + dy[i]
                    if 0<=nx<=h-1 and 0<=ny<=w-1 and maze[nx][ny]=="." and visit[nx][ny]==-1:
                        visit[nx][ny] = visit[px][py] + 1
                        tmp = visit[nx][ny]
                        DQ.append((nx, ny))
            ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import collections # deque, Counter
# import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
# import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # Python3.5以前 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # Python3.6以降
# --------------------------------------------------------------

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

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

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

cnt = 0

for j in range(H):
    for k in range(W):
            if maze[j][k]=='#':
                continue
            else:
                sy = j
                sx = k

                seen = [[-1 for _ in range(W)] for _ in range(H)]
                seen[sy][sx] = 0

                que  = collections.deque()  # 発見済未訪問な頂点
                que.append([sy,sx])

                while(len(que)!=0):
                    p = que.popleft()
                    for i in range(4):
                        ny = p[0] + dy[i]
                        nx = p[1] + dx[i]
                        if (ny >= 0 and nx >=0 and ny < H and nx < W and seen[ny][nx] == -1 and maze[ny][nx] != '#'):
                            seen[ny][nx] = seen[p[0]][p[1]] + 1
                            que.append([ny,nx])

                cnt = max(cnt, max([x for row in seen for x in row]))

print(cnt)

Submission status: Accepted

Solution code:
import sys
import itertools
import collections


def search(H, W, S, start):
    wall_i = ord(b'#')
    used = [[-1 for h in range(W)] for w in range(H)]

    qu = collections.deque()
    qu.append(start)
    used[start[0]][start[1]] = 0

    while qu:
        h, w = qu.popleft()
        cost = used[h][w]
        for h0, w0 in ((h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)):
            if not (0 <= h0 < H and 0 <= w0 < W):
                continue
            if used[h0][w0] != -1:
                continue
            if S[h0][w0] == wall_i:
                continue

            used[h0][w0] = cost + 1
            qu.append((h0, w0))

    return max(cost for costs in used for cost in costs)


def resolve(in_):
    H, W = map(int, next(in_).split())
    S = tuple(s.strip() for s in itertools.islice(in_, H))

    road_i = ord(b'.')

    roads = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == road_i:
                roads.append((h, w))
    
    ans = max(search(H, W, S, start) for start in roads)
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import copy

H,W=map(int,input().split())
MAP=[list(input()) for y in range(H)]

def Maze(_x, _y):
  MAP2=copy.deepcopy(MAP)
  q=deque([[_x,_y]])
  MAP2[_y][_x]=0
  while q:
    xy=q.popleft()
    for d in [(0,-1),(-1,0),(0,1),(1,0)]:
      x2,y2=xy[0]+d[0],xy[1]+d[1]
      if x2<0 or y2<0 or x2>=W or y2>=H:
        continue
      if MAP2[y2][x2]=='.':
        q.append([x2,y2])
        MAP2[y2][x2]=MAP2[xy[1]][xy[0]]+1
  
  maxM=0
  for y in range(H):
    for x in range(W):
      if type(MAP2[y][x])==int:
        maxM=max(maxM, MAP2[y][x])
  return maxM
  

ans=0
for y in range(H):
  for x in range(W):
    if MAP[y][x]=='.':
      ans=max(ans, Maze(x,y))
print(ans)

Submission status: Accepted

Solution code:
#import sys
#input=sys.stdin.readline()
#print(input)

#import pprint
h,w = map(int,input().split())
s = [list(input())for i in range(h)]
#print("s")
#pprint.pprint(s,width=w*10)

visited = [[0 for i in range(w)] for j in range(h)]#sと同じ形に0を配置した表
quene = []#移動元Nowとなることができる座標のリスト
ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            quene.append([i,j])#スタート地点をQueneに追加
            visited[i][j]=1#スタート地点を1にする
#            print("visited")
#            pprint.pprint(visited,width=w*10)
#            print(quene)

            dy_dx=[[1,0],[-1,0],[0,1],[0,-1]]#１回に移動出来る量

            while len(quene)>=1:
                now=quene.pop(0)#queneの左端の項を取り出す
#                print(now)
                for k in range(4):
                    y=now[0]+dy_dx[k][0]#nowから移動先[x,y]へのy軸方向の移動量
                    x=now[1]+dy_dx[k][1]#nowから移動先[x,y]へのx軸方向の移動量
                    if 0<=y<h and 0<=x<w:#移動先が表を飛び出していなければOK
                        if s[y][x]!="#" and visited[y][x]==0:#移動先が壁でない、かつ行ったことがなければOK
                            visited[y][x]=visited[now[0]][now[1]]+1#移動先の値をNowの値+1にする
                            quene.append([y,x])#Queneに移動先座標を追加
#                           pprint.pprint(visited,width=w*10)
#       一つのスタート地点から幅優先探索を終わらせたら、移動量の最大値を求める
        for l in range(h):
            for m in range(w):
                ans = max(ans,visited[l][m])#これまでの最大値と今回得られた移動量の最大値を比較し、大きいほうを新しい答えにする
        visited = [[0 for i in range(w)] for j in range(h)]#visited初期化
print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
R = [[0 for j in range(W)] for i in range(H)]
ans = 0
dx = [[-1, 0], [1, 0], [0, -1], [0, 1]]
for i in range(H):
  inp = input()
  for j in range(W):
  	if inp[j] == "#":
  	  R[i][j] = 1
for s in range(H * W):
  sh = s // W
  sw = s % W
  if R[sh][sw] == 1:
    continue
  D = [[-1 for j in range(W)] for i in range(H)]
  D[sh][sw] = 0
  d = deque([(sh, sw)])
  while len(d):
    a = d.pop()
    for k in range(4):
      hn = a[0] + dx[k][0]
      wn = a[1] + dx[k][1]
      if 0 <= hn < H and 0 <= wn < W and R[hn][wn] == 0 and D[hn][wn] == -1:
        D[hn][wn] = D[a[0]][a[1]] + 1
        ans = max(ans, D[hn][wn])
        d.appendleft((hn, wn))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

field = []
for i in range(H):
    field.append(input())

conn = [[[] for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            for e in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                h, w = i + e[0], j + e[1]
                if 0 <= h < H and 0 <= w < W and field[h][w] == '.':
                    conn[i][j].append([h, w])
d = 0
for i in range(H):
    for j in range(W):
        l = 0
        q = deque([[i, j]])
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[i][j] = 0
        while q:
            v = q.popleft()
            for w in conn[v[0]][v[1]]:
                if dist[w[0]][w[1]] == -1:
                    q.append(w)
                    dist[w[0]][w[1]] = dist[v[0]][v[1]] + 1
                    l = dist[w[0]][w[1]]

        d = max(d, l)

print(d)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
t = ((0,1),(1,0),(-1,0),(0,-1))
m = 0
for sy in range(h):
    for sx in range(w):
        if s[sy][sx] == "#":
            continue
        ss = deepcopy(s)
        ss[sy][sx] = "#"
        q = deque([(0,sy,sx)])
        max_cost = 0
        my,mx = 0,0
        while(q):
            cost,y,x = q.popleft()
            max_cost = max(max_cost,cost)
            cost += 1
            for i,j in t:
                ny = y+i
                nx = x+j
                if 0 <= ny < h and 0 <= nx < w:
                    if ss[ny][nx] == ".":
                        q.append((cost,ny,nx))
                        ss[ny][nx] = "#"
        m = max(m,max_cost)
print(m)

Submission status: Accepted

Solution code:
import math

H, W = map(int, input().split())
S = [list(map(lambda x:x == '.', input())) for _ in range(H)]

d = [[math.inf] * (H * W) for _ in range(H * W)]

def node2pos(i):
    h = i // W
    w = i % W
    return h, w

for i in range(H * W):
    for j in range(H * W):
        h1, w1 = node2pos(i)
        h2, w2 = node2pos(j)
        if (abs(h1-h2) == 1 and w1 == w2) or (abs(w1-w2) == 1 and h1 == h2):
            if S[h1][w1] and S[h2][w2]:
                d[i][j] = 1
            if S[h1][w1]:
                d[i][i] = 1

for k in range(H * W):
    for i in range(H * W):
        for j in range(H * W):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for i in range(H * W):
    for j in range(H * W):
        if d[i][j] != math.inf:
            ans = max(ans, d[i][j])

print(ans)

Submission status: Accepted

Solution code:
import heapq


def abc151d_maze_master():
    h, w = map(int, input().split())
    s = []
    max_val = 0
    for i in range(h):
        s.append(input())
    for hi in range(h):
        for wi in range(w):
            if s[hi][wi] == '#': continue
            flg = [[-1] * w for _ in range(h)]
            flg[hi][wi] = 0
            q = [(0, hi, wi)]
            heapq.heapify(q)
            while len(q) > 0:
                d, hj, wj = heapq.heappop(q)
                for dh, dw in zip([0, 0, 1, -1], [1, -1, 0, 0]):
                    if 0 <= hj + dh < h and 0 <= wj + dw < w and s[hj + dh][wj + dw] != '#' and \
                            (flg[hj + dh][wj + dw] == -1 or flg[hj + dh][wj + dw] > flg[hj][wj] + 1):
                        heapq.heappush(q, (d + 1, hj + dh, wj + dw))
                        flg[hj + dh][wj + dw] = flg[hj][wj] + 1
                # print(q)
            max_val = max(max_val, max([max(v) for v in flg]))
    print(max_val)


abc151d_maze_master()

Submission status: Accepted

Solution code:
from collections import deque

def input_bordered_grid(h, w, wall):
    grid = [wall * (w + 2)]
    for _ in range(1, h+1):
        grid.append(wall + input() + wall)
    grid.append(wall * (w + 2))
    return grid

h, w = map(int, input().split())
grid = input_bordered_grid(h, w, '#')

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

longest = 0
for sy in range(1, h+1):
    for sx in range(1, w+1):
        if grid[sy][sx] == '#':
            continue
        dist = [[-1] * (w+2) for _ in range(h+2)]
        dist[sy][sx] = 0
        q = deque()
        q.append((sy, sx))
        while q:
            y, x = q.popleft()
            longest = max(longest, dist[y][x])
            for dy, dx in move:
                yy = y + dy
                xx = x + dx
                if dist[yy][xx] == -1 and grid[yy][xx] == '.':
                    q.append((yy, xx))
                    dist[yy][xx] = dist[y][x] + 1
print(longest)

Submission status: Accepted

Solution code:
from collections import deque

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

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

ans=0

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


for i in range(h):
  for j in range(w):
        Q=deque()
        Q.append((i,j,0))
        
        if maze[i][j]=='#':
          continue

        dp=[[-1]*w for i in range(h)]

        dp[i][j]=0

        while Q:
          p=Q.popleft()
          ans=max(ans,p[2])
          for k in range(4):
            nx=p[0]+dx[k]
            ny=p[1]+dy[k]

            if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and dp[nx][ny]==-1:
              Q.append((nx,ny,p[2]+1))
              dp[nx][ny]=p[2]+1


print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(i, j):
    dist = [[0] * w for _ in range(h)]
    q = deque()
    q.append((i, j))
    dist[i][j] = 1
    while q:
        nx, ny = q.pop()
        for dx, dy in D:
            X, Y = nx + dx, ny + dy
            if X < 0 or Y < 0 or X >= h or Y >= w:
                continue
            if m[X][Y] == "#":
                continue
            if dist[X][Y] != 0:
                continue

            q.appendleft((X, Y))
            dist[X][Y] = 1 + dist[nx][ny]
    mx = 0
    for i in dist:
        mx = max(mx, max(i))
    return mx


h, w = map(int, input().split())
m = [input() for _ in range(h)]
D = [(-1, 0), (0, -1), (1, 0), (0, 1)]
ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == ".":
            ans = max(ans, bfs(i, j))

print(ans - 1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
m = [list(input()) for _ in range(h)]
D = [(-1, 0), (0, -1), (1, 0), (0, 1)]


def bfs(i, j):
    dist = [[0] * w for _ in range(h)]
    que = deque()
    que.append((i, j))
    dist[i][j] = 1

    while que:
        nx, ny = que.pop()
        for dx, dy in D:
            if nx + dx < 0 or ny + dy < 0 or nx + dx >= h or ny + dy >= w:
                continue
            if m[nx + dx][ny + dy] == "#":
                continue
            if dist[nx + dx][ny + dy] != 0:
                continue

            que.appendleft((nx + dx, ny + dy))
            dist[nx + dx][ny + dy] = 1 + dist[nx][ny]
    mx = 0
    for i in dist:
        mx = max(mx, max(i))
    return mx


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

print(ans - 1)