Problem:


Score : 400 points

Problem Statement

Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.

The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is #, and a "road" square if S_{ij} is ..

From a road square, you can move to a horizontally or vertically adjacent road square.

You cannot move out of the maze, move to a wall square, or move diagonally.

Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.

Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.

In this situation, find the maximum possible number of moves Aoki has to make.

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

Any road square can be reached from any road square in zero or more moves.

Input

Input is given from Standard Input in the following format:

H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

Output

Print the maximum possible number of moves Aoki has to make.

Sample Input 1

3 3
...
...
...

Sample Output 1

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Sample Input 2

3 5
...#.
.#.#.
.#...

Sample Output 2

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Accepted

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

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

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        d = [[False for x in range(w)] for y in range(h)]

        stack = collections.deque()
        stack.append((i, j, 0))
        d[i][j] = True
        while stack:
            y, x, score = stack.popleft()
            if y > 0 and s[y-1][x] == '.' and not d[y-1][x]:
                stack.append((y-1, x, score+1))
                d[y-1][x] = True
            if x < w-1 and s[y][x+1] == '.' and not d[y][x+1]:
                stack.append((y, x+1, score+1))
                d[y][x+1] = True
            if y < h-1 and s[y+1][x] == '.' and not d[y+1][x]:
                stack.append((y+1, x, score+1))
                d[y+1][x] = True
            if x > 0 and s[y][x-1] == '.' and not d[y][x-1]:
                stack.append((y, x-1, score+1))
                d[y][x-1] = True
            if score > ans:
                ans = score
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited,h,w,sx,sy):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    mx = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0<=new_y<h and 0<=new_x<w:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    if visited[new_y][new_x] > mx:
                        mx = visited[new_y][new_x]
                    queue.append([new_y, new_x])

    return mx

if __name__ == "__main__":
    h, w = map(int, input().split())

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

    ans = []
    for idxi,i in enumerate(maze):
        for idxj,j in enumerate(i):
            if j == '.':
                sx,sy = idxj,idxi
                visited = [[-1]*w for j in range(h)]
                ans.append(bfs(maze, visited,h,w,sx,sy))

    print(max(ans))

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    walls = [[c == '#' for c in s] for s in args[1:]]

    count = 0
    Q = deque()

    for sy in range(h):
        for sx in range(w):
            if walls[sy][sx]:
                continue

            passed = [[False]*w for _ in range(h)]
            Q.append((sx, sy, 0))
            while Q:
                x, y, c = Q.popleft()
                if walls[y][x] or passed[y][x]:
                    continue

                passed[y][x] = True
                count = max(c, count)

                if 0 < x:
                    Q.append((x-1, y, c+1))
                if x+1 < w:
                    Q.append((x+1, y, c+1))
                if 0 < y:
                    Q.append((x, y-1, c+1))
                if y+1 < h:
                    Q.append((x, y+1, c+1))

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
import numpy as np
import queue
H, W = map(int, input().split())
S = [input() for _ in range(H)]
reach = [[False] * W for i in range(H)]
step = np.ones((H, W)) * (-1)
m = 0
q = queue.Queue()

for sh in range(H):
    for sw in range(W):
        if False and S[sh][sw] == '#':
            pass
        elif ((sh - 1 >= 0 and S[sh -1][sw] != '#') and  (sh + 1 < H and S[sh +1][sw] != '#')) and ((sw - 1 >= 0 and S[sh][sw-1] != '#') and  (sw + 1 < W and S[sh][sw + 1] != '#')):
            pass
        else:
            reach = [[False] * W for i in range(H)]
            step = np.ones((H, W)) * (-1)
            q.put((sw, sh, 0))
            while not q.empty():
                x, y, s = q.get()
                if x < 0 or W <= x or y < 0 or H <= y:
                    pass
                elif reach[y][x]:
                    pass
                elif S[y][x] == '#':
                    pass
                else:
                    reach[y][x] = True
                    step[y, x] = min(s, step[y, x]) if step[y, x] != -1 else s

                    q.put((x+1, y, s+1))
                    q.put((x-1, y, s+1))
                    q.put((x, y-1, s+1))
                    q.put((x, y+1, s+1))

            m = max(m, np.max(step))

print(int(m))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
N = H * W
board = [[int(x == "#") for x in input()] for _ in range(H)]
INF = N ** 2
A = [[INF] * N for _ in range(N)]
for i in range(N):
    A[i][i] = 0
drc = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for r in range(H):
    for c in range(W):
        for dr, dc in drc:
            nr, nc = r + dr, c + dc
            if nr < 0 or H <= nr or nc < 0 or W <= nc:
                continue
            if board[nr][nc] == 1:
                continue
            A[r * W + c][nr * W + nc] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])
ans = 0
for sr in range(H):
    for sc in range(W):
        if board[sr][sc]:
            continue
        for gr in range(H):
            for gc in range(W):
                if board[gr][gc]:
                    continue
                ans = max(ans, A[sr*W+sc][gr*W+gc])
print(ans)

Submission status: Accepted

Solution code:


def clear_maze(sx, sy, maze):

    INF=-10**9
    global cnt
    cnt=0


    distance = [[INF for i in range(w+1)] for j in range(h+1)]
    #    distance = [[None]*field_x_length]*field_y_length



    def bfs():
        global cnt
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()



            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]


                if (0 <= nx and  0 <= ny  and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))

                    distance[nx][ny] = distance[x][y] + 1
                    if cnt<=distance[nx][ny]:
                        cnt=distance[nx][ny]





        return cnt

    cnt=0
    distance = [[INF for i in range(w + 1)] for j in range(h + 1)]




    return bfs()

h,w = map(int, input().split())
maze=[list(input()) for i in range(h)]
t=[[0]*w for i in range(h)]
for i in range(h):
    maze[i]=['#']+maze[i]+['#']

maze=[['#' for i in range(w+2)]]+maze+[['#' for i in range(w+2)]]




ans=0

for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i][j]=='#':
            continue
        v=(clear_maze(i, j, maze))

        if ans<=v:
            ans=v
print(ans)

Submission status: Accepted

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

LOAD = '.'
WALL = '#'
NOT_REACHED = -1

h, w = [int(i) for i in input().split()]

s = [0] * h
for i in range(h):
    s[i] = input().strip()

def bfs(graph, queue, dist):
    _max = 0
    while queue:
        current = queue.pop(0)

        top = (current[0] - 1, current[1])
        bottom = (current[0] + 1, current[1])
        left = (current[0], current[1] - 1)
        right = (current[0], current[1] + 1)

        for target in (top, bottom, left, right):
            if (target[0] < 0) or (target[0] >= h) or (target[1] < 0) or (target[1] >= w):
                continue
            if dist[target] != NOT_REACHED:
                continue
            if graph[target[0]][target[1]] == LOAD:
                dist[target] = dist[current] + 1
                _max = max(dist[target], _max)
                queue.append(target)
    return _max

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == WALL:
            continue
        queue = [(i, j)]
        dist = {}
        for inner_i in range(h):
            for inner_j in range(w):
                dist[(inner_i, inner_j)] = NOT_REACHED
        dist[(i, j)] = 0
        ans = max(bfs(s, queue, dist), ans)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
infinity = -10**5
H,W = map(int,input().split())

A = np.zeros((H+1,W+1))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            A[i][j] = 1
        else:
            A[i][j] = -1
#print(A)
N = H*W
G=[[] for i in range(N)]

for i in range(H):
    for j in range(W):
        if A[i][j] ==1:
            if A[i+1][j] == 1:
                G[W*(i+1)+j].append(W*i+j)
                G[W*i+j].append(W*(i+1)+j)

            if A[i][j+1] == 1:
                G[W*i+(j+1)].append(W*i+j)
                G[W*i+j].append(W*i+(j+1))

def BFS (s):
    queue = deque()
    d = [infinity]*N
    
    queue.append(s)
    d[s]= 0
    
    while len(queue)!=0:
      u = queue.popleft()
      for v in G[u]:
      	if d[v] == infinity:
        	d[v] = d[u]+1
        	queue.append(v) 	  
  
    return d

ans = 0


for i in range(N):
    I = i//W
    J = i%W
    if A[I][J] == 1:
        d = BFS(i)
        for k in range(N):
            if d[k] == infinity:
                d[k] = -1
        ans = max(ans,max(d))
        
"""

for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            d = BFS(W*i+j)
        ans = max(ans,max(d))
"""
print(ans)

Submission status: Accepted

Solution code:
import heapq
import numpy as np

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

for i in range(H):
    for j, way in enumerate(input()):
        if way == '.':
            maze[i, j] = 1
        else:
            maze[i, j] = 0

able_list = []

for i in range(H):
    for j in range(W):
        able = []
        if maze[i,j] == 1:
            if 0 <= i-1 < H:
                if maze[i-1, j] == 1:
                    able.append([(i-1) * W + j, 1])
            if 0 <= j-1 < W:
                if maze[i, j-1] == 1:
                    able.append([i * W + j - 1, 1])
            if 0 <= j+1 < W:
                if maze[i, j+1] == 1:
                    able.append([i* W + j + 1, 1])
            if 0 <= i+1 < H:
                if maze[i+1, j] == 1:
                    able.append([(i+1)*W + j, 1])
        able_list.append(able)



def Dijkstra(list_adjlist, initnode):
    # list_Dを初期化
    list_D = [-1] * len(list_adjlist)
    # 始点の距離=0
    list_D[initnode] = 0
    # list_Tを初期化
    list_T = [-1] * len(list_adjlist)
    # 最短経路・距離が確定している点のリスト
    list_check = [False] * len(list_adjlist)
    # ヒープの初期化：暫定最短距離と点の名前をペアにしたリストをヒープに格納する
    list_S = []
    heapq.heappush(list_S, (list_D[initnode], initnode))
    # ヒープが空になるまで続ける
    while(len(list_S)):
        # ヒープから暫定最短距離が小さい点を取り出す
        pair_w_node = heapq.heappop(list_S)
        if list_check[pair_w_node[1]] is False:
            list_check[pair_w_node[1]] = True
            # 点pair_w_node[1]の各隣接点について調べる
            for neighbor in list_adjlist[pair_w_node[1]]:
                if list_D[neighbor[0]] == -1 or list_D[neighbor[0]] > list_D[pair_w_node[1]] + neighbor[1]:
                    list_D[neighbor[0]] = list_D[pair_w_node[1]] + neighbor[1]
                    list_T[neighbor[0]] = pair_w_node[1]
                    heapq.heappush(list_S, (list_D[neighbor[0]], neighbor[0]))
    return list_D, list_T

ans = 0
for i in range(H):
    for j in range(W):
        if maze[i, j] == 1:
            list_D, list_T = Dijkstra(able_list, i*W + j)
            if ans < max(list_D):
                ans = max(list_D)
print(ans)

Submission status: Accepted

Solution code:
def meiro(sx,sy):
    num = [[-1] * w for i in range(h)]
    num[sx][sy] = 0
    now = {(sx,sy)}
    for i in range(1,400):
        tmp = set()
        for x,y in now:
            if x > 0:
                if lis[x-1][y] == "." and num[x-1][y] == -1:
                    num[x-1][y] = i
                    tmp.add((x-1,y))
            if x < h-1:
                if lis[x+1][y] == "." and num[x+1][y] == -1:
                    num[x+1][y] = i
                    tmp.add((x+1,y))
            if y > 0:
                if lis[x][y-1] == "." and num[x][y-1] == -1:
                    num[x][y-1] = i
                    tmp.add((x,y-1))
            if y < w-1:
                if lis[x][y+1] == "." and num[x][y+1] == -1:
                    num[x][y+1] = i
                    tmp.add((x,y+1))
        now = tmp
    nu = -1
    for i in range(h):
        for j in range(w):
            if num[i][j] != -1:
                nu = max(nu,num[i][j])
    return nu

h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = -1
for sx in range(h):
    for sy in range(w):
        if lis[sx][sy] == ".":
            ans = max(ans,meiro(sx,sy))
print(ans)

Submission status: Accepted

Solution code:
import copy
from collections import deque

#反省bfsだと計算量が多くなってしまうパターンだった。bfsが正解。
def dfs(x,y,z,grid,H,W):
    if(x-1>=0):
        if(grid[y][x-1]>z or grid[y][x-1]==0):
            grid[y][x-1]=z+1
            dfs(x-1,y,z+1,grid,H,W)
    if(x+1<W):
        if(grid[y][x+1]>z or grid[y][x+1]==0):
            grid[y][x+1]=z+1
            dfs(x+1,y,z+1,grid,H,W)
    if(y-1>=0):
        if(grid[y-1][x]>z or grid[y-1][x]==0):
            grid[y-1][x]=z+1
            dfs(x,y-1,z+1,grid,H,W)
    if(y+1<H):
        if(grid[y+1][x]>z or grid[y+1][x]==0):
            grid[y+1][x]=z+1
            dfs(x,y+1,z+1,grid,H,W)
    return 0
    
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(x,y,grid,H,W):
    dist=[[0 for _ in range(W)] for _ in range(H)]
    que=deque()
    que.append((y,x))
    dist[y][x]=1
    while(len(que)>0):
        y,x=que.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if(0 <= nx < W) and (0 <= ny < H) and grid[ny][nx]==0 and dist[ny][nx] == 0:
                que.append((ny,nx))
                dist[ny][nx]=dist[y][x]+1
    return( max([max(dist[i]) for i in range(H)]))
    
H,W=map(int,input().split())
grid=[]
tmp=[]
for i in range(H):
    S=str(input())
    tmp=[]
    for j in range(W):
        if(S[j]=="."):
            tmp.append(0)
        else:
            tmp.append(-1)
    grid.append(tmp)
ans=0
result=0
for i in range(W):
    for j in range(H):
        if(grid[j][i]==0):
                ans=bfs(i,j,grid,H,W)
                result=max(result,ans)
print(result-1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and \
                visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[y][x]

H, W = map(int, input().split())

maze = ["#"*(W+2)]
for i in range(H):
    tmp = "#"
    tmp += input()
    tmp += "#"
    maze.append(tmp)
maze.append("#"*(W+2))
    
#for i in range(H+2):
#    print(maze[i])

max_bfs = 0
for sy in range(1, H+2):
    for sx in range(1, W+2):
        if maze[sy][sx] == ".":
            visited = [[-1]*(W+2) for j in range(H+2)]
            tmp_bfs = bfs(maze, visited, sy, sx)
            if tmp_bfs > max_bfs:
                max_bfs = tmp_bfs
        
print(max_bfs)

Submission status: Accepted

Solution code:
from collections import deque
r, c = map(int, input().split())
 
orig_maze = [[val for val in list(input())] for _ in range(r)]

maze = [[None for _ in range(c+2)] for _ in range(r+2)]
for r_index in range(r+2):
  for c_index in range(c+2):
    if r_index == 0 or r_index == r+1 or c_index == 0 or c_index == c+1:
      maze[r_index][c_index] = "#"
    else:
      maze[r_index][c_index] = orig_maze[r_index-1][c_index-1]
      
def wfs(queue):
    finish_dist = None
    max_way = 0
    while len(queue) > 0:
        a = queue.popleft()
        y = a[0]
        x = a[1]
        count = a[2]
        if checked_maze[y][x]:
            continue
        
        checked_maze[y][x] = True
        if not maze[y][x] == "#":
            max_way = count
            count += 1
            queue.append((a[0]+1, a[1], count))
            queue.append((a[0]-1, a[1], count))
            queue.append((a[0], a[1]+1, count))
            queue.append((a[0], a[1]-1, count))

    return max_way 
 
if __name__ == "__main__":
    result = 0
    
    for s_y in range(1, r+1):
      for s_x in range(1, c+1):
        checked_maze = [[None for _ in range(c+2)] for _ in range(r+2)]
        que = deque()
        checked_maze[s_y][s_x]= 0
        que.append((s_y, s_x, 0))
        finish_dist = wfs(que)
        result = max(result,finish_dist)
    print(result)

Submission status: Accepted

Solution code:
def bfs(H, W, h, w, maze):
    if maze[h][w] == '#':
        return 0
    visited = []
    distance = []
    for i in range(H):
        visited.append([False] * W)
        distance.append([0] * W)
    visited[h][w] = True
    position = [[h, w]]
    current = 0
    while len(position) > 0:
        h, w = iter(position.pop(0))
        current = distance[h][w]
        if h - 1 >= 0 and maze[h-1][w] == '.' and not(visited[h-1][w]):
            distance[h-1][w] = current + 1
            visited[h-1][w] = True
            position.append([h-1, w])
        if h + 1 < H and maze[h+1][w] == '.' and not(visited[h+1][w]):
            distance[h+1][w] = current + 1
            visited[h+1][w] = True
            position.append([h+1, w])
        if w - 1 >= 0 and maze[h][w-1] == '.' and not(visited[h][w-1]):
            distance[h][w-1] = current + 1
            visited[h][w-1] = True
            position.append([h, w-1])
        if w + 1 < W and maze[h][w+1] == '.' and not(visited[h][w+1]):
            distance[h][w+1] = current + 1
            visited[h][w+1] = True
            position.append([h, w+1])
    return current


H, W = map(int, input().split())
maze = []
for i in range(H):
    maze.append(input())
M = 0
for h in range(H):
    for w in range(W):
        d = bfs(H, W, h, w, maze)
        if d > M:
            M = d
print(M)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import random


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
MEIJI = [[0] * W for i in range(H)]

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "#":
            MEIJI[i][j] = 1


def findStart():
    for x in range(H):
        for y in range(W):
            if MEIJI[x][y] == 0:
                return x, y

    return False


def bfs(H, W, sx, sy):
    if MEIJI[sx][sy] == 1:
        return 0, 0, 0, -1
    d = [[-1] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque([])
    q.append((sx, sy))
    d[sx][sy] = 0

    mx = -1
    gx, gy = -1, -1
    while(len(q) != 0):
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if (0 <= nx and nx <= (H-1) and 0 <= ny and ny <= (W-1) and MEIJI[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx, ny))
                l = d[x][y] + 1
                d[nx][ny] = l

                if l > mx:
                    gx, gy = nx, ny
                    mx = l
    return d, gx, gy, mx


mx = 0
for x in range(H):
    for y in range(W):
        _, _, _, l = bfs(H, W, x, y)
        if l > mx:
            mx = l

print(mx)
exit()

sx, sy = findStart()
_, x, y, _ = bfs(H, W, sx, sy)
_, _, _, l = bfs(H, W, x, y)

if l < 0:
    l = 0

print(l)

Submission status: Accepted

Solution code:
import queue
import itertools
r,c=map(int,input().split())
s=[list(input()) for i in range(r)]
ans=0
for i1 in range(r):
    for i2 in range(c):
        p=0
        a=[[s[j][i] for i in range(c)] for j in range(r)]
        sy,sx=i1,i2
        if a[sy][sx]=="#":
            continue
                #print(sy,sx,gy,gx)
        q = queue.Queue()
        d=[(-1,0),(1,0),(0,-1),(0,1)]
        a[sy][sx]=0
        for i in d:
            if 0<=sy+i[0]<r and 0<=sx+i[1]<c and a[sy+i[0]][sx+i[1]]==".":
                a[sy+i[0]][sx+i[1]]=1
                q.put((sy+i[0],sx+i[1]))
        while not q.empty():
            y,x=q.get()
            for i in d:
                if 0<=y+i[0]<r and 0<=x+i[1]<c and a[y+i[0]][x+i[1]]==".":
                    a[y+i[0]][x+i[1]]=a[y][x]+1
                    q.put((y+i[0],x+i[1]))
        for i in range(r):
            for j in range(c):
                if type(a[i][j])==int:
                    p=max(p,a[i][j])
        ans=max(p,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import itertools
h,w=map(int,input().split())
s=["#"+input()+"#" for i in range(h)]
s.insert(0,'#'*(w+2))
s.append('#'*(w+2))
def dep(s,t,p,q,time):
    print(s)
    s[p][q]=min(time,s[p][q])
    time+=1
    if t[p+1][q]=="." :
        dep(s,t,p+1,q,time)
    if t[p-1][q]=="." :
        dep(s,t,p-1,q,time)
    if t[p][q+1]=="." :
        dep(s,t,p,q+1,time)
    if t[p][q-1]=="." :
        dep(s,t,p,q-1,time)
    return max(itertools.chain.from_iterable(s))

m=0
for i in range(h):
    for j in range(w):
        if s[i+1][j+1]=='.':
            t=[[-1 for l in range(w+2)] for l2 in range(h+2)]
            time=0
            q1=deque([])
            t[i+1][j+1]=time
            q1.appendleft([i+1,j+1])
            while len(q1)!=0:
                q=q1.pop()
                time=t[q[0]][q[1]]+1
                if s[q[0]+1][q[1]]=='.' and t[q[0]+1][q[1]]==-1:
                    t[q[0]+1][q[1]]=time
                    q1.appendleft([q[0]+1,q[1]])
                if s[q[0] - 1][q[1]] == '.' and t[q[0]-1][q[1]] == -1:
                    t[q[0] - 1][q[1]] = time
                    q1.appendleft([q[0] - 1, q[1]])
                if s[q[0]][q[1]+1] == '.' and t[q[0]][q[1]+1] == -1:
                    t[q[0] ][q[1]+1] = time
                    q1.appendleft([q[0] , q[1]+1])
                if s[q[0]][q[1]-1] == '.' and t[q[0]][q[1]-1] == -1:
                    t[q[0] ][q[1]-1] = time
                    q1.appendleft([q[0], q[1]-1])
            m=max(max(itertools.chain.from_iterable(t)),m)
print(m)

Submission status: Accepted

Solution code:
import collections

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

ans=0
for i in range(h):
  for j in range(w):
    if board[i][j]=='#':
      continue
    q=collections.deque()
    q.append((i,j,0))
    checked=[[0]*w for _ in range(h)]
    checked[i][j]=1
    while 1:
      y,x,s=q.popleft()
      if x>0 and board[y][x-1]!='#' and checked[y][x-1]==0:
        q.append((y,x-1,s+1))
        checked[y][x-1]=1
      if x<w-1 and board[y][x+1]!='#' and checked[y][x+1]==0:
        q.append((y,x+1,s+1))
        checked[y][x+1]=1
      if y>0 and board[y-1][x]!='#' and checked[y-1][x]==0:
        q.append((y-1,x,s+1))
        checked[y-1][x]=1
      if y<h-1 and board[y+1][x]!='#' and checked[y+1][x]==0:
        q.append((y+1,x,s+1))
        checked[y+1][x]=1
      if len(q)==0:
        ans=max(ans,s)
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
field = [list(input())for i in range(h)]
a= [[10**4]*w for i in range(h)]

vec = [(-1,0),(1,0),(0,1),(0,-1)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":continue
        stack = [(i,j)]
        visited = [[0]*w for i in range(h)]
        a[i][j] = 0
        
        while stack:
            next = []
            for x,y in stack:
                
                if visited[x][y]:continue

                visited[x][y] = 1
                

                for tx,ty in vec:
                    nx = x+tx
                    ny = y+ty
                    if nx < 0 or ny <0 or nx >=h or ny >=w:continue
                    if field[nx][ny] == "#" :continue
                    if visited[nx][ny]:continue
                    next.append((nx,ny))
                    a[nx][ny] = min(a[x][y] + 1,a[nx][ny])
                    
                    
            stack = next
   
        for m in range(h):
            for n in range(w):
                if a[m][n] != 10**4:
                    ans = max(ans,a[m][n])
                a[m][n] = 10**4
print(ans)

Submission status: Accepted

Solution code:
import queue
import copy
 
def ngoin(bo,now):
    return 0 <= now[0] and now[0] < len(bo) and 0 <= now[1] and now[1] < len(bo[0])
 
def minido(bo,si,sj):
    tb = [[False for i in range(len(bo[0]))] for j in range(len(bo))]
    q = queue.Queue()
    q.put([si,sj,0])
    tb[si][sj] = True
    ret = 0
    while not q.empty():
        now = q.get()
        ret = now[2]
        if ngoin(bo,[now[0]-1,now[1]]):
            if bo[now[0]-1][now[1]] and not tb[now[0]-1][now[1]]:
                q.put([now[0]-1,now[1],now[2]+1])
                tb[now[0]-1][now[1]] = True
                
        if ngoin(bo,[now[0],now[1]+1]):
            if bo[now[0]][now[1]+1] and not tb[now[0]][now[1]+1]:
                q.put([now[0],now[1]+1,now[2]+1])
                tb[now[0]][now[1]+1] = True
                
        if ngoin(bo,[now[0]+1,now[1]]):
            if bo[now[0]+1][now[1]] and not tb[now[0]+1][now[1]]:
                q.put([now[0]+1,now[1],now[2]+1])
                tb[now[0]+1][now[1]] = True
                
        if ngoin(bo,[now[0],now[1]-1]):
            if bo[now[0]][now[1]-1] and not tb[now[0]][now[1]-1]:
                q.put([now[0],now[1]-1,now[2]+1])
                tb[now[0]][now[1]-1] = True
    return ret
            
 
h,w = map(int,input().split())
bo = [[True if x == '.' else False for x in input()] for i in range(h)]
grap = [[float('inf') for i in range(h*w)] for j in range(h*w)]
ans = 0
for i in range(h*w):
    grap[i][i] = 0
for si in range(h):
    for sj in range(w):
        if not bo[si][sj]:
            continue
        ans = max(ans,minido(bo,si,sj))
                
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

H, W = map(int, input().split())

graph_list = []
for i in range(H):
    temp_graph_str = str(input())
    temp_list = [1 if i == "." else 0 for i in temp_graph_str]
    graph_list.append(temp_list)

graph_tree_list = []
for i in range(H):
    for j in range(W):
        temp_list = [0 for x in range(H * W)]
        if graph_list[i][j] == 1:
            if i > 0:
                if graph_list[i - 1][j] == 1:
                    temp_list[(i - 1) * W + j] = 1
            if i < H - 1:
                if graph_list[i + 1][j] == 1:
                    temp_list[(i + 1) * W + j] = 1
            if j > 0:
                if graph_list[i][j - 1] == 1:
                    temp_list[i * W + (j - 1)] = 1
            if j < W - 1:
                if graph_list[i][j + 1] == 1:
                    temp_list[i * W + (j + 1)] = 1
        graph_tree_list.append(temp_list)

graph_tree_array = np.array(graph_tree_list)

sp = shortest_path(graph_tree_array, directed=False, unweighted=True)

# print(sp)
sp[np.isinf(sp)] = 0
print(int(np.max(sp)))

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np

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

v_id_dict = {}
dista = np.ones((400, 400)) * np.inf

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            v_id_dict[i, j] = len(v_id_dict)

            if (i > 0) and (S[i - 1][j] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i - 1, j)]] = 1

            if (j > 0) and (S[i][j - 1] == "."):
                dista[v_id_dict[(i, j)], v_id_dict[(i, j - 1)]] = 1

dist_mat = dijkstra(
    csgraph_from_dense(dista[: len(v_id_dict), : len(v_id_dict)]),
    directed=False,
    unweighted=False,
)

print(int(dist_mat.max()))

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

ans = 0
for v in V:
    dist = bfs(v)
    ans = max(ans, max(dist.values()))
print(ans)