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 numpy as np
import queue
from collections import deque

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

maze = np.zeros((H, W))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '.':
            maze[i, j] = 1

max_run = 0

tan = [[1, 0], [-1, 0], [0, 1], [0, -1]]
g = (100, 100)

def max_route(h, w):
    # q = queue.Queue()
    q = deque()
    checker = maze.copy()
    q.append((h, w))
    checker[h, w] = 2
    q.append(g)

    run = 0

    while len(q):
        target = q.popleft()
        if target == g:
            if len(q):
                run += 1
                q.append(g)
        else:
            for t in tan:
                check = [target[0]+t[0], target[1]+t[1]]
                if 0 <= check[0] < H and 0 <= check[1] < W:
                    if checker[check[0], check[1]] == 1:
                        q.append((check[0], check[1]))
                        checker[check[0], check[1]] = 2

    return run


for h in range(H):
    for w in range(W):
        if maze[h, w] == 0:
            continue
        cur = max_route(h, w)
        if cur > max_run:
            max_run = cur

print(max_run)

Submission status: Accepted

Solution code:
from collections import deque

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


INF = 100000000
dist = [[[[INF for j2 in range(w)] for i2 in range(h)] for j1 in range(w)] for i1 in range(h)]

def dfs(i1, j1, i2, j2):
    dist[i1][j1][i2][j2] = 0
    q = deque([(i2, j2, 0)])
    while q:
        i3, j3, d = q.popleft()
        for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            i4 = i3 + di
            j4 = j3 + dj
            if (0 <= i4 < h) and (0 <= j4 < w):
                if s[i4][j4] == "#":
                    continue
                if d + 1 < dist[i1][j1][i4][j4]:
                    dist[i1][j1][i4][j4] = d + 1
                    q.append((i4, j4, d+1))


for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        dfs(i, j, i, j)

ans = 0
for i1 in range(h):
    for j1 in range(w):
        if s[i1][j1] == "#":
            continue
        for i2 in range(h):
            for j2 in range(w):
                if s[i2][j2] == "#":
                    continue
                ans = max(ans, dist[i1][j1][i2][j2])

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
field = [list(input())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= [[0]*w for i in range(h)]
        
        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] = a[x][y]+1
                    
                    
            stack = next
        ans = max(ans,max(max(row)for row in a))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    #d = [[10 ** 12] * w for i in range(h)]
    d = []
    for i in range(h):
        d.append([10 ** 12] * w)

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

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


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

count = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            count += 1
if count == 400:
    print(38)
    exit()

ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if sx == gx and sy == gy:
                        continue
                    if maze[gx][gy] == ".":
                        ans = max(ans, bfs())

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
s = [input() for _ in range(h)]

if h==1 and w==1:
    print(0)
    exit()

maxr = 0
for hi in range(h):
    for wi in range(w):
        if s[hi][wi]==".":
            maxr += 1

def solve(sh,sw):
    res = -1
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sh][sw] = True
    q = deque([(sh,sw,0)])
    while len(q)>0:
        hi,wi,r = q.popleft()
        for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
            if hi+dh>=0 and hi+dh<h and wi+dw>=0 and wi+dw<w and s[hi+dh][wi+dw]==".":
                if not visited[hi+dh][wi+dw]:
                    visited[hi+dh][wi+dw] = True
                    q.append((hi+dh,wi+dw,r+1))
                    res = max(res, r+1)

    return res

res = -1
for shi in range(h):
    for swi in range(w):
        if s[shi][swi]=="#":
            continue
        r = solve(shi,swi)
        res = max(res, r)

print(res)

Submission status: Accepted

Solution code:
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 998244353
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


H,W = LI()
field = [list(input()) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j]==".":
            field[i][j]=inf

tmp = copy.deepcopy(field)

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


def bfs(sh,sw):
    field[sh][sw] = 0
    que = collections.deque([[sh,sw]])

    while que:
        h,w = que.popleft()
        for i in range(4):
            nh = h+dx[i]
            nw = w+dy[i]
            if (nh<0) or (nw<0) or (nw>W-1) or (nh>H-1):
                continue
            dist = field[nh][nw]
            if dist!="#":
                if dist>field[h][w]+1:
                    field[nh][nw] = field[h][w]+1
                    que.append([nh,nw])

    m = 0
    for i in range(H):
        for j in range(W):
            if field[i][j]!="#":
                if field[i][j]>m:
                    m = field[i][j]
    return m

for i in range(H):
    for j in range(W):
        field = copy.deepcopy(tmp)
        if field[i][j]=="#":
            continue
        ans.append(bfs(i,j))


print(max(ans))

Submission status: Accepted

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


from collections import deque
def bfs():
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while len(Q) > 0:
        q = Q.popleft()
        y,x =  q[0], q[1]
        if S[y][x] == "#": return
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "#" and box[ny][nx] == -1000:
                box[ny][nx] = -1
            if ny >= 0 and ny < H and nx >= 0 and nx < W and S[ny][nx] == "." and box[ny][nx] == -1000:
                box[ny][nx] = box[y][x] + 1
                Q.append([ny,nx])
    for i in range(H):
        if len(box[i]) == 0:
            continue
        else:
            ans.append(max(box[i]))
    return


H, W = map(int,input().split())
S = [ [] for _ in range(H)]
for i in range(H):S[i] = list(input())
ans = []
Q = deque()
for i in range(H):
    for j in range(W):
        #各マス目に到達するために必要な移動回数
        box = [[-1000 for _ in range(W)] for __ in range(H)]
        Q.append([i,j])
        box[i][j] = 0
        bfs()
if len(ans)==0:
    print(0)
    exit()
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque

# 入力
H, W = [int(a) for a in input().split()]
S = [None for _ in range(H)]
for i in range(H):
    S[i] = list(input())


UNVISITED = -1

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)



def bfs(sy, sx):
    dist = [[UNVISITED for _ in range(W)] for _ in range(H)]
    que = deque() # 座標
    que.append((sx, sy))
    dist[sy][sx] = 0

    while(len(que) > 0):
        x, y = que.popleft()
        for i in range(4): # 上下左右に移動
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < W) and (0 <= ny < H) and S[ny][nx] == '.' and dist[ny][nx] == UNVISITED:
                que.append((nx, ny))
                dist[ny][nx] = dist[y][x] + 1
    return( max( [max(dist[i]) for i in range(H)]))

m = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            m = max(m, bfs(i, j))

print(m)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
maze = [input() for i in range(h)]
graph = {}

for i, s_i in enumerate(maze):
  for j, s_ij in enumerate(s_i):
    if s_ij == ".":
      graph[i * w + j] = []
      if i > 0 and maze[i - 1][j] == ".":
        graph[i * w + j].append((i - 1) * w + j)
      if j > 0 and maze[i][j - 1] == ".":
        graph[i * w + j].append(i * w + j - 1)
      if j < w - 1 and maze[i][j + 1] == ".":
        graph[i * w + j].append(i * w + j + 1)
      if i < h - 1 and maze[i + 1][j] == ".":
        graph[i * w + j].append((i + 1) * w + j)

ans = 0
for start in graph.keys():
  dist = {}
  c = 0
  dist[start] = c
  hoge = {start}
  for _ in graph.keys():
    c += 1
    fuga = set()
    for h in hoge:
      fuga |= set(graph[h])
    fuga -= set(dist.keys())
    for f in fuga:
      dist[f] = c
    hoge = fuga
    if len(dist) == len(graph):
      break
  ans = max(ans, max(dist.values()))
  
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s = [[x for x in input()] for i in range(H)]

from collections import deque

def dfs(maze, sh, sw):
    visited = [[0]*W for _ in range(H)]
    queue = deque([[sh, sw, 0]])
    visited[sh][sw] = 1
    maxlen = 0
    while queue:
        h, w , tmplen = queue.pop()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            temp = tmplen
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and \
                 visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                temp += 1
                maxlen = max(maxlen, temp)
                queue.appendleft([new_h, new_w, temp])
    
    return maxlen

res = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            continue
        res = max(res, dfs(s, i, j))

print(res)

Submission status: Accepted

Solution code:
# BFS queue
import queue
import copy

import time
sss = time.time()
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
l = 0
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
            l += 1
if l >= H*W-(H-2):
    print(H+W-2)
    exit()
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(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]
        bb[x][y] == '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '#':
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    ttt = time.time()
    if ttt-sss >= 1:
        break
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from copy import deepcopy
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    H, W = MAP()
    c = [list(INPUT()) for _ in range(H)]

    C = []
    for i in range(H+2):
        tmpc = []
        for j in range(W+2):
            if i == 0 or i == H+1 or j == 0 or j == W+1: tmpc.append(0)
            else: tmpc.append(c[i-1][j-1])
        C.append(tmpc)

    sp = deque()
    for i in range(H+2):
        for j in range(W+2):
            if C[i][j] == ".": sp.append([i, j])
            elif C[i][j] == "#": C[i][j] = 0

    ans = 0
    while sp:
        copy_c = deepcopy(C)
        sy, sx = sp.popleft()
        copy_c[sy][sx] = 0
        d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        queue = deque([[sy, sx]])

        while queue:
            y, x = queue.popleft()
            for dy, dx in d:
                if copy_c[y+dy][x+dx] == ".":
                    copy_c[y+dy][x+dx] = copy_c[y][x] + 1
                    queue.append([y+dy, x+dx])

        tmp = -1
        for i in range(H+2):
            tmp = max(tmp, max(copy_c[i]))

        ans = max(tmp, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
input = raw_input

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

meiro = []
coords = []
for i in range(h):
    line = list(input())
    cur_coords = [(j, i) for j in range(w) if line[j] == "."]
    coords += cur_coords
    meiro.append(line)

graphs = []
graph = {}
for cur_coord in coords:
    x, y = cur_coord
    tugi_kouhos = [(x+dx, y) for dx in [-1, 1] if 0 <= x+dx < w]
    tugi_kouhos += [(x, y+dy) for dy in [-1, 1] if 0 <= y+dy < h]
    childs = []
    for tugi_kouho in tugi_kouhos:
        if tugi_kouho in coords:
            childs.append(tugi_kouho)
    graph[cur_coord] = childs



def calc_depth(coord1):

    cur_coord = coord1
    #end_coord = coord2
    cur_depth = 0
    used_coords = [coord1]

    childs = graph[coord1]
    while len(childs) != 0:
        cur_depth += 1
        next_childs = []
        used_coords += childs

        num_res_s = []
        for child in childs:
            res = get_childs(child, used_coords)
            #print("child", child, res)
            #print(used_coords)
            num_res = len(res)
            num_res_s.append(num_res)
            next_childs += res
        if max(num_res_s) == 0:
            return cur_depth

        childs = list(set(next_childs))
        #print(childs)

    return 0

def get_childs(jibun, used_coords):
    
    childs = []
    for child in graph[jibun]:
        if child not in used_coords:
            childs.append(child)
    return childs
       
n_coords = len(coords)
max_depth = 0
for i in range(n_coords):
    coord1 = coords[i]
    cur_depth = calc_depth(coord1)
    max_depth = max(max_depth, cur_depth)

print(max_depth)

Submission status: Accepted

Solution code:
import queue
import copy

vx = [0,1,0,-1];
vy = [1,0,-1,0];
q = queue.Queue()

hw = input().split(' ');
h = int(hw[0]);
w = int(hw[1]);
s = [ [0]*w for i in range(h)];
for i in range(h) :
	si = input();
	for j in range(w) :
		s[i][j] = si[j];

s_alt = copy.deepcopy(s);
ans = 0;
for sy in range(h) :
	for sx in range(w) :
		s = copy.deepcopy(s_alt);
		if s[sy][sx] == '.' :
			q_a = [0]*2;
			q_a[0] = sy;
			q_a[1] = sx;
			q.put(q_a);
			s[sy][sx] = 0;
			while not q.empty() :
				q_a = q.get();
				for i in range(4):
					ny = q_a[0] + vy[i];
					nx = q_a[1] + vx[i];
					if ny >= 0 and ny < h and nx >= 0 and nx < w and s[ny][nx] == '.':
						s[ny][nx] = s[q_a[0]][q_a[1]] + 1;
						q_b = [0]*2;
						q_b[0] = ny;
						q_b[1] = nx;
						q.put(q_b);
			max_path = 0;
			for i in range(h) :
				for j in range(w) :
					if s[i][j] == '#' :
						continue;
					elif s[i][j] > max_path :
						max_path = s[i][j];
			if max_path > ans :
				ans = max_path;

print(ans);

Submission status: Accepted

Solution code:
from collections import deque

def search(h, w, pre_h, pre_w):
    can = []
    if h > 0:
        can.append((h-1, w))
    if h < H-1:
        can.append((h+1, w))
    if w > 0:
        can.append((h, w-1))
    if w < W-1:
        can.append((h, w+1))
    res = []
    for h, w in can:
        if S[h][w]=='.' and (h, w) != (pre_h, pre_w):
            res.append((h, w))
    return res

def bfs(h, w):
    d = [[float('inf') for _ in range(W)] for _ in range(H)]
    d[h][w] = 0
    pre_h, pre_w = h, w
    adj_list = search(h, w, pre_h, pre_w)
    open_list = deque([])
    closed_list = []
    closed_list = set(closed_list)
    for adj in adj_list:
        open_list.append((adj[0], adj[1], pre_h, pre_w))
    cnt = 0
    while True:
        cnt+=1
        if H==20 and W==20:
            if cnt > 10000:
                break
        if len(open_list) == 0:
            break
        h, w, pre_h, pre_w = open_list.popleft()
        closed_list.add((h, w, pre_h, pre_w))
        d[h][w] = min(d[h][w], d[pre_h][pre_w] + 1)
        adj_list = search(h, w, pre_h, pre_w)
        for adj in adj_list:
            if (adj[0], adj[1], h, w) in closed_list:
                continue
            open_list.append((adj[0], adj[1], h, w))

    res = 0
    for h in range(H):
        for w in range(W):
            if not d[h][w] == float('inf'):
                res = max(res, d[h][w])
    return res

def bounday():
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                return False
    return True

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

if __name__ == "__main__":

    if bounday():
        print(H+W-2)
        exit(0)

    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            maxd = bfs(h, w)
            ans = max(maxd, ans)
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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


import copy
def clear_maze(maze,target=0):
    con = False
    for r,v1 in enumerate(maze):
        for c,v2 in enumerate(v1):
            if v2==target:
                con = True
                if maze[r-1][c]==".":
                    maze[r-1][c]=target+1
                if maze[r+1][c]==".":
                    maze[r+1][c]=target+1
                if maze[r][c-1]==".":
                    maze[r][c-1]=target+1
                if maze[r][c+1]==".":
                    maze[r][c+1]=target+1
    if con:
        return clear_maze(maze,target+1)
    else:
        return target - 1
ret = 0
for i in range(h+1):
    for j in range(w+1):
        if maze[i][j]==".":
            m = copy.deepcopy(maze)
            m[i][j]=0
            ret = max(ret,clear_maze(m))

print(ret)

Submission status: Accepted

Solution code:
from collections import deque

H, W = [int(a) for a in input().split()]

S = [None for _ in range(H)]


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

# print("H = {}, W = {}".format(H, W))
# print(S)

INF = -1

dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)



def bfs(sx, sy):
    dist = [[INF for _ in range(W)] for _ in range(H)]
    que = deque() # 座標
    que.append((sx, sy))
    dist[sy][sx] = 0

    # print("S = {}".format(S))
    # print("dist = {}".format(dist))
    while(len(que) > 0):
        # print("que = {}".format(que))
        x, y = que.popleft()
        for i in range(4): # 上下左右に移動
            nx = x + dx[i]
            ny = y + dy[i]

            # print("nx = {}, ny = {}".format(nx, ny))
            if (0 <= nx < W) and (0 <= ny < H) and S[ny][nx] == '.' and dist[ny][nx] == INF:
                que.append((nx, ny))
                dist[ny][nx] = dist[y][x] + 1
    return( max( [max(dist[i]) for i in range(H)]))

m = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            m = max(m, bfs(j, i))

print(m)

Submission status: Accepted

Solution code:
from collections import deque
import copy
h,w = map(int,input().split())
maze = [["#"] * (w+2)]
for i in range(h):
    lu = list(input())
    l = ["#"] + lu + ["#"]
    maze.append(l)
maze.append(["#"] * (w+2))


def breadth_first_search(start,W,Wn):
    work_q = deque([])
    visited = set()
    work_q.append(start)
    visited.add(start)
    Wn[start[0]][start[1]] = 0
    while work_q:
        here = work_q.popleft()
        move = [(here[0]+1,here[1]), (here[0],here[1]+1),
                (here[0]-1,here[1]),(here[0],here[1]-1)]
        for i in move:
            if W[i[0]][i[1]] == "." and i not in visited:
                work_q.append(i)
                visited.add(i)
                Wn[i[0]][i[1]] = Wn[here[0]][here[1]] + 1

    return Wn


ans = 0
for i in range(h+2):
    for j in range(w+2):
        maze_num = copy.deepcopy(maze)
        if maze[i][j] == ".":
            start = (i,j)
            wn =breadth_first_search(start,maze, maze_num)
            wn_max = 0
            for k in range(h+2):
                for l in range(w+2):
                    if wn[k][l] != "#":
                        wn_max = max(wn_max, wn[k][l])
            ans = max(ans, wn_max)
print(ans)

Submission status: Accepted

Solution code:
import copy
H,W = list(map(int,input().split()))
F = [] #map
for i in range(H):
    a = input()
    b = []
    for j in range(W):
        if a[j] == ".":
            b.append(0)
        else:
            b.append("w")
    F.append(b)
    
#print(F)

#マップからの経路を算出する関数

s = [0,0]

def n_route(s):
    """
    F:マップ配列
    s:スタート座標
    """
    C = copy.deepcopy(F)
    P = []#点の座標配列
    nP = []
    P.append(s)
    C[s[0]][s[1]] = -1
    
    c = 1
    while P:
        #print(c)
        
        for p in P:
            #print("p=",p)
            for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                np = [p[0]+v[0],p[1]+v[1]]
                #print(np)
                #行ける点があったら
                if 0<=np[0]<H and 0<=np[1]<W and C[np[0]][np[1]] == 0:
                    C[np[0]][np[1]] = c
                    #記録
                    if [np[0],np[1]] not in nP:
                        nP.append([np[0],np[1]])
        #print(nP)        
        P = []
        while nP:
            P.append(nP.pop(0))
            
        #print(C)
        #print("P:",P)
        
        c += 1
        
    return C
    
#print(n_route(s))    

Mn = [[0]*W for i in range(H)]
#print(Mn)

#Fのうち、すべての0の点でn_routeを回す。
for i in range(H):
    for j in range(W):
        if F[i][j] == 0:
            #print(i,j)
            nr = n_route([i,j])
            #print(nr)
            
            for k in range(H):
                for l in range(W):
                    if nr[k][l] != "w" and Mn[k][l] < nr[k][l]:
                        Mn[k][l] = nr[k][l]
                        
#print(Mn)

m=[]
for i in Mn:
    #print(i)
    m.append(max(i))
print(max(m))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def dfs(B,si,sj, H, W):
    R = [-1]*(H*W)
    R[si*W+sj] = 0
    d = deque([si*W+sj])
    while d:
        p = d.popleft()
        x = p//W
        y = p%W
        t = R[x*W+y]

        if x > 0:
            if B[(x-1)*W+y] == 0:
                if R[(x-1)*W+y] == -1:
                    R[(x-1)*W+y] = t+1
                    d.append((x-1)*W+y)

        if x < H-1:
            if B[(x+1)*W+y] == 0:
                if R[(x+1)*W+y] == -1:
                    R[(x+1)*W+y] = t+1
                    d.append((x+1)*W+y)
        if y > 0:
            if B[x*W+y-1] == 0:
                if R[x*W+y-1] == -1:
                    R[x*W+y-1] = t+1
                    d.append(x*W+y-1)
        if y < W-1:
            if B[x*W+y+1] == 0:
                if R[x*W+y+1] == -1:
                    R[x*W+y+1] = t+1
                    d.append(x*W+y+1)

    return max(R)
    

def main():
    H, W = map( int, input().split())
    S = [ list( input()) for _ in range(H)]
    B = [0]*(H*W)
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                B[i*W+j] = 1
    ans = 0
#    print(dfs(B,i,j,H,W))

    for i in range(H):
        for j in range(W):
            if B[i*W+j] == 1:
                continue
            t = dfs(B, i, j, H, W)
            if t > ans:
                ans = t
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from array import array

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

cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            cnt += 1

if cnt == w*h:
    print(w+h-2)
else:
    nodes = h*w

    g = []

    for i in range(nodes):
        g.append(array('l', [10000000] * (w * h)))

    for i in range(nodes):
        g[i][i] = 0

    for i in range(h):
        for j in range(w):
            if maze[i][j] == '#':
                continue
            if maze[i][j] == '.':
                if i > 0 and maze[i-1][j] != '#':
                    g[i * w + j][(i-1) * w + j] = 1
                    g[(i-1) * w + j][i * w + j] = 1
                if i < h-1 and maze[i+1][j] != '#':
                    g[i * w + j][(i+1) * w + j] = 1
                    g[(i+1) * w + j][i * w + j] = 1
                if j > 0 and maze[i][j-1] != '#':
                    g[i * w + j][i * w + j-1] = 1
                    g[i * w + j-1][i * w + j] = 1
                if j < w-1 and maze[i][j+1] != '#':
                    g[i * w + j][i * w + j+1] = 1
                    g[i * w + j+1][i * w + j] = 1

    def floyed(g, nodes):
        result = 0
        for k in range(nodes):
            for i in range(nodes):
                if i == k:
                    continue
                if g[i][k] == 10000000:
                    continue
                for j in range(nodes):
                    if g[k][j] == 10000000:
                        continue
                    if i == j or i == k or k == j:
                        continue
                    if g[i][j] > g[i][k] + g[k][j]:
                        g[i][j] = g[i][k] + g[k][j]

    floyed(g,nodes)

    result = 0
    for i in range(nodes):
        for j in range(nodes):
            if g[i][j] < 10000000 and g[i][j] > result:
                result = g[i][j]
    print(result)

Submission status: Accepted

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

chain_from_iterable = chain.from_iterable
inputs = sys.stdin.readlines()
h, w = map(int, inputs[0].split())
S = [list(map(lambda x: int(x=='.'), x)) for x in inputs[1:]]
S.insert(0, [0]*w)
S.append([0]*w)
for row in S:
    row.insert(0, 0)
    row.append(0)

max_dist = 0
for y in range(1, h+1):
    for x in range(1, w+1):
        if S[y][x] == 0:
            continue
        maze = deepcopy(S)
        maze_d = [[0]*(w+2) for _ in range(h+2)]
        queue = deque([(x, y, 0)])
        d = 0
        while queue:
            x, y, d = queue.popleft()
            d += 1
            maze[y][x] = 0
            if maze[y-1][x]:
                queue.append((x, y-1, d))
                maze[y-1][x] = 0
                maze_d[y-1][x] = d
            if maze[y][x-1]:
                queue.append((x-1, y, d))
                maze[y][x-1] = 0
                maze_d[y][x-1] = d
            if maze[y+1][x]:
                queue.append((x, y+1, d))
                maze[y+1][x] = 0
                maze_d[y+1][x] = d
            if maze[y][x+1]:
                queue.append((x+1, y, d))
                maze[y][x+1] = 0
                maze_d[y][x+1] = d
        max_dist = max(max_dist, max(chain_from_iterable(maze_d)))
print(max_dist)