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 queue
import copy
def main():
    h,w = map(int,input().split())
    maze = []
    maze.append(['#' for i in range(w+2)])
    for i in range(h):
        tmp = input()
        tmp = list('#' + tmp + '#')
        maze.append(tmp)
    maze.append(['#' for i in range(w+2)])
    # print(maze)

    dx_ = [0,1,0,-1]
    dy_ = [1,0,-1,0]
    ans = -1
    q = queue.Queue()
    for i in range(1,h+1):
        for j in range(1,w+1):
            new_maze = copy.deepcopy(maze)
            
            dis = [[-1 for a in range(w+2)]for b in range(h+2)]
            # for a in range(1,h):
            #     for b in range(1,w):
            #         dis[a][b] = -1

            if new_maze[i][j]=='.':
                dis[i][j]=0
                q.put([i,j])
            max_dis = -1
            while(not q.empty()):
                [x,y] = q.get()
                new_maze[x][y]='#'
                # print(x,y)
                if max_dis < dis[x][y]:
                    max_dis = dis[x][y]

                for dx,dy in zip(dx_,dy_):
                    # print(x+dx,y+dy)
                    if dis[x+dx][y+dy] == -1 and new_maze[x+dx][y+dy] != '#':
                        # new_maze[x+dx][y+dy] = '#'
                        dis[x+dx][y+dy] = dis[x][y]+1
                        q.put([x+dx,y+dy])
                        # print("put",x+dx,y+dy)

                        # for i in range(len(maze)):
                        #     print(maze[i])
                        # print()
            # print("max is",max_dis)
            if ans < max_dis:
                ans = max_dis

            
    print(ans)
    return 0


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
maze = [input() for _ in [0] * h]
visited = [[0] * w for _ in [0] * h]


def bfs(start, visited, maze, lim_y, lim_x):
    queue = [start]
    visited[start[0]][start[1]] = 1
    distance = {(start[0], start[1]): 0}
    while queue:
        y, x = queue.pop(0)
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            y_, x_ = y + i, x + j
            if -1 < y_ < lim_y and -1 < x_ < lim_x and maze[y_][x_] == '.' and visited[y_][x_] == 0:
                queue.append([y_, x_])
                visited[y_][x_] = 1
                distance[(y_, x_)] = distance[(y, x)] + 1
    return max(distance.values())


max_distance = 0

all_yx = [[j, i] for i in range(w) for j in range(h)]

for start in all_yx:
    if maze[start[0]][start[1]] == '.':
        max_distance = max(max_distance, bfs(
            start, visited, maze, h, w))
        visited = [[0] * w for _ in [0] * h]

print(max_distance)

Submission status: Accepted

Solution code:
import copy

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

max_steps = 0

for i in range(h):
    for j in range(w):
        maze_search = copy.deepcopy(maze)
        if maze_search[i][j] == "#":
            continue
        
        maze_search[i][j] = 0
        numbered_area = [[i, j]]
        step_num = 0
        
        while True:
            
            if not numbered_area:
                if step_num - 1 > max_steps:
                    max_steps = step_num - 1
                break

            step_num += 1
            
            numbered_area_new = []
            for point in numbered_area:
                if point[0] < h - 1 and maze_search[point[0] + 1][point[1]] == ".":
                    maze_search[point[0] + 1][point[1]] = step_num
                    numbered_area_new.append([point[0] + 1, point[1]])
                
                if point[0] > 0 and maze_search[point[0] - 1][point[1]] == ".":
                    maze_search[point[0] - 1][point[1]] = step_num
                    numbered_area_new.append([point[0] - 1, point[1]])
                
                if point[1] < w - 1 and maze_search[point[0]][point[1] + 1] == ".":
                    maze_search[point[0]][point[1] + 1] = step_num
                    numbered_area_new.append([point[0], point[1] + 1])
                
                if point[1] > 0 and maze_search[point[0]][point[1] - 1] == ".":
                    maze_search[point[0]][point[1] - 1] = step_num
                    numbered_area_new.append([point[0], point[1] - 1])
            
            numbered_area = copy.deepcopy(numbered_area_new)
                
print(max_steps)

Submission status: Accepted

Solution code:
from queue import Queue

def bfs(HW, q, x, y):
    num = 0
    mem = [[-1]*(W+1) for i in range(H+1)]
    max_dist = 0
    mem[x][y] = 0
    while not q.empty():
        current = q.get()
        if current[0] >= H or current[0] < 0 or current[1] >= W or current[1] < 0:
            continue
        if HW[current[0]][current[1]] == '#':
            continue
        dist = mem[current[0]][current[1]]
        max_dist = max(max_dist, dist)
        if mem[current[0]+1][current[1]] == -1:
            mem[current[0]+1][current[1]] = dist+1
            q.put([current[0]+1,current[1]])
        if mem[current[0]][current[1]+1] == -1:
            mem[current[0]][current[1]+1] = dist+1
            q.put([current[0],current[1]+1])
        if mem[current[0]-1][current[1]] == -1:
            mem[current[0]-1][current[1]] = dist+1
            q.put([current[0]-1,current[1]])
        if mem[current[0]][current[1]-1] == -1:
            mem[current[0]][current[1]-1] = dist+1
            q.put([current[0],current[1]-1])
    return max_dist


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

HW = [[''] * W for i in range(H)]
for i in range(H):
    h = str(input())
    HW[i] = h

ans = 0
for si in range(H):
    for sj in range(W):
        if HW[si][sj] == '#':
            continue
        q = Queue()
        q.put([si,sj,0])
        ans = max(ans, bfs(HW, q, si, sj))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

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

    maze = []
    for i in range(H):
        maze.append(input())

    def bfs(st):

        INF = -1
        d = np.full((H, W), INF)

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

        que = deque()
        que.append(st)
        d[st[1]][st[0]] = 0

        while len(que):
            p = que.popleft()
            # print(p)

            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                if nx >= 0 and nx < W and ny >= 0 and ny < H and maze[ny][nx] != "#" and d[ny][nx] == INF:
                    # print("next is ", nx, ny)
                    que.append([nx, ny])
                    d[ny][nx] = d[p[1]][p[0]] + 1
                    # print(d)
                    # print(que)

        cost = np.max(d)
        # idx = np.unravel_index(np.argmax(d), d.shape)
        # print(idx)
        # print(cost)
        return cost

    max_cost = 0
    for y in range(H):
        for x in range(W):
            if maze[y][x] == '.':
                st = [x, y]
                cost = bfs(st)
                if cost > max_cost:
                    max_cost = cost 
    
    # print(maze[1])
    # idx, cost = bfs(st)
    # idx, cost = bfs((idx[1], idx[0]))
    print(int(max_cost))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import queue
INF = 100000000

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

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

def bfs(sx, sy):
    d = [[-1 for i in range(W)] for j in range(H)]
    d[sx][sy] = 0
    max_d = 0

    q = queue.Queue()
    q.put([sx, sy])

    while not q.empty():
        p = q.get()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (0 <= nx) & (nx < H) & (0 <= ny) & (ny < W):
                if (S[nx][ny] != "#") & (d[nx][ny] == -1):
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    q.put([nx, ny])
                    max_d = max(max_d, d[nx][ny])

    return max_d

res = 0
for sx in range(H):
    for sy in range(W):
        if S[sx][sy] == ".":
            res = max(res, bfs(sx, sy))

print(res)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


#mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

from collections import deque

def main():
	h,w=map(int,input().split())
	s=[list("#"+input().rstrip().decode('utf-8')+"#") for _ in [0]*h]
	s=[list("#"*(w+2))]+s+[list("#"*(w+2))]
	
	ans=0
	
	for i in range(1,h+1):
		for j in range(1,w+1):
			cnt = ccnt=0
			
			if s[i][j]==".":
				sumi=set()
				Q=deque()
				Q.append((i, j, cnt))
				while Q:
					x,y,cnt=Q.popleft()
					ccnt=max(cnt,ccnt)
					if (x,y) not in sumi:
						sumi.add((x, y))
						if s[x-1][y]==".":
							if (x-1,y) not in sumi:
								Q.append((x-1,y,cnt+1))
						if s[x+1][y]==".":
							if (x+1,y) not in sumi:
								Q.append((x+1,y,cnt+1))
						if s[x][y-1]==".":
							if (x,y-1) not in sumi:
								Q.append((x,y-1,cnt+1))
						if s[x][y+1]==".":
							if (x,y+1) not in sumi:
								Q.append((x,y+1,cnt+1))
							
			ans=max(ans,ccnt)
	
	print(ans)
	
	

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def bfs(start, maze, visited):
    queue = [start]
    visited[start[0]][start[1]] = True
    dist = {(start[0], start[1]): 0}
    max_dist = 0
    while queue:
        y, x = queue.pop(0)
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            x_, y_ = x + i, y + j
            if y_ >= 0 and y_ < h and x_ >= 0 and x_ < w and maze[y_][x_] == "." and not visited[y_][x_]:
                queue.append((y_, x_))
                visited[y_][x_] = True
                dist[y_, x_] = dist[y, x] + 1
                max_dist = max(max_dist, dist[y_, x_])
    return max_dist


h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
max_dist = 0
for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == ".":
            visited = [[False for _ in range(w)] for _ in range(h)]
            max_dist = max(max_dist, bfs((sy, sx), maze, visited))
print(max_dist)

Submission status: Accepted

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
INF = 10 ** 3
(H, W) = list(map(int,input().split()))
# print(H,W)

S = []
N = H * W
c = [[INF for j in range(N)] for u in range(N)]
d = [[INF for j in range(H*W)] for u in range(H*W)]

for k in range(N):
    c[k][k] = 0
    d[k][k] = 0

for i in range(H):
    S.append(input())

#print(S)

def vindex(i,j):
    global W
    return W * (i-1) + j -1

# print(vindex(H,W))
for i in range(1,H+1):
    for j in range(1,W+1):
        index = vindex(i,j)
        s = S[i-1][j-1]
        # print(index,s)
        if i != 1:
            index_t = vindex(i-1,j)
            sup = S[i-2][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
                
        if i != H:
            index_t = vindex(i+1,j)
            sup = S[i][j-1]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != 1:
            index_t = vindex(i,j-1)
            sup = S[i-1][j-2]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1
        if j != W:
            index_t = vindex(i,j+1)
            sup = S[i-1][j]
            if ( s == "." and sup == "."):
                d[index][index_t]=1 
                d[index_t][index]=1

#print("D",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])
    #print(k,d)

ans = 0 
for i in range(N):
    for j in range(N):

        if (d[i][j] != INF and d[i][j] > ans):
            ans = d[i][j]

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

m,n = map(int,list(input().split()))

dirr = ((1,0),(0,1),(-1,0),(0,-1))


def valid(tmp,maze,seen):
    x = tmp[0]
    y = tmp[1]
    if x<0 or y<0 or x>=len(maze) or y>=len(maze[0]) or (tmp in seen) or maze[x][y] == '#':
        return False
    return True

def bfs(maze,i,j):    
    seen = {(i,j)}
    q = deque()
    q.append((i,j))

    tmpMoves = 0

    while q:
        gen = deque()
        while q:
            curr = q.pop()
            for d in dirr:
                x = curr[0]+d[0]
                y = curr[1]+d[1]
                tmp = (x,y)
                if valid(tmp,maze,seen):
                    gen.append(tmp)
                    seen.add(tmp)

        if not gen:break
        tmpMoves+=1        
        q = gen

    return tmpMoves
    

maze = [['.' for _ in range(n) ] for _ in range(m)]
for i in range(m):
    maze[i] = list(input())


max_moves = 0

for i in range(m):
    for j in range(n):
        if maze[i][j] == '#':continue
        ans = bfs(maze,i,j)        
        max_moves = max(ans,max_moves)

print(max_moves)

Submission status: Accepted

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


def bfs(h, w):  # h,wは縦、横の値
    dist = [[-1] * W for iii in range(H)]  # スタートからの距離
    check_que = deque()
    dist[h][w] = 0
    check_que.append((i, j))
    d = 0
    for m in range(H):
        for n in range(W):
            if S[m][n] == "#":
                dist[m][n] = -2
    while check_que:
        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 > h_prime or h_prime >= H or 0 > w_prime or w_prime >= W:
                continue
            if dist[h_prime][w_prime] == -1:
                dist[h_prime][w_prime] = d + 1
                check_que.append((h_prime, w_prime))
    return d


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            dis = bfs(i, j)
            if ans < dis:
                ans = dis
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(n, d):
    #d[i][j]: iからjへの最短距離
    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

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

s = [float("inf") for i in range(h)]
for i in range(h):
    s[i] = list(input())

n = h*w

d = [[float("inf") for i in range(n)] for j in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

for i in range(n):
    d[i][i] = 0

for y in range(h):
    for x in range(w):
        if s[y][x] == '#':
            continue
        if y-1 >= 0 and s[y-1][x] != '#':
            d[y*w + x][(y-1)*w+x] = 1
        if y+1 < h and s[y+1][x] != '#':
            d[y*w + x][(y+1)*w+x] = 1
        if x-1 >= 0 and s[y][x-1] != '#':
            d[y*w+x][y*w+x-1] = 1
        if x+1 < w and s[y][x+1] != '#':
            d[y*w+x][y*w+x+1] = 1

d = warshall_floyd(n, d)

ans = 0

for i in range(n):
    for j in range(n):
        if d[i][j] != float("inf"):
            ans = max(ans, d[i][j])

print(ans)

Submission status: Accepted

Solution code:
def main():
	maximum = 0
	global h, w
	h, w = map(int, input().split())
	street = [[True if z=="." else False for z in input()] for y in range(h)]
	for y in range(h):
		for x in range(w):
			if get(x, y, street):
				r = bfs(x, y, [i[::] for i in street])
				# print(f"x: {x} and y: {y} and r: {r} and max: {maximum}")
				# print(street)
				maximum = max(maximum, r)
	print(maximum)
	return		

def get(x, y, l):
	return l[y][x]

def setter(x, y, z, l):
	l[y][x] = z

def bfs(x, y, visited):
	queue = [(x, y, 0)]
	maximum = 0
	setter(x, y, False, visited)
	for x, y, d in queue:
		if x>0 and get(x-1, y, visited):
			queue.append((x-1, y, d+1))
			setter(x-1, y, False, visited)
		if x<w-1 and get(x+1, y, visited):
			queue.append((x+1, y, d+1))
			setter(x+1, y, False, visited)
		if y>0 and get(x, y-1, visited):
			queue.append((x, y-1, d+1))
			setter(x, y-1, False, visited)
		if y<h-1 and get(x, y+1, visited):
			queue.append((x, y+1, d+1))
			setter(x, y+1, False, visited)
		maximum = max(maximum, d)
	return maximum



main()

Submission status: Accepted

Solution code:
def main():
	maximum = 0
	global h, w
	h, w = map(int, input().split())
	street = [[None for i in range(w)] for j in range(h)]
	for y in range(h):
		line = input()
		for x, z in enumerate(line):
			street[y][x] = True if z=="." else False
	for y in range(h):
		for x in range(w):
			if get(x, y, street):
				r = bfs(x, y, [i[::] for i in street])
				# print(f"x: {x} and y: {y} and r: {r} and max: {maximum}")
				# print(street)
				maximum = max(maximum, r)
	print(maximum)
	return		

def get(x, y, l):
	return l[y][x]

def setter(x, y, z, l):
	l[y][x] = z

def bfs(x, y, visited):
	queue = [(x, y, 0)]
	maximum = 0
	setter(x, y, False, visited)
	for x, y, d in queue:
		if x>0 and get(x-1, y, visited):
			queue.append((x-1, y, d+1))
			setter(x-1, y, False, visited)
		if x<w-1 and get(x+1, y, visited):
			queue.append((x+1, y, d+1))
			setter(x+1, y, False, visited)
		if y>0 and get(x, y-1, visited):
			queue.append((x, y-1, d+1))
			setter(x, y-1, False, visited)
		if y<h-1 and get(x, y+1, visited):
			queue.append((x, y+1, d+1))
			setter(x, y+1, False, visited)
		maximum = max(maximum, d)
	return maximum



main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, h, w, si, sj):
    q = deque([[si, sj]])
    score = [[-1] * w for i in range(h)]
    score[si][sj] = 0
    pattern = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while len(q) > 0:
        i, j = q.popleft()
        for move in pattern:
            ni, nj= i + move[0], j + move[1]
            if ni < 0 or h <= ni or nj < 0 or w <= nj:
                continue
            p = maze[ni][nj]
            if p == '#':
                continue
            if p == '.' and score[ni][nj] == -1:
                score[ni][nj] = score[i][j] + 1
                q.append([ni, nj])
    return max(map(max, score))

h, w = map(int, input().split())
maze = [input() for i in range(h)]
scores = []
for si in range(h):
    for sj in range(w):
        if maze[si][sj] == "#":
            continue
        scores.append(bfs(maze, h, w, si, sj))
print(max(scores))

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]

ans = 0
for sh in range(H):
    for sw in range(W):
        # 通れないマスはスタートになり得ない
        if G[sh][sw] == '#':
            continue

        # BFS
        dist = [[-1] * W for i in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh, sw]])

        while que:
            nh, nw = que.pop()
            for dh, dw in directions:
                # 迷路からはみ出す
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue

                # 移動先が通れないマス
                if G[nh + dh][nw + dw] == '#':
                    continue

                # 探索済み
                if dist[nh + dh][nw + dw] != -1:
                    continue

                dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                que.appendleft([nh + dh, nw + dw])

        ans = max(ans, max([max(d) for d in dist]))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0

for h in range(H):
  for w in range(W):
    if m[h][w] == "#": continue
    q = deque([(h, w, 0)])
    used = set()
    while q:
      h, w, c = q.popleft()
      if (h, w) in used: continue
      ans = max(ans, c)
      if 0 <= h-1 and m[h-1][w] == "." and (h-1, w) not in used: q.append((h-1, w, c+1))
      if h+1 < H  and m[h+1][w] == "." and (h+1, w) not in used: q.append((h+1, w, c+1))
      if 0 <= w-1 and m[h][w-1] == "." and (h, w-1) not in used: q.append((h, w-1, c+1))
      if w+1 < W  and m[h][w+1] == "." and (h, w+1) not in used: q.append((h, w+1, c+1))
      used.add((h, w))
print(ans)

Submission status: Accepted

Solution code:
# BFS queue
import queue
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[100]*W for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start):
    dist = [[100]*W for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        olddist = dist[x][y]
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            xx = x+dx
            yy = y+dy
            if xx>=0 and xx<= H-1 and yy>=0 and yy<=W-1:
                if b[xx][yy] != '#':
                    if dist[xx][yy] == 100:
                        dist[xx][yy] = olddist + 1
                        if far < olddist+1:
                            far = olddist+1
                        q.put((xx,yy))
        if q.empty():
            break
    return far
res = 0
while 1:
    now = qq.get()
    res = max([res, BFS(now)])
    if qq.empty():
        break
print(res)

Submission status: Accepted

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


INF = float('inf')

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

N = H * W
d = [[INF] * N for _ in range(N)]
for k in range(N):
    d[k][k] = 0

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':
            continue
        if y - 1 >= 0 and S[y - 1][x] != '#':
            d[y * W + x][(y - 1) * W + x] = 1
        if y + 1 < H and S[y + 1][x] != '#':
            d[y * W + x][(y + 1) * W + x] = 1
        if x - 1 >= 0 and S[y][x - 1] != '#':
            d[y * W + x][y * W + x - 1] = 1
        if x + 1 < W and S[y][x + 1] != '#':
            d[y * W + x][y * W + x + 1] = 1

warshall_floyd(N, d)

result = 0 
for i in range(N):
    for j in range(N):
        if d[i][j] != INF and d[i][j] > result:
            result = d[i][j]

print(result)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))
res = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] != '.':
            continue
        visited = [[False for _ in range(w)] for _ in range(h)]
        visited[i][j] = True
        queue = [(i, j, 0)]
        while queue:
            c_i, c_j, level = queue.pop(0)
#             visited.append((c_i, c_j))
            for n_i, n_j in ((c_i - 1, c_j), (c_i + 1, c_j), (c_i, c_j - 1), (c_i, c_j + 1)):
                if 0 <= n_i < h and 0 <= n_j < w and grid[n_i][n_j] == '.' and visited[n_i][n_j] == False:
                    queue.append((n_i, n_j, level + 1))
                    visited[n_i][n_j] = True
        res = max(res, level)
print(res)

Submission status: Accepted

Solution code:
import queue

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

max_dist = 0
for h in range(H):
    for w in range(W):
        q = queue.Queue()
        visited=[[False for w in range(W)] for h in range(H)]
        q.put((h, w))
        visited[h][w]=True
        distance = {}
        distance[(h, w)]=0

        while not q.empty():
            x, y = q.get()
            if S[x][y]=='#':
                continue

            if 0<=x-1 and x-1<=H-1 and 0<=y and y<=W-1:
                if visited[x-1][y]==False and S[x-1][y]=='.':
                    visited[x-1][y]=True
                    q.put((x-1,y))
                    distance[(x-1,y)]=distance[(x,y)]+1
            if 0<=x and x<=H-1 and 0<=y-1 and y-1<=W-1:
                if visited[x][y-1]==False and S[x][y-1]=='.':
                    visited[x][y-1]=True
                    q.put((x,y-1))
                    distance[(x,y-1)]=distance[(x,y)]+1
            if 0<=x+1 and x+1<=H-1 and 0<=y and y<=W-1:
                if visited[x+1][y]==False and S[x+1][y]=='.':
                    visited[x+1][y]=True
                    q.put((x+1,y))
                    distance[(x+1,y)]=distance[(x,y)]+1
            if 0<=x and x<=H-1 and 0<=y+1 and y+1<=W-1:
                if visited[x][y+1]==False and S[x][y+1]=='.':
                    visited[x][y+1]=True
                    q.put((x,y+1))
                    distance[(x,y+1)]=distance[(x,y)]+1
        temp_max_dist = max(distance.values())
        if max_dist<temp_max_dist:
            max_dist = temp_max_dist
print(max_dist)

Submission status: Accepted

Solution code:
# 幅優先探索で迷路を進む
# キューに次の行き先を突っ込み、popして進めるか判断していく

from collections import deque
import numpy as np

INF = pow(10, 8) * (-1)

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

## 移動の４方向ベクトル
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

## (sx, sy)から最も遠い場所までの移動距離を返す
def bfs(sx, sy):
  d = [[INF for i in range(W)] for j in range(H)] # dをINFで初期化
  d_arry = np.array(d)
  que = deque()
  # スタート地点をqueに入れ、その距離を0とする
  que.append([sx, sy])
  d_arry[sx][sy] = 0

  # queが空になるまでループ
  while len(que):
    # キューの先頭を取り出す
    pop_pair = que.popleft()
    # 移動４方向をループ
    for i in range(4):
      nx = pop_pair[0] + dx[i]
      ny = pop_pair[1] + dy[i]
    # 移動が可能かの判定と既に訪れたことがあるかの判定(d[nx][ny] != INF なら訪れたことがある)
      if 0 <= nx and nx < H and 0 <= ny and ny < W and maze[nx][ny] != '#' and d_arry[nx][ny] == INF:
        que.append([nx, ny])
        d_arry[nx][ny] = d_arry[pop_pair[0]][pop_pair[1]] + 1
    
  return d_arry.max()

## solve
max_distance = 0
for i in range(H):
  for j in range(W):
    if maze[i][j] == '.':
      res = bfs(i, j)
      if res > max_distance: max_distance = res

print(max_distance)

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))
            '''
            print('===========')
            for line in g:
                print(line)
            '''     
            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 = [input() for _ in range(h)]
ans = 0
dir = ((1,0),(0,1),(-1,0),(0,-1))

def bfs(x,y):
  dis_map = [[None if s[i][j] == '.' else -1 for j in range(w)] for i in range(h)]
  q = deque()
  dis_map[y][x] = 0
  q.append((x,y))
  while q:
    i,j = q.popleft()
    for dx,dy in dir:
      ni = i+dx
      nj = j+dy
      if 0 <= ni <= w-1 and 0 <= nj <= h-1:
        if dis_map[nj][ni] == None:
          dis_map[nj][ni] = dis_map[j][i] + 1
          q.append((ni,nj))
  ans =  max(max(dis) for dis in dis_map)
  return ans
  


for i in range (h):
  for j in range (w): #スタートの選択
    if s[i][j]=='#':continue
    dis = bfs(j,i)
    if ans < dis:
      ans = dis
print(ans)

Submission status: Accepted

Solution code:
from queue import Queue
H, W = map(int, input().split())
MAP = []
for h in range(H):
    MAP.append(input())
MAXIMUM = 0
arrows = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for h in range(H):
    for w in range(W):
        MAX = 0
        Q = Queue()
        CNTS = [[0] * W for h in range(H)]
        RIREKI = [['W'] * W for h in range(H)]
        if MAP[h][w] == '.':
            Q.put((h, w))
        else:
            continue
        while not Q.empty():
            T = Q.get()
            y, x = T[0], T[1]
            # print(x,y)
            for arrow in arrows:

                if not ((0 <= y + arrow[0] < H) and (0 <= x + arrow[1] < W)):
                    continue
                # print(x + arrow[1], y + arrow[0])
                if MAP[y + arrow[0]][x + arrow[1]] == '.' and RIREKI[y + arrow[0]][x + arrow[1]] == 'W':
                    # print(x,y)
                    CNTS[y + arrow[0]][x + arrow[1]] = CNTS[y][x] + 1
                    if MAX < CNTS[y + arrow[0]][x + arrow[1]]:
                        MAX = CNTS[y + arrow[0]][x + arrow[1]]
                    RIREKI[y + arrow[0]][x + arrow[1]] = 'G'
                    Q.put((y + arrow[0], x + arrow[1]))
                else:
                    continue
                RIREKI[y][x] = 'B'
        if MAXIMUM < MAX:
            MAXIMUM = MAX
print(MAXIMUM)

Submission status: Accepted

Solution code:
import collections
INF = 10**9
    
def next(H,W,S,current):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    for i in range(4):
        neighbor = (current[0]+dx[i],current[1]+dy[i])
        if 0 <= neighbor[0] < H and 0 <= neighbor[1] < W and S[neighbor[0]][neighbor[1]] == '.':
            yield neighbor

def bfs(start,H,W,S):
    q = collections.deque([start])
    v = 0
    visited = []
    layer = [[INF for i in range(W)] for j in range(H)]
    layer[start[0]][start[1]] = 0
    while q:
        c = q.popleft()
        if c in visited:
            continue
        visited.append(c)
        for neighbor in next(H,W,S,c):
            if neighbor not in visited:
                q.append(neighbor)
                layer[neighbor[0]][neighbor[1]] = layer[c[0]][c[1]]+1
                v = max(v,layer[neighbor[0]][neighbor[1]])
    #print(layer,start)
    return v

def main():
    H,W  = map(int, input().split())
    S = [[] for i in range(H)]
    route = 0
    for i in range(H):
        S[i]  = list(input())
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                start = (i,j)
                route = max(route,bfs(start,H,W,S))
    print(route)

if __name__ == '__main__':
    main()