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: Wrong Answer

Solution code:
#%%
def dfs_deep_measure(st, h, w, reach):
    #木の深さを、各ノードに対して求める。
    deep = [[500] * w for _ in range(h)]
    check = [[0] * w for _ in range(h)]
    stack = [st]
    st_i, st_j = st[0], st[1]
    check[st_i][st_j] = 1
    deep[st_i][st_j] = 0
    while len(stack) > 0:
        tmp = stack.pop(0)
        tmp_i, tmp_j = tmp[0], tmp[1]
        tmp_list = reach[tmp_i][tmp_j]
        for i in range(len(tmp_list)):
            t_i, t_j = tmp_list[i][0], tmp_list[i][1]
            if check[t_i][t_j] != 1:
                stack.append((t_i, t_j))
                check[t_i][t_j] = 1
                for j in range(len(reach[t_i][t_j])):
                    ii = (reach[t_i][t_j])[j][0]
                    jj = (reach[t_i][t_j])[j][1]
                    deep[t_i][t_j] = min(deep[ii][jj]+1, deep[t_i][t_j])
    return deep


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

move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
reach = [[[] for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        for k in range(len(move)):
            if s[i][j] == '#':
                break
            x = i + move[k][0]
            y = j + move[k][1]
            if 0 <= x <= h-1 and 0 <= y <= w-1:
                if s[x][y] == '.':
                    reach[i][j].append((x, y))




ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            break
        tmp_deep = dfs_deep_measure((i, j), h, w, reach)
        #print(tmp_deep)
        for k in range(h):
            for l in range(w):
                if tmp_deep[k][l] != 500:
                    ans = max(ans, tmp_deep[k][l])


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

INF = float("inf")

XX = [1, -1, 0, 0]
YY = [0, 0, 1, -1]


def main():

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

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

    ans = 0
    for h in range(H):
        for w in range(W):
            # スタート位置 (h, w)
            # 距離
            dist = [[INF]*W for _ in range(H)]

            q = deque([(h, w, 0)])
            while len(q) > 0:
                y, x, p = q.popleft()
                # 上下左右に移動可能ならば、移動して更新する
                for dx, dy in zip(XX, YY):
                    if y + dy < 0 or y + dy >= H:
                        continue
                    if x + dx < 0 or x + dx >= W:
                        continue
                    if S[y+dy][x+dx] == "#":
                        continue
                    if p + 1 < dist[y+dy][x+dx]:
                        dist[y+dy][x+dx] = p+1
                        q.append((y+dy, x+dx, p+1))

            # 一番遠く
            toku = -1
            for i in range(H):
                for j in range(W):
                    if dist[i][j] != INF:
                        toku = max(dist[i][j], toku)
            ans = max(toku, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
    return edges


def main():
    H,W = map(int,input().split())
    ls = [list(input()) for _ in range(H)]
    for i in range(H):
        ls[i].insert(0,"#")
        ls[i].append("#")
    ls.append(["#" for _ in range(W+2)])
    ls.insert(0,["#" for _ in range(W+2)])
    graph = [[float("inf") for _ in range(H*W)] for _ in range(H*W)]

    for i in range(1,H+1):
        for j in range(1,W+1):
            if ls[i][j]==".":
                # ue
                if ls[i-1][j]==".":
                    graph[(i-1)*W+(j-1)][(i-2)*W+(j-1)] = 1
                    graph[(i-2)*W+(j-1)][(i-1)*W+(j-1)] = 1
                # migi
                if ls[i][j+1]==".":
                    graph[(i-1)*W+(j-1)][(i-1)*W+(j)] = 1
                    graph[(i-1)*W+(j)][(i-1)*W+(j-1)] = 1
                # sita
                if ls[i+1][j]==".":
                    graph[(i-1)*W+(j-1)][(i)*W+(j-1)] = 1
                    graph[(i)*W+(j-1)][(i-1)*W+(j-1)] = 1
                # hidari
                if ls[i][j-1]==".":
                    graph[(i-1)*W+(j-1)][(i-1)*W+(j-2)] = 1
                    graph[(i-1)*W+(j-2)][(i-1)*W+(j-1)] = 1
                else:
                    pass
    a = Warshall_Floyd(graph,H*W)
    for i in range(H*W):
        for j in range(H*W):
            if a[i][j]==float("inf"):
                a[i][j]=0
    mx = 0
    for i in a:
        mx = max(mx,max(i))
    print(mx)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(si, sj):
    q = deque()
    q.append([si, sj, 0])
    used = set([])
    ans = MAX_VALUE
    while len(q) > 0:
        prvi, prvj, d = q.popleft()
        for i, j in [[prvi-1, prvj], [prvi+1, prvj], [prvi, prvj-1], [prvi, prvj+1]]:
            if grid[j][i] == '#':
                ans = min(ans, d)
                continue
            elif (i,j) not in used:
                q.append([i,j,d+1])
                used.add((i,j))
    return d

H, W = map(int, input().split())
MAX_VALUE = H * W + 1
grid = ['#'*(W+2)] + [ '#' + input() + '#' for _ in range(H)] + ['#'*(W+2)]

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

Submission status: Wrong Answer

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


def main():
    H, W = [int(x) for x in input().split()]
    A = [["" for i in range(W)] for j in range(H)]

    for j in range(H):
        S = input().strip()
        for i, s in enumerate(list(S)):
            A[j][i] = s


    ma = 0

    dj = [1, 0, -1, 0]
    di = [0, 1, 0, -1]

    for sj in range(H):
        for si in range(W):
            d = [[-1] * W for i in range(H)]
            q = deque([])
            q.append((sj, si))
            d[sj][si] = 0

            while q:
                p = q.popleft()
                for i in range(4):
                    nj = p[0] + dj[i]
                    ni = p[1] + di[i]

                    if 0 <= nj < H and 0 <= ni < W and A[nj][ni] != "#" and d[nj][ni] == -1:
                        q.append((nj, ni))
                        d[nj][ni] = d[p[0]][p[1]] + 1

            for gj in range(H):
                for gi in range(W):
                    ma = max(ma, d[gj][gi])

    print(ma)





    


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split(' '))
table = [[c for c in input()] for _ in range(H)]

def dfs(i, j):
    dists = [[-1 for c in range(W)] for _ in range(H)]

    buf = [(i, j, 0)]
    while buf:
        buf2 = []
        for i, j, d in buf:
            if dists[i][j] != -1:
                continue

            else:
                dists[i][j] = d
                # if dists[i][j] == -1:
                #     dists[i][j] = d
                # else:
                #     dists[i][j] = min(dists[i][j], d)

                if 0 <= i-1 < H and table[i-1][j] == '.':
                    if dists[i-1][j] == -1:
                        buf2.append((i-1, j, d+1))

                if 0 <= i+1 < H and table[i+1][j] == '.':
                    if dists[i+1][j] == -1:
                        buf2.append((i+1, j, d+1))

                if 0 <= j-1 < W and table[i][j-1] == '.':
                    if dists[i][j-1] == -1:
                        buf2.append((i, j-1, d+1))

                if 0 <= j+1 < W and table[i][j+1] == '.':
                    if dists[i][j+1] == -1:
                        buf2.append((i, j+1, d+1))

        buf = buf2
        # print(buf)

    # for d in dists:
    #     print(d)

    return max(max(dists))

# print(table)

ans = 0
for i in range(H):
    for j in range(W):
        if table[i][j] == '.':
            n = dfs(i, j)
            ans = max(ans, n)


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
MEIJI = [[0] * W for i in range(H)]

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "#":
            MEIJI[i][j] = 1


def findStart():
    for x in range(H):
        for y in range(W):
            if MEIJI[x][y] == 0:
                return x, y

    return False


def bfs(H, W, sx, sy):
    d = [[-1] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque([])
    q.append((sx, sy))
    d[sx][sy] = 0

    mx = -1
    gx, gy = -1, -1
    while(len(q) != 0):
        x, y = q.popleft()

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

            if (0 <= nx and nx <= (H-1) and 0 <= ny and ny <= (W-1) and MEIJI[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx, ny))
                l = d[x][y] + 1
                d[nx][ny] = l

                if l > mx:
                    gx, gy = nx, ny
                    mx = l
    return d, gx, gy, mx


sx, sy = findStart()
_, x, y, _ = bfs(H, W, sx, sy)
_, _, _, l = bfs(H, W, x, y)

print(l)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
s = [input() for _ in range(h)]

if h==1 and w==1:
    print(0)
    exit()

def solve(sh,sw,gh,gw):
    if s[sh][sw]=="#" or s[gh][gw]=="#":
        return -1

    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sh][sw] = True
    q = [(sh,sw,0)]
    while len(q)>0:
        hi,wi,r = q.pop(0)
        for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
            if hi+dh>=0 and hi+dh<h and wi+dw>=0 and wi+dw<w and s[hi+dh][wi+dw]==".":
                if hi+dh==gh and wi+dw==gw:
                    return r+1
                elif not visited[hi+dh][wi+dw]:
                    visited[hi+dh][wi+dw] = True
                    q.append((hi+dh,wi+dw,r+1))

    return -1

d = set()
res = -1
for shi in range(h):
    for swi in range(w):
        for ghi in range(h):
            for gwi in range(w):
                if (shi,swi,ghi,gwi) in d:
                    continue
                r = solve(shi,swi,ghi,gwi)
                res = max(res, r)
                d.add((shi,swi,ghi,gwi))
                d.add((ghi,gwi,shi,swi))

print(res)

Submission status: Wrong Answer

Solution code:
import queue

class BreadthFirstSearch:
    def __init__(self, h, w, start_xy, board):
        self.h, self.w = h, w
        (self.sx, self.sy) = start_xy
        self.board = board
        self.hist = [[False] * w for i in range(h)]

    def get_step(self, wall="#"):
        '''
        区切り文字を指定する(デフォルトは#)
        ゴールに着くまでの最短距離を出力
        ゴールにたどり着かない場合は0を出力
        '''
        q = queue.Queue()
        q.put((self.sx, self.sy))
        step = 0
        count = 1
        next_count = 1
        ans = 0
        # キューが空になるまで
        while not q.empty():
            x, y = q.get()
            count -= 1
            if count == 0:
                step += 1
                count = next_count
                next_count = 0
            # ゴールにたどり着くまでのステップ
            for (i, j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                # 範囲内か
                if not(0 <= x+i <= w - 1) or not(0 <= y+j <= h - 1):
                    continue
                # 壁では無いか
                if self.board[y+j][x+i] == wall:
                    continue
                # 既に通ったところか
                if self.hist[y+j][x+i]:
                    continue
                # 通った印をつける
                self.hist[y+j][x+i] = True
                q.put((x+i, y+j))
                next_count += 1
        return step


# 図の形
h, w = map(int, input().split())
# ボードの読み込み
board = [[i for i in list(str(input()))] for i in range(h)]
# スタート地点
ans_ = []
for s_i in range(h):
    for s_j in range(w):
        if board[s_i][s_j] == "#":
            continue
        s_xy = (s_j, s_i)
        bfs = BreadthFirstSearch(h, w, s_xy, board[:])
        ans = bfs.get_step()
        if ans != 0:
            ans_.append(ans)

print(max(ans_) - 1)

Submission status: Wrong Answer

Solution code:
#幅優先探索


from queue import Queue

ans = 0
h,w = map(int, input().split())
maps = [input() for _ in range(h)]
for i in range(h):
  for j in range(w):
    visited = [[-1]*w for _ in range(h)]
    q = Queue()
    q.put([i,j])
    visited[i][j] = 0
    while not q.empty():
      y,x = q.get()
      for k,l in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0 <= y+k < h and 0<= x+l < w:
            new_y,new_x = y+k,x+l
        else: continue
        if visited[new_y][new_x]== -1 and maps[new_y][new_x]==".":
          visited[new_y][new_x]=visited[y][x]+1
          q.put([new_y,new_x])
        elif visited[new_y][new_x] > visited[y][x]+1:
          visited[new_y][new_x]=visited[y][x]+1
          q.put([new_y,new_x])
          
         
    for ii in range(h):
      for jj in range(w):
        ans = max(ans,visited[ii][jj])
        
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from itertools import product
def solve():
    H, W = map(int, input().split())
    M = []
    for i in range(H):
        S = list(int(x=='.') for x in input())
        M.append(S)

    Dist = [[1 if (M[h1][w1] == M[h2][w2] == 1) and (abs(h2-h1)+abs(w2-w1)==1) else float('inf') for h2,w2 in product(range(H), range(W))] for h1,w1 in product(range(H), range(W))]

    for h3,w3 in product(range(H), range(W)):
        for h1,w1 in product(range(H), range(W)):
            for h2,w2 in product(range(H), range(W)):
                Dist[h1*W+w1][h2*W+w2] = min(Dist[h1*W+w1][h2*W+w2], Dist[h1*W+w1][h3*W+w3] + Dist[h3*W+w3][h2*W+w2]);

    return str(max([x for d in Dist for x in d], key = lambda x: int(x) if x < float('inf') else -1))

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

Submission status: Wrong Answer

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

def bfs(q):
  x,y,cnt=q.get()
  if x<0 or x>=w or y<0 or y>=h:
    return
  elif S[y][x]=='#':
    return
  elif memo[y][x]<0:
    memo[y][x]=cnt
    q.put([x-1,y,cnt+1])
    q.put([x+1,y,cnt+1])
    q.put([x,y-1,cnt+1])
    q.put([x,y+1,cnt+1])
  else:
    return max(memo)

ans=0
for x in range(h):
  for y in range(w):
    q=Queue()
    q.put([x,y,0])

    memo=[[-1]*w for _ in range(h)]
    while not q.empty():
      tmp=bfs(q)
      try: ans=max(ans,max(tmp))
      except: TypeError
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict


def bfs():
    adjacent = [(1, 0), (0, 1), (-1, 0), (0, -1)]  # 遷移先を網羅する
    cnt = defaultdict(int)
    hoge = 0
    while len(q):
        cx, cy = q.popleft()  # 現在の位置
        for a, b in adjacent:
            if 0 > cx+a or 0 > cy+b:
                continue
            if abs(cx+a) >= H or abs(cy+b) >= W:
                continue
            if visited[cx+a][cy+b]:
                continue
            if gridgraph[cx+a][cy+b] == "#":
                continue
            cnt[(cx+a, cy+b)] = cnt[(cx, cy)] + 1
            hoge = max(hoge, cnt[(cx+a, cy+b)])
            q.append((cx+a, cy+b))
            visited[cx+a][cy+b] = True
    return hoge


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

ans = 0
for i in range(H):
    for j in range(W):
        visited = [[False]*W for _ in range(H)]
        tmp = 0
        # 開始位置がi, j
        q = deque()
        q.append((i, j))
        visited[i][j] = True
        ans = max(ans, bfs())

print(ans)

Submission status: Wrong Answer

Solution code:
#%%
def dfs_deep_measure(st, h, w, reach):
    #木の深さを、各ノードに対して求める。
    deep = [[500] * w for _ in range(h)]
    check = [[0] * w for _ in range(h)]
    stack = [st]
    st_i, st_j = st[0], st[1]
    check[st_i][st_j] = 1
    deep[st_i][st_j] = 0
    while len(stack) > 0:
        tmp = stack.pop(0)
        tmp_i, tmp_j = tmp[0], tmp[1]
        tmp_list = reach[tmp_i][tmp_j]
        for i in range(len(tmp_list)):
            t_i, t_j = tmp_list[i][0], tmp_list[i][1]
            if check[t_i][t_j] != 1:
                stack.append((t_i, t_j))
                check[t_i][t_j] = 1
                deep[t_i][t_j] = min(deep[tmp_i][tmp_j]+1, deep[t_i][t_j])
    return deep


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

move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
reach = [[[] for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        for k in range(len(move)):
            if s[i][j] == '#':
                break
            x = i + move[k][0]
            y = j + move[k][1]
            if 0 <= x <= h-1 and 0 <= y <= w-1:
                if s[x][y] == '.':
                    reach[i][j].append((x, y))




ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            break
        tmp_deep = dfs_deep_measure((i, j), h, w, reach)
        #print(tmp_deep)
        for k in range(h):
            for l in range(w):
                if tmp_deep[k][l] != 500:
                    ans = max(ans, tmp_deep[k][l])


print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import queue

row, col = map(int, input().split(' '))
maze = [list(input()) for _ in range(row)]

                
def BPS(si, sj):
    global done
    done = [[0 for _ in range(col)] for _ in range(row)]
    q = queue.Queue()
    q.put((si, sj, 0))
    around = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    maxv = 0
    while not q.empty():
        i, j, cnt = q.get()
        done[i][j] = 1
        for ar in around:
            di, dj = ar[0], ar[1]
            i_n, j_n = i + di, j + dj
            if (i_n >= 0 and i_n < row and j_n >= 0 and j_n < col) == False:
                continue
            if maze[i_n][j_n] == '#':
                continue
            if done[i_n][j_n] == 1:
                continue
            if done[i_n][j_n] == 2:
                continue
            maxv = max(maxv, cnt + 1)
            q.put((i_n, j_n, cnt + 1))
            done[i_n][j_n] = 2
        
    return maxv
            
            
def main():        
    maxv = 0
    for i in range(row):
        for j in range(col):
            maxv = max(maxv, BPS(i,j))
    print(maxv)
                    
                
                    
    
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
# from heapq import *
# import functools
# import itertools
# import math
INF = 500000
mod = 10**9+7

import sys
from collections import *
INF = 500000
mod = 10**9+7

H, W = map(int, input().split())
f = [input() for i in range(H)]
es = defaultdict(lambda : INF)
for i in range(H):
    for j in range(W-1):
        if f[i][j] == '.' and f[i][j+1] == '.':
            es[(i, j, i, j+1)] = 1
            es[(i, j+1, i, j)] = 1
for i in range(H-1):
    for j in range(W):
        if f[i][j] == '.' and f[i+1][j] == '.':
            es[(i, j, i+1, j)] = 1
            es[(i+1, j, i, j)] = 1
V = []
for i in range(H):
    for j in range(W):
        if f[i][j] == '.':
            es[((i, j), (i, j))] = 0
            V.append((i, j))
for u, v in V:
    for a, b in V:
        for c, d in V:
            tmp = es[(a, b, u, v)] + es[(u, v, c, d)]
            if tmp < es[(a, b, c, d)]:
                es[(a, b, c, d)] = tmp
ans = 0
for a, b in V:
    for c, d in V:
        if ans < es[(a, b, c, d)]:
            ans = es[(a, b, c, d)]
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
s = [input() for _ in range(h)]

if h==1 and w==1:
    print(0)
    exit()

def solve(sh,sw,gh,gw):
    if s[sh][sw]=="#" or s[gh][gw]=="#":
        return -1

    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sh][sw] = True
    q = [(sh,sw,0)]
    while len(q)>0:
        hi,wi,r = q.pop(0)
        for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
            if hi+dh>=0 and hi+dh<h and wi+dw>=0 and wi+dw<w and s[hi+dh][wi+dw]==".":
                if hi+dh==gh and wi+dw==gw:
                    return r+1
                elif not visited[hi+dh][wi+dw]:
                    visited[hi+dh][wi+dw] = True
                    q.append((hi+dh,wi+dw,r+1))

    return -1

d = set()
res = -1
for shi in range(h):
    for swi in range(w):
        for ghi in range(h):
            for gwi in range(w):
                if (shi,swi,ghi,gwi) in d:
                    continue
                r = solve(shi,swi,ghi,gwi)
                if r==w+h-2:
                    print(r)
                    exit()
                res = max(res, r)
                d.add((shi,swi,ghi,gwi))
                d.add((ghi,gwi,shi,swi))

print(res)

Submission status: Wrong Answer

Solution code:
def dijkstra(g,st):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1]))
    return dist

h,w=map(int,input().split())
field=[[]for i in range(h)]
num=0
st=-1
for i in range(h):
    s=input()
    for j in range(w):
        field[i].append((s[j],num))
        if s[j]=='.' and st==-1:
            st=num
        num+=1
dx=[1,0,-1,0]
dy=[0,1,0,-1]

g=[[]for i in range(h*w)]
for i in range(h):
    for j in range(w):
        if field[i][j][0]!='.':
            continue
        for x,y in zip(dx,dy):
            if 0<=i+x<h and 0<=j+y<w and field[i+x][j+y][0]!='#':
                g[field[i][j][1]].append((1,field[i+x][j+y][1]))
mx=(0,-1)
dd=dijkstra(g,st)
for i in range(len(dd)):
    if dd[i]!=10**18 and dd[i]>mx[0]:
        mx=(dd[i],i)
dl=[]
for i in range(len(dd)):
    if dd[i]==mx[0]:
        dl.append(i)
        
mxx=0
for e in dl:
    for ans in dijkstra(g,e):
        if ans!=10**18:
            mxx=max(mxx,ans)
print(mxx)

Submission status: Wrong Answer

Solution code:
import copy

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

def solve(start):
	flg = copy.deepcopy(flg_orig)
	q = [start]
	cnt = 0
	while q != []:
		cx, cy, cd  = q.pop(0)
		flg[cx][cy] = 1
		nps = [[cx+1,cy],[cx-1,cy],[cx,cy+1],[cx,cy-1]]
		for nx,ny in nps:
			if not (0 <= nx < H and 0 <= ny < W):
				continue
			if flg[nx][ny] == 1:
				continue
			else:
				flg[nx][ny] = 1

			q.append([nx,ny,cd+1])
			cnt = max(cnt, cd+1)
	return cnt


flg_orig = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
	for j in range(W):
		if S[i][j] == "#":
			flg_orig[i][j] = 1


ans = 0
for start_x in range(H):
	for start_y in range(W):
		start = [start_x, start_y, 0]
		tmp_cnt = solve(start)
		ans = max(ans, tmp_cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math
from collections import deque

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

I_MIN = 0
I_MAX = 0
J_MIN = 0
J_MAX = 0
I_DELTA = [1, 0, -1, 0]
J_DELTA = [0, -1, 0, 1]
visited_set = set()
grid = None


def resolve():
    global visited_set, I_MAX, J_MAX, grid

    H, W = [int(x) for x in sys.stdin.readline().split()]
    grid = [list(sys.stdin.readline().split()[0]) for _ in range(H)]

    # logger.debug('{}'.format([H, W, grid]))

    I_MAX = H - 1
    J_MAX = W - 1
    queue = deque()

    max_dist = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '.':
                queue.append((i, j, 0))
                while (len(queue) > 0):
                    i, j, dist = queue.popleft()
                    if max_dist < dist:
                        max_dist = dist
                    for d in range(4):
                        i_next = i + I_DELTA[d]
                        j_next = j + J_DELTA[d]
                        if (
                                i_next, j_next
                        ) not in visited_set and I_MIN <= i_next <= I_MAX and J_MIN <= j_next <= J_MAX:
                            visited_set.add((i_next, j_next))
                            s = grid[i_next][j_next]
                            if s == '.':
                                queue.append((i_next, j_next, dist + 1))
                else:
                    visited_set.clear()
    print(max_dist)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
...
...
..."""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 5
...#.
.#.#.
.#..."""
        output = """10"""
        self.assertIO(input, output)

Submission status: Wrong Answer

Solution code:
def dijkstra(g,st):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st))
    while que:
        c,v=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1]))
    return dist

h,w=map(int,input().split())
field=[[]for i in range(h)]
num=0
st=-1
for i in range(h):
    s=input()
    for j in range(w):
        field[i].append((s[j],num))
        if s[j]=='.' and st==-1:
            st=num
        num+=1
dx=[1,0,-1,0]
dy=[0,1,0,-1]

g=[[]for i in range(h*w)]
for i in range(h):
    for j in range(w):
        if field[i][j][0]!='.':
            continue
        for x,y in zip(dx,dy):
            if 0<=i+x<h and 0<=j+y<w and field[i+x][j+y][0]!='#':
                g[field[i][j][1]].append((1,field[i+x][j+y][1]))
mx=(-1,-1)
dd=dijkstra(g,st)
for i in range(len(dd)):
    if dd[i]!=10**18 and dd[i]>mx[0]:
        mx=(dd[i],i)
dl=[]
for i in range(len(dd)):
    if dd[i]==mx[0]:
        dl.append(i)
        
mxx=-1
for e in dl:
    for ans in dijkstra(g,e):
        if ans!=10**18:
            mxx=max(mxx,ans)
print(mxx)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sheet = [[0]*(W+2) for i in range(H+2)]
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]=='.':
      sheet[i+1][j+1] = 1

m = -1
for i in range(1, H+1):
  for j in range(1, W+1):
    for a in range(1, H+1):
      for b in range(1, W+1):    
        stuck = deque([(j, i, 0)])
        log = [[10**5]*(W+2) for i in range(H+2)]
        log[i][j] = 0
        while stuck:
          x, y, c = stuck.popleft()
          if x==b and y==a:
            if m<c:
              m=c
            break
          for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
              if sheet[y+dy][x+dx]==1 and log[y+dy][x+dx]>c+1:
                log[y+dy][x+dx] = c+1
                stuck += [(x+dx, y+dy, c+1)]
print(m)

Submission status: Wrong Answer

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

import sys

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

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

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

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

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

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