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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
def maze_solve(S_1,S_2,maze_list):
    d = deque()
    d.append([S_1,S_2])
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    while d:
        v = d.popleft()
        x = v[0]
        y = v[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
    return max(list(map(lambda x: max(x), dist)))
h,w = MI()
if h==1 and w == 2:
  print(1)
elif h == 2 and w == 1:
  print(1)
else:
  ans = 0
  maze = [list(input()) for _ in range(h)]
  dist = [[-1]*w for _ in range(h)]
  start_list = []
  for i in range(h):
      for j in range(w):
          if maze[i][j] == "#":
              dist[i][j] = 0
          else:
              start_list.append([i,j])
  dist_copy = deepcopy(dist)
  for k in start_list:
      dist = deepcopy(dist_copy)
      ans = max(ans,maze_solve(k[0],k[1],maze))
  print(ans+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque

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


def bfs(sx, sy):
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [[-1] * w for _ in range(h)]
    q = deque([])

    q.append((sx, sy))
    d[sx][sy] = 0
    ans = 0

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][
                    ny] == -1:
                q.append((nx, ny))
                d[nx][ny] = d[x][y] + 1
                ans = max(ans, d[nx][ny])
    return ans


for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for _ 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 maze[sh][sw] == "#":
            continue
        dist = [[-1] * W for _ in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh, sw]])

        while que:
            nh, nw = que.pop()
            for dh, dw in directions:
                tmp_h, tmp_w = nh + dh, nw + dw
                if not ((0 <= tmp_h < H) and (0 <= tmp_w < W)):
                    continue
                if maze[tmp_h][tmp_w] == "#":
                    continue
                if dist[tmp_h][tmp_w] != -1:
                    continue

                dist[tmp_h][tmp_w] = dist[nh][nw] + 1
                que.appendleft([tmp_h, tmp_w])

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

H,W=map(int,input().split())
S=list(sys.stdin)

ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            continue
        dist=[[-1]*W for _ in range(H)]
        dist[i][j]=0
        que=deque()
        que.append((i,j))
        while que:
            i,j=que.popleft()
            ans=max(ans,dist[i][j])
            for ni,nj in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
                if not (0<=ni<H and 0<=nj<W):
                    continue
                if S[ni][nj]=='#' or dist[ni][nj]!=-1:
                    continue
                dist[ni][nj]=dist[i][j]+1
                que.append((ni,nj))

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

H,W=map(int,input().split())
S=list(sys.stdin)

ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            continue
        dist=[[-1]*W for _ in range(H)]
        dist[i][j]=0
        que=deque()
        que.append((i,j))
        while que:
            i,j=que.popleft()
            ans=max(ans,dist[i][j])
            for ni,nj in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
                if 0<=ni<H and 0<=nj<W and S[ni][nj]=='.' and dist[ni][nj]==-1:
                    dist[ni][nj]=dist[i][j]+1
                    que.append((ni,nj))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

mp = [input() for _ in range(H)]

rlt = 0
dxy = [[-1,0],[1,0],[0,-1],[0,1]]

for i in range(H):
  for j in range(W):
    if mp[i][j] == '#':
      continue
    memo = [[405]*W for _ in range(H)]
    memo[i][j] = 0
    q = deque([[i, j, 0]])
    tmp = 0
    while q:
      t = q.popleft()
      for d in dxy:
        if t[0]+d[0] >= 0 and t[0]+d[0] < H and t[1]+d[1] >= 0 and t[1]+d[1] < W:
          if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo[t[0]+d[0]][t[1]+d[1]] == 405:
            memo[t[0]+d[0]][t[1]+d[1]] = t[2] + 1
            q.append([t[0]+d[0], t[1]+d[1], t[2] + 1])
            tmp = max(tmp, t[2]+1)
    rlt = max(rlt, tmp)
    
print(rlt)

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)]

def bfs(i,j):
    if S[i][j]:
        return 0
    que=deque()
    que.append((i,j))
    vis=[row[:] for row in S]
    vis[i][j]=1
    ans=-1
    while que:
        ans+=1
        for _ in range(len(que)):
            i,j=que.popleft()
            for ni,nj in nbs(i,j):
                if not vis[ni][nj]:
                    que.append((ni,nj))
                    vis[ni][nj]=1
    return ans

def nbs(i,j):
    for ni,nj in (i-1,j),(i,j+1),(i+1,j),(i,j-1):
        if 0<=ni<H and 0<=nj<W:
            yield ni,nj

ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,bfs(i,j))

print(ans)

Submission status: Accepted

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

ans = 0
for sh in range(H):
    for sw in range(W):
        if maze[sh][sw] == "#":
            continue

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

        while que:
            nh, nw = que.pop()
            for dh, dw in direction:
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue
                if maze[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:
import sys
from collections import deque

input = sys.stdin.readline


def bfs(S, sh, sw, dist):
    dist[sh][sw] = 0
    queue = deque([(sh, sw)])
    while queue:
        h, w = queue.popleft()
        for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            y, x = h + i, w + j
            if S[y][x] == "#":
                continue
            if dist[y][x] == -1:
                dist[y][x] = dist[h][w] + 1
                queue.append((y, x))


def main():
    H, W = map(int, input().split())
    S = [None] * (H + 2)
    S[0] = S[-1] = "#" * (W + 2)
    for i in range(1, H + 1):
        S[i] = "".join(["#", input().rstrip(), "#"])

    ans = 0
    for sh in range(1, H + 1):
        for sw in range(1, W + 1):
            if S[sh][sw] == "#":
                continue
            dist = [[-1] * (W + 2) for _ in range(H + 2)]
            bfs(S, sh, sw, dist)
            max_dist = max(map(max, dist))
            ans = max(ans, max_dist)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os
import sys
import numpy as np

def solve(H, W, S):
    N = H*W
    G = np.empty((N, N), dtype=np.int64)
    G[:] = 9999999
    for h in range(H):
        for w in range(W):
            i = h*W + w
            G[i, i] = 0
            if w < W-1 and S[h][w] == S[h][w+1] == 46:
                G[i, i+1] = G[i+1, i] = 1
            if h < H-1 and S[h][w] == S[h+1][w] == 46:
                G[i, i+W] = G[i+W, i] = 1
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i, j] > G[i, k] + G[k, j]:
                    G[i, j] = G[i, k] + G[k, j]
    # G[G>=9999999] = 0
    G = np.where(G>=9999999, 0, G)

    ans = G.max()
    return ans


# >>> numba compile >>>
numba_config = [
    [solve, "i8(i8,i8,u1[:,:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<


import sys
def main():
    input= sys.stdin.buffer.readline
    H, W = map(int, input().split())
    S = np.array([np.frombuffer(input(), dtype=np.uint8) for _ in range(H)])
    print(solve(H, W, S))

main()

Submission status: Accepted

Solution code:
class Graph:
    #入力定義
    def __init__(self,vertex=[]):
        self.vertex=list(vertex)
        self.edge_number=0
        self.adjacent={v:set() for v in vertex}

    #頂点の追加
    def add_vertex(self,*adder):
        k=len(self.vertex)
        m=0

        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]=set()
                self.vertex.append(u)

    #辺の追加
    def add_edge(self,From,To):
        for w in [From,To]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if To not in self.adjacent[From]:
            self.adjacent[From].add(To)
            self.adjacent[To].add(From)
            self.edge_number+=1

    #辺を除く
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        if u in self.adjacent[v]:
            self.adjacent[u].remove(v)
            self.adjacent[v].remove(u)
            self.edge_number-=1

    #頂点を除く
    def remove_vertex(self,*v):
        for w in v:
            if w in self.adjacent:
                self.edge_number-=len(self.adjacent[w])
                for u in self.adjacent[w]:
                    self.adjacent[u].remove(w)
                del self.adjacent[w]


    #Walkの追加
    def add_walk(self,*walk):
        n=len(walk)
        for i in range(n-1):
            self.add_edge(walk[i],walk[i+1])

    #Cycleの追加
    def add_cycle(self,*cycle):
        self.add_walk(*cycle)
        self.add_edge(cycle[-1],cycle[0])

    #頂点の交換
    def __vertex_swap(self,p,q):
        self.vertex.sort()

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        return v in self.adjacent

    #グラフに辺が存在するか否か
    def edge_exist(self,u,v):
        if not(self.vertex_exist(u) and self.vertex_exist(v)):
            return False
        return u in self.adjacent[v]

    #近傍
    def neighbohood(self,v):
        if not self.vertex_exist(v):
            return []
        return list(self.adjacent[v])

    #次数
    def degree(self,v):
        if not self.vertex_exist(v):
            return 0

        return len(self.adjacent[v])

    #頂点数
    def vertex_count(self):
        return len(self.vertex)

    #辺数
    def edge_count(self):
        return self.edge_number

    #頂点vを含む連結成分
    def connected_component(self,v):
        if v not in self.adjacent:
            return []

        from collections import deque
        T={u:False for u in self.adjacent}
        T[v]=True
        S=deque([v])

        while S:
            u=S.popleft()
            for w in self.adjacent[u]:
                if not T[w]:
                    T[w]=True
                    S.append(w)

        return [x for x in self.adjacent if T[x]]

    #距離
    def distance(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.adjacent}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
                    if x==v:
                        return T[x]
        return inf

    #ある1点からの距離
    def distance_all(self,u):
        from collections import deque
        inf=float("inf")
        T={v:inf  for v in self.adjacent}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        return T

    #最短路
    def shortest_path(self,u,v):
        from collections import deque
        inf=float("inf")
        T={v:[] for v in self.vertex}

        if u==v:
            return 0

        Q=deque([u])
        T[u]=[u]
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if not T[x]:
                    T[x]=T[w]+[x]
                    Q.append(x)
                    if x==v:
                        return T[x]
        return None

    #グラフの直径
    def diameter(self):
        from collections import deque
        inf=float("inf")

        u=self.vertex[0]
        T={u:inf  for u in self.vertex}

        Q=deque([u])
        T[u]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)

        w=max(T,key=lambda x:T[x])
        T={u:inf  for u in self.vertex}

        Q=deque([w])
        T[w]=0
        while Q:
            w=Q.popleft()
            for x in self.adjacent[w]:
                if T[x]==inf:
                    T[x]=T[w]+1
                    Q.append(x)
        w=max(T,key=lambda x:T[x])
        return T[w]

def Grid_Graph(m,n):
    E=[]
    for x in range(1,m+1):
        E+=[(x,y) for y in range(1,n+1)]

    G=Graph(E)
    H=[(1,0),(0,1)]

    for y in range(1,n+1):
        for x in range(1,m+1):
            for a,b in H:
                p=x+a
                q=y+b
                if 1<=p<=m and 1<=q<=n:
                    G.add_edge((x,y),(p,q))
    return G
#====================================================
H,W=map(int,input().split())

G=Grid_Graph(W,H)
for y in range(H):
    S=input()
    for x in range(W):
        if S[x]=="#":
            G.remove_vertex((x+1,y+1))

M=-1
for a in G.adjacent:
    U=G.distance_all(a)
    M=max(M,max(U.values()))
print(M)

Submission status: Accepted

Solution code:
import queue
h,w = map(int,input().split())
v = [(1, 0), (0, 1), (-1, 0), (0, -1)]
s = [input() for i in range(h)]

ans = 0
que = queue.Queue()
for i in range(h * w):
    c = 0
    d = [[h*w] * w for i in range(h)]
    p = (i//w, i%w)
    if s[p[0]][p[1]] == '#':
        continue
    d[p[0]][p[1]] = 0
    que.put(p)
    while not que.empty():
        y,x = que.get()
        c = d[y][x]
        for dy, dx in v:
            yy = y + dy
            xx = x + dx
            if yy < 0 or xx < 0 or h <= yy or w <= xx:
                continue
            if s[yy][xx] == '#':
                continue
            if d[yy][xx] < h*w:
                continue
            que.put((yy, xx))
            d[yy][xx] = c + 1
    ans = max(ans, c)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys


H, W = map(int, input().split())
field = ["o" for _ in range(H+2)] #indexed from 1
for i in range(1, H+1):
    field[i] = "#" + input() + "#"
field[0] = "#"*(W+2)
field[H+1] = "#"*(W+2)

idxs = []
dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
for row in range(1, H+1):
    for col in range(1, W+1):
        if field[row][col] == ".":
            idxs.append((row, col))
# graph = {idx: deque() for idx in idxs}
# for idx in idxs:
#     x = idx[0]
#     y = idx[1]
#     for dx, dy in dxdy:
#         if field[x+dx][y+dy] == ".":
#             graph[idx].append((x+dx, y+dy))


def bfs(u,v):
    dist = [[-1] * (W+1) for _ in range(H+1)] #indexed from 1
    seen = [[0] * (W+1) for _ in range(H+1)] #indexed from 1
    queue = deque()
    seen[u][v] = 1
    dist[u][v] = 0
    queue.append((u,v))
    graph = {idx: deque() for idx in idxs}
    for idx in idxs:
        x = idx[0]
        y = idx[1]
        for dx, dy in dxdy:
            if field[x+dx][y+dy] == ".":
                graph[idx].append((x+dx, y+dy))
    while queue:
        p, q = queue[0]
        if not graph[(p,q)]:
            queue.popleft()
            continue
        g,h = graph[(p,q)].popleft()
        if seen[g][h]:
            continue
        seen[g][h] = 1
        dist[g][h] = dist[p][q] + 1
        queue.append((g,h))
    ans = -1
    for i in range(1, H+1):
        for j in range(1, W+1):
            ans = max(ans, dist[i][j])
    return ans


res = -1
for sx, sy in idxs:
    res = max(res, bfs(sx, sy))
print(res)

Submission status: Accepted

Solution code:
from collections import deque
import copy

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

def bfs(x,y):
    check = copy.deepcopy(S)
    que = deque()
    que.append((x,y))
    check[y][x] = 0
    while que.__len__() != 0:
        x,y = que.popleft()
        tmp = check[y][x]
        for dx,dy in (1,0),(-1,0),(0,1),(0,-1):
            sx = x + dx
            sy = y + dy
            if -1 < sx < W and -1 < sy < H:
                if check[sy][sx] == '.':
                    check[sy][sx] = tmp + 1
                    que.append((sx,sy))
    return tmp

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

print(ans)

Submission status: Accepted

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

todo = deque()
done = set()
ans = 0
for sh in range(H):
    for sw in range(W):
        if S[sh][sw] == "#":
            continue
        s = (sh, sw)
        done.clear()
        done.add(s)
        todo.append((s, 0))
        while todo:
            p, count = todo.popleft()
            ncount = count + 1
            for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nh, nw = p[0] + dh, p[1] + dw
                if S[nh][nw] == "#":
                    continue
                np = (nh, nw)
                if np in done:
                    continue
                done.add(np)
                ans = max(ans, ncount)
                todo.append((np, ncount))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


# 隣り合ったマスへ移動するためのテーブル
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

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

# 全ての"."の地点からBFSしてスタートからの各地点への移動回数(深さ)を調べ、最大のものを出力する
def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            # スタートが壁の場合
            if maze[i][j] == "#":
                continue
        
            # BFSの初期化、初期条件
            dist = [[-1] * W for _ in range(H)]
            dist[i][j] = 0
            que = deque()
            que.append([i, j])

            # BFSループ
            while que:
                y, x = que.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    # 迷路から外れる場合
                    if nx >= W or nx < 0 or ny >= H or ny < 0:
                        continue
                    # 既に探索済みの場合
                    if dist[ny][nx] != -1:
                        continue
                    # 隣が壁の場合
                    if maze[ny][nx] == "#":
                        continue
                    dist[ny][nx] = dist[y][x] + 1
                    que.append([ny, nx])

            ans = max(ans, max(max(steps) for steps in dist))
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque


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

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


def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == ".":
                dist = [[-1] * W for _ in range(H)]
                dist[i][j] = 0
                que = deque()
                que.append([i, j])

                while que:
                    y, x = que.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx >= W or nx < 0 or ny >= H or ny < 0:
                            continue
                        if dist[ny][nx] != -1:
                            continue
                        if maze[ny][nx] == "#":
                            continue
                        dist[ny][nx] = dist[y][x] + 1
                        que.append([ny, nx])
            else:
                continue
            ans = max(ans, max(max(steps) for steps in dist))
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque
import copy
H,W = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for i in range(H):
    grid[i] = list(input())
ans = 0
for sy in range(H):
    for sx in range(W):
        if grid[sy][sx] == '#':
            continue
        now_grid = copy.deepcopy(grid)
        time_grid = [[-1]*W for _ in range(H)]
        queue = deque()
        queue.append([sy,sx,0])
        now_grid[sy][sx] = '#'
        while queue:
            y,x,t = queue.popleft()
            for next_y, next_x in [[y+1, x],[y,x+1],[y-1,x],[y,x-1]]:
                if 0<= next_y < H and 0 <= next_x < W and now_grid[next_y][next_x] != '#':
                    queue.append([next_y,next_x,t+1])
                    time_grid[next_y][next_x] = t+1
                    now_grid[next_y][next_x] = '#'
        Max= 0
        for i in range(H):
            for j in range(W):
                Max = max(Max,time_grid[i][j])
        ans = max(ans, Max)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = []
S.append(['#' for _ in range(W+2)])
for _ in range(H):
  s = input()
  s = '#' + s + '#'
  S.append([])
  for k in range(W+2):
    S[-1].append(s[k])
S.append(['#' for _ in range(W+2)])
b = 0
start = []
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h][w] == '.':
      c = 0
      b += 1
      if S[h+1][w] == '.':
        c += 1
      if S[h-1][w] == '.':
        c += 1
      if S[h][w+1] == '.':
        c += 1
      if S[h][w-1] == '.':
        c += 1
      if c == 1:
        start.append([h, w])
if len(start) == 0:
  for h in range(1, H+1):
    for w in range(1, W+1):
      if S[h][w] == '.':
        c = 0
        if S[h+1][w] == '.':
          c += 1
        if S[h-1][w] == '.':
          c += 1
        if S[h][w+1] == '.':
          c += 1
        if S[h][w-1] == '.':
          c += 1
        if c == 2:
          start.append([h, w])
#dfs 121ms
"""
def solve(nowh, noww, point):
  counter[nowh][noww] = point
  flag = True
  if counter[nowh+1][noww] > point + 1:
    solve(nowh+1, noww, point+1)
    flag = False
  if counter[nowh-1][noww] > point + 1:
    solve(nowh-1, noww, point+1)
    flag = False
  if counter[nowh][noww+1] > point + 1:
    solve(nowh, noww+1, point+1)
    flag = False
  if counter[nowh][noww-1] > point + 1:
    solve(nowh, noww-1, point+1)
    flag = False
  if flag:
    return 0
ans = 0
for item in start:
  original_counter = [[b for _ in range(W+2)] for _ in range(H+2)]
  for k in range(H+2):
    for j in range(W+2):
      if S[k][j] == '#':
        original_counter[k][j] = -1
  counter = original_counter
  solve(item[0], item[1], 0)
  anskouho = 0
  for h in range(1, H+1):
    for w in range(1, W+1):
      anskouho = max(anskouho, counter[h][w])
  ans = max(ans, anskouho)

print(ans)
"""
#bfs
def solve(now, point):
  nextlist = []
  for n in now:
    if counter[n[0]+1][n[1]] > point + 1:
      counter[n[0]+1][n[1]] = point + 1
      nextlist.append([n[0]+1, n[1]])
    if counter[n[0]][n[1]+1] > point + 1:
      nextlist.append([n[0], n[1]+1])
      counter[n[0]][n[1]+1] = point + 1
    if counter[n[0]-1][n[1]] > point + 1:
      nextlist.append([n[0]-1, n[1]])
      counter[n[0]-1][n[1]] = point + 1
    if counter[n[0]][n[1]-1] > point + 1:
      nextlist.append([n[0], n[1]-1])
      counter[n[0]][n[1]-1] = point + 1
  if len(nextlist) == 0:
    anskouho.append(point)
    return 0
  else:
    solve(nextlist, point+1)

anskouho = []
for item in start:
  original_counter = [[b for _ in range(W+2)] for _ in range(H+2)]
  for k in range(H+2):
    for j in range(W+2):
      if S[k][j] == '#':
        original_counter[k][j] = -1
  counter = original_counter
  counter[item[0]][item[1]] = 0
  solve([item], 0)
print(max(anskouho))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = []
S.append(['#' for _ in range(W+2)])
for _ in range(H):
  s = input()
  s = '#' + s + '#'
  S.append([])
  for k in range(W+2):
    S[-1].append(s[k])
S.append(['#' for _ in range(W+2)])
b = 0
start = []
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h][w] == '.':
      c = 0
      b += 1
      if S[h+1][w] == '.':
        c += 1
      if S[h-1][w] == '.':
        c += 1
      if S[h][w+1] == '.':
        c += 1
      if S[h][w-1] == '.':
        c += 1
      if c == 1:
        start.append([h, w])
if len(start) == 0:
  for h in range(1, H+1):
    for w in range(1, W+1):
      if S[h][w] == '.':
        c = 0
        if S[h+1][w] == '.':
          c += 1
        if S[h-1][w] == '.':
          c += 1
        if S[h][w+1] == '.':
          c += 1
        if S[h][w-1] == '.':
          c += 1
        if c == 2:
          start.append([h, w])

def solve(nowh, noww, point):
  counter[nowh][noww] = point
  flag = True
  if counter[nowh+1][noww] > point + 1:
    solve(nowh+1, noww, point+1)
    flag = False
  if counter[nowh-1][noww] > point + 1:
    solve(nowh-1, noww, point+1)
    flag = False
  if counter[nowh][noww+1] > point + 1:
    solve(nowh, noww+1, point+1)
    flag = False
  if counter[nowh][noww-1] > point + 1:
    solve(nowh, noww-1, point+1)
    flag = False
  if flag:
    return 0

ans = 0
for item in start:
  original_counter = [[b for _ in range(W+2)] for _ in range(H+2)]
  for k in range(H+2):
    for j in range(W+2):
      if S[k][j] == '#':
        original_counter[k][j] = -1
  counter = original_counter
  solve(item[0], item[1], 0)
  anskouho = 0
  for h in range(1, H+1):
    for w in range(1, W+1):
      anskouho = max(anskouho, counter[h][w])
  ans = max(ans, anskouho)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

h, w = list(map(int, input().split()))
t = h * w

s = ""
for i in range(h):
    s += input().replace( '\n' , '' )

#print(s)

adj = [[] for _ in range(t)]

for i in range(t):
    #よこ
    if i % w != 0 and s[i-1] == ".":
        adj[i].append(i-1)
    if i % w != w-1 and s[i+1] == ".":
        adj[i].append(i+1)
    #たて
    if i - w >= 0 and s[i-w] == ".":
        adj[i].append(i-w)
    if i + w < t and s[i+w] == ".":
        adj[i].append(i+w)

#print(adj)

m = 0
for i in range(t):
    if s[i] == "#":
        pass
    else:
        #BFS
        depth = [0] * t
        visited = [False] * t
        q = deque([i])
        visited[i] = True
        while len(q) > 0:
            v = q.popleft()
            for w in adj[v]:
                if not visited[w]:
                    q.append(w)
                    visited[w] = True
                    depth[w] = depth[v] + 1
        
        #print(depth)
        
        m = max(m, max(depth))

print(m)

Submission status: Accepted

Solution code:
import collections

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

def bfs(x0, y0):
    visited = [[0 for _ in range(w)] for _ in range(h)]
    deq = collections.deque()
    deq.append((x0, y0, -1))

    mx = 0
    while len(deq) > 0:
        x, y, d = deq.popleft()
        nd = d + 1
        visited[x][y] = 1
        mx = max(mx, nd)

        for dx, dy in [(-1, 0), (0, -1), (+1, 0), (0, +1)]:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < h) or not (0 <= ny < w):
                # bound check
                continue
            if smat[nx][ny] == '#':
                # cell attr check
                continue
            if visited[nx][ny] == 1:
                # already visited
                continue
            v = (nx, ny, nd)
            deq.append(v)
    
    return mx

if all(all(col == '.' for col in row) for row in smat):
    print((w - 1) + (h - 1))
else:
    mxall = 0
    for x0 in range(h):
        for y0 in range(w):
            if smat[x0][y0] == '.':
                mx = bfs(x0, y0)
                mxall = max(mxall, mx)
    print(mxall)