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())
s = [input() for _ in range(h)]

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            dis = [[-1] * w for _ in range(h)]
            dis[i][j] = 0
            q = [(i,j)]
            while q:
                l0,l1 = q.pop(0)
                if l0 > 0:
                    if s[l0-1][l1] == '.':
                        if dis[l0-1][l1] > dis[l0][l1] + 1 or dis[l0-1][l1] == -1:
                            dis[l0-1][l1] = dis[l0][l1] + 1
                            q.append((l0-1,l1))
                if l0 < h - 1:
                    if s[l0+1][l1] == '.':
                        if dis[l0+1][l1] > dis[l0][l1] + 1 or dis[l0+1][l1] == -1:
                            dis[l0+1][l1] = dis[l0][l1] + 1
                            q.append((l0+1,l1))
                if l1 > 0:
                    if s[l0][l1-1] == '.':
                        if dis[l0][l1-1] > dis[l0][l1] + 1 or dis[l0][l1-1] == -1:
                            dis[l0][l1-1] = dis[l0][l1] + 1
                            q.append((l0,l1-1))
                if l1 < w - 1:
                    if s[l0][l1+1] == '.':
                        if dis[l0][l1+1] > dis[l0][l1] + 1 or dis[l0][l1+1] == -1:
                            dis[l0][l1+1] = dis[l0][l1] + 1
                            q.append((l0,l1+1))
            dis_max = 0
            for k in dis:
                dis_max = max(max(k), dis_max)
            ans = max(dis_max,ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input=sys.stdin.readline
h,w=map(int,input().split())
s=[]
for i in range(h):
    sub=input().rstrip()
    s.append(sub)
dire=[(1,0),(-1,0),(0,1),(0,-1)]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            l=[[-1]*w for _ in range(h)]
            q=[(i,j)]
            q=deque(q)
            l[i][j]=0
            while len(q)!=0:
                now=q.popleft()
                for d in dire:
                    x=now[0]+d[0]
                    y=now[1]+d[1]
                    if 0<=x<h and 0<=y<w:
                        if s[x][y]=='.':
                            if l[x][y]==-1:
                                l[x][y]=l[now[0]][now[1]]+1
                                ans=max(ans,l[x][y])
                                q.append((x,y))
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(input()))
c = 0
inds = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            inds[i][j] = c
            c += 1
inf = 10**10
graph = [[inf] * c for _ in range(c)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            d = inds[i][j]
            graph[d][d] = 0
            if j > 0 and s[i][j-1] == '.':
                graph[d][inds[i][j-1]] = 1
            if j < w-1 and s[i][j+1] == '.':
                graph[d][inds[i][j+1]] = 1
            if i >0 and s[i-1][j] == '.':
                graph[d][inds[i-1][j]] = 1
            if i < h-1 and s[i+1][j] == '.':
                graph[d][inds[i+1][j]] = 1
for k in range(c):
    for i in range(c):
        for j in range(c):
            graph[i][j] = min(graph[i][j],graph[i][k] + graph[k][j])
mins = 0
for i in range(c):
    for j in range(c):
        if graph[i][j] > mins:
            mins = graph[i][j]
print(mins)

Submission status: Accepted

Solution code:
from collections import deque

h,w = map(int,input().split())
dg = 30

s = [['#']*(w+2)]
for _ in [0]*h:
    s.append(['#'] + list(input()) + ['#'])
s.append(['#']*(w+2))

res = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] == '#':
            continue
        d = [[0]*(w+2) for _ in [0]*(h+2)]
        
        start = i*dg+j
        tank = deque([start])
        while tank:
            x = tank.popleft()
            
            go = x-dg
            if go != start and s[go//dg][go%dg] == '.' and d[go//dg][go%dg] == 0:
                d[go//dg][go%dg] = d[x//dg][x%dg] + 1
                res = max(res,d[go//dg][go%dg])
                tank.append(go)
            go = x+dg
            if go != start and s[go//dg][go%dg] == '.' and d[go//dg][go%dg] == 0:
                d[go//dg][go%dg] = d[x//dg][x%dg] + 1
                res = max(res,d[go//dg][go%dg])
                tank.append(go)
            go = x+1
            if go != start and s[go//dg][go%dg] == '.' and d[go//dg][go%dg] == 0:
                d[go//dg][go%dg] = d[x//dg][x%dg] + 1
                res = max(res,d[go//dg][go%dg])
                tank.append(go)
            go = x-1
            if go != start and s[go//dg][go%dg] == '.' and d[go//dg][go%dg] == 0:
                d[go//dg][go%dg] = d[x//dg][x%dg] + 1
                res = max(res,d[go//dg][go%dg])
                tank.append(go)

print(res)

Submission status: Accepted

Solution code:
INFTY = 10**13
def floyd():
    for k in range(n):
        for i in range(n):
            if d[i][k] == INFTY:
                continue
            for j in range(n):
                if d[k][j] == INFTY:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
n = H*W
d = [[0 if i == j else INFTY for j in range(n)]for i in range(n)]

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        for dh, dw in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            if 0 <= h + dh < H and 0 <= w + dw < W and S[h+dh][w+dw] == '.':
                d[h*W+w][(h+dh)*W+(w+dw)] = 1

floyd()

ans = max([x for row in d for x in row if x != INFTY])
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        line = input().rstrip('\n')
        grid.append(line)

    d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                continue
            ans_new = 0
            seen = [[-100] * W for _ in range(H)]
            seen[i][j] = 0
            que = deque()
            que.append(i*W+j)
            while que:
                v = que.popleft()
                y, x = divmod(v, W)
                for dx, dy in d:
                    x_new = x+dx
                    y_new = y+dy
                    if 0 <= y_new < H and 0 <= x_new < W:
                        if seen[y_new][x_new] == -100:
                            if grid[y_new][x_new] == '.':
                                que.append(y_new * W + x_new)
                                seen[y_new][x_new] = seen[y][x] + 1
                                if ans_new < seen[y_new][x_new]:
                                    ans_new = seen[y_new][x_new]
            ans = max(ans, ans_new)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            result = max(result, f(i, j))
print(result)

Submission status: Accepted

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

H,W=map(int,input().split())
S=[input().strip() for i in range(H)]
from collections import deque

def bfs(x,y):
    if S[x][y]=="#":
        return 0
    
    Q=deque()
    Q.append((x,y))
    count=[[-1]*W for i in range(H)]
    count[x][y]=0

    while Q:
        x,y=Q.pop()
        for z,w in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:
            if 0<=z<H and 0<=w<W and count[z][w]==-1 and S[z][w]==".":
                count[z][w]=count[x][y]+1
                Q.appendleft((z,w))

    #print(x,y)
    #for c in count:
    #    print(c)

    return max([max(c) for c in count])

ANS=0

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

print(ANS)

Submission status: Accepted

Solution code:
import copy
H, W = map(int, input().split())
#field = [list(input().split()) for _ in range(H)]
field = [[] for _ in range(H)]
for i in range(H):
    for s in input():
        field[i].append(s)

# bfsで最大値を求めて出力する
# スタート地点を全探索する

def bfs(sy, sx, field, H, W):
    field[sy][sx] = 0
    pre_list = [(sy,sx)]
    count = 0
    while len(pre_list) > 0:
        count += 1
        next_list = []
        for y,x in pre_list:
            for i,j in ((1,0),(0,-1),(0,1),(-1,0)):
                if y+i < 0 or x+j < 0 or y+i >= H or x+j >= W:
                    continue
                if field[y+i][x+j] == '.':
                    field[y+i][x+j] = count
                    next_list.append((y+i,x+j))
        pre_list = next_list
    return count

ret = 0
for h in range(H):
    for w in range(W):
        if field[h][w] == '#':
            continue
        ret = max(ret, bfs(h, w, copy.deepcopy(field), H, W))

print(ret-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

H,W = map(int,readline().split())
H += 2; W += 2
grid = '#' * W
for _ in range(H-2):
    grid += '#' + readline().rstrip().decode() + '#'
grid += '#' * W

def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1,1,W,-W):
            w = v + move
            if grid[w] == '#':
                continue
            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)
    return max(x for x in dist if x < INF)

answer = max(bfs(v) for v in range(H*W) if grid[v] != '#')
print(answer)

Submission status: Accepted

Solution code:
def main():

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

    ans = 0
    mv = [[1,0], [-1,0], [0, 1], [0,-1]]
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                cnt = 0
                cur = [[i, j]]
                visited = set([(i, j)])
                while cur:
                    temp = []
                    for k, l in cur:
                        for dk, dl in mv:
                            k1, l1 = k+dk, l+dl
                            if 0<=k1<H and 0<=l1<W and S[k1][l1] == "." and (k1,l1) not in visited:
                                visited.add((k1,l1))
                                temp.append([k1, l1])
                    cur = temp
                    if len(cur) > 0: cnt += 1
                ans = max(ans, cnt)
    return ans

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

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
L=[]
Z=["#" for i in range(W+2)]
L.append(Z)
for i in range(H):
    S=["#"]+list(input())+["#"]
    L.append(S)
L.append(Z)

#print(L)
X=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if L[i][j]==".":
            X.append([i,j])
#print(X)
x=[1,-1,0,0]
y=[0,0,1,-1]
import copy
ans=0
for i in range(len(X)):
    l=copy.deepcopy(L)
    l[X[i][0]][X[i][1]]=0
    Q=[[X[i][0],X[i][1]]]
    for j in range(10**9):
        if j==len(Q):
            break
        for k in range(4):
            if l[Q[j][0]+x[k]][Q[j][1]+y[k]]==".":
                l[Q[j][0]+x[k]][Q[j][1]+y[k]]=l[Q[j][0]][Q[j][1]]+1
                Q.append([Q[j][0]+x[k],Q[j][1]+y[k]])
    for a in range(1,H+1):
        for b in range(1,W+1):
            if l[a][b]!="#":
                if l[a][b]>ans:
                    ans=l[a][b]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    h, w = LI()
    s = SR(h)
    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                q = deque()
                q.append((i, j))
                dist = defaultdict(int)
                dist[q[0]] = 1
                while q:
                    p = q.popleft()
                    dp = dist[p]
                    for mx, my in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                        my += p[0]
                        mx += p[1]
                        if 0 <= mx < w and 0 <= my < h:
                            if dist[(my, mx)] or s[my][mx] == "#":
                                continue
                            dist[(my, mx)] = dp + 1
                            q.append((my,mx))
                ans = max(ans, max(dist.values()))
    print(ans-1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
from collections import deque
ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '#': continue
        dist = [[0]*W for i in range(H)]
        visited = [[0]*W for i in range(H)]
        visited[y][x] = 1
        q = deque([(x,y)])
        while q:
            x,y = q.popleft()
            for dx,dy in dxy:
                nx,ny = x+dx,y+dy
                if not 0 <= nx < W: continue
                if not 0 <= ny < H: continue
                if visited[ny][nx]: continue
                if S[ny][nx] == '#': continue
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1
                q.append((nx,ny))
        ans = max(ans, max(max(row) for row in dist))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
S = [input() for _ in range(h)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
def search(sy, sx):
  if S[sy][sx] == "#":
    return -1
  dist = [[-1]*w for _ in range(h)]
  dist[sy][sx] = 0
  dq = deque()
  dq.append((sy, sx))
  while dq:
    y, x = dq.popleft()
    for i in range(4):
      ny = y+dy[i]
      nx = x+dx[i]
      if 0<=ny<h and 0<=nx<w:
        if S[ny][nx] == "#":
          continue
        if dist[ny][nx] != -1:
          continue
        dist[ny][nx] = dist[y][x] + 1
        dq.append((ny, nx))
  A = np.array(dist)
  return A.max()
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, search(i, j))
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
grid = [input() for i in range(n)]

res = 0
dirs = [(0,1),(1,0),(0,-1),(-1,0)]

for a in range(n):
  for b in range(m):
    if grid[a][b] != '.':
      continue
    vis = set([(a,b)])
    q = [(a,b,0)]
    qi = 0
    while qi < len(q):
      i, j, c = q[qi]
      res = max(res, c)
      qi += 1
      for di, dj in dirs:
        ni, nj = i + di, j + dj
        if (ni, nj) in vis or ni < 0 or ni >= n or nj < 0 or nj >= m or grid[ni][nj] != '.':
          continue
        vis.add((ni, nj))
        q.append((ni, nj, c+1))
print(res)

Submission status: Accepted

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


def bfs(start):
    one_steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    seen = set()
    todo = deque()
    todo.append(start)
    dis = {start: 0}
    a = 0
    while len(todo) > 0:
        a += 1
        x, y = todo.popleft()
        if (x, y) in seen:
            continue
        seen.add((x, y))
        for dx, dy in one_steps:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H) or not (0 <= ny < W):
                continue
            if (nx, ny) in seen:
                continue
            elif graph[nx][ny] == "." and (nx, ny) != start:
                dis[(nx, ny)] = dis[(x, y)] + 1
                todo.append((nx, ny))

    return max(dis.values())


ans = -1
for x_ in range(H):
    for y_ in range(W):
        if graph[x_][y_] == ".":
            ans = max(ans, bfs((x_, y_)))
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [input() for _ in range(H)]
from scipy.sparse.csgraph import floyd_warshall as fw

edge = [[float('inf')]*(H*W) for _ in range(H*W)]
def encode(i,j):
    return i*W+j

for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            continue
        for (dx,dy) in [(-1,0),(1,0),(0,-1),(0,1)]:
            if 0<=i+dx<=H-1 and 0<=j+dy<=W-1:
                if (dx,dy)==(0,0):
                    continue
                if S[i+dx][j+dy]=='.':
                    edge[encode(i,j)][encode(i+dx,j+dy)] = 1

cost = fw(edge)
ans = 0
for i in range(H*W):
    for j in range(H*W):
        if cost[i][j]==float('inf'):
            continue
        ans = max(ans,cost[i][j])
ans = int(ans)
print(ans)

Submission status: Accepted

Solution code:
from queue import Queue
H, W  = list(map(int, input().split()))

Ss = []
for i in range(H):
    Ss.append(input())


def bfs(Ss, startX, startY):
    dir = [(1,0), (0, 1), (-1, 0), (0, -1)]

    currentX = startX
    currentY = startY
    queue = Queue()
    visited = set()
    queue.put((currentX, currentY, 0))
    maxDist = 0
    while not queue.empty():
        nextX, nextY, dist = queue.get()
        visited.add((nextX, nextY))
        maxDist = max(maxDist, dist)
        for (dx, dy) in dir:
            y_dy = nextY + dy
            x_dx = nextX + dx
            if y_dy >= 0 and y_dy < len(Ss) and x_dx >= 0 and x_dx < len(Ss[0]):
                if Ss[y_dy][x_dx] != '#':
                    if (x_dx, y_dy) not in visited:
                        queue.put((x_dx, y_dy, dist + 1))
                    visited.add((x_dx, y_dy))
    return maxDist

maxDist = 0
for y in range(H):
    for x in range(W):
        if Ss[y][x] != '#':
            dist = bfs(Ss, x, y)
            maxDist = max(dist, maxDist)
print(maxDist)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

h,w=map(int,input().split())
S=[list(input()) for i in range(h)]
dydx４=((-1,0),(0,-1),(0,1),(1,0))
for i in range(h):
    for j in range(w):
        if S[i][j]=="#": continue
        color=[[-1]*w for i in range(h)]
        color[i][j]=0
        que=collections.deque()
        que.append((i,j,0))
        while que:
            pi,pj,now = que.popleft()
            for di,dj in dydx４:
                ni=pi+di; nj=pj+dj
                if 0<=ni<h and 0<=nj<w:
                    if color[ni][nj]==-1 and S[ni][nj]==".":
                        que.append((ni,nj,now+1))
                        color[ni][nj]=now+1
        tmp=0
        for ci in color:
            tmp=max(tmp,max(ci))
        ans=max(ans,tmp)
        # print(tmp)
        # if i==j==0:
        #     print(*color,sep="\n")
print(ans)

Submission status: Accepted

Solution code:
from collections import  deque

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

S = []

for i in range(H):

    s = list(input())
    S.append(s)

#print (S)

ans = 0

for a in range(H):
    for b in range(W):

        if S[a][b] == "#":
            continue
        
        q = deque([])
        q.append([a,b])
        d = [[float("inf")] * W for i in range(H)]
        d[a][b] = 0

        while len(q) > 0:

            now = q.popleft()
            x = now[0]
            y = now[1]

            if x > 0 and S[x-1][y] == ".":
                if d[x-1][y] > d[x][y] + 1:
                    d[x-1][y] = d[x][y] + 1
                    q.append([x-1,y])
            if x < H-1 and S[x+1][y] == ".":
                if d[x+1][y] > d[x][y] + 1:
                    d[x+1][y] = d[x][y] + 1
                    q.append([x+1,y])

            if y > 0 and S[x][y-1] == ".":
                if d[x][y-1] > d[x][y] + 1:
                    d[x][y-1] = d[x][y] + 1
                    q.append([x,y-1])

            if y < W-1 and S[x][y+1] == ".":
                if d[x][y+1] > d[x][y] + 1:
                    d[x][y+1] = d[x][y] + 1
                    q.append([x,y+1])

        
        for i in range(H):
            for j in range(W):
                if d[i][j] != float("inf"):
                    ans = max(ans,d[i][j])

        #print (d)

print (ans)

Submission status: Accepted

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


def main():
    h, w = map(int, input().split())
    area = [input().strip() for _ in range(h)]
    index = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    maxc = 0
    for x in range(h):
        for y in range(w):
            if area[x][y] == '#':
                continue
            area_flag = [[False for j in range(w)] for i in range(h)]
            search_list = deque([[x, y, 0], ])
            area_flag[x][y] = True
            while len(search_list) > 0:
                nowx, nowy, nowc = search_list.pop()
                maxc = max(maxc, nowc)
                for ix, iy in index:
                    if 0 <= nowx+ix < h and 0 <= nowy+iy < w:
                        if area_flag[nowx+ix][nowy+iy] or area[nowx+ix][nowy+iy] == '#':
                            continue
                        else:
                            area_flag[nowx+ix][nowy+iy] = True
                            search_list.appendleft([nowx+ix, nowy+iy, nowc+1])
    print(maxc)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
q = collections.deque()
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        q.append((i, j))
        tmp = [[-1]*W for i in range(H)]
        tmp[i][j] = 0
        while(q):
            y, x = q.popleft()
            if y > 0 and tmp[y-1][x] < 0 and S[y-1][x] != "#":
                q.append((y-1, x))
                tmp[y-1][x] = tmp[y][x] + 1
                ans = max(ans, tmp[y-1][x])
            if y < H-1 and tmp[y+1][x] < 0 and S[y+1][x] != "#":
                q.append((y+1, x))
                tmp[y+1][x] = tmp[y][x] + 1
                ans = max(ans, tmp[y+1][x])
            if x > 0 and tmp[y][x-1] < 0 and S[y][x-1] != "#":
                q.append((y, x-1))
                tmp[y][x-1] = tmp[y][x] + 1
                ans = max(ans, tmp[y][x-1])
            if x < W - 1 and tmp[y][x+1] < 0 and S[y][x+1] != "#":
                q.append((y, x+1))
                tmp[y][x+1] = tmp[y][x] + 1
                ans = max(ans, tmp[y][x+1])
print(ans)

Submission status: Accepted

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

MAX = 0
for i in range(H):
    for j in range(W):
        s = [i,j]
        if S[i][j] == "#":
            continue
        dist = [[-1 for a in range(W)] for b in range(H)]
        
        dist[i][j] = 0
        de = deque([s])
        while de:
            d = de.popleft()
            h,w = d
            di = dist[h][w]
            if h > 0:
                if S[h-1][w] == "." and dist[h-1][w] < 0:
                    dist[h-1][w] = di+1
                    de.append([h-1,w])
            if h < H-1:
                if S[h+1][w] == "." and dist[h+1][w] < 0:
                    dist[h+1][w] = di+1
                    de.append([h+1,w])
            if w > 0:
                if S[h][w-1] == "." and dist[h][w-1] < 0:
                    dist[h][w-1] = di+1
                    de.append([h,w-1])
            if w < W-1:
                if S[h][w+1] == "." and dist[h][w+1] < 0:
                    dist[h][w+1] = di+1
                    de.append([h,w+1])
                    
        for h in range(H):
            for w in range(W):
                MAX = max(MAX,dist[h][w])
                
print(MAX)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]


def main():
    h,w = inpm()
    maze = []
    for _ in range(h):
        s = list(input())
        maze.append(s)
    ans = 0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    key = 0
    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '#':
                continue
            else:
                d = [[-1 for _ in range(w)] for _ in range(h)]
                que = []
                d[sx][sy] = 0
                que.append([sx,sy])
                M = 0
                while que:
                    [qx,qy]=que[0]
                    que.pop(0)
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append([nx,ny])
                ans = max(ans,M)
    print(ans)
 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#n = int(input())
h,w = [int(i) for i in readline().split()]
b = [input() for _ in range(h)]

dx4=[0, 1, 0,-1]
dy4=[1, 0,-1, 0]

from collections import deque


ans = 0
for sx in range(h):
    for sy in range(w):
        if b[sx][sy] == "#": continue
        
        c = 0    
        memo = [[-1]*w for _ in range(h)]
        q = deque()
        q.append((sx,sy)) #初期状態をキューに入れる
        memo[sx][sy] = 0 #初期状態を訪問済みにする
        while q: #キューが空になるまで
            x,y = q.popleft() #キューから情報を取り出す
            #(x,y)の各隣に対して処理-------------------------------------
            for i in range(4):
                nx = x + dx4[i]
                ny = y + dy4[i]
                #範囲外ならスキップ---------------------------------------------------
                if nx < 0 or nx>=h or ny <0 or ny>=w: continue
                #壁ならスキップ-------------------------------------------------------
                if b[nx][ny] == "#": continue
                #(nx,ny)が確認済みならスキップ----------------------------------------
                if memo[nx][ny] >= 0: continue
                #(nx,ny)が未確認のとき、確認済みにしてキューに入れる------------------
                memo[nx][ny] = memo[x][y]+1
                c = memo[x][y]+1
                q.append((nx,ny))

        if ans < c: ans = c

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Submit as pypy2


from __future__ import print_function, division, unicode_literals

__metaclass__ = type

try:
    input = raw_input
    range = xrange
except NameError:
    pass


import sys


# Test code requires python3
# from hypothesis import given
# from hypothesis import strategies as st
#
#
# def debug(*args, **kwargs):
#     print(*args, *('{}={}'.format(k, v) for k, v in kwargs.items()),
#           sep='; ', file=sys.stderr)


import itertools as it
from collections import deque


def main():
    H, W = map(int, input().split())
    S = [[x == '#' for x in input()] for _ in range(H)]
    ans = 0
    for s in it.product(range(H), range(W)):
        if S[s[0]][s[1]]:
            continue
        D = {s: 0}
        Q = deque([s])
        while Q:
            u = Q.popleft()
            for dr, dc in [(0, +1), (-1, 0), (0, -1), (+1, 0)]:
                v = (u[0] + dr, u[1] + dc)
                if not (0 <= v[0] < H and 0 <= v[1] < W) or S[v[0]][v[1]] or v in D:
                    continue
                D[v] = D[u] + 1
                ans = max(ans, D[v])
                Q.append(v)
    print(ans)


if __name__ == "__main__":
    main()