Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 3
...
...
...

Sample Output 1

4

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

Sample Input 2

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

Sample Output 2

10

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



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


Sample output:
4

Submission status: Accepted

Solution code:
from collections import deque

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

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


def bfs(sy, sx):
    table = [[-1] * W for _ in range(H)]
    table[sy][sx] = 0
    queue = deque([[sy, sx]])
    while queue:
        y, x = queue.popleft()
        for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.' and table[ny][nx] == -1:
                table[ny][nx] = table[y][x] + 1
                m = table[ny][nx]
                queue.append([ny, nx])
    return m


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == '.':
            ans = max(ans, bfs(y, x))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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

delta = [(-1,0),(1,0),(0,1),(0,-1)]

edges = [[-1 for _ in range(h*w)] for __ in range(h*w)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            for x in delta:
                to_i = i+x[0]
                to_j = j+x[1]
                if 0 <= to_i < h and 0 <= to_j < w:
                    if s[to_i][to_j] == '.':
                        edges[i*w+j][to_i*w+to_j] = 1
                        edges[to_i*w+to_j][i*w+j] = 1

n = h*w

def dijkstra(s,n,edges):
    #edges[i][j] : the cost of i→j
    #import 'heap'
    d = [10**13] * n
    d[s] = 0
    q = [(0,s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if c >= 0:
                if d[v] > dist_u + c:
                    d[v] = dist_u + c
                    heappush(q, (d[v], v))
    return d

ans = 0

for i in range(h):
    for j in range(w):
        d = dijkstra(i*w+j,n,edges)
        for l in d:
            if l < 10**6:
                ans = max(ans,l)

print(ans)

Submission status: Accepted

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

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

cell_name = [[np.infty]*W for i in range(H)]
count = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            cell_name[i][j] = count
            count += 1
            
tot_cell = count

dist = [[np.infty]*tot_cell for i in range(tot_cell)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            name = cell_name[i][j]
            if i >= 1:
                if S[i-1][j] == ".":
                    dist[name][cell_name[i-1][j]] = 1
            if i < H-1:
                if S[i+1][j] == ".":
                    dist[name][cell_name[i+1][j]] = 1
            if j >= 1:
                if S[i][j-1] == ".":
                    dist[name][cell_name[i][j-1]] = 1
            if j < W-1:
                if S[i][j+1] == ".":
                    dist[name][cell_name[i][j+1]] = 1

cost = floyd_warshall(dist)

max_dist = 0
for i in range(tot_cell):
    for j in range(tot_cell):
        if cost[i][j] > max_dist:
            max_dist = cost[i][j]
print(int(max_dist))

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = list(input() for _ in range(H))
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]

    def bfs(h,w):
        Q = deque([(h,w)])
        dist = [[-1] * W for _ in range(H)]
        dist[h][w] = 0
        while Q:
            y, x = Q.popleft()

            for i in range(4):
                nh = y + dy[i]
                nw = x + dx[i]

                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and dist[nh][nw] == float(-1):
                    dist[nh][nw] = dist[y][x] + 1
                    Q.append((nh,nw))

        tmp = 0
        for a in range(H):
            tmp = max(tmp, max(dist[a]))
        return tmp
    
    ans = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                ans.append(bfs(h,w))
    

    print(max(ans))


    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
S = [list(input()) for _ in range(H)]
import queue
import copy
class gridMan:
  def __init__(s, L):
    s.L = L
  def makeWall(s, x):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S):
    T = copy.deepcopy(s.L)
    T[S[0] + 1][S[1] + 1] = 1
    q = queue.Queue()
    q.put([S[0] + 1, S[1] + 1])
    ans = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      ans = max(ans, k)
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if T[hh][ww] == -1:
          continue
        t = T[hh][ww]
        if t == 0:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return ans - 1

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

g = gridMan(S)
g.makeWall(-1)
ans = 0
for sx in range(H):
  for sy in range(W):
    if S[sx][sy] == -1:
      continue
    ans = max(ans, g.dist([sx, sy]))

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int,input().split())
#alist = list(map(int, input().split()))

road=[]

for i in range(h):
    row=input()
    road.append(row)

ikel=0

for i in range(h):
    for j in range(w):
        if road[i][j]=='.':
            ikel+=1

maxrecord=0

for i in range(h):
    for j in range(w):
        turn=1
        ima=1
        now=[[i, j]]
        rlist=[]
        for hh in range(h):
            rlist.append([999]*w)
        rlist[i][j]=0
        if road[i][j]=='.':
            while ima<ikel:
                koho=[]
                for nw in now:
                    if nw[0]>0:
                        koho.append([nw[0]-1, nw[1]])
                    if nw[0]<h-1:
                        koho.append([nw[0]+1, nw[1]])
                    if nw[1]>0:
                        koho.append([nw[0], nw[1]-1])
                    if nw[1]<w-1:
                        koho.append([nw[0], nw[1]+1])
                now=[]
                for kh in koho:
                    if road[kh[0]][kh[1]]=='.':
                        if rlist[kh[0]][kh[1]]>turn:
                            rlist[kh[0]][kh[1]]=turn
                            now.append([kh[0], kh[1]])
                            ima+=1
                            record=turn
                turn+=1
            if record>maxrecord:
                maxrecord=record

print(maxrecord)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Map = []
for i in range(H):
    Map.append(input())
for i in range(H):
    for j in range(W):
        if Map[i][j] == 's':
            (sx, sy) = (j, i)
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)

def maxlen(sx, sy):
    visited = [[-1] * W for i in range(H)]
    stack = [(sx, sy)]
    visited[sy][sx] = 0
    c = 1
    while stack:
        st = []
        for a in stack:
            x = a[0]
            y = a[1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<W and 0<=ny<H and visited[ny][nx] == -1:
                    if Map[ny][nx] == '.':
                        visited[ny][nx] = c
                        st.append((nx, ny))
        stack = st
        c += 1
    return c-2
ans = -1
for i in range(H):
    for j in range(W):
        if Map[i][j] == '.':
            ans = max(ans, maxlen(j, i))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

S = [[c == '.' for c in input()] for _ in range(H)]

INF = 10 ** 5


def get_new_maze():
    return [[INF for _ in range(W)] for _ in range(H)]


def get_max_distance(w_start, h_start):
    if not S[h_start][w_start]:
        return -1
    maze_map = get_new_maze()
    q = deque()
    q.append([w_start, h_start, 0])

    ret_dist = 0

    while len(q) > 0:
        next_q = q.popleft()
        h = next_q[1]
        w = next_q[0]
        g = next_q[2]
        if S[h][w] and maze_map[h][w] > g:
            maze_map[h][w] = g
            ret_dist = max(g, ret_dist)
            if h > 0:
                q.append([w, h - 1, g + 1])
            if h < H - 1:
                q.append([w, h + 1, g + 1])
            if w > 0:
                q.append([w - 1, h, g + 1])
            if w < W - 1:
                q.append([w + 1, h, g + 1])

    return ret_dist


ans = 0

for c in range(W):
    for r in range(H):
        ans = max(ans, get_max_distance(c, r))

print(ans)

Submission status: Accepted

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


def idx(i, j):
    return i * W + j


adj = [[float('inf')] * N for _ in range(N)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        index = idx(i, j)
        if i > 0 and S[i - 1][j] == '.':
            adj[index][idx(i - 1, j)] = 1
            adj[idx(i - 1, j)][index] = 1
        if j < W - 1 and S[i][j + 1] == '.':
            adj[index][idx(i, j + 1)] = 1
            adj[idx(i, j + 1)][index] = 1
        if i < H - 1 and S[i + 1][j] == '.':
            adj[index][idx(i + 1, j)] = 1
            adj[idx(i + 1, j)][index] = 1
        if j > 0 and S[i][j - 1] == '.':
            adj[index][idx(i, j - 1)] = 1
            adj[idx(i, j - 1)][index] = 1

class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


from math import isinf

wf = WarshallFloyd(adj)
ans = 0
for r in wf._dist:
    m = max(filter(lambda x: not isinf(x), r))
    ans = max(ans, m)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 0

def bfs(sx, sy):
    global ans
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque()
    q.append((sx, sy))
    dist[sy][sx] = 0

    while q:
        v = q.popleft()
        x, y = v[0], v[1]
        for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            newx, newy = x+dx, y+dy
            if not (0 <= newx < W):
                continue
            if not (0 <= newy < H):
                continue
            if M[newy][newx] == '#':
                continue
            if dist[newy][newx] != -1:
                continue
            q.append((newx, newy))
            d = dist[y][x] + 1
            dist[newy][newx] = dist[y][x] + 1
            ans = max(ans, d)

for y in range(H):
    for x in range(W):
        if M[y][x] == '#':
            continue
        bfs(x, y)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
grid = ["#" * (w + 2)]
grid += ["#" + input() + "#" for _ in range(h)]
grid += ["#" * (w + 2)]
move = ((1, 0), (-1, 0), (0, 1), (0, -1))

ans = 0
for i, j in enumerate(grid):
    for k, l in enumerate(j):
        if l == ".":
            done = [[-1 for _ in range(w + 2)] for _ in range(h + 2)]
            done[i][k] = 0
            todo = deque([(i, k)])
            while todo:
                n, m = todo.popleft()
                d = done[n][m]
                for dn, dm in move:
                    if grid[n + dn][m + dm] == "#":
                        pass
                    elif done[n + dn][m + dm] >= 0:
                        pass
                    elif grid[n + dn][m + dm] == ".":
                        todo.append((n + dn, m + dm))
                        done[n + dn][m + dm] = d + 1
            for x in done:
                for y in x:
                    ans = max(ans, y)
print(ans)

Submission status: Accepted

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

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


for h in range(H):
    for w in range(W):
        # BFSのためのデータ構造
        if field[h][w] == "#":
            continue
        dist = [[-1] * W for _ in range(H)]
        que_x = deque()
        que_y = deque()
        dist[h][w] = 0
        que_x.append(h)
        que_y.append(w)

        # BFS開始
        while que_x and que_y:
            x = que_x[0]
            y = que_y[0]
            que_x.popleft()
            que_y.popleft()
            tmp_max = 0
            for direct in range(4):
                nx = x + dx[direct]
                ny = y + dy[direct]
                if nx < 0 or H <= nx or ny < 0 or W <= ny:      # 場外はスルー
                    continue
                if field[nx][ny] == "#":     # 壁はスルー
                    continue
                if dist[nx][ny] == -1:          # まだ見ていない時
                    que_x.append(nx)
                    que_y.append(ny)
                    dist[nx][ny] = dist[x][y] + 1   # 距離の更新
        for i in range(H):
            for k in range(W):
                tmp_max = max(dist[i][k], tmp_max)
        ans = max(tmp_max, ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def solve():
    H, W = map(int, input().split())
    S = [[0 for i in range(W)] for j in range(H)]
    visited = [[-1 for i in range(W)] for j in range(H)]
    # print(visited)

    for h in range(H):
        a = input()
        for w in range(W):
            if a[w] == '#':
                S[h][w] = -1

    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    ans = -1

    for h in range(H):
        for w in range(W):
            if S[h][w] == -1:
                continue

            visited[h][w] = 0
            queue = deque([[h, w]])
            while queue:
                y, x = queue.popleft()
                for dir in directions:
                    next_y = y + dir[0]
                    next_x = x + dir[1]
                    if next_y >= 0 and next_x >= 0 and next_y < H and next_x < W and S[next_y][next_x] == 0 and visited[next_y][next_x] == -1:
                        visited[next_y][next_x] = visited[y][x] + 1
                        queue.append([next_y, next_x])

            for row in visited:
                ma = max(row)
                ans = max(ans, ma)

            visited = [[-1 for i in range(W)] for j in range(H)]

    print(ans)


solve()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[[1 if c=='#' else 0 for c in input()] for i in range(H)]
from collections import deque
r=0
for i in range(H):
    for j in range(W):
        if S[i][j]==1:
            continue
        d=[[-1]*W for x in range(H)]
        q=deque([(i,j,0)])
        d[i][j]=0
        while q:
            x,y,d0=q.popleft()
            if x>0 and S[x-1][y]==0 and d[x-1][y]==-1:
                q.append((x-1,y,d0+1))
                d[x-1][y]=d0+1
            if y>0 and S[x][y-1]==0 and d[x][y-1]==-1:
                q.append((x,y-1,d0+1))
                d[x][y-1]=d0+1
            if x<H-1 and S[x+1][y]==0 and d[x+1][y]==-1:
                q.append((x+1,y,d0+1))
                d[x+1][y]=d0+1
            if y<W-1 and S[x][y+1]==0 and d[x][y+1]==-1:
                q.append((x,y+1,d0+1))
                d[x][y+1]=d0+1
        r=max(r,d0)
print(r)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(grid, start, wall, h, w):
    visited = [[False for _ in range(w+2)] for _ in range(h+2)]
    visited[start[0]][start[1]] = True

    queue = deque([])
    queue.append([start[0], start[1], 0])
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    cost = 0
    while queue:
        y,x,cnt = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall or visited[y_][x_]:
                continue
            queue.append([y_,x_,cnt+1])
            if cnt+1 > cost:
                cost = cnt+1
            visited[y_][x_] = True
    return cost

h,w = map(int, input().split())
wall = '#'
edges = [wall] * (w+2)
grid = [edges]
for i in range(h):
    s = input()
    grid.append([wall] + list(s) + [wall])
grid.append(edges)


cand = {2:[], 3:[], 4:[]}
dxy = [(1,0), (-1,0), (0,1), (0,-1)]
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[y][x] == wall:
            continue
        wl = 0
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                wl += 1
        if wl > 1:
            cand[wl].append((y,x))

ans = 0
starts = []
for i in [4,3,2]:
    if cand[i] != []:
        starts = cand[i]
        break
for start in starts:
    cnt = bfs(grid, start, wall, h, w)
    if cnt > ans:
        ans = cnt
print(ans)

Submission status: Accepted

Solution code:
import collections

H,W=map(int,input().split())
S=[input() for i in range(H)]
cl=set()
for sy,sx in [[h,w] for h in range(H) for w in range(W)]:
    if S[sy][sx]!="#":
        stack=collections.deque([[sy,sx,0]])
        itta=set([sy*100+sx])
        #print(stack)
        while stack:
            y,x,m=stack.popleft()
            cl.add(m)
            lst=[]

            if y>0:lst.append([-1,0])
            if y<H-1:lst.append([1,0])
            if x>0:lst.append([0,-1])
            if x<W-1:lst.append([0,1])

            for a,b in lst:
                Y=y+a
                X=x+b
                #print(Y,X)
                if S[Y][X]=="." and not Y*100+X in itta:
                    stack.append([Y,X,m+1])
                    itta.add(Y*100+X)
print(max(cl))

Submission status: Accepted

Solution code:
def dijkstra(g,st):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1]))
    return dist

h,w=map(int,input().split())
field=[[]for i in range(h)]
num=0
st=-1
for i in range(h):
    s=input()
    for j in range(w):
        field[i].append((s[j],num))
        if s[j]=='.' and st==-1:
            st=num
        num+=1
dx=[1,0,-1,0]
dy=[0,1,0,-1]

g=[[]for i in range(h*w)]
for i in range(h):
    for j in range(w):
        if field[i][j][0]!='.':
            continue
        for x,y in zip(dx,dy):
            if 0<=i+x<h and 0<=j+y<w and field[i+x][j+y][0]!='#':
                g[field[i][j][1]].append((1,field[i+x][j+y][1]))

mxx=0
for i in range(h):
    for j in range(w):
        if field[i][j][0]=='#':
            continue
        for ans in dijkstra(g,field[i][j][1]):
            if ans!=10**18:
                mxx=max(mxx,ans)
print(mxx)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict


def bfs():
    adjacent = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # 遷移先を網羅する
    cnt = defaultdict(int)
    hoge = 0
    while len(q):
        cx, cy = q.popleft()  # 現在の位置
        for a, b in adjacent:
            if 0 > cx+a or 0 > cy+b:
                continue
            if abs(cx+a) >= H or abs(cy+b) >= W:
                continue
            if visited[cx+a][cy+b]:
                continue
            if gridgraph[cx+a][cy+b] == "#":
                continue
            cnt[(cx+a, cy+b)] = cnt[(cx, cy)] + 1
            hoge = max(hoge, cnt[(cx+a, cy+b)])
            q.append((cx+a, cy+b))
            visited[cx+a][cy+b] = True
    return hoge


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

ans = 0
for i in range(H):
    for j in range(W):
        visited = [[False]*W for _ in range(H)]
        tmp = 0
        # 開始位置がi, j
        if gridgraph[i][j] == "#":
            continue
        q = deque()
        q.append((i, j))
        visited[i][j] = True
        ans = max(ans, bfs())

print(ans)

Submission status: Accepted

Solution code:
import heapq


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


def dfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '#':
        return 0
    dist[y][x] = 0

    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = []
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            if meiro[ny][nx] == '.':
                heapq.heappush(todo, [1, ny, nx])

    while todo:
        d, y, x = heapq.heappop(todo)
        if meiro[y][x] == '#':
            continue
        if dist[y][x] != -1:
                continue

        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1:
                if dist[ny][nx] == -1 and meiro[ny][nx] == '.':
                    heapq.heappush(todo, [d+1, ny, nx])

    res = 0
    for line in dist:
        res = max(max(line), res)

    return res


ans = []
for y in range(h):
    for x in range(w):
        ans.append(dfs(y, x))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy


def solve():
    H, W = map(int, input().split())
    maze = [[-2 for _ in range(W)] for _ in range(H)]
    s_point = []
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == '#':
                maze[i][j] = -1
            else:
                s_point.append((i, j))

    dyx = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    N = len(s_point)
    ans = 0
    for i in range(N):
        ans_tmp = 0
        maze_tmp = deepcopy(maze)
        sy, sx = s_point[i]
        maze_tmp[sy][sx] = 0
        que = deque([[sy, sx]])
        while que:
            cy, cx = que.popleft()
            for j in range(4):
                ny, nx = cy + dyx[j][0], cx + dyx[j][1]
                if 0 <= ny <= H - 1 and 0 <= nx <= W - 1:
                    if maze_tmp[ny][nx] == -2:
                        maze_tmp[ny][nx] = maze_tmp[cy][cx] + 1
                        ans_tmp = max(ans_tmp, maze_tmp[ny][nx])
                        que.append([ny, nx])
        ans = max(ans, ans_tmp)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import copy
from collections import deque
H,W=map(int, input().split())
Abase=[[None]*W for _ in range(H)]
starts=deque()
for h in range(H):
  s=input()
  for w in range(W):
    if s[w]=='.':
      starts.append((h,w))
    else:
      Abase[h][w]=-1
 
DIF=[(1,0),(0,1),(-1,0),(0,-1)]
answers=[]
while starts:
  A=copy.deepcopy(Abase)
  st=starts.popleft()
  A[st[0]][st[1]]=0
  d=deque()
  d.append(st)
  while d:
    point=d.popleft()
    for dif in DIF:
      x=point[0]+dif[0]
      y=point[1]+dif[1]
      if 0<=x<H and 0<=y<W and A[x][y]==None:
        d.append((x,y))
        A[x][y]=A[point[0]][point[1]]+1
  ans=0    
  for h in range(H):
    Amax=max(A[h])
    ans=max(ans,Amax)
  answers.append(ans)
print(max(answers))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math
from collections import deque

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

I_MIN = 0
I_MAX = 0
J_MIN = 0
J_MAX = 0
I_DELTA = [1, 0, -1, 0]
J_DELTA = [0, -1, 0, 1]
visited_set = set()
grid = None


def resolve():
    global visited_set, I_MAX, J_MAX, grid

    H, W = [int(x) for x in sys.stdin.readline().split()]
    grid = [list(sys.stdin.readline().split()[0]) for _ in range(H)]

    # logger.debug('{}'.format([H, W, grid]))

    I_MAX = H - 1
    J_MAX = W - 1
    queue = deque()

    max_dist = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                queue.append((i, j, 0))
                visited_set.add((i, j))
                while (len(queue) > 0):
                    i, j, dist = queue.popleft()
                    if max_dist < dist:
                        max_dist = dist
                    for d in range(4):
                        i_next = i + I_DELTA[d]
                        j_next = j + J_DELTA[d]
                        if (
                                i_next, j_next
                        ) not in visited_set and I_MIN <= i_next <= I_MAX and J_MIN <= j_next <= J_MAX:
                            visited_set.add((i_next, j_next))
                            s = grid[i_next][j_next]
                            if s == '.':
                                queue.append((i_next, j_next, dist + 1))
                else:
                    visited_set.clear()
    print(max_dist)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
...
...
..."""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 5
...#.
.#.#.
.#..."""
        output = """10"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1 2
.."""
        output = """1"""
        self.assertIO(input, output)

Submission status: Accepted

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

n = h * w
m = [[float('inf') for _ in range(n)] for _ in range(n)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            m[i * w + j][i * w + j] = 0

#for x in m: print(x)
for i in range(h):
    for j in range(w-1):
        if s[i][j] == '.':
            if s[i][j+1] == '.':
                m[i * w + j][i * w + j + 1] = 1
                m[i * w + j + 1][i * w + j] = 1

for i in range(h-1):
    for j in range(w):
        if s[i][j] == '.':
            if s[i+1][j] == '.':
                m[i*w+j][(i+1)*w+j] = 1
                m[(i+1)*w+j][i*w+j] = 1

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

m = warshall_floyd(m)
ans = 0
for i in range(n):
    for j in range(n):
        if m[i][j] != float('inf'):
            ans = max(ans, m[i][j])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque 
h,w=map(int,input().split())
S=[input() for _ in range(h)]
def long(S,start):
    tbl=[[-1]*w for _ in range(h)]
    tbl[start[0]][start[1]]=0
    todo=deque([start])
    while todo:
        a,b=todo.popleft()
        c=tbl[a][b]
        if a!=0 and S[a-1][b]=="." and tbl[a-1][b]==-1:
            tbl[a-1][b]=c+1
            todo.append([a-1,b])
        if a!=h-1 and S[a+1][b]=="." and tbl[a+1][b]==-1:
            tbl[a+1][b]=c+1
            todo.append([a+1,b])
        if b!=0 and S[a][b-1]=="." and tbl[a][b-1]==-1:
            tbl[a][b-1]=c+1
            todo.append([a,b-1])
        if b!=w-1 and S[a][b+1]=="." and tbl[a][b+1]==-1:
            tbl[a][b+1]=c+1
            todo.append([a,b+1])
    m=0
    for i in range(h):
        for j in range(w):
            m=max(m,tbl[i][j])
    return m
ans=0
for x in range(h):
    for y in range(w):
        if S[x][y]==".":
            ans=max(ans,long(S,[x,y]))
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = []
ans = 0
for _ in range(h):
  si = str(input())
  s.append(si)
for i in range(h):
  for j in range(w):
    if s[i][j] == ".":
      t = [[-1 for _ in range(w)] for _ in range(h)]
      t[i][j] = 0
      stack = [[i,j]]
      while stack:
        ni,nj = stack.pop(0)
        tn = t[ni][nj]
        for p,q in [[-1,0],[1,0],[0,-1],[0,1]]:
          x = ni+p
          y = nj+q
          if 0 <= x and x <= h-1 and 0 <= y and y <= w-1:
            if t[x][y] == -1:
              if s[x][y] == ".":
                t[x][y] = tn+1
                stack.append([x,y])
      mx = max(max(t[xx]) for xx in range(h))
      if mx > ans:
        ans = mx
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.readline
H,W = map(int, input().split())
table = []
dist = []
dx = [1,0,-1,0]
dy = [0,-1,0,1]
ans = 0

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

for sy in range(H):
    for sx in range(W):
        if table[sy][sx] == "#":
            continue
        Q = deque()
        Q.append((sy,sx))
        temp = [[-1]*W for i in range(H)]
        temp[sy][sx] = 0
        max_d = 0
        while Q:
            y,x = Q.popleft()
            for i in range(4):
                ny = y+dy[i]
                nx = x+dx[i]
                if 0<=ny<H and 0<=nx<W and temp[ny][nx]==-1 and table[ny][nx]==".":
                    Q.append((ny,nx))
                    temp[ny][nx]=temp[y][x]+1
                    max_d = max(max_d,temp[y][x]+1)
        ans = max(ans,max_d)
print(ans)