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

def main():
    H,W=map(int,input().split())
    S=[]
    for i in range(H):
        s=input()
        S.append(s)

    G=[]
    for i in range(H):
        for j in range(W):
            tmp=[]
            if S[i][j]=="#":
                G.append(tmp)
                continue
            if i-1>=0:
                if S[i-1][j]==".":
                    tmp.append((i-1)*W+j)
            if i+1<=H-1:
                if S[i+1][j]==".":
                    tmp.append((i+1)*W+j)
            if j-1>=0:
                if S[i][j-1]==".":
                    tmp.append(i*W+j-1)
            if j+1<=W-1:
                if S[i][j+1]==".":
                    tmp.append(i*W+j+1)
            G.append(tmp)

    res=0

    for start in range(H*W):
        dist = 0
        v = [-1 for _ in range(H * W)]
        que=deque([])
        que.append(start)
        v[start]=dist
        while len(que)>0:
            next_index=que.popleft()
            next=G[next_index]
            for i in next:
                if v[i]==-1:
                    que.append(i)
                    v[i]=v[next_index]+1

        if max(v)>=res:
            res=max(v)

    print(res)


if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def main():
    h, w = map(int, input().split())
    maze = [input() for i in range(h)]
    # 行ったかどうかのフラグ
    visited = [[-1]*w for j in range(h)]
    start_yx = []
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                sy = i
                sx = j
                start_yx .append([sy, sx])

    # 移動パターン
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    ans = 0
    for sy, sx in start_yx :
        visited = [[-1]*w for j in range(h)]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        while q:
            y, x = q.popleft()
            ans = max(ans, visited[y][x])
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                else:
                    continue
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    field = "#"*(W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#"*(W+2)

    INF = 10**9
    cost = [INF]*len(field)
    move = [-1, 1, -(W+2), W+2]
    def bfs(s, g):
        q = deque()
        dequeue = q.popleft
        enqueue = q.append
        cost[s] = 0
        enqueue(s)

        while q:
            now = dequeue()
            now_cost = cost[now]
            for dx in move:
                nv = now + dx
                if nv == g:
                    cost[g] = now_cost + 1
                    return
                if field[nv] == "#" or cost[nv] < INF:
                    continue
                else:
                    cost[nv] = now_cost + 1
                    q.append(nv)
    
    ans = 0
    for si in range(H):
        for sj in range(W):
            for gi in range(H):
                for gj in range(W):
                    start = (si+1)*(W+2)+sj+1
                    goal = (gi+1)*(W+2)+gj+1
                    if field[start] == "#" or  field[goal] == "#" or start == goal:
                        continue
                    cost = [INF] * len(field)
                    bfs(start, goal)
                    ans = max(ans, cost[goal])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

H,W = map(int,input().split())
S = [input().rstrip() for _ in range(H)]
ans = 0
for hi in range(H):
    for wi in range(W):
        flag = 0
        if S[hi][wi] =='.':
            flag = 1
            tmp = [hi,wi]
    
            cost = [[-1]*W for _ in range(H)]
            q = collections.deque([tmp])
            cost[tmp[0]][tmp[1]] = 0
            while q:
                now = q.popleft()
                if 0<= now[0]+1 < H:
                    if cost[now[0]+1][now[1]] == -1 and S[now[0]+1][now[1]] =='.':
                        cost[now[0]+1][now[1]] = cost[now[0]][now[1]] +1
                        q.append([now[0]+1,now[1]])

                if 0<= now[0]-1 < H:
                    if cost[now[0]-1][now[1]] == -1 and S[now[0]-1][now[1]] =='.':
                        cost[now[0]-1][now[1]] = cost[now[0]][now[1]] +1
                        q.append([now[0]-1,now[1]])

                if 0<=now[1]+1 < W:
                    if cost[now[0]][now[1]+1] == -1 and S[now[0]][now[1]+1] =='.':
                        cost[now[0]][now[1]+1] = cost[now[0]][now[1]] +1
                        q.append([now[0],now[1]+1])

                if 0<=now[1]-1 < W:
                    if cost[now[0]][now[1]-1] == -1 and S[now[0]][now[1]-1] =='.':
                        cost[now[0]][now[1]-1] = cost[now[0]][now[1]] +1
                        q.append([now[0],now[1]-1])

            ans = max(ans,cost[now[0]][now[1]])

            cost = [[-1]*W for _ in range(H)]
            q = collections.deque([tmp])
            cost[now[0]][now[1]] = 0
            while q:
                now = q.popleft()
                if 0<= now[0]+1 < H:
                    if cost[now[0]+1][now[1]] == -1 and S[now[0]+1][now[1]] =='.':
                        cost[now[0]+1][now[1]] = cost[now[0]][now[1]] +1
                        q.append([now[0]+1,now[1]])

                if 0<= now[0]-1 < H:
                    if cost[now[0]-1][now[1]] == -1 and S[now[0]-1][now[1]] =='.':
                        cost[now[0]-1][now[1]] = cost[now[0]][now[1]] +1
                        q.append([now[0]-1,now[1]])

                if 0<=now[1]+1 < W:
                    if cost[now[0]][now[1]+1] == -1 and S[now[0]][now[1]+1] =='.':
                        cost[now[0]][now[1]+1] = cost[now[0]][now[1]] +1
                        q.append([now[0],now[1]+1])

                if 0<=now[1]-1 < W:
                    if cost[now[0]][now[1]-1] == -1 and S[now[0]][now[1]-1] =='.':
                        cost[now[0]][now[1]-1] = cost[now[0]][now[1]] +1
                        q.append([now[0],now[1]-1])
            
    if flag == 1:
        ans = max(ans,cost[now[0]][now[1]])
        
print(ans)

Submission status: Accepted

Solution code:
h,w = list(map(int,input().split()))
h += 2
w += 2
grid = '#'*w
for _ in range(h-2):
    grid += '#' + input() + '#'
grid += '#'*w

from collections import deque
ans = 0
for i in range(len(grid)):
    INF = 10**9
    dist = [INF]*(h*w)
    if grid[i]=='#':
        continue
    dist[i] = 0
    q = deque([i])
    while q:
        v = q.popleft()
        dv = dist[v]
        for m in (-1,1,w,-w):
            move = v + m
            if grid[move]=='#':
                continue
            dmove = dv + 1
            if dmove >= dist[move]:
                continue
            dist[move] = dmove
            q.append(move)
    # print([dist[i] if dist[i]!=INF else 0 for i in range(len(dist))])
    ans = max(ans, max([dist[i] if dist[i]!=INF else 0 for i in range(len(dist))]))
    # print(ans)
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
           
def bfs(sx, sy):
    q = deque([])
    d = [[-1 for _ in range(W)] for _ in range(H)]
    q.append([sx, sy])
    d[sx][sy] = 0
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < H and ny >= 0 and ny < W:
                if s[nx][ny] != "#" and d[nx][ny] == -1:
                    q.append([nx, ny])
                    d[nx][ny] = d[x][y] + 1
    return d

def max_dim2(d):
    ret = 0
    for i in range(len(d)):
        for j in d[i]:
            ret = max(ret, j)
    return ret

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

Submission status: Accepted

Solution code:
# sr,sc,gr,gcの総当りでTLEした
# goalは各startに対して最も遠い地点とすればよい

def main():
    from collections import deque

    dd = 0, 1, 0, -1

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

    def dist(sr, sc):
        if G[sr][sc] == '#':
            return -1

        memo = [[-1] * W for _ in range(H)]

        dq = deque()
        dq.append((sr, sc, 0))
        memo[sr][sc] = 0
        while dq:
            r, c, d = dq.popleft()
            nd = d + 1
            for i in range(4):
                nr = r + dd[i]
                nc = c + dd[i ^ 1]
                if not (0 <= nr < H and 0 <= nc < W):
                    continue
                if ~memo[nr][nc]:
                    continue
                if G[nr][nc] == '#':
                    continue
                dq.append((nr, nc, nd))
                memo[nr][nc] = nd

        return d

    ans = 0
    for sr in range(H):
        for sc in range(W):
            ans = max(ans, dist(sr, sc))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

s = []

for i in range(h):
    s.append(list(input()))


def bfs(x, y):
    if s[y][x] == '#':
        return 0

    queue = deque()
    queue.appendleft([x, y])
    visited = dict()
    visited[(x, y)] = 0

    while queue:
        nx, ny = queue.pop()
        cur = visited[(nx, ny)]

        if nx - 1 >= 0 and (nx - 1, ny) not in visited:
            if s[ny][nx - 1] == '.':
                visited[(nx - 1, ny)] = cur + 1
                queue.appendleft((nx - 1, ny))

        if nx + 1 < w and (nx + 1, ny) not in visited:
            if s[ny][nx + 1] == '.':
                visited[(nx + 1, ny)] = cur + 1
                queue.appendleft((nx + 1, ny))

        if ny - 1 >= 0 and (nx, ny - 1) not in visited:
            if s[ny - 1][nx] == '.':
                visited[(nx, ny - 1)] = cur + 1
                queue.appendleft((nx, ny - 1))

        if ny + 1 < h and (nx, ny + 1) not in visited:
            if s[ny + 1][nx] == '.':
                visited[(nx, ny + 1)] = cur + 1
                queue.appendleft((nx, ny + 1))

    return max(visited.values())


result = 0
for i in range(h):
    for j in range(w):
        r = bfs(j, i)
        result = max(result, r)

print(result)

Submission status: Accepted

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


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    is_visited[start[0]][start[1]] = 1

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (is_visited[next_h][next_w] == 1) or \
           M[next_h][next_w] == '#':
           # (dist[next_h][next_w] != float('inf')) or \
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        is_visited[next_h][next_w] = 1

        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

Submission status: Accepted

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


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      # is_visited[now_h][now_w] = 1
      is_visited[now_h][now_w] = float('inf')
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '#':
           # (is_visited[next_h][next_w] == float('inf')) or \
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

Submission status: Accepted

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


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '#':
           # is_visited[next_h][next_w] or \
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

Submission status: Accepted

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


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '#':
          continue

        # temp = dist[now_h][now_w] + 1
        # dist[next_h][next_w] = temp
        # if max_ < temp:
        #   max_ = temp
        dist[next_h][next_w] = dist[now_h][now_w] + 1
        max_ = max(max_, dist[next_h][next_w])
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

Submission status: Accepted

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


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '#':
          continue

        temp = dist[now_h][now_w] + 1
        dist[next_h][next_w] = temp
        if max_ < temp:
          max_ = temp
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

Submission status: Accepted

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


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '#':
          continue

        temp = dist[now_h][now_w] + 1
        dist[next_h][next_w] = temp
        if max_ < temp:
          max_ = temp
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int, input().split())
hw = [input() for _ in range(h)]

def bfs(s):
    que = deque([s])
    m = [[-1]*w for _ in range(h)]
    sh, sw = s
    m[sh][sw] = 0
    ret = 0
    while que:
        now_h, now_w = que.popleft()
        for dh, dw in [(1,0), (-1,0), (0,-1), (0,1)]:
            nh = now_h + dh
            nw = now_w + dw
            if not (0<=nh<h and 0<=nw<w) or m[nh][nw] != -1 or hw[nh][nw] == '#':
                continue
            m[nh][nw] = m[now_h][now_w] + 1
            que.append((nh,nw))
            ret = max(ret, m[now_h][now_w] + 1)
    return ret

ans = 0
for y in range(h):
    for x in range(w):
        if hw[y][x] == '#':
            continue
        s = (y, x)
        ans = max(bfs(s), ans)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def BFS(s):
  q = deque()
  q.append(s)
  dist = [[10**10]*(W+2) for _ in range(H+2)]
  dist[s[0]][s[1]] = 0
  d = ((0,1),(0,-1),(1,0),(-1,0))
  far = []
  
  while len(q)>0:
    i,j = q.popleft()
    for di,dj in d:
      if field[i+di][j+dj] == "." and dist[i+di][j+dj] == 10**10:
        q.append([i+di,j+dj])
        dist[i+di][j+dj] = dist[i][j]+1
    res = dist[i][j]
  
  return res



H,W = map(int,input().split())
field = ["#"*(W+2)]
field += ["#"+input()+"#" for _ in range(H)]
field += ["#"*(W+2)]
res = 0

for i in range(H+2):
  for j in range(W+2):
    if field[i][j] == ".":
      s = [i,j]
      res = max(res,BFS(s))
      
print(res)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
from itertools import combinations_with_replacement, product
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    ans = 0
    for H, W in product(range(h), range(w)):
        if s[H][W] == '#':
            continue
        s2 = deepcopy(s)
        s2[H][W] = 0
        d = deque()
        d.append([H, W])
        while d:
            Hn,Wn = d.popleft()
            for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
                if ((0 <= Hn+i < h) and (0 <= Wn+j < w)):
                    
                    if s2[Hn+i][Wn+j] != '.':
                        continue
                    s2[Hn+i][Wn+j] = s2[Hn][Wn] + 1
                    d.append([Hn+i, Wn+j])
                    if ans < s2[Hn+i][Wn+j]:
                        ans = s2[Hn+i][Wn+j]
        del s2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

queue = []
visited = []
visited = [[0 for _ in range(W)] for _ in range(H)]
ans = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            queue.append([i,j])
            visited[i][j] = 1

            while len(queue) > 0:
                now_y, now_x = map(int,queue.pop(0))
                for next_x, next_y in [(1,0),(0,1),(-1,0),(0,-1)]:
                    y = now_y + next_y
                    x = now_x + next_x
                    if 0 <= y < H and 0 <= x < W:
                        if maze[y][x] != '#' and visited[y][x] == 0:
                            visited[y][x] = visited[now_y][now_x] + 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 _ in range(W)] for _ in range(H)]



print(ans-1)

Submission status: Accepted

Solution code:
from collections import deque
INFTY = 10**3
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
cmax = 0
for x in range(H):
    for y in range(W):
        if S[x][y]==".":
            A = [[INFTY for _ in range(W)] for _ in range(H)]
            hist = {(i,j):0 for i in range(H) for j in range(W)}
            que = deque([(x,y,0)])
            A[x][y] = 0
            hist[(x,y)] = 1
            while que:
                i,j,d = que.popleft()
                if j+1<W and S[i][j+1]=="." and hist[(i,j+1)]==0:
                    A[i][j+1]=d+1
                    hist[(i,j+1)]=1
                    que.append((i,j+1,d+1))
                if i-1>=0 and S[i-1][j]=="." and hist[(i-1,j)]==0:
                    A[i-1][j]=d+1
                    hist[(i-1,j)]=1
                    que.append((i-1,j,d+1))
                if j-1>=0 and S[i][j-1]=="." and hist[(i,j-1)]==0:
                    A[i][j-1]=d+1
                    hist[(i,j-1)]=1
                    que.append((i,j-1,d+1))
                if i+1<H and S[i+1][j]=="." and hist[(i+1,j)]==0:
                    A[i+1][j]=d+1
                    hist[(i+1,j)]=1
                    que.append((i+1,j,d+1))
            cnt=0
            for i in range(H):
                for j in range(W):
                    if S[i][j]==".":
                        cnt = max(cnt,A[i][j])
            cmax = max(cmax,cnt)
print(cmax)

Submission status: Accepted

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

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]=="#":continue
    sh=i
    sw=j
    visited=[[-1]*w for _ in range(h)]
    ans=max(ans,bfs(sh,sw))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

t_max = 0
for i in range(H):
    for j in range(W):
        step = [[0]*W for _ in range(H)]
        visited = [[False]*W for _ in range(H)]
        queue = deque([(i, j)])
        while queue:
            x, y = queue.popleft()
            if maze[x][y] == "#":
                continue
            if visited[x][y]:
                continue
            for dx, dy in XY:
                nx = x + dx
                ny = y + dy
                if 0 <= nx <= H-1 and 0 <= ny <= W-1:
                    step[nx][ny] = step[x][y] + 1
                    queue.append((nx, ny))
                    t_max = max(t_max, step[nx][ny])
            visited[x][y] = True

print(t_max-1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[]
import heapq
INF=10**9
def Dijkstra(graph, start):
  dist=[INF]*len(graph)
  parent=[INF]*len(graph)
  queue=[(0, start)]
  while queue:
    path_len, v=heapq.heappop(queue)
    if dist[v]==INF: 
      dist[v]=path_len
      for w in graph[v]:
        if dist[w[0]]==INF:
          parent[w[0]]=v
          heapq.heappush(queue, (dist[v]+w[1], w[0]))         
  return (dist,parent)
for i in range(h):
  a=input()
  s.append(a)
graph=[]
ans=0
for i in range(h):
  for j in range(w):
    graph.append([])
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      if i>0 and s[i-1][j]=='.':
        graph[i*w+j].append([(i-1)*w+j,1])
      if i<h-1 and s[i+1][j]=='.':
        graph[i*w+j].append([(i+1)*w+j,1])
      if j>0 and s[i][j-1]=='.':
        graph[i*w+j].append([i*w+j-1,1])
      if j<w-1 and s[i][j+1]=='.':
        graph[i*w+j].append([i*w+j+1,1])
for i in range(h):
  for j in range(w):
    if s[i][j]=='.':
      a,b=Dijkstra(graph,i*w+j)
      for k in range(h):
        for l in range(w):
          if a[k*w+l]!=INF:
            ans=max(ans,a[k*w+l])
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
from collections import deque
query = [list(input()) for _ in range(H)]
dirc = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def bfs(start):
    Q = deque([start])
    checked = [[0]*W for _ in range(H)]
    checked[start[0]][start[1]] = 1
    dist = [[0]*W for _ in range(H)]
    ret = 0
    while Q:
        y, x = Q.popleft()
        ret = max(ret, dist[y][x])
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny>=H or ny<0 or nx>=W or nx<0: continue
            if query[ny][nx]=='#': continue
            if checked[ny][nx]: continue
            checked[ny][nx] = 1
            dist[ny][nx] = dist[y][x]+1
            Q.append((ny, nx))
    return ret

ans = 0
for h in range(H):
    for w in range(W):
        if query[h][w]=='#': continue
        ans = max(ans, bfs((h, w)))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
INF = 10**5
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            continue
        q = deque([(i, j)])
        dist = [[INF]*w for _ in range(h)]
        dist[i][j] = 0
        while q:
            y, x = q.popleft()
            for dx, dy in dxdy:
                if not (0<=x+dx<w and 0<=y+dy<h):
                    continue
                if s[y+dy][x+dx]=='#' or dist[y+dy][x+dx]<INF:
                    continue
                dist[y+dy][x+dx] = dist[y][x] + 1
                q.append((y+dy, x+dx))
        for row in dist:
            for ele in row:
                if ele==INF:
                    continue
                ans = max(ans, ele)
print(ans)

Submission status: Accepted

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

dp = [[10**6]*(H*W) for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        p = W*i+j
        if i > 0 and S[i-1][j] == ".":
            dp[p][p-W] = 1
            dp[p-W][p] = 1
        if i < H-1 and S[i+1][j] == ".":
            dp[p][p+W] = 1
            dp[p+W][p] = 1
        if j > 0 and S[i][j-1] == ".":
            dp[p][p-1] = 1
            dp[p-1][p] = 1
        if j < W-1 and S[i][j+1] == ".":
            dp[p][p+1] = 1
            dp[p+1][p] = 1

for i in range(H*W):
    dp[i][i] = 0
for k in range(H*W):
    for i in range(H*W):
        for j in range(H*W):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dp[i][j] == 10**6:
            continue
        ans = max(ans, dp[i][j])
            
print(ans)

Submission status: Accepted

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

def bfs(sy, sx):
    mx=0
    q=Queue()
    dist=[[-1]*W for _ in range(H)]
    q.put((sy,sx))
    dist[sy][sx]=0
    while not q.empty():
        y, x=q.get()
        y_nxt=[y+1, y-1, y, y]
        x_nxt=[x, x, x+1, x-1]
        for Y,X in zip(y_nxt, x_nxt):
            if not (0 <= Y < H) or not (0 <= X < W) or S[Y][X]=="#":
                continue
            if dist[Y][X]==-1:
                dist[Y][X]=dist[y][x]+1
                q.put((Y, X))
                mx=max(mx, dist[Y][X])
    return mx

mx=0
for y in range(H):
    for x in range(W):
        if S[y][x]=="#":
            continue
        else:
            mx=max(bfs(y,x),mx)

print(mx)