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 maxelm(matrix):
	ans = 0
	for i in matrix:
		m = max(i)
		ans = max(ans, m)
	return ans
	
def resolve():
	import numpy as np
	from collections import deque

	h, w = map(int, input().split())
	s = [input() for i in range(h)] # [[input()] for ...] は誤答 （文字列も配列であることを考えると3重配列になっちゃう） 
	directions = [[0, 1], [0, -1], [1, 0], [-1, 0]] # [y軸, x軸]
	ans = 0

	for sh in range(h): # start hight
		for sw in range(w):
			if s[sh][sw] == "#":
				continue
			distance = [[-1 for j in range(w)] for i in range(h)]
			distance[sh][sw] = 0
			q = deque([[sh, sw]]) # 1段目の[]はdequeの引数がイテラブルであるため、2段目の[]はy軸x軸のペアを表現するため

			while q:
				y, x = q.popleft() # アンパックしてくれる
				for i, j in directions:
					ny, nx = y+i, x+j

					# エリア内判定
					if not ((0 <= ny < h) and (0 <= nx < w)):
						continue
					# 壁判定
					elif s[ny][nx] == "#":
						continue
					# 訪問済み判定
					elif distance[ny][nx] != -1:
						continue

					distance[ny][nx] = distance[y][x] + 1
					q.append([ny, nx]) # q.append([[ny, nx]]) は誤答
			ans = max(ans, maxelm(distance))
			#ans = max(ans, np.max(distance))
	print(ans)
resolve()

Submission status: Accepted

Solution code:
def resolve():
	import numpy as np
	from collections import deque

	h, w = map(int, input().split())
	s = [input() for i in range(h)] # [[input()] for ...] は誤答 （文字列も配列であることを考えると3重配列になっちゃう） 
	directions = [[0, 1], [0, -1], [1, 0], [-1, 0]] # [y軸, x軸]
	ans = 0

	for sh in range(h): # start hight
		for sw in range(w):
			if s[sh][sw] == "#":
				continue
			distance = [[-1 for j in range(w)] for i in range(h)]
			distance[sh][sw] = 0
			q = deque([[sh, sw]]) # 1段目の[]はdequeの引数がイテラブルであるため、2段目の[]はy軸x軸のペアを表現するため

			while q:
				y, x = q.popleft() # アンパックしてくれる
				for i, j in directions:
					ny, nx = y+i, x+j

					# エリア内判定
					if not ((0 <= ny < h) and (0 <= nx < w)):
						continue
					# 壁判定
					elif s[ny][nx] == "#":
						continue
					# 訪問済み判定
					elif distance[ny][nx] != -1:
						continue

					distance[ny][nx] = distance[y][x] + 1
					q.append([ny, nx]) # q.append([[ny, nx]]) は誤答
			#ans = max(ans, max(max(distance)))
			ans = max(ans, np.max(distance))
	print(ans)
resolve()

Submission status: Accepted

Solution code:
def resolve():
	h, w = map(int, input().split())
	s = [input() for i in range(h)]
	import numpy as np
	from collections import deque
	directions = [[0, 1], [0, -1], [1, 0], [-1, 0]] # [y軸, x軸]
	ans = 0
	for sh in range(h): # start hight
		for sw in range(w):
			if s[sh][sw] == "#":
				continue
			distance = [[-1 for j in range(w)] for i in range(h)]
			distance[sh][sw] = 0
			q = deque([[sh, sw]])
			while q:
				y, x = q.popleft()
				for i, j in directions:
					ny = y+i
					nx = x+j
					# エリア内判定
					if not ((0 <= ny < h) and (0 <= nx < w)):
						continue
					# 壁判定
					elif s[ny][nx] == "#":
						continue
					# 訪問済み判定
					elif not distance[ny][nx] == -1:
						continue
					distance[ny][nx] = distance[y][x] + 1
					q.append([ny, nx])
			ans = max(ans, np.max(distance))
	print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()
 
from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    visited = [False] * (H * W)
    q = deque([(start[0], start[1], 0)])
    max_d = 0
    while q:
        (i, j, d) = q.popleft()
        max_d = max(max_d, d)
        if visited[i * W + j]:
            continue
        visited[i * W + j] = True
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if visited[(i + dy) * W + j + dx]:
                    continue
                q.append((i + dy, j + dx, d + 1))
    return max_d
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()
 
from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    visited = [False] * (H * W)
    q = deque([(start[0], start[1], 0)])
    max_d = 0
    while q:
        (i, j, d) = q.popleft()
        max_d = max(max_d, d)
        visited[i * W + j] = True
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if visited[(i + dy) * W + j + dx]:
                    continue
                visited[(i + dy) * W + j + dx] = True
                q.append((i + dy, j + dx, d + 1))
    return max_d
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()
 
from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([start])
    dist[start[0] * W + start[1]] = 0
    max_d = 0
    while q:
        (i, j) = q.popleft()
        d = dist[i * W + j]
        max_d = max(d, max_d)
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx))
    return max_d
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([(start[0], start[1], 100)])
    dist[start[0] * W + start[1]] = 0
    while q:
        (i, j, z) = q.popleft()
        d = dist[i * W + j]
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx, 100))
    return max(x for x in dist if x < INF)

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([start])
    dist[start[0] * W + start[1]] = 0
    while q:
        (i, j) = q.popleft()
        d = dist[i * W + j]
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx))
    return max(x for x in dist if x < INF)

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

inf = 10**15
h, w = map(int, input().split())
#隣接リスト
#G = defaultdict(lambda:[])
G = [[inf]*(h*w) for _ in range(h*w)]
#################################

def warshall_floyd(d):
    #d[i][j]:iからjに行く最短経路
    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])
    return d
  
li = []
for j in range(h):
    g = list(input())
    temp = []
    for i in g:
      if i=='.':
        temp.append(0)
      else:
        temp.append(1)
    li.append(temp)
for i in range(h):
    for j in range(w-1):
        if li[i][j]==0 and li[i][j+1]==0:
            G[i*w+j][i*w+j+1] = 1
            G[i*w+j+1][i*w+j] = 1
            G[i*w+j][i*w+j] = 0
            G[i*w+j+1][i*w+j+1] = 0
for i in range(h-1):
    for j in range(w):
        if li[i][j] ==0 and li[i+1][j]==0:
            G[i*w+j][i*w+w+j] = 1
            G[i*w+j+w][i*w+j] = 1
            G[i*w+j+w][i*w+j+w] = 0
            G[i*w+j][i*w+j] = 0
    
#################################
d = warshall_floyd(G)
max_ = 0
for i in range(h*w):
  for j in range(h*w):
    if d[i][j] < inf:
      max_ = max(max_, d[i][j])
print(max_)

Submission status: Accepted

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

res = 0
move = [(1,0),(0,1),(0,-1),(-1,0)]
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      visited = [[False]*W for _ in range(H) ]
      q = deque([(i,j)])
      depth = -1
      while q:
        depth += 1
        L = len(q)
        new = deque([])
        for _ in range(L):
          i,j = q.popleft()
          if visited[i][j]: continue
          visited[i][j] = True
          for y,x in move:
            if 0<=i+y<H and 0<=j+x<W and not visited[i+y][j+x]:
              if maze[i+y][j+x] == ".":
                new.append((i+y,j+x))
        q = new
      res = max(res, depth)

print(res)

Submission status: Accepted

Solution code:
def bfs(x0, y0, maze, dis):
    from collections import deque
    max_x = len(maze[0])
    max_y = len(maze)

    dis[y0][x0] = 0
    dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    q = deque()
    q.append([x0, y0, dis[y0][x0]])

    while len(q) > 0:
        x, y, d = q.popleft()

        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy

            if 0 > nx or max_x <= nx or 0 > ny or max_y <= ny:
                continue
            if maze[ny][nx] == "#":
                continue
            if dis[ny][nx] != -1:
                continue

            dis[ny][nx] = d + 1
            q.append([nx, ny, dis[ny][nx]])

    return


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

s = [[] for _ in range(h)]

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

ans = 0
for i in range(h):
    for j in range(w):
        dis = [[-1] * w for _ in range(h)]

        if s[i][j] != "#":
            bfs(j, i, s, dis)

        d = 0

        for k in range(h):
            for l in range(w):
                d = max(d, dis[k][l])

        ans = max(ans, d)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

h,w=list(map(int,input().split()))
graph=[input() for _ in range(h)]#graph初期化

def f(x,y):#start地点(x,y)
  x-=1;y-=1
  dist=[[-1 for j in range(w)] for i in range(h)]#distance設定
  dist[x][y]=0#スタート地点は初期値0
  que = deque([(x,y,0)])#スタート地点とdist初期値を入力 

  while que:#queの中身がある限り
    r,s,t = que.popleft()
    for i,j in [(-1,0),(0,-1),(1,0),(0,1)]:#これでi,jとれるの
      if not (0<=r+i<h and 0<=s+j<w):#座標がh,w内でなければ探索しない
        continue
      if dist[r+i][s+j]>=0:#すでに訪れていたら探索しない。>=
        continue
      if graph[r+i][s+j]=="#":#壁なら探索しない
        continue
      dist[r+i][s+j]=t+1#距離を前回の＋1
      que.append([r+i,s+j,t+1])#訪れてないのでqueに今の地点を追加する
  return np.amax(dist)#2次元配列の最大値を返す
ans=0
for i in range(1,h+1):#全探索（indexのため1~h+1まで）
  for j in range(1,w+1):
    if graph[i-1][j-1]=="#":#壁なら探索しない
      continue
    ans=max(ans,f(i,j))
print(ans)

Submission status: Accepted

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

from collections import deque

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

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

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

Submission status: Accepted

Solution code:
h,w=list(map(int,input().split()))
maze1=[]
for i in range(h):
  maze1.append(list(input()))
from collections import deque
import copy

#スタートする座標をa,bとしておく
def bfs(a,b):
  maze=copy.deepcopy(maze1)
  dp=[[0 for i in range(w)] for j in range(h)]
  q=deque([[a,b]])
  #まず自分がいるところを＃に変えておく
  maze[a][b]="#"
  while len(q)>0:
    i,j=q.popleft()
    if 0<=i+1<=h-1 and 0<=j<=w-1 and maze[i+1][j]==".":
      maze[i+1][j]="#" 
      dp[i+1][j]=dp[i][j]+1
      q.append([i+1,j])
    if 0<=i-1<=h-1 and 0<=j<=w-1 and maze[i-1][j]==".":
      maze[i-1][j]="#"
      dp[i-1][j]=dp[i][j]+1
      q.append([i-1,j])
    if 0<=i<=h-1 and 0<=j-1<=w-1 and maze[i][j-1]==".":
      maze[i][j-1]="#"
      dp[i][j-1]=dp[i][j]+1
      q.append([i,j-1])
    if 0<=i<=h-1 and 0<=j+1<=w-1 and maze[i][j+1]==".":
      maze[i][j+1]="#"
      dp[i][j+1]=dp[i][j]+1
      q.append([i,j+1])
  sum=0
  for i in range(h):
    sum=max(max(dp[i]),sum)
  return sum
  
  
ans=0
for k in range(h):
  for l in range(w):
    if maze1[k][l]==".":
      ans=max(bfs(k,l),ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
l=list()
l.append('#'*(w+2))#壁
for i in range(h):
    l.append('#'+input()+'#')
l.append('#'*(w+2))#壁
p=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if l[i][j]=='#':
            continue
        s=[[-1 for a in b] for b in l]
        q=deque([[i,j]])
        s[i][j]=0
        while len(q)>0:
            a,b=q.popleft()
            for x,y in [[1,0],[0,1],[-1,0],[0,-1]]:
                if l[a+x][b+y]=='#' or s[a+x][b+y]>-1:
                    continue
                q.append([a+x,b+y])
                s[a+x][b+y]=s[a][b]+1
        r=0
        for x in s:
            for y in x:
                r=max(y,r)
        p=max(r,p)
print(p)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
road = [(i,j) for i in range(h) for j in range(w) if s[i][j]=='.']

from collections import deque

dists = set()
for r in road:
  d = deque()
  d.append(r)
  dist = {r:0}
  while d:
    x,y = d.popleft()
    if s[x][y] == '#':continue
    for p in [(x,y+1),(x,y-1),(x-1,y),(x+1,y)]:
      if (0<=p[0]<h and 0<=p[1]<w) == False:continue
      if s[p[0]][p[1]] == '#': continue
      if p in dist:continue
      dist[p]=dist[(x,y)]+1
      d.append(p)
  dist_max = max([dist[v] for v in dist])
  dists.add(dist_max)
print(max(dists))

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
L = [str(input()) for _ in range(H)]
ans = 0
for h in range(H):
    for w in range(W):
        if L[h][w] == '#':
            continue
        else:
            flag = [[-1] * W for _ in range(H)]
            depth = [[0] * W for _ in range(H)]
            flag[h][w] = 0
            q = deque([(h, w)])
            while q:
                i, j = q.popleft()
                d = depth[i][j]
                if i != H - 1:
                    if L[i+1][j] == '.' and flag[i+1][j] < 0:
                        flag[i+1][j] = 0
                        depth[i+1][j] = d + 1
                        q.append((i+1, j))
                if i != 0:
                    if L[i-1][j] == '.' and flag[i-1][j] < 0:
                        flag[i-1][j] = 0
                        depth[i-1][j] = d + 1
                        q.append((i-1, j))
                if j != W - 1:
                    if L[i][j+1] == '.' and flag[i][j+1] < 0:
                        flag[i][j+1] = 0
                        depth[i][j+1] = d + 1
                        q.append((i, j+1))
                if j != 0:
                    if L[i][j-1] == '.' and flag[i][j-1] < 0:
                        flag[i][j-1] = 0
                        depth[i][j-1] = d + 1
                        q.append((i, j-1))
                ans = max(ans, d)
print(ans)

Submission status: Accepted

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

A=[]
for i in range(h):
  s=input()
  A.append([s[i] for i in range(w)])
g=[[[]for i in range(w)] for _ in range(h)]

for i in range(h):
  for j in range(w):
    if A[i][j]=='.':
      if i-1>=0:
          if A[i-1][j]=='.':
            g[i][j].append((i-1,j))
      if i+1<h:
          if A[i+1][j]=='.':
            g[i][j].append((i+1,j))          
      if j+1<w:
          if A[i][j+1]=='.':
            g[i][j].append((i,j+1))          
      if j-1>=0:
          if A[i][j-1]=='.':
            g[i][j].append((i,j-1))  
        
from collections import deque
def bfs(a,b):
  time=[[-1]*w for _ in range(h)]
  time[a][b]=0
  stack=deque([])
  stack.append((a,b))
  n=1
  while stack:
    d=stack.popleft()
    for v in g[d[0]][d[1]]:
      if time[v[0]][v[1]]==-1:
        time[v[0]][v[1]]=time[d[0]][d[1]]+1
        stack.append(v)
        
      else:
        continue
     
  timem=0
  for i in range(h):
    for j in range(w):
      timem=max(timem,time[i][j])
  return timem
ans=0
for i in range(h):
  for j in range(w):
    bfsm=bfs(i,j)
    ans=max(ans,bfsm)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
s = [list(input()) 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 s[i][j] == "#":
            continue
        dist = [[-1] * w for _ in range(h)]
        dist[i][j] = 0
        d = deque()
        d.append([i, j])

        while d:
            pos_x, pos_y = d.popleft()
            dist_max = dist[pos_x][pos_y]
            for k in range(4):
                x, y = pos_x + dx[k], pos_y + dy[k]
                if 0 <= x < h and 0 <= y < w and s[x][y] == "." and dist[x][y] == -1:
                    dist[x][y] = dist[pos_x][pos_y] + 1
                    d.append([x, y])

        res = max(res, dist_max)

print(res)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
s = [0]*(h+2)
s[0]  = ["#"]*(w+2)
s[-1] = ["#"]*(w+2)
for i in range(h):
    s[i+1] = ["#"] + list(input()) + ["#"]
ans = 1
for i in range(h+2):
    for j in range(w+2):
        if s[i][j] != ".":
            pass
        else:
            xs,ys = j,i
            qx = deque([])
            qx.append(xs)
            qy = deque([])
            qy.append(ys)
            reach = [[0 for _1 in range(w+2)] for _2 in range(h+2)]
            reach[ys][xs] = 1
            while qx:
                x = qx.popleft()
                y = qy.popleft()

                if s[y-1][x] == "." and reach[y-1][x] == 0:
                    qx.append(x)
                    qy.append(y-1)
                    reach[y-1][x] = reach[y][x] + 1
                if s[y+1][x] == "." and reach[y+1][x] == 0:
                    qx.append(x)
                    qy.append(y+1)
                    reach[y+1][x] = reach[y][x] + 1
                if s[y][x-1] == "." and reach[y][x-1] == 0:
                    qx.append(x-1)
                    qy.append(y)
                    reach[y][x-1] = reach[y][x] + 1
                if s[y][x+1] == "." and reach[y][x+1] == 0:
                    qx.append(x+1)
                    qy.append(y)
                    reach[y][x+1] = reach[y][x] + 1
            m = 1
            for k in range(h+2):
                m = max(m,max(reach[k][:])-1)
            ans = max(ans,m)
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*s=open(0)
M=999
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+20]=u>'#'<(s+['#'*M])[i][j];j+=1;g[k][k+1]=u>'#'<t[j]
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*s=open(0)
M=999
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<(s+['#'*M])[i][j];j+=1
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*s=open(0)
M=999
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 i+=1;j=0
 for u in t:k=~-i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<(s+['#'*M])[i][j];j+=1
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*s=open(0)
M=999
*g,=eval('[0]*M,'*M)
i=0
for t in s:
 j=0
 for u in t:k=i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<(s+['#'*M])[i+1][j];j+=1
 i+=1
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<M])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*s=open(0)
*g,=eval('[0]*500,'*500)
i=-1
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<(s+['#'*20])[i+1][j];j+=1
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<999])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
_,*s=open(0)
r=s+["#"*20]
*g,=eval("[0]*500,"*500)
i=-1
for t in s:
 i+=1;j=0
 for u in t:k=i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<r[i+1][j];j+=1
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<999])))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from scipy.sparse.csgraph import floyd_warshall
INF = float("inf")

h, w = map(int, input().split())
M = [input() for _ in [0]*h]
E = [[0]*h*w for _ in [0]*h*w]
D = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def point(x, y):
    return w * x + y

for i in range(h):
    for j in range(w):
        if M[i][j] == ".":
            for x, y in D:
                I, J = i + x, j + y
                if w > J >= 0 <= I < h and M[I][J] == ".":
                    E[point(i, j)][point(I, J)] = 1

a = floyd_warshall(E)
print(int(a[a != INF].max()))

Submission status: Accepted

Solution code:
#D
import queue
H,W=map(int,input().split())
P=[0 for i in range(H)]
for i in range(H):
    P[i]=str(input())
ans=0
for i in range(H*W):
    s=(i//W,i%W)
    if P[s[0]][s[1]]=="#":
        continue
    st=queue.Queue()
    st.put(s)
    log=[[-1 for i in range(W)] for j in range(H)]
    log[s[0]][s[1]]=0
    while not st.empty():
        y,x=st.get()
        for z,w in [(y+1,x),(y-1,x),(y,x+1),(y,x-1)]:
            if 0>z or 0>w:
                continue
            elif z>=H or w>=W:
                continue
            elif P[z][w]=="." and log[z][w]==-1:
                st.put((z,w))
                log[z][w]=log[y][x]+1
                ans=max(ans,log[z][w])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
h, w = map(int, input().split())
s = []
a = 0
for _ in range(h):
    s.append(list(input()))
mx = [1,-1,0,0]
my = [0,0,1,-1]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            d = [[-1 for a in range(w)] for b in range(h)]
            d[i][j] = 0
            q = deque([(j,i)])
            while q:
                x, y = q.popleft()
                for c in range(4):
                    new_x = x + mx[c]
                    new_y = y + my[c]
                    if 0<=new_x<=w-1 and 0<=new_y<=h-1 and s[new_y][new_x] != "#" and d[new_y][new_x] < 0:
                        q.append((new_x,new_y))
                        d[new_y][new_x] = d[y][x] + 1
                        a = max(a, d[new_y][new_x])
                        
print(a)

Submission status: Accepted

Solution code:
from collections import deque

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

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

m = -1
N = len(l)
for i in range(N-1):
    for j in range(i+1, N):
        start = l[i]
        goal = l[j]
        visited = [[-1]*W for i in range(H)]
        d = deque()
        d.appendleft(start)
        visited[start[0]][start[1]] = 0
        while d:
            now = d.pop()
            for direction in directions:
                next = (now[0]+direction[0], now[1]+direction[1])
                if not (next[0] in range(H) and next[1] in range(W)):
                    continue
                if visited[next[0]][next[1]] != -1:
                    continue
                if S[next[0]][next[1]] == '.':
                    visited[next[0]][next[1]] = visited[now[0]][now[1]] + 1
                    d.appendleft(next)
                if next == goal:
                    m = max(visited[goal[0]][goal[1]], m)
                    d = deque()

print(m)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
maze = []
for i in range(h):
    maze.append(list(input()))
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            d = [[-1 for a in range(w)] for b in range(h)]
            dq = deque([(j,i)])
            d[i][j] = 0
            while dq:
                x,y = dq.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "#" and d[ny][nx] == -1:
                        dq.append((nx,ny))
                        d[ny][nx] = d[y][x]+1
                        ans = max(ans,d[ny][nx])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy
h,w = map(int,input().split())
origin = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
for i in range(h):
    origin.append(list(input()))
for i in range(h):
    if "#" in origin[i]:
        break
else:
    print(h+w-2)
    exit()
for i in range(h):
    for j in range(w):
        if origin[i][j] == ".":
            d = [[0 for j in range(w)] for i in range(h)]
            maze = copy.deepcopy(origin)
            dq = deque([(j,i)])
            while dq:
                x,y = dq.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "#":
                        dq.append((nx,ny))
                        d[ny][nx] = d[y][x]+1
                        ans = max(ans,d[ny][nx])
                maze[y][x] = "#"
            #print(maze)
print(ans)