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:
H, W = map(int, input().split())
#外壁として障害物置く
H += 2
W += 2
P = [[] for _ in range(H*W)]

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

for y in range(1, H-1):
  for x in range(1, W-1):
    for z in move:
      P[x+W*y].append(x+z[0]+W*(y+z[1]))

for y in range(H-2):
  L = input()
  for x, s in enumerate(L):
    if s == "#":
      P[x+1 + W*(y+1)] = []

def bfs(x, y):
    s = x + W*y
    d = [-1] * (H*W)
    d[s] = 0
    p_old = [s]
    cnt = 1
    m_cnt = 0
    last = 1
    #print(d, p_old)
    while p_old:
      p_new = []
      for i in p_old:
        for j in P[i]:
          if d[j] == -1 and P[j] != []:
            d[j] = cnt
            m_cnt = max(m_cnt, cnt)
            p_new.append(j)
      p_old = p_new
      cnt += 1
      #print(d, p_old)
    return m_cnt

ans = 0

for y in range(1, H-1):
  for x in range(1, W-1):
    ans = max(ans, bfs(x, y))

print(ans)

Submission status: Accepted

Solution code:
from networkx import*
e=enumerate
_,*s=open(0)
g=[]
for i,t in e(s,1):
 for j,u in e(t):g+=[(k:=i*20+j,k+20)]*(u>'#'<(s+['#'*k])[i][j])+[(k,k+1)]*(u>'#'<t[j+1])
print(max(t[i]for _,t in shortest_path_length(Graph(g))for i in t))

Submission status: Accepted

Solution code:
from networkx import*
_,*s=open(i:=0)
g=[]
for t in s:
 i+=1;j=0
 for u in t:g+=[(k:=i*20+j,k+20)]*(u>'#'<(s+['#'*k])[i][j])+[(k,k+1)]*(u>'#'<t[j+1]);j+=1
print(max(t[i]for _,t in shortest_path_length(Graph(g))for i in t))

Submission status: Accepted

Solution code:
from networkx import*
_,*s=open(i:=0)
g=[]
for t in s:
 i+=1;j=0
 for u in t:g+=[(k:=i*20+j,k+20)]*(u>'#'<(s+['#'*k])[i][j]);j+=1;g+=[(k,k+1)]*(u>'#'<t[j])
print(max(t[i]for _,t in shortest_path_length(Graph(g))for i in t))

Submission status: Accepted

Solution code:
import queue
h, w = map(int, input().split())
m = []
for i in range(h):
  m.append(input())
#print(h, w)
#print(m)
q = queue.Queue()
a = []
def init():
  global a
  a = []
  for i in range(h):
    a.append([-1] * w)

def bfs(cx, cy):
  nxs = [1, 0, -1, 0]
  nys = [0, -1, 0, 1]
  for i in range(4):
    nx = cx + nxs[i]
    ny = cy + nys[i]
    if 0 <= nx and nx < w and 0 <= ny and ny < h and m[ny][nx] == '.' and a[ny][nx] == -1:
      a[ny][nx] = a[cy][cx] + 1
      q.put([nx, ny])
  
def check(start_x, start_y):
  if m[start_y][start_x] == '#':
    return 0
  
  global a, q
  init()
  q.put([start_x, start_y])
  a[start_y][start_x] = 0
  end_x = -1
  end_y = -1
  while not q.empty():
    cx, cy = q.get()
    bfs(cx, cy)
    end_x = cx
    end_y = cy
  return a[end_y][end_x]

ans = 0
for i in range(h * w - 1):
    start_x = i % w
    start_y = i // w
    ans = max(ans, check(start_x, start_y))
    
print(ans)

Submission status: Accepted

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

def func(si, sj):
    queue = deque([si, sj])  
    seen = [[-1]*W for _ in range(H)]
    seen[si][sj] = 0
    while queue:
        x = queue.popleft()
        y = queue.popleft()
        
        for i in range(4):
            nx = x + vx[i]
            ny = y + vy[i]
            if nx<0 or nx>=H or ny<0 or ny>=W:
                continue
            if S[nx][ny]=="#" or seen[nx][ny]>=0:
                continue
            seen[nx][ny]=seen[x][y]+1
            queue.append(nx)
            queue.append(ny)
    return seen[x][y]
    
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            ans = max(ans, func(i, j))
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
maze = [["#"]*(W+2)] + [["#"] + list(input()) + ["#"] for i in range(H)] + [["#"]*(W+2)]
from copy import deepcopy
grid = deepcopy(maze)
ans = 0

from collections import deque
for sh in range(H+2):
    for sw in range(W+2):
        
        if grid[sh][sw] == '.':
            
            grid[sh][sw] = 0
            depth = 0
            que = deque()
            que.append([sh,sw])
            dxs = [-1,1,0,0]
            dys = [0,0,-1,1]
            while que:
                h,w = que.popleft()
                for i in range(4):
                    dx = dxs[i]
                    dy = dys[i]

                    if grid[h+dx][w+dy] == '.':
                        grid[h+dx][w+dy] = grid[h][w] + 1
                        que.append([h+dx,w+dy])
                        depth = max(depth,grid[h+dx][w+dy])
            ans = max(ans,depth)
        grid = deepcopy(maze)
        #print(grid)
print(ans)
#print(grid)
#print(maze)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

H,W = map(int,readline().split())
S = [None] * H
for i in range(H):
  S[i] = readline().rstrip()

ans = 0
from collections import deque
cases = ((1,0),(-1,0),(0,1),(0,-1))
for i in range(H):
  for j in range(W):
    q = deque([[i,j,0]])
    seen = set()
    while q:
      y,x,d = q.popleft()
      if S[y][x] == "#":
        continue
      if (y,x) in seen:
        continue
      seen.add((y,x))
      if d > ans:
        ans = d
      for c in cases:
        if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
          q.append([y + c[0], x + c[1], d + 1])

print(ans)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
from collections import deque


# from decorator import stop_watch
#
#
# @stop_watch
def solve(H, W, Ss):
    Ss = ['#' + S + '#' for S in Ss]
    Ss = ['#' * (W + 2)] + Ss + ['#' * (W + 2)]
    # for S in Ss:
    #     print(S)
    ans = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if Ss[i][j] == '#':
                continue
            visited = [[-1] * (W + 2) for _ in range(H + 2)]
            now = 0
            visited[i][j] = now
            q = deque([(i, j, now)])
            while q:
                x, y, n = q.popleft()
                # for v in visited:
                #     print(v)
                # input()
                for x1, y1 in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if Ss[x1][y1] == '.' \
                            and visited[x1][y1] < 0:
                        q.append((x1, y1, n + 1))
                        visited[x1][y1] = n + 1
            ans = max(ans, max([max(v) for v in visited]))

    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Ss = [input() for _ in range(H)]
    solve(H, W, Ss)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(H, W, Ss):
    Ss = ['#' + S + '#' for S in Ss]
    Ss = ['#' * (W + 2)] + Ss + ['#' * (W + 2)]
    # for S in Ss:
    #     print(S)
    ans = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if Ss[i][j] == '#':
                continue
            visited = [[-1] * (W + 2) for _ in range(H + 2)]
            now = 0
            visited[i][j] = now
            q = deque([(i, j, now)])
            while q:
                x, y, n = q.popleft()
                # for v in visited:
                #     print(v)
                # input()
                if Ss[x + 1][y] == '.' \
                        and visited[x + 1][y] < 0:
                    q.append((x + 1, y, n + 1))
                    visited[x + 1][y] = n + 1
                if Ss[x - 1][y] == '.' \
                        and visited[x - 1][y] < 0:
                    q.append((x - 1, y, n + 1))
                    visited[x - 1][y] = n + 1
                if Ss[x][y + 1] == '.' \
                        and visited[x][y + 1] < 0:
                    q.append((x, y + 1, n + 1))
                    visited[x][y + 1] = n + 1
                if Ss[x][y - 1] == '.' \
                        and visited[x][y - 1] < 0:
                    q.append((x, y - 1, n + 1))
                    visited[x][y - 1] = n + 1
            ans = max(ans, max([max(v) for v in visited]))
    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Ss = [input() for _ in range(H)]
    solve(H, W, Ss)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        queue = deque([[i, j, 0]])
        visited = [[0 for _ in range(w)] for _ in range(h)]
        while queue:
            y, x, cnt = queue.popleft()
            if not (0 <= y < h and 0 <= x < w) or visited[y][x] == 1 or s[y][x] == "#":
                continue
            ans = max(ans, cnt)
            visited[y][x] = 1
            for p in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                y2 = y + p[0]
                x2 = x + p[1]
                queue.append([y2, x2, cnt + 1])
# print(s)
print(ans)

Submission status: Accepted

Solution code:
import collections, copy

h, w = map(int, input().split())
maze = []
maze.append("#" * (w + 2))
for i in range(h):
    maze.append("#" + input() + "#")
maze.append("#" * (w + 2))
dis = []
for i in range(h + 2):
    temp = [-1] * (w + 2)
    dis.append(temp)

def search(x, y):
    dis2 = copy.deepcopy(dis)
    move = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    queue = collections.deque([[x, y]])
    dis2[x][y] = 0
    while queue:
        test = queue.popleft()
        for i in move:
            place = [test[0] + i[0], test[1] + i[1]]
            if maze[place[0]][place[1]] == ".":
                if dis2[place[0]][place[1]] == -1:
                    dis2[place[0]][place[1]] = dis2[test[0]][test[1]] + 1
                    queue.append(place)
    return max([max([dis2[i][j] for j in range(w + 2)]) for i in range(h + 2)])

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i + 1][j + 1] == ".":
            dist = search(i + 1, j + 1)
            ans = max(ans, dist)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(sy,sx):
  q=deque([[sy,sx]])
  visited[sy][sx]=0
  while q:
    y,x=q.popleft()
    for dy,dx in ([1,0],[-1,0],[0,1],[0,-1]):
      ny,nx=y+dy,x+dx
      if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="#":continue
      if path[ny][nx]=="." and visited[ny][nx]==-1:
        visited[ny][nx]=visited[y][x]+1
        q.append([ny,nx])
  res=-1
  for i in range(h):
    for j in range(w):
      res=max(visited[i][j],res)
  return res

h,w=map(int,input().split())
path=[input() for i in range(h)]
visited=[[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=0,0
ans=0
for i in range(h):
  for j in range(w):
    if path[i][j]=="#":continue
    sy=i
    sx=j
    visited=[[-1]*w for _ in range(h)]
    t=bfs(sy,sx)
    ans=max(t,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Sss = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

def bfsGridGraph(Sss, xS, yS, INF):
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]
    distss = [[(INF if S != '#' else -1) for S in Ss] for Ss in Sss]
    distss[xS][yS] = 0
    Q = deque([(xS, yS)])
    while Q:
        x, y = Q.popleft()
        dist = distss[x][y]
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if distss[x2][y2] == INF:
                distss[x2][y2] = dist + 1
                Q.append((x2, y2))
    return distss

ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if Sss[i][j] == '#': continue
        distss = bfsGridGraph(Sss, i, j, INF)
        maxDist = max(map(max, distss))
        ans = max(ans, maxDist)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        dist = [[-1]*W for _ in range(H)]
        dist[i][j] = 0
        que = deque([[i,j]])
        while que:
            h,w = que.pop()
            for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
                nh = h+dh
                nw = w+dw
                if nh < 0 or nw < 0 or nh >= H or nw >= W:
                    continue
                if maze[nh][nw] == '#':
                    continue
                if dist[nh][nw] == -1:
                    dist[nh][nw] = dist[h][w]+1
                    que.appendleft([nh,nw])
        ans = max(ans,max([max(d) for d in dist]))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        dist = [[-1]*W for _ in range(H)]
        dist[i][j] = 0
        que = deque([[i,j]])
        while que:
            h,w = que.pop()
            for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
                nh = h+dh
                nw = w+dw
                if nh < 0 or nw < 0 or nh >= H or nw >= W:
                    continue
                if maze[nh][nw] == '#':
                    continue
                if dist[nh][nw] == -1:
                    dist[nh][nw] = dist[h][w]+1
                    que.appendleft([nh,nw])
        ans = max(ans,max([max(d) for d in dist]))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)

H, W = (None, None)
S = None


def bfs(h, w):
    if S[h][w] == '#':
        return 0
    q = queue.Queue()
    q.put((w, h))
    steps = [[-1 for _ in range(W)]for _ in range(H)]
    steps[h][w] = 0
    while not q.empty():
        p = q.get()
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for d in DIR:
            n = (p[0] + d[0], p[1] + d[1])
            if not (0 <= n[0] < W and 0 <= n[1] < H):
                continue
            if steps[n[1]][n[0]] != -1:
                continue
            if S[n[1]][n[0]] == '#':
                continue
            steps[n[1]][n[0]] = steps[p[1]][p[0]] + 1
            q.put(n)
    res = 0
    for s in steps:
        res = max(res, max(s))
    return res


def solve():
    global H, W, S
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, bfs(h, w))
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def dfs(h, w):
    Step = [[0]*W for _ in range(H)]
    Step[h][w] = 0
    stack = deque([(h, w)])
    visited =[[False]*W for _ in range(H)]
    while stack:
        i, j = stack.popleft()
        visited[i][j] = True
        for dx, dy in XY:
            x = i + dx
            y = j + dy
            if 0 <= x <= H-1 and 0 <= y <= W-1:
                if x == h and y == w:
                    continue
                if Step[x][y]:
                    continue
                if S[x][y] == '#':
                    continue
                stack.append((x, y))
                Step[x][y] = Step[i][j] + 1
    ans = 0
    for step in Step:
        ans = max(ans, max(step))
    return ans

for h in range(H):
    for w in range(W):
        if S[h][w] != '#':
            ans = max(ans, dfs(h, w))

print(ans)

Submission status: Accepted

Solution code:
H ,W = map(int,input().split())

from collections import deque

S = [input() for i in range(H)]
directions = [[0,1],[1,0],[-1,0],[0,-1]]


counter = 0

#インデックス番号　xが行番号　yが列番号
for x in range(H):
    for y in range(W):
        if S[x][y]=="#":
            continue
         
        que =  deque([[x,y]])
        memory = [[-1]*W for _ in range(H)]
        memory[x][y]=0
       
        while True:
            if len(que)==0:
               break
            h,w = que.popleft()

            for i,k in directions:
                x_new,y_new = h+i,w+k

                if not(0<=x_new<=H-1) or not(0<=y_new<=W-1) :
                    continue
                
                elif not memory[x_new][y_new]==-1 or S[x_new][y_new]=="#":
                    continue

                memory[x_new][y_new] = memory[h][w]+1
                que.append([x_new,y_new]) 
        counter = max(counter,max(max(i) for i in memory))

print(counter)

Submission status: Accepted

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

from collections import deque

h,w = nm()

s = []

for y in range(h):
  s.append([_ for _ in input()])



def bfs(sx,sy,visited):
  xx=[1,-1,0,0]
  yy=[0,0,1,-1]
  
  q=deque([(sx,sy)])
  visited[sy][sx] = 0

  while q:
    _ = q.popleft()
    x=_[0]
    y=_[1]

    for i in range(4):
      nx = x + xx[i]
      ny = y + yy[i]
      
      if 0 <= nx < w and 0 <= ny < h:
        if s[ny][nx] == '.' and visited[ny][nx]==-1:
          visited[ny][nx] = visited[y][x]+1
          q.append((nx,ny))
  mx=0
  for y in range(h):
    for x in range(w):
      mx = max(mx,visited[y][x])
  return mx

MX = 0

for sx in range(w):
  for sy in range(h):
    if s[sy][sx] == '.':
      b = bfs(sx,sy,[[-1]*w for _ in range(h)])
      MX = max(MX,b)

print(MX)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
meiro = [list(input()) for i in range(h)]
# meiro[y][x]


def bfs(a, b):  # a縦b横
    mx_dist = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dist = [[-1] * w for i in range(h)]
    dist[a][b] = 0
    que = deque([])
    que.append((a, b))
    while que:
        y, x = que.popleft()
        D = dist[y][x]
        for i in range(4):
            X = x + dx[i]
            Y = y + dy[i]
            if 0 <= Y and Y <= h - 1 and X <= w - 1 and 0 <= X:
                if meiro[Y][X] == ".":
                    if dist[Y][X] == -1:
                        dist[Y][X] = D + 1
                        que.append((Y, X))
                        mx_dist = max(mx_dist, D + 1)

    return mx_dist


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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7

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

dd = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(h):
    for j in range(w):
        if ini_grid[i][j] == '.':
            temp_grid = [row[:] for row in ini_grid]
            dis_grid = [[-1]*w for i in range(h)]
            dis_grid[i][j] = 0
            dq = deque([(i, j, 0)])
            temp_grid[i][j] = '#'
            while dq:
                curr = dq.popleft()
                for di, dj in dd:
                    ni = curr[0] + di
                    nj = curr[1] + dj 
                    if (0 <= ni <= h-1) and (0 <= nj <= w-1) and temp_grid[ni][nj] == '.':
                        temp_grid[ni][nj] = '#'
                        dis_grid[ni][nj] = curr[2] + 1
                        dq.append((ni, nj, curr[2] + 1))
                        if curr[2] + 1 > ans:
                            ans = curr[2] + 1

print(ans)

Submission status: Accepted

Solution code:
import networkx as nx

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

G = nx.Graph()
# 辺を加えていく
for h in range(H):
    for w in range(W - 1):
        if maze[h][w] == maze[h][w + 1] == '.':
            G.add_edge((h, w), (h, w + 1))
for h in range(H - 1):
    for w in range(W):
        if maze[h][w] == maze[h + 1][w] == '.':
            G.add_edge((h, w), (h + 1, w))


def bfs(sy, sx):
    d = dict()
    d[(sy, sx)] = 0
    for coordinate_from, coordinate_to in nx.bfs_edges(G, (sy, sx)):
        d[coordinate_to] = d[coordinate_from] + 1
    return max(d.values())


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:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]

    res = []
    for sh in range(H):
        for sw in range(W):
            if grid[sh][sw] == "#":
                continue
            maze = [[f_inf] * W for _ in range(H)]
            maze[sh][sw] = 0
            que = deque([[sh, sw]])
            while que:
                h, w = que.popleft()
                for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    next_h, next_w = h + dh, w + dw
                    if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W or grid[next_h][
                        next_w] == "#":
                        continue
                    if maze[next_h][next_w] > maze[h][w] + 1:
                        maze[next_h][next_w] = maze[h][w] + 1
                        que.append([next_h, next_w])
                        res.append(maze[next_h][next_w])
    print(max(res))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import networkx as nx

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

G = nx.grid_2d_graph(H, W)
for h in range(H):
    for w in range(W):
        # 壁に入る辺を削除
        if maze[h][w] == '#':
            for dh, dw in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                if ((h - dh, w - dw), (h, w)) in G.edges():
                    G.remove_edge((h - dh, w - dw), (h, w))


def bfs(sy, sx):
    d = dict()
    d[(sy, sx)] = 0
    for coordinate_from, coordinate_to in nx.bfs_edges(G, (sy, sx)):
        d[coordinate_to] = d[coordinate_from] + 1
    return max(d.values())


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