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:
from collections import deque
''' 
INF = float('inf')
MOD = 10 ** 9 + 7
'''
## ここは１つにまとめれる
# dy = (0, -1, 0, 1)
# dx = (1, 0, -1, 0)
d=[(1,0),(0,1),(-1,0),(0,-1)]

    
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for _ in range(H)]
        if M[i][j] == '.':
            Ma = 0
            q.append((i, j))
            dist[i][j] = 0
            while q:
                cx,cy = q.popleft()
                for nx,ny in d:
                    x ,y= cx+nx,cy+ny
                    ''' ここの処理がをnotにしてわかりやすく
                    if x<0 or y<0 or x>=H or y>=W or dist[x][y]>0:
                        continue
                    '''
                    if 0<= x < H and 0<= y < W and dist[x][y]<=0:

                        if M[x][y] == "." and dist[x][y] == -1:
                            dist[x][y]=dist[cx][cy]+1
                            Ma = max(Ma,dist[x][y])
                            q.append((x,y))
            Max_list.append(Ma)

print(max(Max_list))

Submission status: Accepted

Solution code:
import queue

H, W = map(int, input().split())
S = [input() for i in range(H)]
q = queue.Queue()
longest_path = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            g = [[0 if S[k][l] == '.' else -1 for l in range(W)] for k in range(H)]
            q.put((i,j))
            g[i][j] = 0
            while not(q.empty()):
                x, y = q.get()
                for nx, ny in [(x+1, y),(x-1, y),(x, y+1),(x, y-1)]:
                    if nx < 0 or nx > H-1 or ny < 0 or ny > W-1: continue
                    if g[nx][ny] != 0: continue
                    if nx == i and ny == j: continue
                    g[nx][ny] = g[x][y] + 1
                    q.put((nx,ny))
            longest_path = max(longest_path, max(map(max, g)))
print(longest_path)

Submission status: Accepted

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

ans = 0
INF = 111111

for i in range(h+1):
  for j in range(w+1):
    if s[i][j] == '#':
      continue
    visited = [[0] * (w+2) for _ in range(h+2)]
    visited[i][j] = 1
    max_s = 0
    dq = deque([(i, j, 0)])

    while dq:
      ci, cj, step = dq.popleft()
      if step > max_s:
        max_s = step
      step += 1

      for di, dj in ((ci+1, cj), (ci, cj+1), (ci-1, cj), (ci, cj-1)):
        if s[di][dj] == '#' or visited[di][dj] == 1:
          continue
        visited[di][dj] = 1
        dq.append((di, dj, step))
    ans = max(max_s, ans)

print(ans)

Submission status: Accepted

Solution code:
import queue

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

ddx = [1,-1,0,0]
ddy = [0,0,1,-1]

INF = 1<<30
ans = 0
for sx in range(W):
    for sy in range(H):       
        if S[sy][sx] == '#': continue
        d = 0
        q = queue.Queue()
        dist = [[INF]*W for _ in range(H)]
        dist[sy][sx] = 0
        q.put([sx,sy])
        while not q.empty():
            x,y = q.get()
            for i in range(4):
                dx = ddx[i]
                dy = ddy[i]
                if y+dy<0 or y+dy>=H or x+dx<0 or x+dx>=W:
                    continue
                if S[y+dy][x+dx] == '.' and dist[y+dy][x+dx] == INF:
                    dist[y+dy][x+dx] = dist[y][x] + 1
                    q.put([x+dx,y+dy])
        
        for i in range(H):
            for j in range(W):
                if dist[i][j] != INF:
                    d = max(d,dist[i][j])
            
        ans = max(ans,d)
        
print(ans)

Submission status: Accepted

Solution code:
def bfs(x):
  from collections import deque
  dist = [INF] * (H * W)
  dist[x] = 0
  stack = deque([(0, x)]) #
  while stack:
    v, s = stack.popleft() #
    for w, g in graph[s]:
      if dist[g] > v + w:
        dist[g] = v + w
        stack.append((dist[g], g)) #
  return dist

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

INF = 10**15
graph = [[] for _ in range(H * W)]
 
for i in range(H):
  for j in range(W):
    for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
      if 0 <= ni < H and 0 <= nj < W and S[ni][nj] != "#":
        graph[W * i + j].append((1, W * ni + nj))

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = bfs(i * W + j)
      for ii in range(H * W):
        if dist[ii] != INF:
          answer = max(answer, dist[ii])
      
print(answer)

Submission status: Accepted

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

INF = 10**15
graph = [[] for _ in range(H * W)]
 
for i in range(H):
  for j in range(W):
    for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
      if 0 <= ni < H and 0 <= nj < W and S[ni][nj] != "#":
        graph[W * i + j].append((W * ni + nj, 1))

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [INF for _ in range(H * W)]
      dist[W * i + j] = 0
      stack = deque([W * i + j])
      while stack:
        s = stack.popleft()
        for g, w in graph[s]:
          if dist[g] > dist[s] + w:
            dist[g] = dist[s] + w
            stack.append(g)
      for ii in range(H * W):
        if dist[ii] != INF:
          answer = max(answer, dist[ii])
      
print(answer)

Submission status: Accepted

Solution code:
import copy
import queue

input_int_list = list(map(int, input().split()))

H = input_int_list[0]
W = input_int_list[1]

MAX_DIST = 100000

# master_maze_list =[ [0] * H ] * W
master_maze_list = [[-1 for i in range(H+2)] for j in range(W+2)]
for vertical_i in range(H):
	input_str_H = input()
	for holizontal_i in range(W):
		if input_str_H[holizontal_i] == '#':
			master_maze_list[holizontal_i+1][vertical_i+1] = -1
		elif input_str_H[holizontal_i] == '.':
			master_maze_list[holizontal_i+1][vertical_i+1] = MAX_DIST


# print(master_maze_list)


distance_max = 0

for vertical_i in range(H):
	for holizontal_i in range(W):
		search_target_maze = copy.deepcopy(master_maze_list)
		root_h = holizontal_i+1
		root_v = vertical_i+1
		if search_target_maze[root_h][root_v] == -1:
			continue
		next_place_queue = queue.Queue()
		next_place_queue.put(root_h)
		next_place_queue.put(root_v)
		search_target_maze[root_h][root_v] = 0
		
		while next_place_queue.empty() != True:
			now_h = next_place_queue.get()
			now_v = next_place_queue.get()
			now_place_val = search_target_maze[now_h][now_v]

			if now_place_val == -1:
				pass
			else:
				if search_target_maze[now_h+1][now_v] > now_place_val+1:
					search_target_maze[now_h+1][now_v] = now_place_val+1
					next_place_queue.put(now_h+1)
					next_place_queue.put(now_v)

				if search_target_maze[now_h][now_v+1] > now_place_val+1:
					search_target_maze[now_h][now_v+1] = now_place_val+1
					next_place_queue.put(now_h)
					next_place_queue.put(now_v+1)

				if search_target_maze[now_h-1][now_v] > now_place_val+1:
					search_target_maze[now_h-1][now_v] = now_place_val+1
					next_place_queue.put(now_h-1)
					next_place_queue.put(now_v)

				if search_target_maze[now_h][now_v-1] > now_place_val+1:
					search_target_maze[now_h][now_v-1] = now_place_val+1
					next_place_queue.put(now_h)
					next_place_queue.put(now_v-1)
		distance_max = max(distance_max, now_place_val)
#		print(distance_max)

print(distance_max)

Submission status: Accepted

Solution code:
#ABC151D
h,w=map(int,input().split())
s=[input() for i in range(h)]
ans=0
from collections import deque
for i in range(h):
    for j in range(w):
        q=deque()
        q.append([i,j,0])
        seen=[[False for j in range(w)] for i in range(h)]
        while q:
            node=q.popleft() 
            y=node[0]
            x=node[1]
            dist=node[2]
            if s[y][x]=='#':
                continue
            if seen[y][x]:
                continue
            seen[y][x]=True
            if dist>ans:
                ans=dist
            dif=((0,1),(0,-1),(1,0),(-1,0))
            for d in dif:
                if 0<=y+d[0]<h and 0<=x+d[1]<w:
                    q.append([y+d[0],x+d[1],dist+1])
print(ans)

Submission status: Accepted

Solution code:
from queue import Queue

h, w = list(map(int, input().split()))
s = []
for i in range(h):
    s.append(input().strip())

ans = 0
for i in range(h):
    for j in range(w):
        start = s[i][j]
        if start == "#":
            continue
        else:
            visited = [[False for _ in range(w)] for _ in range(h)]
            visited[i][j] = True
            queue = Queue()
            queue.put((i, j, 0))

            while 0 < queue.qsize():
                now = queue.get()
                ans = max(ans, now[2])

                if (now[0] <= (h - 2)) and (s[now[0] + 1][now[1]] == ".") and not visited[now[0] + 1][now[1]]:
                    queue.put(((now[0] + 1), now[1], (now[2] + 1)))
                    visited[now[0] + 1][now[1]] = True
                if (now[1] <= (w - 2)) and (s[now[0]][now[1] + 1] == ".") and not visited[now[0]][now[1] + 1]:
                    queue.put((now[0], (now[1] + 1), (now[2] + 1)))
                    visited[now[0]][now[1] + 1] = True
                if (1 <= now[0]) and (s[now[0] - 1][now[1]] == ".") and not visited[now[0] - 1][now[1]]:
                    queue.put(((now[0] - 1), now[1], (now[2] + 1)))
                    visited[now[0] - 1][now[1]] = True
                if (1 <= now[1]) and (s[now[0]][now[1] - 1] == ".") and not visited[now[0]][now[1] - 1]:
                    queue.put((now[0], (now[1] - 1), (now[2] + 1)))
                    visited[now[0]][now[1] - 1] = True

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

MAZE = ["#" * (w + 2)]
for _ in range(h):
    s = "#" + input().strip() + "#"
    MAZE.append(s)
MAZE.append("#" * (w + 2))

I = [-1, 0, 0, 1]
J = [0, -1, 1, 0]
def bfs(r, c):
    DISTANCES = {}
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            DISTANCES[(i, j)] = -1
    DISTANCES[(r, c)] = 0
    Q = [(r, c)]
    while Q:
        i, j = Q.pop(0)
        for k in range(4):
            if MAZE[i + I[k]][j + J[k]] == "." and DISTANCES[(i + I[k], j + J[k])] == -1:
                DISTANCES[(i + I[k], j + J[k])] = DISTANCES[(i, j)] + 1
                Q.append((i + I[k], j + J[k]))
    return max(DISTANCES.values())

BFS = []
for r in range(1, h + 1):
    for c in range(1, w + 1):
        if MAZE[r][c] == ".":
            BFS.append(bfs(r, c))

print(max(BFS))

Submission status: Accepted

Solution code:
from collections import deque

def simulate(h, w, s, sx, sy):
    dist = [[-1 for x in range(w)] for y in range(h)]
    dist[sy][sx] = 0
    que = deque([(sx, sy)])
    res = 0
    while que:
        cx, cy = que.popleft()
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx, ny = cx+dx, cy+dy
            if (0 <= nx < w) and (0 <= ny < h) and (s[ny][nx] == ".") and (dist[ny][nx] == -1):
                que.append((nx, ny))
                dist[ny][nx] = dist[cy][cx] + 1
                res = max(res, dist[ny][nx])
    return res

def solve(h, w, s):
    best = 0
    for y in range(h):
        for x in range(w):
            if s[y][x] == ".":
                best = max(best, simulate(h, w, s, x, y))
    return best

h, w = map(int, input().split())
s = [input() for i in range(h)]
print(solve(h, w, s))

Submission status: Accepted

Solution code:

length, width = map(int, input().split())
Maze = [list(input()) for _ in range(length)]

def bfs(i, j):
    t = [[-1] * width for _ in range(length)]
    t[i][j] = 0
    stack = [(i, j)]
    while(stack):
        x, y = stack.pop(0)
        if x - 1 >= 0 and Maze[x - 1][y] != '#' and t[x-1][y] == -1:
            t[x-1][y] = t[x][y] + 1
            stack.append((x-1, y))
        if x + 1 < length and Maze[x + 1][y] != '#' and t[x + 1][y] == -1:
            t[x + 1][y] = t[x][y] + 1
            stack.append((x+1, y))
        if y - 1 >= 0 and Maze[x][y-1] != '#' and t[x][y-1] == -1:
            t[x][y-1] = t[x][y] + 1
            stack.append((x, y-1))
        if y + 1 < width and Maze[x][y+1] != '#' and t[x][y+1] == -1:
            t[x][y+1] = t[x][y] + 1
            stack.append((x, y+1))
    return max(max(answer) for answer in t)
answer = 0

for i in range(length):
    for j in range(width):
        if Maze[i][j] != '#':
            answer = max(answer, bfs(i,j))

print(answer)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
grid = [input() for i in range(H)]
INF = 10**18
ans = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            continue
        q = [(i,j)]
        dis = [[INF]*W for i in range(H)]
        dis[i][j] = 0
        d = 1
        while q:
            qq = []
            for y,x in q:
                for dy, dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                    yy,xx = dy+y,dx+x
                    if not(0<= yy < H and 0 <= xx < W):
                        continue
                    if dis[yy][xx] != INF:
                        continue
                    if grid[yy][xx] == '#':
                        continue
                    dis[yy][xx] = d
                    qq.append((yy,xx))
            q = qq
            d += 1
        for k in range(H):
            for l in range(W):
                if dis[k][l] != INF:
                    ans = max(ans,dis[k][l])
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
maze=[]
maze.append(['#']*(W+2))
for i in range(H):
    tmp=['#']+list(input())+['#']
    if '.' in tmp:
        a,b=i,tmp.index('.')
    maze.append(tmp)
maze.append(['#']*(W+2))
infty=10**5

def far(a,b):
    cost[a][b]=0
    point[0].append((a,b))
    stocks=1
    highscore=0
    tops=[]
    while stocks>0:
        stocks-=1
        for i in range(infty):
            if point[i]==[]:
                continue
            else:
                a,b=point[i].pop(0)
                break
        if i==highscore:
            tops.append((a,b))
        elif i>highscore:
            highscore,tops=i,[(a,b)]
        if maze[a][b+1]=='.' and cost[a][b+1]==infty:
            cost[a][b+1]=i+1
            point[i+1].append((a,b+1))
            stocks+=1
        if maze[a][b-1]=='.' and cost[a][b-1]==infty:
            cost[a][b-1]=i+1
            point[i+1].append((a,b-1))
            stocks+=1
        if maze[a-1][b]=='.' and cost[a-1][b]==infty:
            cost[a-1][b]=i+1
            point[i+1].append((a-1,b))
            stocks+=1
        if maze[a+1][b]=='.' and cost[a+1][b]==infty:
            cost[a+1][b]=i+1
            point[i+1].append((a+1,b))
            stocks+=1
    return tops,i


cost=[[infty]*(W+2) for i in range(H+2)]
point=[[] for i in range(infty)]

a,b=far(a,b)[0][0]

cost=[[infty]*(W+2) for i in range(H+2)]
point=[[] for i in range(infty)]

tops=far(a,b)[0]
res=0


for i,j in tops:
    cost=[[infty]*(W+2) for tmp in range(H+2)]
    point=[[] for i in range(infty)]
    tmp=far(i,j)[1]
    if res<tmp:res=tmp

print(res)

Submission status: Accepted

Solution code:
import copy

h, w = map(int, input().split())
maze = []
maze.append([-1 for i in range(w+2)])
for i in range(h):
    si = input()
    s_lst = [-1]
    for j in range(w):
        if si[j] == '.':
            s_lst.append(0)
        else:
            s_lst.append(-1)
    s_lst.append(-1)
    maze.append(s_lst)
maze.append([-1 for i in range(w+2)])

def solve_maze(maze, s):
    queue = [s]
    maze[s[0]][s[1]] = -2
    cnt = 0
    while queue != []:
        cnt += 1
        next_queue = []
        for ten in queue:
            i, j = ten[0], ten[1]
            if maze[i-1][j] == 0:
                maze[i-1][j] = cnt
                next_queue.append([i-1, j])
            if maze[i+1][j] == 0:
                maze[i+1][j] = cnt
                next_queue.append([i+1, j])
            if maze[i][j-1] == 0:
                maze[i][j-1] = cnt
                next_queue.append([i, j-1])
            if maze[i][j+1] == 0:
                maze[i][j+1] = cnt
                next_queue.append([i, j+1])
        queue = next_queue.copy()
    return cnt-1

ans = 0
for i in range(h+2):
    for j in range(w+2):
        if maze[i][j] == 0:
            copied_maze = copy.deepcopy(maze)
            ans = max(ans, solve_maze(copied_maze, [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
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '#'*(w+2)
A = []
A.append(grid)
for i in range(h):
    tmp = "#" + readline().rstrip().decode() + "#"
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque()
    q.append((i,j ))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "#":
                continue
            if dist[hh+k][ww+l] <= dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

anss = 0
for i in range(h+2):
    for j in range(w+2):
        if A[i][j] == "#":
            continue
        anss = max(anss,bfs(i,j))
print(anss)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
s=[input() for _  in range(H)]
G=[["#"]*(W+2) for _ in range(H+2)]

for i in range(H):
    for j in range(W):
        G[i+1][j+1]=s[i][j]

def search(y,x):
    q=[(y,x)]
    d=[[-1]*(W+2) for _ in range(H+2)]
    d[y][x]=0
    while q:
        y1,x1=q.pop(0)
        for y2,x2 in ((y1+1,x1),(y1,x1+1),(y1-1,x1),(y1,x1-1)):
            if G[y2][x2]=="." and d[y2][x2]==-1:
                d[y2][x2]=d[y1][x1]+1
                q.append((y2,x2))
    return max(max(_) for _ in d)

ans=0
for i in range(H):
    for j in range(W):
        if G[i+1][j+1]==".":
            ans=max(search(i+1,j+1),ans)

print(ans)

Submission status: Accepted

Solution code:
# adj = {
#     1: [2, 3, 4, 8, 9],
#     2: [1, 3, 5],
#     3: [1, 2, 6],
#     4: [1, 6],
#     5: [2, 6, 7],
#     6: [5, 3, 4],
#     7: [5],
#     8: [1],
#     9: [1]
# }

from collections import deque

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

adj = {(i, j): [] for i in range(H) for j in range(W)}
for i in range(H):
    for j in range(W):
        for m in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            row, col = m[0], m[1]
            if 0 <= row <= H - 1 and 0 <= col <= W - 1 and d[row][col] != '#':
                adj[i, j].append(m)


def bfs(g, s):
    if d[s[0]][s[1]] == "#":
        return 0
    visited = {}
    distance = {}
    q = deque()
    q.append(s)
    visited[s] = True
    distance[s] = 0
    while q:
        u = q.popleft()
        for i in g[u]:
            if i not in visited:
                q.append(i)
                visited[i] = True
                distance[i] = distance[u] + 1

    return max(distance.values())


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, bfs(adj, (i, j)))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy


def bfs(start, s):
    h = len(s)
    w = len(s[0])
    distance = 0
    maze = [[-1] * w for _ in range(h)]
    maze[start[0]][start[1]] = 0
    s[start[0]][start[1]] = "#"
    drcs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    q = deque()
    q.append(start)
    while(q):
        cr, cc = q.popleft()
        for dr, dc in drcs:
            nr, nc = cr + dr, cc + dc
            if nr < 0 or nc < 0 or nr >= h or nc >= w:
                continue
            if s[nr][nc] == ".":
                q.append([nr, nc])
                s[nr][nc] = "#"
                maze[nr][nc] = maze[cr][cc] + 1
                if maze[nr][nc] > distance:
                    distance = maze[nr][nc]
                    goal = [nr, nc]
    return goal, distance


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    for r in range(h):
        if "." in s[r]:
            start = [r, s[r].index(".")]
    goal, distance = bfs(start, copy.deepcopy(s))
    _, res = bfs(goal, s)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
import numpy as np
from collections import deque
m,n = list(map(int, input().split()))
o2 = []
dist_mat = []
for i in range(m):
    o1 = list(str(input()))
    o2.append(o1)
    dist_mat.append(np.zeros(len(o1)))

in_mat = np.array(o2)
#dist_mat = np.zeros_like(in_mat)
dist_mat = []
for i in in_mat:
    dist_mat.append(np.zeros(len(i)))
dist_mat = np.array(dist_mat)
rows,cols = dist_mat.shape

qu = deque()

for r in range(rows):
    for c in range(cols):
        if in_mat[r][c] == ".":
            qu.appendleft((r,c))

dist_mat_base = copy.deepcopy(dist_mat)

ans = []
lenqu = len(qu)
for i in range(lenqu):
    strt = qu.pop()
    qu2 = deque()
    qu2.appendleft(strt)
    dist_mat = copy.deepcopy(dist_mat_base)

    while qu2:
        curr_r, curr_c = qu2.pop()
        dist = dist_mat[curr_r][curr_c]
        adj_cells = [(0,1), (1,0), (0,-1), (-1,0)]
        for r_adj, c_adj in adj_cells:
            adj_row = curr_r + r_adj
            adj_col = curr_c + c_adj
            if 0 <= adj_row < rows and 0 <= adj_col < cols:
                if dist_mat[adj_row][adj_col] == 0 and in_mat[adj_row][adj_col] == "." and not (adj_row, adj_col) == strt:
                    dist_mat[adj_row][adj_col] = dist + 1
                    qu2.appendleft((adj_row, adj_col))

    dist_vec = np.concatenate(dist_mat)
    ans.append(round(max(dist_vec)))

print(int(max(ans)))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
f=H*W
d=[[0]*f for _ in range(f)]


s=[input() for _  in range(H)]
    
for i in range(H):
    for j in range(W-1): 
        cnt=W*i+j
        d[cnt+1][cnt]=s[i][j]==s[i][j+1]=="."
        d[cnt][cnt+1]=s[i][j]==s[i][j+1]=="."
       
for i in range(H-1):
    for j in range(W): 
        cnt=W*i+j
        d[cnt][cnt+W]=s[i][j]==s[i+1][j]=="."
        d[cnt+W][cnt]=s[i][j]==s[i+1][j]=="."
        
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
csr=np.array(d)


ans=-1
k=shortest_path(csr)
for i in range(f):   
    for q in range(f):
            if k[i][q]>=f+1:k[i][q]=-1

    ans=max(ans,max(k[i]))

print(int(ans))

Submission status: Accepted

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


def bfs(S, H, W, start):
    INF = -1
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == -1:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return max(map(max, distance))
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            ans = max(ans, bfs(S, H, W, (j, i)))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
 
H, W = map(int, input().split())
S = [list(input().split()[0]) for _ in range(H)]
 
def bfs(S, H, W, start):
    INF = -1
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == -1:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return max(map(max, distance))
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "#":
            ans = max(ans, bfs(S, H, W, (j, i)))
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:
import sys
input = sys.stdin.readline
from collections import deque

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

def bfs(S, H, W, start):
    INF = -1
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == -1:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return max(map(max, distance))

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

Submission status: Accepted

Solution code:
import copy

def maze_maker():
    h,w = map(int,input().split())
    maze = []
    for i in range(h):
        maze.append(list(input()))
    return maze,h,w

def search():
    v = 0
    now = [[i1,j1,0]]
    meiro[i1][j1] = 0
    go = True
    while go:
        for i in now[:]:
            #上
            if i[0] == 0:
                pass
            else:
                if meiro[i[0]-1][i[1]] == ".":
                    now.append([i[0]-1,i[1],i[2]+1])
                    meiro[i[0]-1][i[1]] = i[2]+1
            #下
            if i[0] == h-1:
                pass
            else:
                if meiro[i[0]+1][i[1]] == ".":
                    now.append([i[0]+1,i[1],i[2]+1])
                    meiro[i[0]+1][i[1]] = i[2]+1
            #左
            if i[1] == 0:
                pass
            else:
                if meiro[i[0]][i[1]-1] == ".":
                    now.append([i[0],i[1]-1,i[2]+1])
                    meiro[i[0]][i[1]-1] = i[2]+1
            #右
            if i[1] == w-1:
                pass
            else:
                if meiro[i[0]][i[1]+1] == ".":
                    now.append([i[0],i[1]+1,i[2]+1])
                    meiro[i[0]][i[1]+1] = i[2]+1
            v = max(v,i[2])
            now.remove(i)
            if now == []:
                return v


saitankeiro = 0
maze,h,w = maze_maker()
for i1 in range(h):
    for j1 in range(w):
        if maze[i1][j1] != "#":
            meiro = copy.deepcopy(maze)
            saitankeiro = max(saitankeiro,search())
print(saitankeiro)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def main():
  H, W = map(int, input().split())
  M = list(itertools.chain.from_iterable([[c == '.' for c in input().strip()] for _ in range(H)]))
  size = W * H
  dist = [[size] * (size) for _ in range(size)]

  for i in range(size):
    if not M[i]:
      continue

    x, y = i % W, i // W

    dist[i][i] = 0

    if x > 0 and M[i - 1]:
      dist[i][i - 1] = 1
      dist[i - 1][i] = 1

    if y > 0 and M[i - W]:
      dist[i][i - W] = 1
      dist[i - W][i] = 1

  for i in range(size):
    for j in range(size):
      for k in range(size):
        if M[j] and M[k]:
          dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

  r = 1

  for v in itertools.chain.from_iterable(dist):
    if v < size:
      r = max(r, v)

  print(r)


if __name__ == '__main__':
  main()