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:
from collections import deque

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

d=[[-1 for j in range(W)] for i in range(H)]
f=False
for i in range(H):
    if f:
        break
    for j in range(W):
        if S[i][j]:
            si,sj=i,j
            f=True
            break
# print((si,sj))
q=deque()
q.append((si,sj));d[si][sj]=0
while q:
    ui,uj=q.popleft()    
    for vi,vj in [(ui-1,uj),(ui+1,uj),(ui,uj-1),(ui,uj+1)]:
        # print(q)     
        if 0<=vi<H and 0<=vj<W and d[vi][vj]==-1 and S[vi][vj] :
            q.append((vi,vj));d[vi][vj]=d[ui][uj]+1
for i in range(H):
    for j in range(W):
        if d[si][sj]<d[i][j]:
            si,sj=i,j
'''
for Si in S:
    print(Si)
for di in d:
    print(di)
'''
d=[[-1 for j in range(W)] for i in range(H)]
# print(si,sj)
q.append((si,sj));d[si][sj]=0
while q:
    ui,uj=q.popleft()    
    for vi,vj in [(ui-1,uj),(ui+1,uj),(ui,uj-1),(ui,uj+1)]:
        # print(q)     
        if 0<=vi<H and 0<=vj<W and d[vi][vj]==-1 and S[vi][vj] :
            q.append((vi,vj));d[vi][vj]=d[ui][uj]+1
for i in range(H):
    for j in range(W):
        if d[si][sj]<d[i][j]:
            si,sj=i,j
'''
for Si in S:
    print(Si)
for di in d:
    print(di)
'''
ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,d[i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
def meiro(sx,sy,gx,gy):
    num = [[-1] * w for i in range(h)]
    num[sx][sy] = 0
    now = {(sx,sy)}
    for i in range(1,50):
        tmp = set()
        for x,y in now:
            if x > 0:
                if lis[x-1][y] == "." and num[x-1][y] == -1:
                    num[x-1][y] = i
                    tmp.add((x-1,y))
            if x < h-1:
                if lis[x+1][y] == "." and num[x+1][y] == -1:
                    num[x+1][y] = i
                    tmp.add((x+1,y))
            if y > 0:
                if lis[x][y-1] == "." and num[x][y-1] == -1:
                    num[x][y-1] = i
                    tmp.add((x,y-1))
            if y < w-1:
                if lis[x][y+1] == "." and num[x][y+1] == -1:
                    num[x][y+1] = i
                    tmp.add((x,y+1))
        now = tmp
    return num[gx][gy]

h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = 0
for sx in range(h):
    for sy in range(w):
      for gx in range(h):
          for gy in range(w):
              ans = max(ans,meiro(sx,sy,gx,gy))
print(ans)

Submission status: Wrong Answer

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

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

def check():
  for y in range(H):
    for x in range(W):
      m = M[y][x]
      if m == ".":
        return x,y

st_x,st_y = check()

went = {(st_x,st_y):0}
q = [(st_x,st_y)]
idx = 0
while idx<len(q):
  x,y = q[idx]
  for dx,dy in [(0,-1),(0,1),(-1,0),(1,0)]:
    if (x+dx, y+dy) not in went.keys()  and 0<=x+dx<W and 0<= y+dy<H and M[y+dy][x+dx] == ".":
      q.append((x+dx,y+dy))
      went[(x+dx,y+dy)]=went[(x,y)]+1
  idx+=1

went = {(x,y):0}
q = [(x,y)]
idx = 0
while idx<len(q):
  x,y = q[idx]
  for dx,dy in [(0,-1),(0,1),(-1,0),(1,0)]:
    if (x+dx, y+dy) not in went.keys() and 0<=x+dx<W and 0<= y+dy<H and M[y+dy][x+dx] == ".":
      q.append((x+dx,y+dy))
      went[(x+dx,y+dy)]=went[(x,y)]+1
  idx+=1
print(max(went.values()))

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[[1 if c=='#' else 0 for c in input()] for i in range(H)]
from collections import deque
r=0
for i in range(H):
    for j in range(W):
        if S[i][j]==1:
            continue
        d=[[0]*W for i in range(H)]
        q=deque([(i,j,0)])
        D=0
        while q:
            x,y,d0=q.popleft()
            D=max(D,d0)
            if x>0 and S[x-1][y]==d[x-1][y]==0:
                q.append((x-1,y,d0+1))
                d[x-1][y]=d0+1
            if y>0 and S[x][y-1]==d[x][y-1]==0:
                q.append((x,y-1,d0+1))
                d[x][y-1]=d0+1
            if x<H-1 and S[x+1][y]==d[x+1][y]==0:
                q.append((x+1,y,d0+1))
                d[x+1][y]=d0+1
            if y<W-1 and S[x][y+1]==d[x][y+1]==0:
                q.append((x,y+1,d0+1))
                d[x][y+1]=d0+1
        r=max(r,D)
print(r)

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy
def dfs(B,si,sj, H, W):
    R = [[-1]*W for _ in range(H)]
    R[si][sj] = 0
    d = deque([(si, sj)])
#    print(B)
    while d:
        x, y = d.popleft()
        t = R[x][y]
        if x > 0:
            if B[x-1][y] == 0:
                if R[x-1][y] == -1:
                    R[x-1][y] = t+1
                    d.append((x-1, y))
                elif R[x-1][y] > t+1:
                    R[x-1][y] = t+1
                    d.append((x-1,y))
        if x < H-1:
            if B[x+1][y] == 0:
                if R[x+1][y] == -1:
                    R[x+1][y] = t+1
                    d.append((x+1,y))
                elif R[x+1][y] > t+1:
                    R[x+1][y] = t+1
                d.append((x+1,y))
        if y > 0:
            if B[x][y-1] == 0:
                if R[x][y-1] == -1:
                    R[x][y-1] = t+1
                    d.append((x, y-1))
                elif R[x][y-1] > t+1:
                    R[x][y-1] = t+1
                    d.append((x,y-1))
        if y < W-1:
            if B[x][y+1] == 0:
                if R[x][y+1] == -1:
                    R[x][y+1] = t+1
                    d.append((x, y+1))
                elif R[x][y+1] > t+1:
                    R[x][y+1] = t+1
                    d.append((x,y+1))

    return max( [ max(R[i]) for i in range(H)])
    

def main():
    H, W = map( int, input().split())
    S = [ list( input()) for _ in range(H)]
    B = [[0]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                B[i][j] = 1
    ans = 0
#    print(B)
    for i in range(H):
        for j in range(W):
            t = dfs(B, i, j, H, W)
            if t > ans:
                ans = t
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
for i in range(h):
    for j in range(w):
        if l[i][j]=='.':
            s=[i,j]
v=[[0 for i in range(w)] for j in range(h)]       
v[s[0]][s[1]]=1
mc=0
ms=s
q=[[s,0]]
while q:
    p=q.pop(0)
    x=p[0][0]
    y=p[0][1]
    c=p[1]
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    for j in k:
        nx=x+j[0]
        ny=y+j[1]
        if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
            v[nx][ny]=1
            q.append([[nx,ny],c+1])
            if mc<c+1:
                mc=c+1
                ms=[nx,ny]
v=[[0 for i in range(w)] for j in range(h)]       
v[ms[0]][ms[1]]=1
mc=0
q=[[ms,0]]
while q:
    p=q.pop(0)
    x=p[0][0]
    y=p[0][1]
    c=p[1]
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    for j in k:
        nx=x+j[0]
        ny=y+j[1]
        if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
            v[nx][ny]=1
            q.append([[nx,ny],c+1])
            if mc<c+1:
                mc=c+1
                ms=[nx,ny]
print(mc)

Submission status: Wrong Answer

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

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

# 4方向の移動
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


for h in range(H):
    for w in range(W):
        # BFSのためのデータ構造
        if field[h][w] == "#":
            continue
        dist = [[-1] * W for _ in range(H)]
        que_x = deque()
        que_y = deque()
        dist[h][w] = 0
        que_x.append(h)
        que_y.append(w)

        # BFS開始
        while que_x and que_y:
            x = que_x[0]
            y = que_y[0]
            que_x.popleft()
            que_y.popleft()
            tmp_max = 0
            for direct in range(4):
                nx = x + dx[direct]
                ny = y + dy[direct]
                if nx < 0 or H <= nx or ny < 0 or W <= ny:      # 場外はスルー
                    continue
                if field[nx][ny] == "#":     # 壁はスルー
                    continue
                if dist[nx][ny] == -1:          # まだ見ていない時
                    que_x.append(nx)
                    que_y.append(ny)
                    dist[nx][ny] = dist[x][y] + 1   # 距離の更新

        tmp_max = max(max(dist))
        ans = max(tmp_max, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
# BFS queue
import queue
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
end = (0,0)
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            start = (i,j)
            dist[i][j]=0
            break
    if start != (-1,-1):
        break
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
q = queue.Queue()
q.put(start)
# BFS
while 1:
    now = q.get()
    x = now[0]
    y = now[1]
    for elem in move:
        dx = elem[0]
        dy = elem[1]
        if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
            if b[x+dx][y+dy] != '#':
                if dist[x+dx][y+dy] > dist[x][y]:
                    dist[x+dx][y+dy] = dist[x][y] + 1
                    if dist[x+dx][y+dy] > far:
                        far = dist[x+dx][y+dy]
                        far2 = (x+dx,y+dy)
                    q.put((x+dx,y+dy))
    if q.empty():
        break
dist = [[10**9 for _ in range(W)] for _ in range(H)]
q = queue.Queue()
q.put(far2)
dist[far2[0]][far2[1]]=0
far=0
# BFS
while 1:
    now = q.get()
    x = now[0]
    y = now[1]
    for elem in move:
        dx = elem[0]
        dy = elem[1]
        if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
            if b[x+dx][y+dy] != '#':
                if dist[x+dx][y+dy] > dist[x][y]:
                    dist[x+dx][y+dy] = dist[x][y] + 1
                    if dist[x+dx][y+dy] > far:
                        far = dist[x+dx][y+dy]
                        far2 = (i,j)
                    q.put((x+dx,y+dy))
    if q.empty():
        break
print(far)

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)
mxx=-1
for ans in dijkstra(g,mx[1]):
    if ans!=10**18:
        mxx=max(mxx,ans)
print(mxx)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[[1 if c=='#' else 0 for c in input()] for i in range(H)]
from collections import deque
r=0
for i in range(H):
    for j in range(W):
        if S[i][j]==1:
            continue
        d=[[0]*W for i in range(H)]
        q=deque([(i,j,0)])
        while q:
            x,y,d0=q.popleft()
            if x>0 and S[x-1][y]==d[x-1][y]==0:
                q.append((x-1,y,d0+1))
                d[x-1][y]=d0+1
            if y>0 and S[x][y-1]==d[x][y-1]==0:
                q.append((x,y-1,d0+1))
                d[x][y-1]=d0+1
            if x<H-1 and S[x+1][y]==d[x+1][y]==0:
                q.append((x+1,y,d0+1))
                d[x+1][y]=d0+1
            if y<W-1 and S[x][y+1]==d[x][y+1]==0:
                q.append((x,y+1,d0+1))
                d[x][y+1]=d0+1
        r=max(r,d0)
print(r)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

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

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

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

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

ans = 0
for si in range(H):
    for sj in range(W):
        for gi in range(H):
            for gj in range(W):
                if si==gi and sj==gj:
                    continue
                d = bfs(S,(si,sj),(gi,gj))
                #print(d)
                if d==float('inf'):
                    continue
                if d>ans:
                    ans = d
print(ans)

Submission status: Wrong Answer

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

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

res = -1
for shi in range(h):
    for swi in range(w):
        for ghi in range(h):
            for gwi in range(w):
                r = solve(shi,swi,ghi,gwi)
                res = max(res, r)

print(res)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def solve(maze, st_tuple, g_tuple):
    st_row, st_col = st_tuple
    g_row, g_col = g_tuple
    W, H = len(maze[0]), len(maze)
    visited = [[0 for _ in range(W)] for __ in range(H)]
    q = deque()
    q.append((st_row, st_col, 0))
    while q:
        cur_row, cur_col, count = q.popleft()
        if cur_row == g_row and cur_col == g_col:
            return count
        for dr, dc in zip(DR, DC):
            next_row = cur_row + dr
            next_col = cur_col + dc
            if 0 <= next_row < H and 0 <= next_col < W:
                pass
            else:
                continue
            if maze[next_row][next_col] == '#':
                continue
            if visited[next_row][next_col]:
                continue
            q.append((next_row, next_col, count + 1))
            visited[next_row][next_col] = 1
    return -1

def main():
    H, W = LI()
    maze = []
    for _ in range(H):
        maze.append(S())
    num = 0
    for st_row in range(H):
        for st_col in range(W):
            for g_row in range(H):
                for g_col in range(W):
                    a = solve(maze, (st_row, st_col), (g_row, g_col))
                    num = max(num, a)

    print(num)
main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
s = ['#' * (w + 2)] + ['#' + input() + '#' for i in range(h)] + ['#' * (w + 2)]
# print(*s, sep='\n')

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


def bfs(si, sj):
    queue = deque([(si, sj, 0)])
    cost = [[-1] * (w + 2) for _ in range(h + 2)]
    cost[si][sj] = 0
    while queue:
        ci, cj, cc = queue.popleft()
        for k in range(4):
            ni = ci + di[k]
            nj = cj + dj[k]
            if s[ni][nj] == '#' or cost[ni][nj] != -1:
                continue
            else:
                queue.append((ni, nj, cc + 1))
                cost[ni][nj] = cc + 1

    return max(map(lambda x: max(x), cost))


ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = sys.maxsize
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d

@mt
def slv(H, W, S):
    ans = 0
    g = defaultdict(dict)
    for i in range(H):
        for j in range(W):
            if S[i][j] != '.':
                continue
            if i > 0 and S[i-1][j] == '.':
                g[(i, j)][(i-1, j)] = 1

            if i < H-1 and S[i+1][j] == '.':
                g[(i, j)][(i+1, j)] = 1

            if j > 0 and S[i][j-1] == '.':
                g[(i, j)][(i, j-1)] = 1

            if j < W-1 and S[i][j+1] == '.':
                g[(i, j)][(i, j+1)] = 1

    d = warshall_floyd(g)
    ans = 0
    for v in d.values():
        for c in v.values():
            ans = max(ans, c)

    return ans


def main():
    H, W = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# 4方向の移動
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


for h in range(H):
    for w in range(W):
        # BFSのためのデータ構造
        dist = [[-1] * W for _ in range(H)]
        que_x = deque()
        que_y = deque()
        dist[h][w] = 0
        que_x.append(h)
        que_y.append(w)

        # BFS開始
        while que_x and que_y:
            x = que_x[0]
            y = que_y[0]
            que_x.popleft()
            que_y.popleft()
            tmp_max = 0
            for direct in range(4):
                nx = x + dx[direct]
                ny = y + dy[direct]
                if nx < 0 or H <= nx or ny < 0 or W <= ny:      # 場外はスルー
                    continue
                if field[nx][ny] == "#":     # 壁はスルー
                    continue
                if dist[nx][ny] == -1:          # まだ見ていない時
                    que_x.append(nx)
                    que_y.append(ny)
                    dist[nx][ny] = dist[x][y] + 1   # 距離の更新
        tmp_max = max(max(dist))
        ans = max(tmp_max, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
ans = 0
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for h in range(H):
    for w in range(W):
        if maze[h][w] == '#':
            continue
        queue = deque()
        max_depth = 0
        visited = [[False] * W for i in range(H)]
        queue.append((h, w, 0))
        while queue:
            i, j, depth = queue.popleft()
            max_depth = max(max_depth, depth)
            for di, dj in move:
                ni, nj = i+di, j+dj
                if 0 <= ni < H and 0 <= nj < W and maze[ni][nj] == '.' and not visited[ni][nj]:
                    queue.append((ni, nj, depth+1))
                    visited[ni][nj] = True
        ans = max(ans, max_depth)
print(ans)

Submission status: Wrong Answer

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

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

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


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


for h in range(H):
    for w in range(W):
        if state[h][w] == ".":
            sh, sw = h, w
            break

lh, lw, _ = bfs(sh, sw)
_, _, waaa = bfs(lh, lw)
print(waaa)

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)

res1 = bfs(H, W, grid, (1, 1))
mx = 0
s = (1, 1)
for i in range(1, H+1):
    for j in range(1, W+1):
        if res1[i][j] > mx:
            mx = res1[i][j]
            s = (i, j)

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

Submission status: Wrong Answer

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

s = [input() for _ in range(h)]

def search(s_h, s_w):
    stack = [(s_h, s_w, 0)]
    isuse = [[False] * w for _ in range(h)]
    isuse[s_h][s_w]=True
    def add(a, b,score):
        nonlocal stack, isuse
        if not (0 <= a < h and 0 <= b < w):
            return 0
        if s[a][b] == "#":
            return 0
        if isuse[a][b]:
            return 0
        isuse[a][b] = True
        stack.append((a,b,score+1))
        

    while stack:
        a,b,c = stack.pop(0)
        add(a + 1, b, c)
        add(a , b, c)
        add(a , b + 1, c)
        add(a, b - 1, c)
        add(a - 1, b, c)
    return c

search(0,0)

ans = 0
for s_h in range(h):
    for s_w in range(w):
        ans = max(search(s_h, s_w), ans)
print(ans)