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
n,m = map(int,input().split())
l = []
for i in range(n):
    a = list(input())
    l.append(a)

ans = 0
for i in range(n):
    for j in range(m):
        if l[i][j] == ".":
            bfs = [[-1]*m for k in range(n)]
            bfs[i][j] = 0
            q = deque([])
            q.append((i,j))
            dx = [0,0,-1,1]
            dy = [-1,1,0,0]
            while q:
                x,y = q.popleft()

                for t in range(4):
                    nx = x+dx[t]
                    ny = y + dy[t]

                    if 0 <= nx < n and 0 <= ny < m and bfs[nx][ny] == -1 and l[nx][ny] != "#":
                        q.append((nx,ny))
                        bfs[nx][ny] = bfs[x][y] +1

            for bf in bfs:
                ans = max(ans,max(bf))
            
print(ans)

Submission status: Accepted

Solution code:
import sys
h, w = [int(i) for i in sys.stdin.readline().split()]
s_ls = []
target = []
for i in range(h):
    s = sys.stdin.readline().strip()
    for j, _s in enumerate(s):
        if _s == ".":
            target.append(i * h + j)
    s_ls.append(s)

len_target = len(target)
already = set()
def wfs(x, y):
    res = 0
    for plus_x, plus_y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        next_x = max(0, min(w - 1, x + plus_x))
        next_y = max(0, min(h - 1, y + plus_y))
        if (next_y, next_x) not in already and s_ls[next_y][next_x] == ".":
            already.add((next_y, next_x))
            res = max(res, wfs(next_x, next_y) + 1)
    return res

best = 0
for start in range(h * w):
    start_x, start_y = start % w, start // w
    if s_ls[start_y][start_x] == "#":
        continue
    already = {(start_y, start_x)}
    ls = {start_y * w + start_x : 0}
    que = [(start_y, start_x, 0)]
    res = 0
    while len(que) > 0:
        y, x, dis = que.pop(0)
        for plus_x, plus_y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            next_x = max(0, min(w - 1, x + plus_x))
            next_y = max(0, min(h - 1, y + plus_y))
            if (next_y, next_x) not in already and s_ls[next_y][next_x] == ".":
                already.add((next_y, next_x))
                que.append((next_y, next_x, dis+1))
                ls[next_y * w + next_x] = dis + 1
                res = max(res, dis + 1)
        if len(already) == len_target:
            break
    best = max(best, res)
print(best)

Submission status: Accepted

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

N = W * H
E = [[0] * N  for _ in range(N)]
for i, e in enumerate(E):
    e[i] = 1

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

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            for di, dj in dij:
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == ".":
                    E[W * i + j][W * ni + nj] = 1

from scipy.sparse.csgraph import floyd_warshall

INF = float("inf")

A = floyd_warshall(E)
print(int(max(max(a if a != INF else 0 for a in a) for a in A)))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

H,W = II()
S = [list(map(str, input())) for _ in range(H)]

def bfs(c,s):
    X=[[-1]*W for i in range(H)]
    if c[s[0]][s[1]]=='#':
        return X
    X[s[0]][s[1]]=0
    q=[s]
    counter=1
    d = [(0,1),(0,-1),(1,0),(-1,0)]
    #f = float('inf')
    while q:
        q1=[]
        for i in q:
            for d0 in d:
                j = (i[0]+d0[0],i[1]+d0[1])
                if 0<=j[0]<=H-1 and 0<=j[1]<=W-1:
                    if c[j[0]][j[1]]=='.':
                        #if j[0]==g[0] and j[1]==g[1]:
                        #    f = min(f,counter)
                        if X[j[0]][j[1]]==-1:
                            X[j[0]][j[1]]=counter
                            q1.append(j)
        q=q1
        counter+=1
    return X

ans = 0
for si in range(H):
    for sj in range(W):
        d = bfs(S,(si,sj))
        #print(d)
        now = 0
        for i in range(len(d)):
            for j in range(len(d[0])):
                if d[i][j]>now:
                    now = d[i][j]
        if now==-1:
            continue
        if now>ans:
            ans = now
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

H,W=map(int,input().split())
S=[list(input().strip()) for _ in range(H)]
G=[[float("inf")]*H*W for _ in range(H*W)]
for i in range(H*W):
    G[i][i]=0
#print(S)
for h in range(H):
    for w in range(W-1):
        if S[h][w]=="." and S[h][w+1]==".":
            G[W*h+w][W*h+w+1]=1
            G[W*h+w+1][W*h+w]=1

for h in range(H-1):
    for w in range(W):
        if S[h][w]=="." and S[h+1][w]==".":
            G[W*h+w][W*(h+1)+w]=1
            G[W*(h+1)+w][W*h+w]=1

#print(G)
n=H*W
G=warshall_floyd(G)
#print(G)
ans=0
for h in range(H*W):
    for w in range(H*W):
        if G[h][w]!=float("inf"):
            ans=max(ans,G[h][w])
print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(H, W, grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    h, w = src
    directions = ((1,0),(-1,0),(0,1),(0,-1))
    que = deque([(h, w, 0)])
    dist = list2d(H+2, W+2, -1)
    while que:
        h, w, c = que.popleft()
        if dist[h][w] != -1:
            continue
        dist[h][w] = c
        for dh, dw in directions:
            h2 = h + dh
            w2 = w + dw
            if grid[h2][w2] == '#':
                continue
            que.append((h2, w2, c+1))
    return dist

H, W = MAP()
grid = build_grid(H, W, '#', str, space=0, padding=1)

ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j] != '#':
            res = bfs(H, W, grid, (i, j))
            for k in range(1, H+1):
                for l in range(1, W+1):
                    ans = max(ans, res[k][l])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
field=[["#"]+list(input())+["#"] for i in range(h)]
field=[["#" for i in range((w+2))]]+field+[["#" for j in range(w+2)]]
def bfs(a,b):
  Q=deque([(a,b)])
  s=[[0 for i in range(w+2)] for j in range(h+2)]
  visited=[[False for i in range(w+2)] for j in range(h+2)]
  visited[a][b]=True
  while Q:
    v=Q.popleft()
    for i in [(1,0),(0,-1),(-1,0),(0,1)]:
      if visited[v[0]+i[0]][v[1]+i[1]]:continue
      if field[v[0]+i[0]][v[1]+i[1]]=="#":continue
      visited[v[0]+i[0]][v[1]+i[1]]=True
      s[v[0]+i[0]][v[1]+i[1]]=s[v[0]][v[1]]+1
      Q.append([v[0]+i[0],v[1]+i[1]])
  return max([max(s[i]) for i in range(h+2)])
ans=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if field[i][j]=="#":continue
    if bfs(i,j)>ans:ans=bfs(i,j)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys

h, w = [int(_) for _ in input().split()]
s = []
M = -1
for i in range(h):
    s.append(input())
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        dp = [[-1 for _ in range(w)] for i in range(h)]
        dp[i][j] = 0
        que = deque([(i, j)])
        # c = 0
        while len(que) != 0:
            i_f, j_f = que.popleft()
            # print(que)
            d_f = dp[i_f][j_f]
            l = [(i_f, j_f + 1),(i_f, j_f - 1), (i_f - 1, j_f), (i_f + 1, j_f)]
            for p in range(len(l)):
                i_t, j_t = l[p]
                if 0 <= i_t <= h - 1 and 0 <= j_t <= w - 1:
                    # print(i_t, j_t)
                    # print(dp)
                    # print(s)
                    # print(dp[0][1])
                    # print(s[0][1])
                    if dp[i_t][j_t] == -1 and s[i_t][j_t] == '.':
                        que.append((i_t, j_t))
                        dp[i_t][j_t] = d_f + 1
            # c += 1
            # print(que)
            # print(dp)
            # print(l)
            # if c == 2:
            #     sys.exit()
        # print('**********')
        # print(i, j)
        # for i in range(h):
        #     print(dp[i])
        # print('**********')
        for i_q in range(h):
            for j_q in range(w):
                M = max(dp[i_q][j_q], M)
print(M)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w=map(int,input().split())
s=[input() for i in range(h)]
# print(40**3)

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# n,w = map(int,input().split()) #n:頂点数　w:辺の数
n=h*w
d = [[float("inf") for i in range(h*w)] for i in range(h*w)]
# print(d)
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(h):
    for j in range(w):
        if i+1<h:
            if s[i][j]!="#" and s[i+1][j]!="#":
                d[i*w+j][(i+1)*w+j]=1
                d[(i+1)*w+j][i*w+j]=1
        if j+1<w:
            if s[i][j]!="#" and s[i][j+1]!="#":
                d[i*w+j][i*w+j+1]=1
                d[i*w+j+1][i*w+j]=1
# for i in range(w):
#     x,y,z = map(int,input().split())
#     d[x][y] = 1
#     d[y][x] = 1
for i in range(h*w):
    d[i][i] = 0 #自身のところに行くコストは０
# print(d)
li=warshall_floyd(d)
ans=0
for i in range(len(li)):
    for j in range(len(li[i])):
        if li[i][j]!=float("inf"):
            ans=max(ans,li[i][j])

print(ans)

Submission status: Accepted

Solution code:
from queue import Queue
from copy import deepcopy

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

WHITE = 0
GRAY = 1
BLACK = 2

dhw = [[-1, 0], [1, 0], [0, -1], [0, 1]]

color_orginal = [[WHITE] * w for _ in range(h)]
for hi in range(h):
    for wi in range(w):
        if s[hi][wi] == "#":
            color_orginal[hi][wi] = BLACK


def dfs(sh, sw):
    q = Queue()
    q.put([sh, sw])

    color = deepcopy(color_orginal)
    d = [[-1] * w for _ in range(h)]

    d[sh][sw] = 0
    dd = 0

    while not q.empty():
        uh, uw = q.get()
        color[uh][uw] = BLACK
        for dh, dw in dhw:
            nxth = uh + dh
            nxtw = uw + dw
            if 0 <= nxth <= h - 1 and 0 <= nxtw <= w - 1:
                if color[nxth][nxtw] == WHITE:
                    q.put([nxth, nxtw])
                    color[nxth][nxtw] = GRAY
                    d[nxth][nxtw] = d[uh][uw] + 1
                    dd = max(d[nxth][nxtw], dd)

    return dd


ans = 0
for hi in range(h):
    for wi in range(w):
        if s[hi][wi] == ".":
            ans = max(ans, dfs(hi, wi))

print(ans)

Submission status: Accepted

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

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

def nexts(h, w):
    pq = []
    if h != 0: pq.append((h-1, w))
    if w != 0: pq.append((h, w-1))
    if h != H-1: pq.append((h+1, w))
    if w != W-1: pq.append((h, w+1))
    return pq


def bfs(sh, sw):
    Ds = [[-1]*W for _ in range(H)]
    q = [(sh, sw)]
    d = 0
    Ds[sh][sw] = 0
    while q:
        qq = []
        d += 1
        for h, w in q:
            for nh, nw in nexts(h, w):
                if state[nh][nw] == "#":
                    Ds[nh][nw] = -2
                elif Ds[nh][nw] == -1:
                    Ds[nh][nw] = d
                    qq.append((nh, nw))
        q = qq
    
    maxd = 0
    for h in range(H):
        for w in range(W):
            if maxd < Ds[h][w]:
                maxd = Ds[h][w]
                lh, lw = h, w
    return maxd

ans = 0
for h in range(H):
    for w in range(W):
        if state[h][w] == ".":
            d = bfs(h, w)
            ans = max(ans, d)

print(ans)

Submission status: Accepted

Solution code:
# A happy new year, AtCoder !
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

myinf = 10 ** 9 + 7
tab_graph = [[myinf] * (H * W) for _ in range(H * W)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '#': continue
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if i + di < 0: continue
            if i + di >= H: continue
            if j + dj < 0: continue
            if j + dj >= W: continue
            # print("#", i, j, '->', i + di, j + dj)
            if S[i + di][j + dj] == '#': continue
            #
            src = i * W + j
            dst = (i + di) * W + (j + dj)
            tab_graph[src][dst] = 1

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

G = csgraph_from_dense(tab_graph, null_value=myinf)
d = floyd_warshall(G)

# print("#", d)
ans = 0
for i in range(H * W):
    for j in range(H * W):
        if i == j: continue
        # print("##", i, j, d[i][j])
        if d[i][j] < myinf: ans = max(ans, int(d[i][j]))

print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import heapq

def dijkstra():
    #n:辺数,w:スタート一
    n,w = map(int,input().split())

    edge = [[] for i in range(n)]
    dg = 10**7
    # edge[i]:[コスト]
    for i in range(n-1):
        x,y = map(int,input().split())
        z = 1
        x -= 1
        y -= 1
        edge[x].append(dg + y)
        edge[y].append(dg + x)
    
    s = w-1
    d = [-1]*n
    d[s] = 0

    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)

        

    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        v,c = minedge%dg,minedge//dg
        if d[v] >= 0:
            continue
        d[v] = c
        for e in edge[v]:
            vNext = e%dg
            if d[vNext]:
                heapq.heappush(edgelist, (e//dg+d[v])*dg + vNext)

    return d


def warshall_floyd(n,d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d




N,M = m()


d = [[mod for i in range(N*M)] for j in range(N*M)]
for i in range(N*M):
    d[i][i] = 0
a = []
for i in range(N):
    a.append(list(input()))
    for j in range(M):
        if i != 0:
            if a[-1][j] == "." and a[-2][j] == ".":
                d[i*M+j-M][i*M+j] = 1
                d[i*M+j][i*M+j-M] = 1
        if j != 0:
            if a[-1][j] == "." and a[-1][j-1] == ".":
                d[i*M+j][i*M+j-1] = 1
                d[i*M+j-1][i*M+j] = 1

for k in range(N*M):
    for i in range(N*M):
        for j in range(N*M):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])

ma = 0
for i in range(N*M):
    for j in range(N*M):
        if d[i][j] != mod:
            ma = max(ma,d[i][j])

print(ma)

Submission status: Accepted

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

a= []

for i in range(h):
    arrc = input()
    a.append(arrc)
ans = 0
for gg in range(1,h+1):
    for bb in range(1,w+1):
        if a[gg-1][bb-1] == ".":
            ys=gg
            xs=bb
            n=[(ys-1,xs-1)]
            route={n[0]:0}
            p=[[1,0],[0,1],[-1,0],[0,-1]]
            count=1
            while count != 401:
                n2=[]
                for i in n:
                    for j in p:
                       
                        np=(i[0]+j[0],i[1]+j[1])
                        if 0<=np[0]<=h-1 and 0<=np[1]<=w-1:
                            if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                                n2.append(np)
                                route[np]=count
                n=n2
                count+=1
            
            ll= max(list(route.values()))
            if ll > ans:
                ans = ll

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
search = [[0]*W for _ in range(H)]
max_num = 0
q = deque()

def BFS(point):  # point : (h, w)
	global max_num
	while q:
		point = q.popleft()
		for i in range(4):
			x = point[1] + dx[i]
			y = point[0] + dy[i]
			if 0 <= x <= W-1 and 0 <= y <= H-1 and S[y][x] != "#" and search[y][x] == -1:
				search[y][x] = search[point[0]][point[1]] + 1
				max_num = max(search[y][x], max_num)
				q.append((y, x))

ans = 0
for i in range(H):
	for j in range(W):
		if S[i][j] == "#":
			continue
		q = deque()
		search = [[-1]*W for _ in range(H)]
		search[i][j] = 0
		start = (i, j)
		q.append(start)
		max_num = 0
		BFS(start)
		# print(search)
		ans = max(ans, max_num)
print(ans)

Submission status: Accepted

Solution code:
# coding=utf-8
get = lambda: int(raw_input().strip())
gets = lambda: map(int, raw_input().strip().split())
getss = lambda x: [gets() for _ in xrange(x)]
getl = lambda x: [gets() for _ in xrange(x)]


m, n = gets()
A0 = [list(raw_input().strip()) for _ in xrange(m)]

for i in xrange(m):
    for j in xrange(n):
        if A0[i][j] == '.':
            A0[i][j] = 0
        else:
            A0[i][j] = -1


def test(i, j):
    # print '\ntest ', i, j
    A = [row[:] for row in A0]
    bfs = [[i, j]]
    A[i][j] = 1
    dep = 0
    while bfs:
        dep += 1
        bfs2 = []
        for i, j in bfs:
            for di, dj in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
                i2, j2 = i + di, j + dj
                if 0 <= i2 < m and 0 <= j2 < n and A[i2][j2] == 0:
                    A[i2][j2] = dep + 1
                    bfs2.append([i2, j2])
        bfs = bfs2
    # for row in A:
    #     print row
    # print
    return dep


res = 0
for i in xrange(m):
    for j in xrange(n):
        if A0[i][j] < 0: continue
        res = max(res, test(i, j) - 1)
print res

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools
import itertools
import fractions

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29


def mk1d(n, val=INF):
    return [val for i in range(n)]

def mk2d(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]

DIV = 998244353

def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)


def floyd_warshall(costs):
    N = len(costs)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                costs[i][j] = min(costs[i][j], costs[i][k]+costs[k][j])
    return costs

def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

def main():
    H,W = isRaw()
    SS = [sRaw() for _ in range(H)]
    costs = mk2d(H*W, H*W, INF)
    for h in range(H):
        for w in range(W):
            cur = h*W+w
            costs[cur][cur] = 0
            if h<H-1 and SS[h][w]=="." and SS[h+1][w]==".":
                costs[cur][cur+W] = 1
                costs[cur+W][cur] = 1
            if w < W-1 and SS[h][w] == "." and SS[h][w+1] == ".":
                costs[cur][cur+1] = 1
                costs[cur+1][cur] = 1                
    costs = floyd_warshall(costs)
    maxCost = 0
    for cur in range(H*W):
        for nxt in range(H*W):
            if(costs[cur][nxt]!=INF) and cur!=nxt:
                maxCost = max(maxCost,costs[cur][nxt])
    return maxCost

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque
from operator import itemgetter
from heapq import heappop, heappush
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
H, W = inpl()
G = [[1]*(W+2)]
for _ in range(H):
    G.append([1] + [int(s=="#") for s in input()] + [1])
G.append([1]*(W+2))

ans = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        if G[h][w] == 1:
            continue
        dist = [[-1]*(W+2) for _ in range(H+2)]
        dist[h][w] = 0
        Q = deque()
        Q.append([h, w])
        while Q:
            ph, pw = Q.popleft()
            for dh, dw in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                qh, qw = ph+dh, pw + dw
                if G[qh][qw]:
                    continue
                if dist[qh][qw] == -1:
                    dist[qh][qw] = dist[ph][pw] + 1
                    Q.append([qh, qw])
                
        for y in range(1, H+1):
            for x in range(1, W+1):
                ans = max(ans, dist[y][x])
print(ans)

Submission status: Accepted

Solution code:
import copy
import queue
q=queue.Queue()
dx=[-1,0,1,0]
dy=[0,1,0,-1]
n,m=map(int,input().split())
b=[list(input()) for i in range(n)]
def abc(s,sy,sx):
    q=queue.Queue()
    for i in range(n):
        if 'S' in s[i]:
            sy=s[i].index('S')
            sx=i
            break
    # for i in range(n):
    #     if 'G' in s[i]:
    #         gy=s[i].index('G')
    #         gx=i
    #         break
    d=[[-1 for i in range(m)] for j in range(n)]
    q.put([sx,sy])
    d[sx][sy]=0
    while not q.empty():
        p=q.get()
        # if p[0]==gx and p[1]==gy:
        #     break
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if 0<=nx<n and 0<=ny<m and s[nx][ny]!='#' and d[nx][ny]==-1:
                q.put([nx,ny])
                d[nx][ny]=d[p[0]][p[1]]+1
    return d

s=copy.deepcopy(b)
res=0
for i in range(n):
    for j in range(m):
        if s[i][j]==".":
            a=abc(s,j,i)
            for k in range(n):
                a_max=max(a[k])
                if res<a_max:
                    res=a_max
print(res)

Submission status: Accepted

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

ans = 0
inf = 10**12
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        q = deque()
        q.append((i, j, 0))
        used = [[inf]*W for _ in range(H)]
        used[i][j] = 0
        while q:
            temp = q.popleft()
            k = temp[0]
            l = temp[1]
            d = temp[2]
            if k > 0 and S[k-1][l] == "." and used[k-1][l] > d+1:
                used[k-1][l] = d+1
                q.append((k-1, l, d+1))
            if k < H-1 and S[k+1][l] == "." and used[k+1][l] > d+1:
                used[k+1][l] = d+1
                q.append((k+1, l, d+1))
            if l > 0 and S[k][l-1] == "." and used[k][l-1] > d+1:
                used[k][l-1] = d+1
                q.append((k, l-1, d+1))
            if l < W-1 and S[k][l+1] == "." and used[k][l+1] > d+1:
                used[k][l+1] = d+1
                q.append((k, l+1, d+1))

        for s in range(H):
            for t in range(W):
                if used[s][t] < inf:
                    ans = max(ans, used[s][t])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
INF = float('inf')
MOD = 10 ** 9 + 7
dy = (0, -1, 0, 1)
dx = (1, 0, -1, 0)


H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dx = [0,0,-1,1]
dy = [1,-1,0,0]
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for _ in range(H)]
        if M[i][j] == '.':
            Ma = 0
            q.append((i, j))
            dist[i][j] = 0
            while q:
                cx,cy = q.popleft()
                for nx,ny in zip(dx,dy):
                    x ,y= cx+nx,cy+ny
                    if x<0 or y<0 or x>=H or y>=W or dist[x][y]>0:
                        continue
                    if M[x][y] == "." and dist[x][y] == -1:
                        dist[x][y]=dist[cx][cy]+1
                        Ma = max(Ma,dist[x][y])
                        q.append((x,y))
            # print(Ma)
            Max_list.append(Ma)
# print(Max_list)

print(max(Max_list))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
def warshal_floyd(d, n):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
        
  return d

h, w = map(int, input().split())
m = [str(input()) for _ in range(h)]
d = [[float('inf') for i in range(h*w)] for j in range(h*w)]
for i in range(h*w):
  d[i][i] = 0
  
for i in range(h*w):
  for j in range(h*w):
    py, px = i//w, i%w
    qy, qx = j//w, j%w
    if (px == qx and abs(py-qy) == 1) or (py == qy and abs(px-qx) == 1):
      pm = m[py][px]
      qm = m[qy][qx]
      if qm in ['.'] and pm in ['.']:
        d[i][j] = 1
        
#print(d)
d = warshal_floyd(d, h*w)
#print(d)

ans = 0
for i in range(h*w):
  for j in range(h*w):
    if d[i][j] != float('inf'):
      ans = max(ans, d[i][j])
print(ans)