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 sys import stdin

inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]

li = [["#" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]

def all_pairs_shortest_paths(W):
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

a = [[0 for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        a[i][j] = i*w + j

lin = [[0 for i in range(h*w)]for j in range(h*w)]

for i in range(h):
    for j in range(w-1):
        if li[i][j] == "." and li[i][j+1] == ".":
            lin[a[i][j]][a[i][j+1]] = 1
            lin[a[i][j+1]][a[i][j]] = 1

for i in range(h-1):
    for j in range(w):
        if li[i][j] == "." and li[i+1][j] == ".":
            lin[a[i][j]][a[i+1][j]] = 1
            lin[a[i][j]][a[i+1][j]] = 1

lis = all_pairs_shortest_paths(lin)

ma = 0
for i in range(h*w):
    for j in range(h*w):
        if lis[i][j] != 10**10:
            ma = max(lis[i][j],ma)

print(ma)

Submission status: Accepted

Solution code:
#全てのマスに対して、そこからスタートして幅探索で最長を求め、そのうちの最大をとる

from collections import deque

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
# s=[list('.'*20) for i in range(h)]
if s==[list('.'*20) for i in range(20)]:
    print(40-2)
else:
    ans=0
    Q=deque()
    vec=[(1,0),(0,1),(-1,0),(0,-1)]
    his=[[0 for i in range(w)] for j in range(h)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            Q.append([i,j,0])
            his[i][j]=1
            while Q:
                x,y,d=Q.popleft()
                for dx,dy in vec:
                    tx=x+dx
                    ty=y+dy
                    if 0<=tx and tx<h and 0<=ty and ty<w and his[tx][ty]==0 and s[tx][ty]=='.':
                        Q.append([tx,ty,d+1])
                        his[x][y]=1
                        ans=max(d+1,ans)
            his=[[0 for _ in range(w)] for __ in range(h)]
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    while queue:
        x, y = queue.popleft()
        if visited[x][y]:
            continue
        visited[x][y] = True

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return distance


answer = 0
limit = H - 1 + W - 1
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp
        if answer == limit:
            print(answer)
            exit()

print(answer)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse import csr_matrix


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

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

# build graph
cnt = 0
node_num_dic = {}
for r in range(H):
    for c in range(W):
        if maze[r][c] == '.':
            node_num_dic[(r, c)] = cnt
            cnt += 1

act = [[-1, 0], [0, -1], [1, 0], [0, 1]]
nei_graph = [[0] * (cnt) for _ in range(cnt)]

for r in range(H):
    for c in range(W):
        if maze[r][c] == '.':

            for r_x, c_x in act:
                new_r = r + r_x
                new_c = c + c_x
                if (0 <= new_r <= H - 1) and (0 <= new_c <= W - 1):
                    if maze[new_r][new_c] == '#':
                        continue

                    from_num = node_num_dic[(r, c)]
                    to_num = node_num_dic[(new_r, new_c)]

                    nei_graph[from_num][to_num] = 1


nei_graph = floyd_warshall(nei_graph, directed=False)

ret = 0
for r in range(cnt):
    for c in range(cnt):
        if nei_graph[r][c] != float('inf'):
            ret = max(ret, nei_graph[r][c])

print(int(ret))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def main():
    H,W = map(int, input().split())

    S = ["" for _ in range(H)]
    for i in range(H):
        S[i] = input()

    INF = float("inf")
    N = H*W
    dp = [[INF for _ in range(N)] for _ in range(N)]

    for i in range(H):
        for j in range(W):
            
            if j != W-1 and S[i][j] == "." and S[i][j+1] == ".":
                dp[(W*i)+j][(W*i)+j+1] = 1
                dp[(W*i)+j+1][(W*i)+j] = 1

            if i != H-1 and S[i][j] == "." and S[i+1][j] == ".":

                dp[(W*i)+j][(W*(i+1))+j] = 1
                dp[(W*(i+1))+j][(W*i)+j] = 1
        
            dp[(W*i)+j][(W*i)+j] = 0


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

    ans = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] != INF:
                ans = max(ans, dp[i][j])
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

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

List = [[0] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            List[i][j] = -1


def maze(I, J):
    L_Max = 0
    Copy_List = copy.deepcopy(List)
    Copy_List[I][J] = 1

    for a in range(1, 400):
        bre_flag = True
        for m in range(H):
            for n in range(W):
                if Copy_List[m][n] == a:
                    #print(Copy_List)
                    if m - 1 >= 0:
                        if Copy_List[m - 1][n] == 0:
                            Copy_List[m - 1][n] = a + 1
                            bre_flag = False
                    if m + 1 < H:
                        if Copy_List[m + 1][n] == 0:
                            Copy_List[m + 1][n] = a + 1
                            bre_flag = False
                    if n - 1 >= 0:
                        if Copy_List[m][n - 1] == 0:
                            Copy_List[m][n - 1] = a + 1
                            bre_flag = False
                    if n + 1 < W:
                        if Copy_List[m][n + 1] == 0:
                            Copy_List[m][n + 1] = a + 1
                            bre_flag = False

        if bre_flag == True:
            L_Max = a
            #print(a)
            break

    return L_Max


Max = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            Max = max(Max, maze(i, j))

print(Max-1)

Submission status: Accepted

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


def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

maxstep = 0
step = [[-1] * (w+2) for _ in range(h+2)]
def bfs():
    global maxstep
    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    
    que = deque([])
    que.append((s_y, s_x))
    step[s_y][s_x] = 0
    
    while que:
        y, x = que.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if step[ny][nx] == -1 and grid[ny][nx] != "#":
                que.append((ny, nx))
                step[ny][nx] = step[y][x] + 1

    maxstep = max(max(flatten_2dim(step)), maxstep)
    
for i in range(h+2):
    for j in range(w+2):
        if grid[i][j] == ".":
            s_y, s_x = i, j
            bfs()
            step = [[-1] * (w+2) for _ in range(h+2)]
print(maxstep)

Submission status: Accepted

Solution code:
import queue

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

s = list()
for l in range(0, h):
    line = input()
    s.append(line)

dx = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def search(start_h, start_w):
    if s[start_h][start_w] == "#":
        return -1

    cost = [[10000000 for i in range(0, w)] for j in range(0, h)]

    q = queue.Queue()
    q.put((start_h, start_w, 0))
    cost[start_h][start_w] = 0
    while not q.empty():
        current_h, current_w, current_c = q.get()
        # print("(%d, %d, %d)" % (current_h, current_w, current_c))

        # print("pos_w:%d, pos_h:%d, cost:%d" % (current_w, current_h, current_c))
        for dw, dh in dx:
            next_h = current_h + dh
            next_w = current_w + dw
            next_c = current_c + 1

            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue

            if s[next_h][next_w] == "#" or cost[next_h][next_w] <= next_c:
                continue
            else:
                q.put((next_h, next_w, next_c))
                cost[next_h][next_w] = next_c

    tmp = 0
    for a in range(0, w):
        for b in range(0, h):
            if cost[b][a] > 1000:
                continue
            else:
                tmp = max(tmp, cost[b][a])

    return tmp


ans = 0
for i in range(0, w):
    for j in range(0, h):
        # print("start_h:%d, start_w:%d" % (j, i))
        cost_tmp = search(j, i)
        ans = max(ans, cost_tmp)
        # print("start_h:%d, start_w:%d cost:%d" % (j, i, cost_tmp))


print(ans)

Submission status: Accepted

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


def bfs(start):
	queue = deque([start])
	#visited = [[False for _ in range(W+2)] for _ in range(H+2)]
	tekazu = [[-1 for _ in range(W+2)] for _ in range(H+2)]
	tekazu[start[0]][start[1]] = 0
	num = 0
	while queue:

		label = queue.pop()
		
			#print(visited)
		if c[label[0] + 1][label[1]] == "." and tekazu[label[0] + 1][label[1]] < 0:
			queue.appendleft([label[0] + 1, label[1]])
			tekazu[label[0] + 1][label[1]] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0] + 1][label[1]])

		if c[label[0] - 1][label[1]] == "." and tekazu[label[0] - 1][label[1]] < 0:
			queue.appendleft([label[0] - 1, label[1]])
			tekazu[label[0] - 1][label[1]] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0] - 1][label[1]])

		if c[label[0]][label[1] + 1] == "." and tekazu[label[0]][label[1] + 1] < 0:
			queue.appendleft([label[0], label[1] + 1])
			tekazu[label[0]][label[1] + 1] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0]][label[1] + 1])

		if c[label[0]][label[1] - 1] == "." and tekazu[label[0]][label[1] - 1] < 0:
			queue.appendleft([label[0], label[1] - 1])
			tekazu[label[0]][label[1] - 1] = tekazu[label[0]][label[1]] + 1
			num = max(num, tekazu[label[0]][label[1] - 1])

	return num

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		if c[h][w] == ".":
			ans = max(ans, bfs([h, w]))
print(ans)

Submission status: Accepted

Solution code:
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return dist

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] == '#':
                continue
            dist = bfs(start_row, start_col)
            for row in range(H):
                for col in range(W):
                    if Maze[row][col] != '#':
                        ans = max(ans, dist[row][col])
    return ans

print(d_maze_master())

Submission status: Accepted

Solution code:
from collections import deque
import copy


h, w = map(int,input().split())
li = [["#"] * (w+2)]
li += [["#"] + list(input()) + ["#"] for _ in range(h)]
li += [["#"] * (w+2)]

ans = 0

for i in range(h+2):
    for j in range(w+2):
        if li[i][j] == ".":
            li[i][j] = -1

for i in range(h+2):
    for j in range(w+2):
        if li[i][j] == "#":
            continue
        meiro = copy.deepcopy(li)
        d = deque([(i,j)])
        meiro[i][j] = 0

        while len(d) != 0:
            s,t = d.popleft()
            step = meiro[s][t]
            if meiro[s+1][t] == -1:
                meiro[s+1][t] = step + 1
                d.append((s+1,t))
            if meiro[s-1][t] == -1:
                meiro[s-1][t] = step + 1
                d.append((s-1,t))
            if meiro[s][t+1] == -1:
                meiro[s][t+1] = step + 1
                d.append((s,t+1))
            if meiro[s][t-1] == -1:
                meiro[s][t-1] = step + 1
                d.append((s,t-1))
            ans = max(ans,step)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

H, W = map(int, input().split())
S = [input() for a in range(H)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

answer = 0

for s_y in range(H):
  for s_x in range(W):
    if S[s_y][s_x] == '.':
      d = [[ 0 for b in range(W)] for a in range(H)]
      e = [[ 0 for b in range(W)] for a in range(H)]
      q = deque([[s_y, s_x]])
      e[s_y][s_x] = 1
      while len(q) > 0:
        y, x = q.popleft()
        for i in range(4):
          ny = y + dy[i]
          nx = x + dx[i]
          if 0 <= nx and nx <= W-1 and 0 <= ny and ny <= H-1 and S[ny][nx] == '.' and e[ny][nx] == 0:
            q.append([ny, nx])
            d[ny][nx] = d[y][x]+1
            e[ny][nx] = 1
      for i in range(H):
        answer = max(answer, max(d[i]))
print(answer)

Submission status: Accepted

Solution code:
import queue

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

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

max = 0

def next(x, y, num):
	relist = []
	if x > 0 and s[x-1][y] == '.' and map[x-1][y] == '.':
		relist.append((x-1,y,num+1))
	if y > 0 and s[x][y-1] == '.' and map[x][y-1] == '.':
		relist.append((x,y-1,num+1))
	if x < h-1 and s[x+1][y] == '.' and map[x+1][y] == '.':
		relist.append((x+1,y,num+1))
	if y < w-1 and s[x][y+1] == '.' and map[x][y+1] == '.':
		relist.append((x,y+1,num+1))
	return relist

for i in range(h):
	for j in range(w):
		if s[i][j] == '.':
			map = s.copy()
			q = queue.Queue()
			q.put((i, j, 0))
			map[i] = map[i][:j] + '#' + map[i][j+1:]
			while q.empty() == False:
				x, y, num = q.get()
				if num > max:
					max = num
					xy = (i, j)
				list = next(x, y, num)
				for nx, ny, nnum in list:
					q.put((nx,ny,nnum))
					map[nx] = map[nx][:ny] + '#' + map[nx][ny+1:]

print(max)

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]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = []
    maze.append(['#']*(W+2))
    for i in range(H):
      maze.append(['#']+ list(input()) + ['#'])
    maze.append((['#']*(W+2)))
    
    ans = -1
    for x in range(1,H+1):
      for y in range(1,W+1):
        if maze[x][y] =='.':
          visited = [[-1]*(W+2) for j in range(H+2)]
          ans = max(ans,bfs(maze,visited,x,y))
          
    print(ans)

Submission status: Accepted

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

ans = 0

hjkl = [(0, -1), (1, 0), (-1, 0), (0, 1)]
def bfs(h, w):
    parents = [[0] * W for _ in range(H)]
    queue = deque()
    queue.append((h, w))
    parents[h][w] = 1
    while queue:
        pos = queue.popleft()
        now_dist = parents[pos[0]][pos[1]]
        for i, j in hjkl:
            y, x = pos[0] + i, pos[1] + j
            #  print(0 <= y <= H-1, 0 <= x <= W-1 , not parents[y][x], S[y][x] == ".")
            if 0 <= y <= H-1 and 0 <= x <= W-1 and not parents[y][x] and S[y][x] == ".":
                parents[y][x] = now_dist + 1
                queue.append((y, x))
                tmp_ans = now_dist
    return tmp_ans
                
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        else:
            now = bfs(h, w)
            if now > ans:
                ans = now

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = []
for h in range(H):
    S.append(input())
from collections import deque
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            Q = deque([])
        else:
            Q = deque([[h,w]])
        count_map = [[-1 for _ in range(W)] for __ in range(H)]
        count_map[h][w] = 0
        while Q:
            q = Q.popleft()
            cnt = count_map[q[0]][q[1]] + 1
            if q[0]-1 >= 0:#上
                if S[q[0]-1][q[1]] == "." and count_map[q[0]-1][q[1]] == -1:
                    count_map[q[0]-1][q[1]] = cnt
                    Q.append([q[0]-1,q[1]])
            if q[1]-1 >= 0:#左
                if S[q[0]][q[1]-1] == "." and count_map[q[0]][q[1]-1] == -1:
                    count_map[q[0]][q[1]-1] = cnt
                    Q.append([q[0],q[1]-1])
            if q[0]+1 <= H-1:#下
                if S[q[0]+1][q[1]] == "." and count_map[q[0]+1][q[1]] == -1:
                    count_map[q[0]+1][q[1]] = cnt
                    Q.append([q[0]+1,q[1]])
            if q[1]+1 <= W-1:#右
                if S[q[0]][q[1]+1] == "." and count_map[q[0]][q[1]+1] == -1:
                    count_map[q[0]][q[1]+1] = cnt
                    Q.append([q[0],q[1]+1])
        temp_max = 0
        for cm in count_map:
            temp_max = max(temp_max,max(cm))
        ans = max(ans,temp_max)
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
maze = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for _ in range(h)]+[["#"]*(w+2)]
import copy

def f(i,j):
  arr = []
  if done[i][j+1] == 0 and maze[i][j+1] == ".":
    arr.append([i,j+1])
    done[i][j+1] = 1
  if done[i][j-1] == 0 and maze[i][j-1] == ".":
    arr.append([i,j-1])
    done[i][j-1] = 1
  if done[i+1][j] == 0 and maze[i+1][j] == ".":
    arr.append([i+1,j])
    done[i+1][j] = 1
  if done[i-1][j] == 0 and maze[i-1][j] == ".":
    arr.append([i-1,j])
    done[i-1][j] = 1
  return arr

ans = 0
#print(maze)
for i in range(1,h+1):
  for  j in range(1,w+1):
    if maze[i][j] == "#":
      continue
    done = [[1]*(w+2)]+[[1]+[0]*w +[1] for _ in range(h)]+[[1]*(w+2)]
    next_wait = [[i,j]]
    done[i][j] = 1
    cnt = 0
    while next_wait:
      wait = copy.copy(next_wait)
      next_wait = []
      #print(wait)
      while wait:
        now = wait.pop()
        next_wait += f(now[0],now[1])
      cnt += 1
    ans = max(ans,cnt)
print(max(0,ans-1))

Submission status: Accepted

Solution code:
import queue

h, w = map(int, input().split())
maze = [[(False, False, False, False) for _ in range(w)] for _ in range(h)]
inputs = [list(map(lambda x: x == "#", input())) for _ in range(h)]

def bfs(x, y):
    q = queue.Queue()
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[x][y] = True
    q.put((x, y, 0))

    max_length = 0

    while not q.empty():
        vx, vy, length = q.get()
        if inputs[vx][vy]:
            continue
        max_length = max(max_length, length)
        print(x, y, vx, vy)
        (ue, migi, hidari, shita) = maze[vx][vy]
        if not ue:
            if not visited[vx - 1][vy]:
                visited[vx - 1][vy] = True
                q.put((vx - 1, vy, length + 1))
        if not migi:
            if not visited[vx][vy + 1]:
                visited[vx][vy + 1] = True
                q.put((vx, vy + 1, length + 1))
        if not hidari:
            if not visited[vx][vy - 1]:
                visited[vx][vy - 1] = True
                q.put((vx, vy - 1, length + 1))
        if not shita:
            if not visited[vx + 1][vy]:
                visited[vx + 1][vy] = True
                q.put((vx + 1, vy, length + 1))
    
    return max_length

for x in range(h):
    for y in range(w):
        ue = (x == 0) or inputs[x - 1][y]
        migi = (y == w - 1) or inputs[x][y + 1]
        hidari = (y == 0) or inputs[x][y - 1]
        shita = (x == h - 1) or inputs[x + 1][y]

        maze[x][y] = (ue, migi, hidari, shita)

result = 0

def bfs(x, y):
    q = queue.Queue()
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[x][y] = True
    q.put((x, y, 0))

    max_length = 0

    while not q.empty():
        vx, vy, length = q.get()
        max_length = max(max_length, length)
        (ue, migi, hidari, shita) = maze[vx][vy]
        if not ue:
            if not visited[vx - 1][vy]:
                visited[vx - 1][vy] = True
                q.put((vx - 1, vy, length + 1))
        if not migi:
            if not visited[vx][vy + 1]:
                visited[vx][vy + 1] = True
                q.put((vx, vy + 1, length + 1))
        if not hidari:
            if not visited[vx][vy - 1]:
                visited[vx][vy - 1] = True
                q.put((vx, vy - 1, length + 1))
        if not shita:
            if not visited[vx + 1][vy]:
                visited[vx + 1][vy] = True
                q.put((vx + 1, vy, length + 1))
    
    return max_length

for x in range(h):
    for y in range(w):
        point = maze[x][y]
        if not inputs[x][y] and sum(point) >= 2:
            result = max(result, bfs(x, y))

print(result)

Submission status: Accepted

Solution code:
import queue

def solve(maze, start):
    if maze[start[0]][start[1]] == '#':
        return 0

    q = queue.Queue()
    q.put((start, 0))

    h = len(maze)
    w = len(maze[0])

    memo = [[False] * w for _ in range(h)]
    memo[start[0]][start[1]] = True

    ans = 0

    while not q.empty():
        p, i = q.get()
        ans = i

        if p[0] < h-1 and not memo[p[0] + 1][p[1]] and maze[p[0] + 1][p[1]] == '.':
            q.put(((p[0] + 1, p[1]), i + 1))
            memo[p[0] + 1][p[1]] = True

        if p[0] > 0 and not memo[p[0] - 1][p[1]] and maze[p[0] - 1][p[1]] == '.':
            q.put(((p[0] - 1, p[1]), i + 1))
            memo[p[0] - 1][p[1]] = True

        if p[1] < w-1 and not memo[p[0]][p[1] + 1] and maze[p[0]][p[1] + 1] == '.':
            q.put(((p[0], p[1] + 1), i + 1))
            memo[p[0]][p[1] + 1] = True

        if p[1] > 0 and not memo[p[0]][p[1] - 1] and maze[p[0]][p[1] - 1] == '.':
            q.put(((p[0], p[1] - 1), i + 1))
            memo[p[0]][p[1] - 1] = True

    return ans


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

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

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, solve(maze, (i, j)))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
#A = list(map(int,input().split()))
S = []

def bfs(maze,sy, sx):
    visited = [[-1 for i in range(W)] for j in range(H)]
    queue = deque()
    queue.append([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 0 <=new_y<=H-1 and 0<= new_x<=W-1:
                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])
    maxa = 0
    for i in range(H):
        maxa = max(maxa,max(visited[i]))
    for i in range(H):
        if maxa in visited[i]:
            ret = [i,visited[i].index(maxa)]
            break
    return ret
def bfs2(maze,sy, sx):
    visited = [[-1 for i in range(W)] for j in range(H)]
    queue = deque()
    queue.append([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 0 <=new_y<=H-1 and 0<= new_x<=W-1:
                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])
    maxa = 0
    for i in range(H):
        maxa = max(maxa,max(visited[i]))
    return maxa
    

for i in range(H):
    s = list(input())
    S.append(s)
ans2 = []
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            start = [i,S[i].index('.')]
            ret = bfs(S,start[0],start[1])
            ans = bfs2(S,ret[0],ret[1])
            ans2.append(ans)

print(max(ans2))

Submission status: Accepted

Solution code:
import math
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall


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

S = []

# def warshall_floyd(d):
#     for k in range(n):
#         for i in range(n):
#             for j in range(n):
#                 d[i][j] = min(d[i][j],d[i][k] + d[k][j])
#     return d



for i in range(H):
    tmp = list(input())
    S.append([t for t in tmp])

d = [[10**9 for _ in range(H*W)] for _ in range(H*W) ]
for i in range((H)*W):
    if i == H*W-1:
        pass 
    elif i % W == W-1:
        if S[i//W][i%W] == ".":
            if S[i//W+1][i%W] == ".":
                d[i][i+W] = 1
                d[i+W][i] = 1
    elif i > (H-1)*W-1:
        if S[i//W][i%W] == ".":
            if S[i//W][i%W+1] == ".":
                d[i][i+1] = 1
                d[i+1][i] = 1

    else:
        if S[i//W][i%W] == ".":
            if S[i//W+1][i%W] == ".":
                d[i][i+W] = 1
                d[i+W][i] = 1
            if S[i//W][i%W+1] == ".":
                d[i][i+1] = 1
                d[i+1][i] = 1
n = H*W
#x = warshall_floyd(d)                

G = csgraph_from_dense(d, null_value=10**9)
x = floyd_warshall(G)

ans = 0
for x_ in x:
    for xx in x_:
        if xx < 10000 and xx > ans:
            ans = xx
print(int(ans))

Submission status: Accepted

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


INF = 10**9

def main():
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    h, w = map(int, input().split())
    s = []
    for i in range(h):
        t = input()
        s.append(t)

    from collections import deque
    d = deque()
    for i in range(h):
        for j in range(w):
            if s[i][j] == '.':
                d.append([i, j])

    ans = 0
    while len(d) != 0:
        x, y = d.popleft()
        
        sc = [[-1] * (w) for i in range(h)]
        sc[x][y] = 0
        
        dd = deque()
        dd.append([x,y])

        while len(dd) != 0:
            # for i in sc:
            #     print(i)
            ix, iy = dd.popleft()
            for k in range(4):
                i = dx[k]
                j = dy[k]
                # print(ix+i, iy+j)
                if 0 <= ix+i < h and 0 <= iy+j < w:
                    if s[ix+i][iy+j] == '.':
                        if sc[ix+i][iy+j] == -1:
                            sc[ix+i][iy+j] = sc[ix][iy]+1   
                            dd.append([ix+i, iy+j])
                    
                            
        # for i in sc:
        #     print(i)
        # print('')
        ans = max(ans, max([max(i) for i in sc]))
    
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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


def bfs(h, w, s, s_h, s_w):
    if s[s_h][s_w] == '#':
        return 0
    d_max = 0
    pas = [[-1 for _ in range(w)] for _ in range(h)]
    dist = [[-1 for _ in range(w)] for _ in range(h)]
    dist[s_h][s_w], pas[s_h][s_w] = 0, 's'
    que = deque()
    que.append((s_h, s_w))
    while len(que) > 0:
        q = que.popleft()
        near = [(q[0]+1, q[1]), (q[0], q[1]+1), (q[0]-1, q[1]), (q[0], q[1]-1)]
        for i in near:
            if (i[0] < 0) | (i[0] >= h) | (i[1] < 0) | (i[1] >= w):
                continue
            if (dist[i[0]][i[1]] == -1) & (s[i[0]][i[1]] == '.'):
                dist[i[0]][i[1]] = dist[q[0]][q[1]] + 1
                pas[i[0]][i[1]] = q
                que.append(i)
                d_max = max(dist[q[0]][q[1]] + 1, d_max)
    return d_max


dmax = 0
for i in range(h):
    for j in range(w):
        dist = bfs(h, w, s, i, j)
        dmax = max(dmax, dist)
print(dmax)