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

ans = 0

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

for i in range(h):
    for j in range(w):
        if(maze[i][j]=="."):
            dist = [ [99999999]*w for _ in range(h) ]
            
            dq = deque()
            y=i
            x=j
            d=0
            dist[y][x]=0
            dq.append((y,x,d))
            
            while(len(dq)):
                
                y,x,d = dq.popleft()
                
                for m in move:
                    if((0<=x+m[0]<w) and (0<=y+m[1]<h) and
                        (dist[y+m[1]][x+m[0]] > d+1) and
                            (maze[y+m[1]][x+m[0]] == ".")):
                                dist[y+m[1]][x+m[0]]=d+1
                                dq.append((y+m[1],x+m[0],d+1))
                                
            ans = max(ans,d)
            # print(d,i,j)
print(ans)

Submission status: Accepted

Solution code:
# Https://atcoder.jp/contests/abc151/tasks/abc151_d

from collections import deque

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


def bfs(sx, sy):
    result = 0
    count = [[-1] * W for i in range(H)]
    count[sx][sy] = 0
    d = deque()
    d.append((sx, sy))
    while d:
        x, y = d.popleft()
        result = count[x][y]
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            tx, ty = x + i, y + j
            if (
                not (0 <= tx < H)
                or not (0 <= ty < W)
                or maze[tx][ty] == "#"
                or count[tx][ty] != -1
            ):
                continue
            else:
                count[tx][ty] = count[x][y] + 1
                d.append((tx, ty))
    return result


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

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


h, w = LI()
s = SRL(h)
ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        v = [[-1] * w for _ in range(h)]
        q = deque()
        q.append((i, j))
        v[i][j] = 1
        goal = tuple()
        while q:
            r, c = q.popleft()
            for x, y in ((1, 0), (-1, 0), (0, -1), (0, 1)):
                if r + x < 0 or r + x > h - 1 or c + y < 0 or c + y > w - 1 or s[r + x][c + y] == "#" or v[r + x][c + y] > 0:
                    continue
                v[r + x][c + y] = v[r][c] + 1
                q.append((r + x, c + y))
        ans.append(max(chain.from_iterable(v)) - 1)
print(max(ans))

Submission status: Accepted

Solution code:
import math
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    H, W = read_ints()
    last_S = ''
    INF = 10**9+1
    dist = [
        [INF for _ in range(H*W)] for _ in range(H*W)
    ]
    for i in range(H*W):
        dist[i][i] = 0
    for i in range(H):
        S = input().strip()
        for j in range(W):
            if S[j] == '#':
                continue
            top = (i-1)*W+j
            left = i*W+j-1
            current = i*W+j
            if j > 0 and S[j-1] == '.':
                dist[left][current] = dist[current][left] = 1
            if i > 0 and last_S[j] == '.':
                dist[top][current] = dist[current][top] = 1
        last_S = S
    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    return max(cell for row in dist for cell in row if cell != INF)


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            cnt=[[-1]*w for _ in range(h)]
            cnt[i][j]=0
            queue=deque()
            queue.append([i,j])
            for k in range(100*h*w):
                if len(queue)==0:
                    break
                num=queue.popleft()
                num1=num[0]
                num2=num[1]
                if num1!=0:
                    if s[num1-1][num2]=="." and cnt[num1-1][num2]==-1:
                        cnt[num1-1][num2]=cnt[num1][num2]+1
                        queue.append([num1-1,num2])
                if num2!=0:
                    if s[num1][num2-1]=="." and cnt[num1][num2-1]==-1:
                        cnt[num1][num2-1]=cnt[num1][num2]+1
                        queue.append([num1,num2-1])
                if num1!=h-1:
                    if s[num1+1][num2]=="." and cnt[num1+1][num2]==-1:
                        cnt[num1+1][num2]=cnt[num1][num2]+1
                        queue.append([num1+1,num2])
                if num2!=w-1:
                    if s[num1][num2+1]=="." and cnt[num1][num2+1]==-1:
                        cnt[num1][num2+1]=cnt[num1][num2]+1
                        queue.append([num1,num2+1])
            cnt2=0
            for k in range(h):
                cnt2=max(cnt2,max(cnt[k]))
            ans=max(ans,cnt2)
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
C = [list(input()) for i in range(h)]

queue = []
visited = [] 
visited = [[0 for i in range(w)] for i in range(h)]
ans = 0

for i in range(h):
    for j in range(w):
        if C[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

            while len(queue) > 0:
                now = queue.pop(0)
                for k in range(4):
                    y = now[0]+dy_dx[k][0]
                    x = now[1]+dy_dx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if C[y][x] != '#' and visited[y][x] == 0:
                            visited[y][x] = visited[now[0]][now[1]]+1 #移動回数のカウント
                            queue.append([y,x])
                    
        for l in range(h):
            for m in range(w):
                ans = max(ans,visited[l][m])
            
        queue = []
        visited = [[0 for i in range(w)] for i in range(h)]              
        
print(ans-1)

Submission status: Accepted

Solution code:
from collections import *
from copy import *
H,W = map(int,input().split())
S = [(W+2)*["#"]]+[["#"]+list(input())+["#"] for h in range(H)]+[(W+2)*["#"]]
D = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
P = deque([])
Q = deque([])

for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]==".":
      P+=[[h,w]]

while P:
  T = deepcopy(S)
  sx,sy = P.popleft()
  T[sx][sy] = 0
  Q = deque([[sx,sy]])
  while Q:
    x,y = Q.popleft()
    for dx,dy in D:
      if T[x+dx][y+dy]==".":
        T[x+dx][y+dy] = T[x][y]+1
        Q+=[[x+dx,y+dy]]
        ans = max(ans,T[x+dx][y+dy])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    row, col = map(int, input().split())
    S = [list(input()) for _ in range(row)]
    ans = 0

    for r in range(row):
        for c in range(col):
            if S[r][c] == "#":
                continue
            q = deque()
            q.append((r, c))
            dist = [[-1 for _ in range(col)] for _ in range(row)]
            dist[r][c] = 0

            while q:
                r, c = q.popleft()
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if not(0 <= nr < row and 0 <= nc < col):
                        continue
                    if S[nr][nc] == "#":
                        continue
                    if dist[nr][nc] != -1:
                        continue
                    q.append((nr, nc))
                    dist[nr][nc] = dist[r][c] + 1
                    ans = max(ans, dist[nr][nc])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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


def bfs(sy, sx):
    reached = [[-1] * W for _ in range(H)]
    reached[sy][sx] = 0
    from collections import deque
    que = deque([[sy, sx]])
    #d_max = 0
    while que:
        iy, ix = que.popleft()
        for d in direction:
            tx, ty = ix + d[0], iy + d[1]
            if tx >= W or ty >= H or tx < 0 or ty < 0:
                continue
            if reached[ty][tx] != -1 or maze[ty][tx] == '#':
                continue
            reached[ty][tx] = reached[iy][ix] + 1
            #d_max = max(reached[ty][tx], d_max)
            que.append([ty, tx])
    d_max = 0
    for i in range(H):
        for j in range(W):
            d_max = max(d_max,reached[i][j])

    return d_max


ans = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            ans = max(ans, bfs(i, j))

# for i in range(H):
#     for j in range(i, W):
#         for k in range(H):
#             for l in range(k, W):
#                 if maze[i][j] == '#' or maze[k][l] == '#':
#                     continue
#                 else:
#                     ans = max(ans, bfs(i, j, k, l))
print(ans)

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**20
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    mod=10**9+7
    H,W=MI()
    S=[]
    S.append("#"*(W+2))
    for i in range(H):
        s="#"+input()+"#"
        S.append(s)
    S.append("#"*(W+2))
    
    djk=Dijkstra((H+2)*(W+2))
    
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    for i in range(1,H+1):
        for j in range(1,W+1):
            if S[i][j]==".":
                for k in range(4):
                    ii=i+dx[k]
                    jj=j+dy[k]
                    if S[ii][jj]==".":
                        v= (W+2)*i + j
                        nv=(W+2)*ii+jj
                        djk.add2(v,nv,1)
                        
    ans=0
    for i in range((H+2)*(W+2)):
        d=djk.shortest_path(i)
        for di in d:
            if di<=10**10:
                ans=max(ans,di)
                
    print(ans)
            
            
    


main()

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

H,W=mint()
S=[input() for _ in range(H)]

ans=0
for s in product(range(H),range(W)):
    if S[s[0]][s[1]]=='#':
        continue
    q=deque([s])
    d=[[-1]*W for _ in range(H)]
    d[s[0]][s[1]]=0
    while len(q)>0:
        i,j = q.popleft()
        for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
            if 0<=x<H and 0<=y<W and S[x][y]=='.' and d[x][y]<0:
                d[x][y]=d[i][j]+1
                q.append((x,y))
    for i in range(H):
        for j in range(W):
            ans=max(ans,d[i][j])
print(ans)

Submission status: Accepted

Solution code:
def solve(maze,H, W, S):
    next_set = set()
    next_set.add(S)
    seen = [[False]*W for _ in range(H)]
    n = 0
    while next_set:
        n += 1
        curr_ = list(next_set)
        next_set = set()
        for h, w in curr_:
            if seen[h][w]:
                continue
            seen[h][w] = True
            for nh, nw in maze[h][w]:
                if seen[nh][nw] == False:
                    next_set.add((nh, nw))
    return n-1

# 入力
H, W = list(map(int, input().split()))
maze = [[[] for _ in range(W)] for _ in range(H)]
for h in range(H):
    row = input()
    for w in range(W):
        if row[w] == '#':
            maze[h][w] = False


# mazeに移動可能移動可能なマスを記録
for h in range(H):
    for w in range(W):
        if maze[h][w] == False:
            continue
        for nh, nw in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if 0 <= nh < H and 0<= nw < W:
                if maze[nh][nw] != False:
                    maze[h][w].append((nh, nw))
        # print(maze)
# print(maze)
ans = 0
for i in range(H*W-1):
        h = i//W
        w = i%W
        if maze[h][w]:
            ans = max(ans, solve(maze, H, W, (h, w)))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def getdistance(row,col,sw,h,w):
    maze = deque([[row,col,0]])
    marker = [[0]*w for _ in range(h)]
    marker[row][col] = 1
    while len(maze)!=0:
        r, c, d = maze.popleft()
        if r!=0:
            if sw[r-1][c]!="#" and marker[r-1][c] != 1:
                marker[r-1][c] = 1
                maze.append([r-1,c,d+1])
        if r!=h-1:
            if sw[r+1][c]!="#" and marker[r+1][c] != 1:
                marker[r+1][c] = 1
                maze.append([r+1,c,d+1])
        if c!=w-1:
            if sw[r][c+1]!="#" and marker[r][c+1] != 1:
                marker[r][c+1] = 1
                maze.append([r,c+1,d+1])
        if c!=0:
            if sw[r][c-1]!="#" and marker[r][c-1] != 1:
                marker[r][c-1] = 1
                maze.append([r,c-1,d+1])
    return d
h, w = map(int, input().split())
sw = [input() for _ in range(h)]
ans = 0
for row in range(h):
    for col in range(w):
        if sw[row][col]=="#":
            continue
        ans = max(ans,getdistance(row,col,sw,h,w))
print(ans)

Submission status: Accepted

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

def bfs(maze, sy, sx):
    visited = [[-1]*W for j in range(H)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        ans=0
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1 :
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
                    
    for l in range(H):
        for m in range(W):
            ans = max(ans,visited[l][m])
            
    return ans
        
ma=0
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == ".":
            if bfs(maze,sy,sx) is not None:
                ma = max(bfs(maze, sy, sx),ma)
print(ma)

Submission status: Accepted

Solution code:
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            v = set()
            q = deque([(i, j, 0)])
            v.add((i, j))
            while q:
                ii, jj, cnt = q.popleft()
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                    v.add((ii + 1, jj))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                    v.add((ii, jj + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                    v.add((ii - 1, jj))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
                    v.add((ii, jj - 1))
    return ret


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            q = deque([(i, j, 0)])
            v = [[0] * w for _ in range(h)]
            v[i][j] = 1
            while q:
                ii, jj, cnt = q.popleft()
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and v[ii + 1][jj] == 0:
                    v[ii + 1][jj] = 1
                    q.append((ii + 1, jj, cnt + 1))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and v[ii][jj + 1] == 0:
                    v[ii][jj + 1] = 1
                    q.append((ii, jj + 1, cnt + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and v[ii - 1][jj] == 0:
                    v[ii - 1][jj] = 1
                    q.append((ii - 1, jj, cnt + 1))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and v[ii][jj - 1] == 0:
                    v[ii][jj - 1] = 1
                    q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def bfs(y, x):
    dist = [[-1] * w for _ in range(h)]
    dist[y][x] = 0
    que, frag = deque([(x, y)]), set([(x, y)])

    while que:
        qx, qy = que.popleft()
        near = [(-1, 0), (0, -1), (1, 0), (0, 1)]
        for i, j in near:
            i, j = qx + i, qy + j
            if (i, j) in frag:
                continue
            if 0 <= i < w and 0 <= j < h and s[j][i] == '.':
                dist[j][i] = dist[qy][qx] + 1
                que.append((i, j)), frag.add((i, j))
    return dist[qy][qx]


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

ans = 0
for i, si in enumerate(s):
    for j, sij in enumerate(si):
        if sij == '.':
            ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(y, x):
    dist = [[-1] * w for _ in range(h)]
    dist[y][x] = 0
    que, frag = deque([(x, y)]), set([(x, y)])

    while que:
        qx, qy = que.popleft()
        near = [(qx - 1, qy), (qx, qy - 1), (qx + 1, qy), (qx, qy + 1)]
        for i, j in near:
            if (i, j) in frag:
                continue
            if 0 <= i < w and 0 <= j < h and s[j][i] == '.':
                dist[j][i] = dist[qy][qx] + 1
                que.append((i, j)), frag.add((i, j))
    return dist[qy][qx]


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

ans = 0
for i, si in enumerate(s):
    for j, sij in enumerate(si):
        if sij == '.':
            ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

ans = 0
for x in range(H):
    for y in range(W):
        #壁からはスタートできない
        if maze[x][y] == "#":
            continue

        distance = [[-1]*W for _ in range(H)]
        distance[x][y] = 0
        #start位置
        stack = deque([[x,y]])

        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == -1:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])

        ans = max(ans, np.max(distance))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1e9)+7
INF = float('inf')


def solve():
    n, m = [int(x) for x in input().split()]
    a = []
    starts = []
    for i in range(n):
        a.append(input())
        for j in range(m):
            if a[i][j] == '.':
                starts.append((i, j))

    def bfs(v):
        q = deque([(v, 0)])
        mx = 0
        mv = v
        w = defaultdict(int)
        w[v] = 1
        while q:
            v, d = q.popleft()
            if d > mx:
                mv = v
                mx = d
            i, j = v
            for x, y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                if 0 <= i + x < n and 0 <= j + y < m and not w[(i+x,j+y)] and a[i+x][j+y] == '.':
                    w[(i+x,j+y)] = 1
                    q.append(((i+x, j+y), d + 1))
            

        return mx, mv

    ans = 0
    for start in starts:
        _, start = bfs(start)
        cur, start = bfs(start)

        ans = max(ans, cur)
    print(ans)


    

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""
1
4
-1 1 1 -1

"""

Submission status: Accepted

Solution code:
from collections import deque

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

dis = [[0, 1], [0, -1], [1, 0], [-1, 0]]
answer = 0
for h in range(H):
  for w in range(W):
    if mazes[h][w] == '#':
      continue
    else:
      last = 0
      arrived = [[0 for _ in range(W)] for __ in range(H)]
      routes = deque([[h, w]])
      arrived[h][w] = 1
      while(len(routes) > 0):
        hy, wx = routes.pop()
        move = arrived[hy][wx]
        last = move
        for y, x in dis:
          if 0 <= hy+y < H and 0 <= wx+x < W and mazes[hy+y][wx+x] == '.' and arrived[hy+y][wx+x] == 0:
            routes.appendleft([hy+y, wx+x])
            arrived[hy+y][wx+x] = move + 1
      answer = max(answer, last-1)
print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Sep  8 18:25:14 2020

@author: liang
"""

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

field = [input() for i in range(H)]

def Init():
    return [[-1]*W for _ in range(H)]

ans = -1

from collections import deque
q = deque()
adj = ((1,0), (-1,0), (0,1), (0,-1))
def BFS(y,x):
    def isValid(t):
        if t[0] < 0 or t[0] >= H or t[1] < 0 or t[1] >= W or field[t[0]][t[1]] == "#":
            return False
        return True
    d = Init()
    if field[y][x] == '#':
        return -1
    d[y][x] = 0
    q.append((y,x))
    res = 0
    while q:
        cur = q.popleft()
        for a in adj:
            nex = (cur[0]+a[0], cur[1]+a[1])
            if isValid(nex) and (d[nex[0]][nex[1]]== -1 or d[nex[0]][nex[1]] > d[cur[0]][cur[1]]+1):
                d[nex[0]][nex[1]] = d[cur[0]][cur[1]]+1
                #if res < d[nex[0]][nex[1]]:
                #    res = d[nex[0]][nex[1]]
                res = max(res, d[nex[0]][nex[1]])
                q.append(nex)
    return res

for i in range(H):
    for j in range(W):
        tmp = BFS(i,j)
        if tmp > ans:
            ans = tmp
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Sep  8 18:25:14 2020

@author: liang
"""

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

field = [input() for i in range(H)]

def Init():
    return [[-1]*W for _ in range(H)]

ans = -1

from collections import deque
q = deque()
adj = ((1,0), (-1,0), (0,1), (0,-1))
def BFS(y,x):
    def isValid(t):
        if t[0] < 0 or t[0] >= H or t[1] < 0 or t[1] >= W or field[t[0]][t[1]] == "#":
            return False
        return True
    d = Init()
    if field[y][x] == '#':
        return -1
    d[y][x] = 0
    q.append((y,x))
    res = 0
    while q:
        cur = q.popleft()
        for a in adj:
            nex = (cur[0]+a[0], cur[1]+a[1])
            if isValid(nex) and (d[nex[0]][nex[1]]== -1 or d[nex[0]][nex[1]] > d[cur[0]][cur[1]]+1):
                d[nex[0]][nex[1]] = d[cur[0]][cur[1]]+1
                if res < d[nex[0]][nex[1]]:
                    res = d[nex[0]][nex[1]]
                q.append(nex)
    return res

for i in range(H):
    for j in range(W):
        tmp = BFS(i,j)
        if tmp > ans:
            ans = tmp
print(ans)