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())
C = [list(input()) for i in range(h)]

queue = []
visited = [] 
ans = 0

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

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:
h,w = map(int,input().split())
C = [list(input()) for i in range(h)]

queue = []
visited = [] 
ans = 0
for i in range(h):
    T = [0]*w
    visited.append(T) 


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 ii in range(h):
            for jj in range(w):
                ans = max(ans,visited[ii][jj])
            
        queue = []
        visited = [] 
        for l in range(h):
            T = [0]*w
            visited.append(T) 
                        
        
print(ans-1)

Submission status: Accepted

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

ans = -1

for si in range(h):
    for sj in range(w):
        if S[si][sj] == ".":
            V = [[-1] * w for i in range(h)]
            Q = [[si, sj, 0]]
            s = 0
            V[si][sj] = 0
            while s < len(Q):
                i = Q[s][0]
                j = Q[s][1]
                d = Q[s][2]
                for t in [[-1,0], [1,0], [0,-1], [0,1]]:
                    di = t[0]
                    dj = t[1]
                    if 0 <= i+di < h and 0 <= j+dj < w and V[i+di][j+dj] == -1 and S[i+di][j+dj] == ".":
                        V[i+di][j+dj] = d+1
                        Q.append([i+di, j+dj, d+1])
                s += 1

            # print(V)

            ans = max(ans, max([max(V[i]) for i in range(h)]))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy
h,w = map(int,input().split())
maze = [["#"] * (w+2)]
for i in range(h):
    lu = list(input())
    l = ["#"] + lu + ["#"]
    maze.append(l)
maze.append(["#"] * (w+2))


def breadth_first_search(start,W,Wn):
    work_q = deque([])
    visited = set()
    work_q.append(start)
    visited.add(start)
    Wn[start[0]][start[1]] = 0
    max_dist = 0
    while work_q:
        here = work_q.popleft()
        move = [(here[0]+1,here[1]), (here[0],here[1]+1),
                (here[0]-1,here[1]),(here[0],here[1]-1)]
        for i in move:
            if W[i[0]][i[1]] == "." and i not in visited:
                work_q.append(i)
                visited.add(i)
                Wn[i[0]][i[1]] = Wn[here[0]][here[1]] + 1
                max_dist = max(max_dist, Wn[i[0]][i[1]])
    return Wn, max_dist


ans = 0
for i in range(h+2):
    for j in range(w+2):
        maze_num = copy.deepcopy(maze)
        if maze[i][j] == ".":
            start = (i,j)
            wn, wn_max = breadth_first_search(start,maze, maze_num)
            ans = max(ans, wn_max)
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
h,w=map(int,input().split())
s=[input() for _ in range(h)]
n=w*h
e=[[0]*n for _ in range(n)]
d=[(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
  for j in range(w):
    if s[i][j]==".":
      for x,y in d:
        ni,nj=i+x,j+y
        if 0<=ni<h and 0<=nj<w and s[ni][nj]==".":
          e[w*i+j][w*ni+nj]=1
ans=floyd_warshall(e)
INF=float("inf")
print(int(max(max(a if a != INF else 0 for a in a) for a in ans)))

Submission status: Accepted

Solution code:
import queue
def search(sy,sx):
    global H,W,Maze
    q = queue.Queue()

    Visit = [[-1]*W for _ in range(H)]
    Dir = [[0,1],[0,-1],[1,0],[-1,0]]

    Visit[sy][sx] = 0 
    q.put([sy,sx])

    while not q.empty():
        ty,tx = q.get()
        path = Visit[ty][tx]

        for dy,dx in Dir:
            ny = ty + dy
            nx = tx + dx
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if Maze[ny][nx] == '.':
                    if Visit[ny][nx] == -1:
                        Visit[ny][nx] = path+1
                        q.put([ny,nx])
    max1 = 0
    for h in range(H):
        for w in range(W):
            max1 = max(max1,Visit[h][w])
    return max1

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

ans = 0
for sy in range(H):
    for sx in range(W):
        if Maze[sy][sx] == '#':
            continue
        p = search(sy,sx)          
        if p > 0:
            ans = max(ans,p)
print(ans)

Submission status: Accepted

Solution code:
def A():
    c = input()
    print(chr(ord(c)+1))

def B():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    K = temp[1]
    M = temp[2]
    A = [int(k) for k in input().split()]
    ans = M*N - sum(A)
    if ans <= K:
        print(max(0, ans))
    else:
        print(-1)

from collections import defaultdict
def C():
    temp = [int(k) for k in input().split()]
    N = temp[0]
    M = temp[1]
    penal = defaultdict(int)
    P = []
    S = []
    for i in range(M):
        temp = input().split()
        P.append(int(temp[0]))
        S.append(temp[1])
    ac_problems = set()

    for i in range(M-1, -1, -1):
        if P[i] not in ac_problems and S[i] == 'AC':
            ac_problems.add(P[i])
        elif P[i] in ac_problems:
            if S[i] == 'WA':
                penal[P[i]] += 1
            elif S[i] == 'AC':
                penal[P[i]] = 0
    
    print(len(ac_problems), sum(penal.values()))

def D():
    temp = [int(k) for k in input().split()]
    H = temp[0]
    W = temp[1]
    S = []
    for i in range(H):
        S.append(input())
    ans = 0
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    def bfs(x, y):
        to_visit = [(x, y, 0)]
        visited = set()
        ret = 0
        while to_visit:
            x, y, distance = to_visit[0]
            del to_visit[0]
            if (x, y) in visited:
                continue
            visited.add((x, y))
            ret = max(distance, ret)
            for d in directions:
                if x+d[0] < H and x+d[0] >= 0:
                    if y+d[1] < W and y+d[1] >= 0:
                        if (x+d[0], y+d[1]) not in visited:
                            if S[x+d[0]][y+d[1]] == '.':
                                to_visit.append((x+d[0], y+d[1], distance+1))
        #print(memo)
        return ret

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                ans = max(bfs(i, j), ans)
                
    #print(memo)

    print(ans)

D()

Submission status: Accepted

Solution code:
M=410
e=enumerate
_,*s=open(0)
r=s+['#'*20]
d=eval('[M]*M,'*M)
for i,t in e(s):
  for j,u in e(t):
    k=i*20+j
    if u>'#'<t[j+1]:
      d[k][k+1]=1
      d[k+1][k]=1
    if u>'#'<r[i+1][j]:
      d[k][k+20]=1
      d[k+20][k]=1
r=range(M)
for i in r:d[i][i]=0
for k in r:
  for i in r:
    for j in r:d[i][j]=min(d[i][j],d[i][k]+d[k][j])
print(max(u for t in d for u in t if u<M))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
from collections import deque
def resolve():
    h,w=map(int,input().split())
    G=[list(input()) for _ in range(h)]

    D=[(-1,0),(1,0),(0,-1),(0,1)]
    ans=0
    for si,sj in product(range(h),range(w)):
        if(G[si][sj]=='#'): continue

        # bfs して距離を出し、その max の max
        dist=[[INF]*w for _ in range(h)]
        dist[si][sj]=0
        Q=deque([(si,sj)])
        while(Q):
            i,j=Q.popleft()
            for di,dj in D:
                ni,nj=i+di,j+dj
                if(not (0<=ni<h and 0<=nj<w)): continue
                if(G[ni][nj]=='#'): continue
                if(dist[ni][nj]>dist[i][j]+1):
                    dist[ni][nj]=dist[i][j]+1
                    Q.append((ni,nj))

        ans=max(ans,max(dist[i][j] for i,j in product(range(h),range(w)) if dist[i][j]!=INF))

    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

inf = float('inf')

delta = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def bfs(sy, sx):
    dist_max = 0
    visited = set()
    queue = deque([(0, sy, sx)])
    while queue:
        d, y, x = queue.popleft()
        if (y, x) in visited:
            continue
        visited.add((y, x))
        dist_max = max(dist_max, d)
        for dy, dx in delta:
            i = y + dy
            j = x + dx
            if maze[i][j] == '.' and not (i, j) in visited:
                queue.append((d+1, i, j))
    return dist_max
        
h, w = map(int, sys.stdin.readline().split())
maze = ['#' * (w + 2)]
maze += ['#' + sys.stdin.readline().rstrip() + '#' for _ in range(h)]
maze += ['#' * (w + 2)]

def main():
    res = 0
    for sy in range(1, h+1):
        for sx in range(1, w+1):
            if maze[sy][sx] == '#':
                continue
            res = max(res, bfs(sy, sx))
    
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse import*
e=enumerate
_,*s=open(0)
r=s+['#'*20]
*g,=eval('[0]*500,'*500)
for i,t in e(s):
 for j,u in e(t):k=i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<r[i+1][j]
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<999])))

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque

# 最短にする
# 0回以上でたどり着けるのでスタート=ゴールのことがある ふざけんな
h, w = map(int, input().split())
table = [[] for _ in range(h)]
for i in range(h):
    table[i] = list(input())


def bfs(y, x, t):
    steps = [0, 1, 0, -1, 0]
    queue = deque([[y, x]])
    ret = 0
    while len(queue) > 0:
        cur_y, cur_x = queue.popleft()
        for i in range(4):
            next_y, next_x = cur_y + steps[i], cur_x + steps[i + 1]
            if 0 <= next_y < h and 0 <= next_x < w:
                if t[next_y][next_x] == ".":
                    t[next_y][next_x] = t[cur_y][cur_x] + 1
                    ret = max(ret, t[next_y][next_x])
                    queue.append([next_y, next_x])

    return ret


ans = 0
for sy in range(h):
    for sx in range(w):
        # table[sy][sx]をスタート地点とする
        if table[sy][sx] != ".":
            continue
        mytable = deepcopy(table)
        mytable[sy][sx] = 0
        ret = bfs(sy, sx, mytable)
        ans = max(ans, ret)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
a = [input() for _ in range(h)]
r = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == '.':
      b = list(map(list, a))
      q = deque()
      b[i][j] = 0
      q.append((i, j))
      while(q):
        i, j = q.popleft()
        r = max(r, b[i][j])
        for di in range(-1, 2):
          i1 = i + di
          if 0 <= i1 < h:
            for dj in range(di % 2 - 1, 2, 2):                
              j1 = j + dj
              if 0 <= j1 < w and b[i1][j1] == '.':
                b[i1][j1] = b[i][j] + 1
                q.append((i1, j1))
print(r)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
r = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == '.':
      b = deepcopy(a)
      q = deque()
      b[i][j] = 0
      q.append((i, j))
      while(q):
        i, j = q.popleft()
        r = max(r, b[i][j])
        for di in range(-1, 2):
          i1 = i + di
          if 0 <= i1 < h:
            for dj in range(di % 2 - 1, 2, 2):                
              j1 = j + dj
              if 0 <= j1 < w and b[i1][j1] == '.':
                b[i1][j1] = b[i][j] + 1
                q.append((i1, j1))
print(r)

Submission status: Accepted

Solution code:
from scipy.sparse import*
e=enumerate
_,*s=open(0)
r=s+['#'*20]
*g,=eval('[0]*500,'*500)
for i,t in e(s):
 for j,u in e(t):k=i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<r[i+1][j]  
a=csgraph.johnson(csr_matrix(g),0)
print(int(max(a[a<999])))

Submission status: Accepted

Solution code:
from scipy.sparse import*
e=enumerate
_,*s=open(0)
r=s+['#'*20]
*g,=eval('[0]*500,'*500)
for i,t in e(s):
 for j,u in e(t):k=i*20+j;g[k][k+1]=u>'#'<t[j+1];g[k][k+20]=u>'#'<r[i+1][j]  
a=csgraph.johnson(csr_matrix(g),0)
print(int(a[a<999].max()))

Submission status: Accepted

Solution code:
from scipy.sparse import*
e=enumerate
_,*s=open(0)
r=s+['#'*20]
*g,=eval('[0]*500,'*500)
for i,t in e(s):
  for j,u in e(t):
    k=i*20+j
    g[k][k+1]=u>'#'<t[j+1]
    g[k][k+20]=u>'#'<r[i+1][j]  
a=csgraph.johnson(csr_matrix(g),0)
print(int(a[a<999].max()))

Submission status: Accepted

Solution code:
from scipy.sparse import*
e=enumerate
h,*s=open(0)
h=int(h[:2])
*g,=eval('[0]*500,'*500)
for i,t in e(s):
  for j,u in e(t):
    k=i*20+j
    g[k][k+1]=u>'#'<t[j+1]
    g[k][k+20]=(i<h-1)*u>'#'<s[i+1][j]  
a=csgraph.johnson(csr_matrix(g),0)
print(int(a[a<999].max()))

Submission status: Accepted

Solution code:
from scipy.sparse import*
e=enumerate
h,*s=open(0)
h,w=map(int,h.split())
*g,=eval('[0]*500,'*500)
for i,t in e(s):
  for j,u in e(t):
    k=i*w+j
    g[k][k+1]=u>'#'<t[j+1]
    g[k][k+w]=(i<h-1)*u>'#'<s[i+1][j]  
a=csgraph.johnson(csr_matrix(g),0)
print(int(a[a<999].max()))

Submission status: Accepted

Solution code:
INF = float("inf")

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

N = W * H
E = [[INF] * N  for _ in range(N)]

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
A = floyd_warshall(E)
INF = float("inf")

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

Submission status: Accepted

Solution code:
from collections import deque
import copy

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

road = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            road.append((h, w))

ans = 0
for rh, rw in road:
    SC, q = copy.deepcopy(S), deque([(rh, rw, 0)])
    SC[rh][rw] = 0
    while len(q) > 0:
        h, w, i = q.popleft()
        for nh, nw in neig:
            if 0 <= h - nh < H and 0 <= w - nw < W and SC[h - nh][w - nw] == '.':
                SC[h - nh][w - nw] = i + 1
                ans = max(ans, i + 1)
                q.append([h - nh, w - nw, i + 1])

print(ans)

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

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
A = floyd_warshall(E)
INF = float("inf")

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

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

# print(E)

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

# print(E)

from scipy.sparse.csgraph import floyd_warshall
INF = float("inf")

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

Submission status: Accepted

Solution code:
H,W = (int(x) for x in input().split())
a = []
que = []
dis =[]
longDis = 0

for i in range(H):
    a += list(input().split())

h = -1
w = 0

for _ in range(H*W):
    com = [[0 for i in range(W)] for j in range(H)]
    k = 0
    dis = [k]
    l = 0

    if h < H-1:
        h += 1
    else:
        h = 0
        w += 1

    if a[h][w] != '.':
        continue

    que += [[h,w]]
    com[h][w] = 1
    i = h
    j = w
    
    while True:
        k = dis[l] + 1

        #上
        if i-1 >= 0 and a[i-1][j] == '.':
            if com[i-1][j] == 0:
                que += [[i-1,j]]
                dis += [k]
                com[i-1][j] = 1

        #下
        if i+1 < H and a[i+1][j] == '.':
            if com[i+1][j] == 0:
                que += [[i+1,j]]
                dis += [k]
                com[i+1][j] = 1

        #左
        if j-1 >= 0 and a[i][j-1] == '.':
            if com[i][j-1] == 0:
                que += [[i,j-1]]
                dis += [k]
                com[i][j-1] = 1 

        #右
        if j+1 < W and a[i][j+1] == '.':
            if com[i][j+1] == 0:
                que += [[i,j+1]]
                dis += [k]
                com[i][j+1] = 1

        l += 1

        if l == len(que):
            break
        
        i = que[l][0]
        j = que[l][1]

    for i in range(len(dis)):
        if dis[i] > longDis:
            longDis = dis[i]

    dis.clear()
    que.clear()

print(longDis)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
S=[[False]*(W+2)]
for i in range(H):
    S.append([False]+[c=='.' for c in input()]+[False])
S.append([False]*(W+2))

r=[] # 道のマスの座標 t->(i,j)
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]:
            r.append((i,j))
m=len(r)
d=[[10**3 for j in range(m)] for i in range(m)] # d[i][j]=i番目の道のマスからj番目の道のマスまでの距離
for u in range(m-1):
    d[u][u]=0
    si,sj=r[u]
    for v in range(u+1,m):
        ti,tj=r[v]
        if (si==ti and abs(sj-tj)==1) or (abs(si-ti)==1 and sj==tj):
            d[u][v]=d[v][u]=1
'''
print(r)
for di in d:
    print(di)
'''
for k in range(m):
    for s in range(m):
        for g in range(m):
            d[s][g]=min(d[s][g], d[s][k]+d[k][g])
    '''
    for di in d:
        print(di)
    print()
    '''
ans=0
for i in range(m-1):
    for j in range(i+1,m):
        ans=max(ans,d[i][j])

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n, m = map(int, input().split())
g = [input() for _ in range(n)]
maze = np.array(list(map(list, g)))

from collections import deque


def dfs(s, maze):
    H, W = maze.shape

    visited = np.array([[-1 for _ in range(W)] for _ in range(H)])
    visited[s[0]][s[1]] = 0

    actions = [(-1,0),(1,0),(0,-1),(0,1)]
    queue = deque([s])

    while queue:
        x,y = queue.popleft()
        for action in actions:
            nx = x + action[0]
            ny = y + action[1]
            if nx in range(H) and ny in range(W) and maze[(nx,ny)]=='.' and visited[(nx,ny)]==-1:
                visited[(nx,ny)] = visited[(x,y)] + 1
                queue.append((nx,ny))
    return np.max(visited)
    
ret = -1
H, W = maze.shape

for sx in range(H):
    for sy in range(W):
        if maze[sx][sy] == '.':
            ret = max(dfs((sx,sy), maze), ret)
print(ret)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
from collections import deque
from itertools import combinations
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

H,W=LI()
MP=[input() for _ in range(H)]
CORD=[(i,j) for i in range(H) for j in range(W)]

max_dist = 0
for i in range(len(CORD)):
    st = CORD[i]
    if MP[st[0]][st[1]] == ".":
        QUE=deque()
        visited = [[0]*W for i in range(H)]
        visited[st[0]][st[1]] = 1
        QUE.append((st[0], st[1], 0))
        res = 0
        while QUE:
            ii, jj, dist = QUE.popleft()
            max_dist = max(max_dist, dist)
            for iii, jjj in [(ii-1,jj),(ii+1,jj),(ii,jj-1),(ii,jj+1)]:
                if iii >= 0 and jjj >= 0 and iii < H and jjj < W and MP[iii][jjj] != '#' and not visited[iii][jjj]:
                    QUE.append((iii, jjj, dist+1))
                    visited[iii][jjj] = 1


print(max_dist)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

def in_range(t, l, r):
    return l <= t and t < r

def main():
    H, W = rip()
    S = [""] * H
    for i in range(H): S[i] = rs()

    inf = int(1e9)
    ma = 0
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#': continue

            mi = [[inf] * W for i in range(H)]
            mi[i][j] = 0
            q = collections.deque()
            q.append((i,j))
            while len(q) > 0:
                y, x = q.popleft()
                for t in range(4):
                    ny = y + dy[t]
                    nx = x + dx[t]
                    if (not in_range(nx, 0, W)) or (not in_range(ny, 0, H)) : continue
                    if S[ny][nx] == '#': continue
                    if mi[ny][nx] == inf:
                        mi[ny][nx] = mi[y][x] + 1
                        q.append((ny, nx))
            for k in range(H):
                for l in range(W):
                    if S[k][l] == '#': continue
                    ma = max(ma, mi[k][l])
    
    print(ma)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def solve(s, start):
    if s[start[0]][start[1]] == "#":
        return -1 
    q = deque([start])
    distance = [[-1] * w for _ in range(h)]
    distance[start[0]][start[1]] = 0

    while q:
        y, x = q.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + i, x + j
            if not(0 <= new_y < h and 0 <= new_x < w): continue
            if s[new_y][new_x] == "#": continue
            if distance[new_y][new_x] == -1:
                distance[new_y][new_x] = distance[y][x] + 1
                q.append([new_y, new_x])

    return max(map(max, distance))


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

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, solve(s, [i, j]))

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
h,w=map(int,input().split())
l=set()
for i in range(h):
    t=input()
    for j in range(w):
        if t[j]==".":
            l.add((i,j))

s=set()
from collections import deque
graph=np.zeros((h*w,h*w),dtype=np.int64)
for x,y in l:
        if (x+1,y) in l and (x*w+y,(x+1)*w+y) not in s:
            graph[x*w+y,(x+1)*w+y]=1
            s.add((x*w+y,(x+1)*w+y))
        if (x,y+1) in l and (x*w+y,x*w+y+1) not in s:
            graph[x*w+y,x*w+y+1]=1
            s.add((x*w+y,x*w+y+1))

from scipy.sparse.csgraph import floyd_warshall


ans=floyd_warshall(graph,directed=False)
cond=ans!=float("inf")
print(int(ans[cond].max()))

Submission status: Accepted

Solution code:
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S_ = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
for i, j in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S_[i][j] == '.':
        S = copy.deepcopy(S_)
        S[i][j] = '#'
        q = collections.deque([(i, j, 0)])
        while q:
            x, y, d = q.popleft()
            for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                if S[x + dx][y + dy] == '.':
                    X, Y = x + dx, y + dy
                    S[X][Y] = '#'
                    q += [(X, Y, d + 1)]
        ans = max(d, ans)
print(ans)

Submission status: Accepted

Solution code:
# ABC 151 C Maze Master
from collections import deque

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

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

ans = 0
for si in range(H):
    for sj in range(W):
        if graph[si][sj] == "#": continue
        que = deque()
        que.append([si, sj])

        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[si][sj] = 0
        
        while que:
            y, x = que.popleft()

            for dir in range(4):
                ny = y + dy[dir]
                nx = x + dx[dir]
                if ny < 0 or ny >= H or nx < 0 or nx >= W: continue
                if graph[ny][nx] == "#": continue
                if dist[ny][nx] != -1: continue

                if graph[ny][nx] == ".":
                    dist[ny][nx] = dist[y][x] + 1
                    que.append([ny, nx])

        for i in range(H):
            for j in range(W):
                if dist[i][j] == -1: continue
                ans = max(ans, dist[i][j])

print(ans)

Submission status: Accepted

Solution code:
'''input
3 3
.#.
#..
.#.
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0 and maze[x - 1][y] != '#' and mp([x - 1, y]) not in visited:
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n and maze[x + 1][y] != '#' and mp([x + 1, y]) not in visited:
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0 and maze[x][y - 1] != '#' and mp([x, y - 1]) not in visited:
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m and maze[x][y + 1] != '#' and mp([x, y + 1]) not in visited:
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		


# main starts
n, m = list(map(int, input().split()))
maze = []
for _ in xrange(n):
	state = list(input().strip())
	maze.append(state)

# from random import randint
# for _ in xrange(1000):
# maze = []
# n = randint(1, 20)
# m = randint(1, 20)
# for i in xrange(n):
# 	temp = []
# 	for j in xrange(m):
# 		k = randint(1, 2)
# 		if k == 1:
# 			temp.append('.')
# 		else:
# 			temp.append('#')
# 	maze.append(temp)

ans = 0
for i in xrange(n):
	for j in xrange(m):
		if maze[i][j] != '#':
			first = [i, j]
			ans = max(ans, bfs(first))
print(ans)

Submission status: Accepted

Solution code:
'''input
3 3
.#.
#..
.#.
'''
# A coding delight
from sys import stdin, stdout
import gc
gc.disable()
input = stdin.readline
from collections import deque


def mp(arr):
	arr = map(str, arr)
	return ' '.join(arr)


def bfs(source):
	myq = deque()
	myq.append(source)
	visited = dict()
	visited[mp(source)] = True
	dist = -1
	while len(myq) > 0:
		temp = deque()
		dist += 1
		while len(myq) > 0:
			x, y  = myq.popleft()
			if x - 1 >= 0 and maze[x - 1][y] != '#' and mp([x - 1, y]) not in visited:
					visited[mp([x -1, y])] = True
					temp.append([x - 1, y])
			if x + 1 < n and maze[x + 1][y] != '#' and mp([x + 1, y]) not in visited:
					visited[mp([x + 1, y])] = True
					temp.append([x + 1, y])
			if y - 1 >= 0 and maze[x][y - 1] != '#' and mp([x, y - 1]) not in visited:
					visited[mp([x, y - 1])] = True
					temp.append([x, y - 1])
			if y + 1 < m and maze[x][y + 1] != '#' and mp([x, y + 1]) not in visited:
					visited[mp([x, y + 1])] = True
					temp.append([x, y + 1])
		myq = temp
	return dist		


# main starts
n, m = list(map(int, input().split()))
maze = []
for _ in range(n):
	state = list(input().strip())
	maze.append(state)

# from random import randint
# for _ in range(1000):
# maze = []
# n = randint(1, 20)
# m = randint(1, 20)
# for i in range(n):
# 	temp = []
# 	for j in range(m):
# 		k = randint(1, 2)
# 		if k == 1:
# 			temp.append('.')
# 		else:
# 			temp.append('#')
# 	maze.append(temp)

ans = 0
for i in range(n):
	for j in range(m):
		if maze[i][j] != '#':
			first = [i, j]
			ans = max(ans, bfs(first))
print(ans)