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:
'''input
3 3
.#.
#..
.#.
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0:
				if maze[x - 1][y] != '#' and mp([x - 1, y]) not in visited:
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n:
				if maze[x + 1][y] != '#' and mp([x + 1, y]) not in visited:
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0:
				if maze[x][y - 1] != '#' and mp([x, y - 1]) not in visited:
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m:
				if maze[x][y + 1] != '#' and mp([x, y + 1]) not in visited:
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		


# main starts
n, m = list(map(int, input().split()))
maze = []
for _ in range(n):
	state = list(input().strip())
	maze.append(state)

# from random import randint
# for _ in range(1000):
# maze = []
# n = randint(1, 20)
# m = randint(1, 20)
# for i in range(n):
# 	temp = []
# 	for j in range(m):
# 		k = randint(1, 2)
# 		if k == 1:
# 			temp.append('.')
# 		else:
# 			temp.append('#')
# 	maze.append(temp)

ans = 0
for i in range(n):
	for j in range(m):
		if maze[i][j] != '#':
			first = [i, j]
			ans = max(ans, bfs(first))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import itertools
import copy

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

def solve(s):
    d = ((1, 0), (-1, 0), (0, -1), (0, 1))
    queue = deque([s])
    steps = [[-1 for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        for i in d:
            ny = cy+i[0]
            nx = cx+i[1]
            # はみ出さないかつ通路であるかつ通ってない
            if (0<=ny<H and 0<=nx<W) and S[ny][nx]=='.' and steps[ny][nx] < 0:
                queue.append([ny, nx])
                steps[ny][nx] = steps[cy][cx] + 1
        
    return max([max(i) for i in steps])

maxStep = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '.':
        maxStep = max(solve([s[0], s[1]]), maxStep)

print(maxStep)

Submission status: Accepted

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

from collections import deque
def main():
    H,W = map(int,input().split())
    S = ["#"*(W+2)]+["#"+input()+"#" for _ in range(H)]+["#"*(W+2)]

    vector = [(1,0),(-1,0),(0,1),(0,-1)]
    answer = 0
    for i in range(H+2):
        for j in range(W+2):
            if S[i][j] == "#":
                continue

            queue = deque()
            queue.append((i,j,0))
            max_dist = 0
            isVisited = [[False]*(W+2) for _ in range(H+2)]

            while queue:
                x,y,dist = queue.popleft()
                if S[x][y] == "." and isVisited[x][y] == False:
                    isVisited[x][y] = True
                    max_dist = dist

                    for lr,ud in vector:
                            queue.append((x+lr,y+ud,dist+1))
                
            answer = max(answer,max_dist)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
h,w=map(int,input().split())
maze = [['#']+list(input())+['#'] for i in range(h)]
maze.insert(0,['#']*(w+2))
maze.append(['#']*(w+2))

def get_max_length_from_start(maze,x,y):
    tmp_maze=copy.deepcopy(maze)
    searching = [[y,x]]
    length=0
    while len(searching)!=0:
        next_searching_list=[]
        for point in searching:
            tmp_maze[point[0]][point[1]]='/'
            mawari = [
                [point[0]+1,point[1]],
                [point[0]-1,point[1]],
                [point[0],point[1]+1],
                [point[0],point[1]-1]
            ] 
            next_searching = list(filter(lambda x:tmp_maze[x[0]][x[1]]==".",mawari))
            if len(next_searching)==0:
                max_length=length
                continue
            next_searching_list += next_searching
        searching = list(map(list, set(map(tuple, next_searching_list))))
        length+=1
    return max_length

ans=0
for y in range(1,h+1):
    for x in range(1,w+1):
        if maze[y][x]=='#':
            continue
        max_length=get_max_length_from_start(maze,x,y)
        ans = max_length if max_length>ans else ans

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import itertools
import copy

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

def solve(s):
    M = copy.deepcopy(S)
    d = ((1, 0), (-1, 0), (0, -1), (0, 1))
    queue = deque([s])
    steps = [[-1 for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        # M[cy][cx] = '#'
        for i in d:
            ny = cy+i[0]
            nx = cx+i[1]
            # はみ出さないかつ通ってない
            if (0<=ny<H and 0<=nx<W) and M[ny][nx]=='.' and steps[ny][nx] < 0:
            # if (0<=ny<H and 0<=nx<W) and M[ny][nx]!='#':
                queue.append([ny, nx])
                steps[ny][nx] = steps[cy][cx] + 1
        
    return max([max(i) for i in steps])

maxStep = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '.':
        maxStep = max(solve([s[0], s[1]]), maxStep)

print(maxStep)

Submission status: Accepted

Solution code:
from pprint import pprint

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

# 入力
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * w + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx and nx < w and -1 < ny and ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
import itertools
res = itertools.chain(*dp)  # 二次元配列を一次元にして
res = filter(lambda x: x != INF, res)  # INFを取り除き
res = max(res)  # 最大値を得る
print(res)

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[1]][start[0]] = 0#start地点を0に
    
    while queue:#queueにたまっている間は処理を続ける
        x, y = queue.popleft()#今いる地点をpop
        
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):#左右上下に進むパターンをそれぞれ考える
            next_x, next_y = x+i, y+j#次に行く地点
            
            if 0 <= next_x < W and 0 <= next_y < H:#次の地点が範囲内にある場合
                if grid[next_y][next_x] == '.' and distance[next_y][next_x] == -1:#次の地点が壁ではなくかつ訪れたことがない場合
                    distance[next_y][next_x] = distance[y][x] + 1#訪れた印として現在までの距離に1を足す
                    queue.append((next_x, next_y))#訪れる先をqueueに詰めとく
        
        if not queue:#最後にqueueをpopし終えてなくなったら最後に出力
            return distance[y][x]
        
answer = 0
for i in range(H):#y
    for j in range(W):#x
        #スタート地点を決める
        
        if S[i][j] == '#':#スタート地点が壁
            continue

        tmp = bfs(S, (j, i))#このスタート地点での一番遠い距離
        
        if tmp > answer:#最大の距離
            answer = tmp

print(answer)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from collections import deque


def main():
    H,W = map(int,input().split())
    S = [input().split()[0] for _ in range(H)]

    INF = 1001001001
    res = 0

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

    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                continue
            dist = [[INF for l in range(W)] for k in range(H)]
            queue = deque([[i,j]])
            dist[i][j] = 0
            maxdist = 0
            while len(queue):
                nowi,nowj = queue.popleft()
                for k in range(4):
                    tari = nowi + di[k]
                    tarj = nowj + dj[k]
                    if (tari<0)|(tari>=H)|(tarj<0)|(tarj>=W):
                        continue
                    if S[tari][tarj] == '#':
                        continue
                    if dist[tari][tarj] == INF:
                        dist[tari][tarj] = dist[nowi][nowj] + 1
                        queue.append([tari,tarj])
                        maxdist = max(maxdist,dist[tari][tarj])
            res = max(res,maxdist)

    print(res)


main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
from copy import deepcopy

input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
m = [['#' for _ in range(w+2)] for _ in range(h+2)]

for hi in range(1, h+1):
    for wi, s in enumerate(input().strip(), start=1):
        m[hi][wi] = s

def bfs(hs, ws, m):
    cost = -1
    if m[hs][ws] == '#':
        return cost
    q = deque([(hs, ws)])
    m[hs][ws] = '#'
    while q:
        cost += 1
        q_ = deque(q)
        q = deque([])
        for h, w in q_:
            m[h][w] = '#'
            for offset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
                if m[h+offset[0]][w+offset[1]] == '.':
                    m[h+offset[0]][w+offset[1]] = '#'
                    q.append((h+offset[0], w+offset[1]))
    return cost

ans = 0
for hi in range(1, h+1):
    for wi in range(1, w+1):
        ans = max(ans, bfs(hi, wi, deepcopy(m)))

print(ans)

Submission status: Accepted

Solution code:
from queue import Queue
H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w] != '.':
            continue
        q = Queue()
        seen = [[False]*W for _ in range(H)]
        q.put((h, w, 0))
        seen[h][w] = True
        while not q.empty():
            h, w, d = q.get()
            for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
                if nh < 0 or nw < 0 or nh >= H or nw >= W:
                    continue
                if not seen[nh][nw] and S[nh][nw] == '.':
                    q.put((nh, nw, d+1))
                    seen[nh][nw] = True
                    ans = max(d+1, ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

def bfs(initial):
    distance = [[-1] * w for _ in range(h)]
    frontier = deque()
    frontier.append(initial)
    distance[initial[0]][initial[1]] = 0
    while len(frontier):
        current_node = frontier.popleft()
        x,y = current_node
        for i,j in ((1,0),(-1,0),(0,1),(0,-1)):
            new_x, new_y = x+i, y+j
            if 0<=new_x<h and 0<=new_y<w:
                if maze[new_x][new_y] == '.' and distance[new_x][new_y]==-1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]

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

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [input() for _ in range(n)]

def bfs(r, c):
    t = [[-1] * m for v in g]
    q = []
    t[r][c] = 0
    q += (r, c),
    h = 0
    dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    while h < len(q):
        r, c = q[h]
        h += 1
        for d in range(4):
            r1, c1 = r + dirs[d][0], c + dirs[d][1]
            if 0 <= r1 < n and 0 <= c1 < m and '.' == g[r1][c1] and t[r1][c1] < 0:
                t[r1][c1] = t[r][c] + 1
                q += (r1, c1),
    ret = -1
    for v in t:
        ret = max(ret, max(v))
    return ret

ans = 0
for i in range(n):
    for j in range(m):
        if g[i][j] == '.':
            ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

table = [ list(input()) for _ in range(h) ]

search = [[1, 0], [0, 1], [-1, 0], [0, -1]] 
# right, up, left, down

maxlength = 0
for si in range(h):
    for sj in range(w):
        if table[si][sj]=="#":
            pass
        else:
            table_past_flag = [ [0]*w for _ in range(h) ]
            q = deque([[si,sj,0]])
            table_past_flag[si][sj] = 1
            while(q):
                tmp = q.popleft()
                maxlength = max(maxlength,tmp[2])
                for di,dj in search:
                    ni = tmp[0] + di
                    nj = tmp[1] + dj
                    if 0 <= ni < h and 0<= nj < w:
                        if table_past_flag[ni][nj]!=1 and table[ni][nj]!="#":
                            q.append([ni,nj,tmp[2]+1])
                            table_past_flag[ni][nj] = 1
                        else:
                            pass
print(maxlength)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
readline = sys.stdin.readline


H,W = map(int,readline().split())
grid='#'*(W+2) + ''.join('#'+readline().strip()+'#' for _ in range(H)) + '#'*(W+2)
INF = 400
def shortest(grid, start, cost=0):
    dist = [INF] * (H+2)*(W+2)
    move=(-1,1,W+2,-W-2)
    st = [start]
    dist[start]=0
    while(st):
        sx = heappop(st)
        c=dist[sx]
        for a in move:
            x = sx + a
            if grid[x]=='#':
              continue
            dx = dist[sx] + 1
            if dist[x] <= dx:
                continue
            dist[x] = dx
            heappush(st, x)
    return max(x for x in dist if x < INF)

m=0
for i in range(W+3, (H+1)*(W+2)-1):
    if grid[i]=='#':
      continue
    tm = shortest(grid, i)
    if m < tm:
      m=tm
print(m)

Submission status: Accepted

Solution code:
from collections import deque
 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
 
INF = 10**15
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)]
      dist[i][j] = 0
      stack = deque([(i, j)])
      
      while stack:
        s = stack.popleft()
        si, sj = s
        for di, dj in d:
          if 0 <= si + di <= H - 1 and 0 <= sj + dj <= W - 1 and S[si + di][sj + dj] != "#":
            if dist[si + di][sj + dj] > dist[si][sj] + 1:
              dist[si + di][sj + dj] = dist[si][sj] + 1
              stack.append((si + di, sj + dj))
      #print(dist)
 
      max_dist = 0
      for ii in range(H):
        #print(dist[ii])
        for jj in range(W):
          if dist[ii][jj] != INF:
            max_dist = max(max_dist, dist[ii][jj])
      #print("")
      answer = max(max_dist, answer)
      
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

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

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]==-2 and S[data[0]-1][data[1]]=='.':
    m[data[0]-1][data[1]]=-1
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]==-2 and S[data[0]+1][data[1]]=='.':
    m[data[0]+1][data[1]]=-1
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]==-2 and S[data[0]][data[1]-1]=='.':
    m[data[0]][data[1]-1]=-1
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]==-2 and S[data[0]][data[1]+1]=='.':
    m[data[0]][data[1]+1]=-1
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-2]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
      if data[2]>out:
        out=data[2]
      
print(out)

Submission status: Accepted

Solution code:
import _pickle as cPickle

from collections import deque
h,w=map(int,input().split())
p=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]
b=cPickle.loads(cPickle.dumps(p, -1))
ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        p=cPickle.loads(cPickle.dumps(b, -1))
        if p[i][j]=='.':
            s0=i
            s1=j
            p[s0][s1]=0
            d=[(1,0),(-1,0),(0,1),(0,-1)]
            q=deque([[s0,s1]])
            while q:
                x,y=q.popleft()
                for dx,dy in d:
                    if p[x+dx][y+dy]==".":
                        p[x+dx][y+dy]=p[x][y]+1
                        q.append([x+dx,y+dy])
                        if ans<p[x+dx][y+dy]:
                            ans=p[x+dx][y+dy]
print(ans)

Submission status: Accepted

Solution code:
# 幅優先探索（BFS)
def calc_maze(maze, sh, sw):
    H = len(maze)
    W = len(maze[0])

    # 距離行列
    distance = []
    for i in range(H):
        distance.append([])
        for j in range(W):
            distance[i].append(-1)

    # 座標格納キュー
    # (H座標, W座標, 距離)
    queue = []
    # 初期ポジション格納
    queue.append((sh, sw))
    distance[sh][sw] = 0
    # 最大距離を格納
    max_distance = 0
    # 探索する場所がなくなるまで
    while queue:
        h, w = queue.pop(0)

        for i in range(0, 4):
            nh, nw = h + [1, 0, -1, 0][i], w + [0, 1, 0, -1][i]
            if (0 <= nh and nh < H and 0 <= nw and nw < W and maze[nh][nw] != '#' and distance[nh][nw] == -1):
                queue.append((nh, nw))
                distance[nh][nw] = distance[h][w] + 1
                # 最大距離更新
                if max_distance < (distance[h][w] + 1):
                    max_distance = distance[h][w] + 1
    return max(max(d) for d in distance)



def main():
    H, W = map(int, input().split())
    maze = []
    ans = 0

    for _ in range(H):
        l = list(input())
        maze.append(l)

    for j in range(W):
        for i in range(H):
            if maze[i][j] != "#":
                ans = max(ans, calc_maze(maze, i, j))
    print(ans)
    return 0
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline


H, W = map(int, readline().split())
grid = '#' * (W + 2) + ''.join('#' + readline().strip() +
                               '#' for _ in range(H)) + '#' * (W + 2)
INF = 400


def shortest(grid, start, cost=0):
    dist = [INF] * (H + 2) * (W + 2)
    move = (-1, 1, W + 2, -W - 2)
    st = deque([start])
    dist[start] = 0
    while(st):
        sx = st.popleft()
        c = dist[sx]
        for a in move:
            x = sx + a
            if grid[x] == '#':
                continue
            dx = dist[sx] + 1
            if dist[x] <= dx:
                continue
            dist[x] = dx
            st.append(x)
    return max(x for x in dist if x < INF)


m = 0
for i in range(W + 3, (H + 1) * (W + 2) - 1):
    if grid[i] == '#':
        continue
    tm = shortest(grid, i)
    if m < tm:
        m = tm
print(m)

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
readline = sys.stdin.readline


H, W = map(int, readline().split())
grid = '#' * (W + 2) + ''.join('#' + readline().strip() +
                               '#' for _ in range(H)) + '#' * (W + 2)
INF = 400


def shortest(grid, start, cost=0):
    dist = [INF] * (H + 2) * (W + 2)
    move = (-1, 1, W + 2, -W - 2)
    st = [start]
    dist[start] = 0
    while(st):
        sx = heappop(st)
        c = dist[sx]
        for a in move:
            x = sx + a
            if grid[x] == '#':
                continue
            dx = dist[sx] + 1
            if dist[x] <= dx:
                continue
            dist[x] = dx
            heappush(st, x)
    return max(x for x in dist if x < INF)


m = 0
for i in range(W + 3, (H + 1) * (W + 2) - 1):
    if grid[i] == '#':
        continue
    tm = shortest(grid, i)
    if m < tm:
        m = tm
print(m)

Submission status: Accepted

Solution code:
from scipy.sparse import*
e=enumerate
h,*s=open(0)
h,w=map(int,h.split())
r,c=[],[]
for i,t in e(s):
  for j,u in e(t):
    if u>'#'<t[j+1]:r+=i*w+j,;c+=i*w+j+1,
    if(i<h-1)*u>'#'<s[i+1][j]:r+=i*w+j,;c+=j-~i*w,    
a=csgraph.johnson(csr_matrix(([1]*len(r),(r,c)),[h*w]*2),0)
print(int(a[a<999].max()))

Submission status: Accepted

Solution code:
from scipy.sparse import*
e=enumerate
h,*s=open(0)
h,w=map(int,h.split())
r,c=[],[]
for i,t in e(s):
  for j,u in e(t):
    if u>'#'<t[j+1]:r+=i*w+j,;c+=i*w+j+1,
    if(i<h-1)*u>'#'<s[i+1][j]:r+=i*w+j,;c+=j-~i*w,    
print(int((csgraph.johnson(csr_matrix(([1]*len(r),(r,c)),[h*w]*2),0).clip(0,999)%999).max()))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
field=[]
field.append([True for i in range(w+2)])
start=[]
for i  in range(h):
    s=input()
    sub=[True]
    for j in range(w):
        if s[j]=="#":
            sub.append(True)
        else:
            sub.append(False)
            start.append((i+1,j+1))
    
    sub.append(True)
    field.append(sub)

            
        
    
field.append([True for i in range(w+2)])

from collections import deque
import copy
dis=[]
for i in range(len(start)):

        fields=copy.deepcopy(field)
        d=deque()
        e=deque()
        distance=0
        fields[start[i][0]][start[i][1]]=True

        d.append((start[i][0],start[i][1]))
        while d:
            for some in d:
                index1,index2=some[0],some[1]
                if fields[index1-1][index2]==False:
                    fields[index1-1][index2]=True
                    e.append((index1-1,index2))
                if fields[index1+1][index2]==False:
                    fields[index1+1][index2]=True
                    e.append((index1+1,index2))
                if fields[index1][index2+1]==False:
                    fields[index1][index2+1]=True
                    e.append((index1,index2+1))
                if  fields[index1][index2-1]==False:
                    fields[index1][index2-1]=True
                    e.append((index1,index2-1))
            distance+=1
            d=e
            e=deque()

        dis.append(distance)
    


print(max(dis)  -1)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    H,W = LMIIS()
    MOD = H*W
    S = [input() for _ in range(H)]


    def tansaku(S,V,y,x,length):

        
        if  x >= 1 and S[y][x-1] == '.' and V[y][x-1] > length+1:
            V[y][x-1] = length+1
            tansaku(S,V,y,x-1,length+1)


        if x < W-1 and S[y][x+1] == '.' and V[y][x+1] > length+1:
            V[y][x+1] = length+1
            tansaku(S,V,y,x+1,length+1)


        if y >= 1 and S[y-1][x] == '.' and V[y-1][x] > length+1:
            V[y-1][x] = length+1
            tansaku(S,V,y-1,x,length+1)


        if y < H-1 and S[y+1][x] == '.' and V[y+1][x]> length+1:
            V[y+1][x] = length+1
            tansaku(S,V,y+1,x,length+1)

        return
    
    def getmax():
        max_length = 0
        for h in range(H):
            for w in range(W):
                V = [[MOD] * W for _ in range(H)]
                if S[h][w] == '.':
                    V[h][w] = 0
                    tansaku(S,V,h,w,0) 
                for v in V:
                    v = list(map(lambda x:x%MOD,v))
                    max_length = max(v+[max_length])
                    # print(V)
        return max_length
    
    print(getmax())
    






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs(initial):
    # goal判定はなく、一番遠いところで返す
    distance = [[-1] * W for _ in range(H)]
    frontier = deque()
    frontier.append(initial)
    distance[initial[0]][initial[1]] = 0
    while len(frontier):
        current_node = frontier.popleft()
        x, y = current_node
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_x, new_y = x + i, y + j
            if 0 <= new_x < H and 0 <= new_y < W:
                if maze[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]


ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        solution = bfs((i, j))
        if ans < solution:
            ans = solution

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w = list(map(int,input().split()))
s = []
for i in range(h):
    sh = list(input())
    s.append(sh)
ki = [[] for i in range(h*w)]
def ichi(a,b):
    return a + b*h
for a in range(h):
    for b in range(w):
        if s[a][b] == ".":
            if  a+1 < h and s[a+1][b] == "." :
                ki[ichi(a+1,b)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a+1,b))
            if  a-1 >= 0 and s[a-1][b] == ".":
                ki[ichi(a-1,b)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a-1,b))
            if b-1 >= 0 and s[a][b-1] == ".":
                ki[ichi(a,b-1)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a,b-1))
            if b+1 < w and s[a][b+1] == "." :
                ki[ichi(a,b+1)].append(ichi(a,b))
                ki[ichi(a,b)].append(ichi(a,b+1))
        else:
            pass
for i in range(w*h):
    ki[i] = list(set(ki[i]))
ans = [0]
for i in range(w*h):
    ikeru = deque([i])
    sumi = []
    kaisuu = [-1]*(w*h)
    kaisuu[i] = 0
    while ikeru:
        j = ikeru.popleft()
        sumi.append(j)
        for k in range(len(ki[j])):
            if ki[j][k] in sumi:
                pass
            else:
                if ki[j][k] not in ikeru:
                    ikeru.append(ki[j][k])
                if kaisuu[ki[j][k]] > kaisuu[j] + 1:
                    kaisuu[ki[j][k]] = kaisuu[j] + 1
                elif kaisuu[ki[j][k]] == -1:
                    kaisuu[ki[j][k]] = kaisuu[j] + 1 
#        print(i,kaisuu,ikeru)
    ans.append(max(kaisuu))
#print(ans)
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque


def solve(maze, init_y, init_x, H, W):
    distances = [[-1 for _ in range(W)] for _ in range(H)]
    distances[init_y][init_x] = 0

    def is_inside(y, x):
        return 0 <= x < W and 0 <= y < H

    def need_to_search(y, x):
        return maze[y][x] != "#" and distances[y][x] == -1

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

    q = deque()
    q.appendleft([init_y, init_x])

    while q:
        y, x = q.pop()
        d = distances[y][x]

        for dy, dx in four_directions:
            ny, nx = y+dy, x+dx
            if not is_inside(ny, nx):
                continue
            if need_to_search(ny, nx):
                q.appendleft([ny, nx])
                distances[ny][nx] = d+1

    farthest = 0
    for i in range(H):
        for j in range(W):
            # if maze[i][j] != "#":
            farthest = max(farthest, distances[i][j])
    return farthest


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

    farthest = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == "#":
                continue
            distance = solve(maze, i, j, H, W)
            farthest = max(distance, farthest)

    print(farthest)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def solve(maze, init_y, init_x, H, W):
    distances = [[-1 for _ in range(W)] for _ in range(H)]
    distances[init_y][init_x] = 0

    def is_inside(y, x):
        return 0 <= x < W and 0 <= y < H

    def need_to_search(y, x):
        return maze[y][x] != "#" and distances[y][x] == -1

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

    q = deque()
    q.appendleft([init_y, init_x])

    while q:
        y, x = q.pop()
        d = distances[y][x]

        for dy, dx in four_directions:
            ny, nx = y+dy, x+dx
            if not is_inside(ny, nx):
                continue
            if need_to_search(ny, nx):
                q.appendleft([ny, nx])
                distances[ny][nx] = d+1

    farthest = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] != "#":
                farthest = max(farthest, distances[i][j])
    return farthest


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

    farthest = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == "#":
                continue
            distance = solve(maze, i, j, H, W)
            farthest = max(distance, farthest)

    print(farthest)


if __name__ == '__main__':
    main()