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:
import copy

h,w = [int(i) for i in input().split()]
m = [list(input()) for i in range(h)]
#成型
for l in m:
    l.insert(0,'#')
    l.append('#')
m.insert(0,['#']*(w+2))
m.append(['#']*(w+2))

Maxlist = []
ans = [0]

def numap(i,j,m,add=True):
    que = [[i,j]]
    count = 0
    while que:
        newque = []
        for q in que:
            frag = 0#4になると極大値
            x=q[0]
            y=q[1]
            m[x][y]=count
            if m[x+1][y]=='.':
                newque.append([x+1,y])
            else:
                frag+=1
            if m[x-1][y]=='.':
                newque.append([x-1,y])
            else:
                frag+=1
            if m[x][y-1]=='.':
                newque.append([x,y-1])
            else:
                frag+=1
            if m[x][y+1]=='.':
                newque.append([x,y+1])
            else:
                frag+=1
            if frag == 4 and add:
                Maxlist.append([x,y])
        que = newque
        count+=1
    ans[0] = max(ans[0],count-1)

# i行j列 という指定の仕方になる
mp = copy.deepcopy(m)
breakflag = False
for i,a in enumerate(mp):
    for j,b in enumerate(a):
        if b == '.':
            numap(i,j,mp)
            breakflag = True
            break
    if breakflag:
        break

for l in Maxlist:
    mp = copy.deepcopy(m)
    numap(l[0],l[1],mp,add=False)

print(ans[0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
from itertools import product

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = defaultdict(list)
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.': E[(i, j)].append((x, y)); E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

start = V[0]
D1 = bfs(start)
distant_v, _ = sorted(D1.items(), reverse=True, key=lambda x: x[1])[0]
D2 = bfs(distant_v)
print(max(D2.values()))

Submission status: Wrong Answer

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


"""
s_idx = [-1,-1]
g_idx = [-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == 'S':
            s_idx[0] = i
            s_idx[1] = j
        if s[i][j] == 'G':
            g_idx[0] = i
            g_idx[1] = j
"""

tate = [0,0,1,-1]
yoko = [-1,1,0,0]

mat=[[10**18 for i in range(w*h)] for j in range(w*h)]

for i in range(w*h):
	mat[i][i]=0

for i in range(w*h):
    for j in range(4):
        next_idx = i + w*tate[j] + yoko[j]
        if next_idx < 0 or next_idx >= w*h:
            continue
        if i % w == 0:
            if j == 0:
                continue
        if i % w == w - 1:
            if j == 1:
                continue
        if s[next_idx//w][next_idx%w] == '#':
            mat[i][next_idx] = 10**18
        else:
            mat[i][next_idx] = 1

for i in range(w*h):
    #print(i,i,i,i,i,i,i,i,i)
    for x in range(w*h):
        for y in range(w*h):
            """
            if x == s_idx[0]*w+s_idx[1] and y == g_idx[0]*w+g_idx[1]:
                print(mat[x][y],mat[x][i] , mat[i][y],i)
            """
            mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
    
ans = 5000
tmp = []

for i in range(w*h):
    for j in range(w*h):
        if ans > mat[i][j]:
            tmp.append(mat[i][j])
            
print(max(tmp))

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [0]*H
for i in range(H):
    S[i] = input()
# print(H, W, S)


def is_inside(w, h, W, H):
    if w >= 0 and w < W and h >= 0 and h < H:
        return True
    return False

def solve(sh, sw):
    T = [[0]* W for h in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#':
                T[i][j] = -1
    V = deque([(sh, sw)])
    T[sh][sw] = -2
    while len(V) != 0:
        v = V.popleft()
        h = v[0]
        w = v[1]
        # print(h, w)
        t = T[h][w]
        if t == -2:
            t = 0
        if is_inside(h - 1, w, H, W):
            if T[h - 1][w] == 0:
                T[h - 1][w] = t + 1
                V.append((h - 1, w))
        if is_inside(h + 1, w, H, W):
            if T[h + 1][w] == 0:
                T[h + 1][w] = t + 1
                V.append((h + 1, w))
        if is_inside(h, w - 1, H, W):
            if T[h][w - 1] == 0:
                T[h][w - 1] = t + 1
                V.append((h , w - 1))
        if is_inside(h, w + 1, H, W):
            if T[h][w + 1] == 0:
                T[h][w + 1] = t + 1
                V.append((h , w + 1))
    # print(sh, sw, T)
    return T


ans = 0

for h in range(H):
    for w in range(W):
        T = solve(h, w)
        distance = 0
        for i in range(H):
            for j in range(W):
                d = T[i][j]
                distance = max(distance, d)
        ans = max(distance, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

maze=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]
INF=10800 #>50*50
visited=[[-INF]*(w+2) for i in range(h+2)]

ss=[]

for i in range(1,h+1):
  for j in range(1,w+1):
    if maze[i][j]==".":
      ss.append((i,j))



def bfs(maze,visited,sy,sx):#,gy,gx):
  queue=deque([[sy,sx]])
  visited[sy][sx]=0
  while queue:
    [y,x]=queue.popleft()
    for i,j in ((-1,0),(1,0),(0,1),(0,-1)):
      y_new,x_new=y+i,x+j
      if maze[y_new][x_new]=="." and visited[y_new][x_new]==-INF:
        visited[y_new][x_new]=visited[y][x]+1
        queue.append([y_new,x_new])

        
        
ans=0
for i,j in ss:
  visited=[[-INF]*(w+2) for i in range(h+2)]
  bfs(maze,visited,i,j)
  for i in range(1,h+1):
    for j in range(1,w+1):
      ans=max(ans,visited[i][j])
      print(ans)

    
    
print(ans)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7

    H,W = LMIIS()
    S = [input() for _ in range(H)]
    # print(S)

    def tansaku(S,V,y,x,length):
        if  x >= 1 and S[y][x-1] == '.' and V[y][x-1] > length+1:
            V[y][x-1] = length+1
            left = tansaku(S,V,y,x-1,length+1)
        else:
            left = length

        if x < W-1 and S[y][x+1] == '.' and V[y][x+1] > length+1:
            V[y][x+1] = length+1
            right = tansaku(S,V,y,x+1,length+1)
        else:
            right = length

        if y >= 1 and S[y-1][x] == '.' and V[y-1][x] > length+1:
            V[y-1][x] = length+1
            up = tansaku(S,V,y-1,x,length+1)
        else:
            up = length

        if y < H-1 and S[y+1][x] == '.' and V[y+1][x]> length+1:
            V[y+1][x] = length+1
            down = tansaku(S,V,y+1,x,length+1)
        else:
            down = length
        return
    
    def getmax():
        max_length = 0
        for h in range(H):
            for w in range(W):
                V = [[MOD] * W for _ in range(H)]
                tansaku(S,V,h,w,0)
                for v in V:
                    v = list(map(lambda x:x%MOD,v))
                    max_length = max(v+[max_length])
                    # print(V)
        return max_length
    
    print(getmax())
    






if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
visited = [[False for i in range(W+2)] for j in range(H+2)]                                     # ノードの訪問済みフラグ
graph = [['#']+[i for i in input()]+['#'] for j in range(H)]
graph = [['#' for i in range(W+2)]]+graph+[['#' for i in range(W+2)]]
 
import copy
# dfs:ノードvについて、エッジで接続した未訪問のノードを浅いほうから訪問(LILO)
def dfs(r,c,goal):
    visited = [[False for i in range(W+2)] for j in range(H+2)]
    step = 0
    queue = [[r,c]]
    if graph[r][c]=='#':
      return -1
    queue_2 = []
    while len(queue) != 0:
        step += 1
        for now in queue:
          visited[now[0]][now[1]] = True
          for next in [[1,0],[0,1],[-1,0],[0,-1]]:
            if visited[now[0]+next[0]][now[1]+next[1]] == True:continue
            if graph[now[0]+next[0]][now[1]+next[1]] == '#':continue
            if [now[0]+next[0],now[1]+next[1]] == goal:return step
            if [now[0]+next[0],now[1]+next[1]] in queue_2:continue
            queue_2.append([now[0]+next[0],now[1]+next[1]])
        queue.clear()
        queue = copy.deepcopy(queue_2)
        queue_2.clear()
    return -1

print(max(dfs(1,1,[H,W]),dfs(H,1,[1,W])))

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys

sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    H, W = LMIIS()
    s = [[] for _ in range(H+2)]
    s[0] = "#" * (W+2)
    s[H+1] = "#" * (W+2)
    for i in range(1, H+1):
        s[i] = "#" + input() + "#"

    g = [[] for _ in range(H*W)]
    for i in range(1, H+1):
        for j in range(1, W+1):
            if s[i][j] == "#":
                g[(i-1)*W + j -1] = [-1]
            else:
                if s[i-1][j] == ".":
                    g[(i-1)*W + j -1].append((i-2)*W + j - 1)
                if s[i][j-1] == ".":
                    g[(i-1)*W + j -1].append((i-1)*W + j - 2)
                if s[i+1][j] == ".":
                    g[(i-1)*W + j -1].append(i*W + j - 1)
                if s[i][j+1] == ".":
                    g[(i-1)*W + j -1].append((i-1)*W + j)


    ans = 0
    for i in range(H*W):
        m = [-1] * (H*W)
        m[i] = 0
        q = g[i]
        l = 1
        while len(q) > 0:
            tmp = []
            for a in q:
                m[a] = l
                for b in g[a]:
                    if m[b] == -1 and not b in tmp:
                        tmp.append(b)
                    else:
                        m[b] = min(l+1, m[b])

            l += 1
            q = tmp[:]

        ans = max(ans, max(m))
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        x=[[inf for i in range(w)] for i in range(h)]
        q=queue.Queue()
        d=0
        q.put([i,j])
        while q.qsize()!=0:
            d+=1
            l=q.qsize()
            for t in range(l):
                I,J=q.get()
                if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                    q.put([I-1,J])
                    x[I-1][J]=d
                if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                    q.put([I+1,J])
                    x[I+1][J]=d
                if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                    q.put([I,J-1])
                    x[I][J-1]=d
                if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                    q.put([I,J+1])
                    x[I][J+1]=d
        ma_sub=0
        for k in range(h):
            for l in range(w):
                if x[k][l]!=inf:
                    ma_sub=max(ma_sub,x[k][l])
        ma.append(ma_sub)
print(max(ma))

Submission status: Wrong Answer

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

def solve(h, w, a):
    dp = [[-1] * (h * w) for _ in range(h * w)]
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    def bfs(x1, y1, x2, y2):
        s = y1 * w + x1
        t = y2 * w + x2
        visited = [[False] * w for _ in range(h)]
        cur = []
        visited[y1][x1] = True
        cur.append((x1, y1))
        cnt = 1
        while True:
            nex = []
            for x, y in cur:
                for i in range(4):
                    tx = x + dx[i]
                    ty = y + dy[i]
                    if 0 <= tx < w and 0 <= ty < h and a[ty][tx] != '#' and not visited[ty][tx]:
                        visited[ty][tx] = True
                        if tx == x2 and ty == y2:
                            return cnt
                        if dp[ty * w + tx][t] >= 0:
                            return cnt + dp[ty * w + tx][t]
                        nex.append((tx, ty))
                        dp[s][ty * w + tx] = cnt
            if len(nex) > 0:
                cur = nex
            else:
                break
            cnt += 1
        return -1

    ret = -1
    for i in range(h):
        for j in range(w):
            for i2 in range(h):
                for j2 in range(w):
                    if (not (i == i2 and j == j2)) and a[i][j] == '.' and a[i2][j2] == '.' and dp[w * i + j][w * i2 + j2] < 0:
                        tmp = bfs(j, i, j2, i2)
                        ret = max(ret, tmp)
                        #dp[w * i + j][w * i2 + j2] = tmp
                        #dp[w * i2 + j2][w * i + j] = tmp
                        #print(i, j, i2, j2)
                        #print(tmp)
    print(ret)
    return

def main():
    h, w = map(int, input().split())
    a = []
    for i in range(h):
        a.append(input())
    solve(h, w, a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import queue

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

s = list()
for l in range(0, h):
    line = input()
    s.append(line)

dx = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def search(start_h, start_w):
    if s[start_h][start_w] == "#":
        ans = -1

    cost = [[10000000 for i in range(0, w)] for j in range(0, h)]

    q = queue.Queue()
    q.put((start_h, start_w, 0))
    while not q.empty():
        current_h, current_w, current_c = q.get()
        if cost[current_h][current_w] < 10000000:
            continue
        else:
            cost[current_h][current_w] = current_c

        # print("pos_w:%d, pos_h:%d, cost:%d" % (current_w, current_h, current_c))
        for dw, dh in dx:
            next_h = current_h + dh
            next_w = current_w + dw
            next_c = current_c + 1

            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue

            if s[next_h][next_w] == "#" or cost[next_h][next_w] < next_c:
                continue
            else:
                q.put((next_h, next_w, next_c))

    tmp = 0
    for a in range(0, w):
        for b in range(0, h):
            if cost[b][a] > 1000:
                continue
            else:
                tmp = max(tmp, cost[b][a])

    return tmp


ans = 0
for i in range(0, w):
    for j in range(0, h):
        # print("start_h:%d, start_w:%d" % (j, i))
        cost_tmp = search(j, i)
        ans = max(ans, cost_tmp)
        # print("start_h:%d, start_w:%d cost:%d" % (j, i, cost_tmp))


print(ans)

Submission status: Wrong Answer

Solution code:
import queue

h, w = map(int, input().split())
maze = [[(False, False, False, False) for _ in range(w)] for _ in range(h)]
inputs = [list(map(lambda x: x == "#", input())) for _ in range(h)]

def bfs(x, y):
    q = queue.Queue()
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[x][y] = True
    q.put((x, y, 0))

    max_length = 0

    while not q.empty():
        vx, vy, length = q.get()
        max_length = max(max_length, length)
        (ue, migi, hidari, shita) = maze[vx][vy]
        if not ue:
            if not visited[vx - 1][vy]:
                visited[vx - 1][vy] = True
                q.put((vx - 1, vy, length + 1))
        if not migi:
            if not visited[vx][vy + 1]:
                visited[vx][vy + 1] = True
                q.put((vx, vy + 1, length + 1))
        if not hidari:
            if not visited[vx][vy - 1]:
                visited[vx][vy - 1] = True
                q.put((vx, vy - 1, length + 1))
        if not shita:
            if not visited[vx + 1][vy]:
                visited[vx + 1][vy] = True
                q.put((vx + 1, vy, length + 1))
    
    return max_length

for x in range(h):
    for y in range(w):
        ue = (x == 0) or inputs[x - 1][y]
        migi = (y == w - 1) or inputs[x][y + 1]
        hidari = (y == 0) or inputs[x][y - 1]
        shita = (x == h - 1) or inputs[x + 1][y]

        maze[x][y] = (ue, migi, hidari, shita)

result = 0

for x in range(h):
    for y in range(w):
        point = maze[x][y]
        if sum(point) >= 3:
            pass
        result = max(result, bfs(x, y))

print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def bfs(s, t):
    dist = [[None] * W for _ in range(H)]
    que = deque([(s, t)])
    dist[s][t] = 0
    while que:
        u, v = que.popleft()
        d = dist[u][v]
        G = []
        if u > 0 and S[u-1][v] == ".":
            G.append((u-1, v))
        if u < H - 1 and S[u+1][v] == ".":
            G.append((u+1, v))
        if v > 0 and S[u][v-1] == ".":
            G.append((u, v-1))
        if v < W - 1 and S[u][v+1] == ".":
            G.append((u, v+1))
        for w, x in G:
            if dist[w][x] is None:
                dist[w][x] = d + 1
                que.append((w, x))
    mi = s
    mj = t
    d = 0
    for i in range(H):
        for j in range(W):
            if dist[i][j] is not None:
                if dist[i][j] > d:
                    d = dist[i][j]
                    mi = i
                    mj = j
    return (d, (mi, mj))

for i in range(H):
    j = S[i].find(".")
    if j >= 0:
        _, (u, v) = bfs(i, j)
        d, _ = bfs(u, v)
        print(d)
        break

Submission status: Wrong Answer

Solution code:
import sys
import queue
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

d = [[-1,0],[1,0],[0,-1],[0,1]]

H,W = LI()
S = [list(input()) for _ in range(H)]

def bfs(s):
    dist = [[-1]*W for _ in range(H)]
    h,w = s
    dist[h][w] = 0
    que = queue.Queue()
    que.put(s)
    while(not(que.empty())):
        h,w = que.get_nowait()
        for dh,dw in d:
            nh,nw = h+dh,w+dw
            if 0<=nh<H and 0<=nw<W and dist[nh][nw]==-1 and S[nh][nw]=='.':
                dist[nh][nw] = dist[h][w] + 1
                que.put([nh,nw])
    return dist[h][w]

def main():
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                way = 0
                for dh,dw in d:
                    nh,nw = h+dh,w+dw
                    if 0<=nh<H and 0<=nw<W and S[nh][nw]=='.':
                        way += 1
                if way == 1 or ((h==0 or h==H-1) and (w==0 or w==W-1)):
                    ans = max(ans,bfs([h,w]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict

H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(1,0),(-1,0),(0,1),(0,-1)]

def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    Visit[start]=1
    L=defaultdict(lambda: 0)    #距離

    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and (to_x,to_y) not in Visit:
                    Visit[to_x,to_y]=1
                    L[(to_x,to_y)]=L[(fro_x,fro_y)]+1
                    q.append((to_x,to_y))
    if len(L.values())==0:
        return 0
    else:
        return max(L.values())

ans=0
for h in range(H):
    for w in range(W):
        ans=max(ans,bfs((h,w)))

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, N):
    d = g
    for k in range(N):
        for i in range(N):
            for j in range(N):
                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 = [[INF] *(H*W) for _ in range(H*W)]
    def idx(i, j):
        return i*W + j
    for i in range(H):
        for j in range(W):
            if S[i][j] != '.':
                continue
            if i > 0 and S[i-1][j] == '.':
                g[idx(i, j)][idx(i-1, j)] = 1

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

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

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

    d = warshall_floyd(g, W*H)
    ans = 0
    for r in d:
        for v in r:
            if v != INF:
                ans = max(ans, v)
    return ans


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


    # H = 20
    # W = 20
    # S = ['.'*W]*H
    print(slv(H, W, S))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.sparse.csgraph as g

h, w = map(int, input().split())
board = np.zeros((h, w), dtype=bool)

for i in range(h):
    line = input()
    for j, s in enumerate(line):
        board[i][j] = s == "."


def get_around(i, j):
    if i > 0:
        yield (i - 1, j)
    if i < h - 1:
        yield (i + 1, j)
    if j > 0:
        yield (i, j - 1)
    if j < w - 1:
        yield (i, j + 1)


from collections import deque


def length(start, end):
    q = deque()
    q.append((start, 0))
    seen = np.zeros((h, w), dtype=bool)
    seen[start] = True
    while q:
        cur, l = q.popleft()
        if cur == end:
            return l
        for ncur in get_around(*cur):
            if board[ncur] and not seen[ncur]:
                seen[ncur] = True
                q.append(((ncur), l + 1))


graph=np.zeros((h*w,h*w),dtype=int)

def yield_pos():
    for i in range(h):
        for j in range(w):
            if board[i, j]:
                yield (i, j)

def flat(s):
    return s[0]*w+s[1]
for s in yield_pos():
    for t in get_around(*s):
        graph[flat(s),flat(t)] = 1

csg=g.csgraph_from_dense(graph)
d=g.floyd_warshall(csg)
# d=np.nan_to_num(d)
d[np.isinf(d)]=0
print(int(d.max()))

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = 1e9
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def bfs(sy, sx):
    que = deque()
    que.append((sy, sx))
    d[sy][sx] = 0
    m = 0
    xy = [[0]*c for _ in range(r)]
    while len(que) > 0:
        y, x = que.popleft()
        if xy[y][x] !=0:
            break
        xy[y][x]=1

        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0 <= ny and ny < r and 0 <= nx and nx < c and wall[ny][nx] != "#" and d[ny][nx] == INF:
                que.append((ny, nx))
                d[ny][nx] = d[y][x]+1
                m = max(d[ny][nx],m)

    return m


r, c = map(int, input().split())
wall = [list(input()) for _ in range(r)]

ans = 0
for i in range(r):
    for j in range(c):
        d = [[INF]*c for _ in range(r)]
        a = bfs(i, j)
        ans = max(ans, a)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
h,w=20,20
s=[["."]*20for j in range(20)]
e=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            p=[i,j]
            q=[p]
            t=[[1]*w for j in range(h)]
            t[p[0]][p[1]]=0
            g=0
            while q:
                c=[]
                for i,j in q:
                    a=[1,-1,0,0]
                    b=[0,0,1,-1]
                    for d in range(4):
                        if 0<=i+a[d]<h and 0<=j+b[d]<w:
                            if s[i+a[d]][j+b[d]]==".":
                                if t[i+a[d]][j+b[d]]:
                                    t[i+a[d]][j+b[d]]=0
                                    c.append([i+a[d],j+b[d]])
                if len(c)==0:
                    break
                else:
                    g+=1
                    q=c[::]
            e=max(e,g)
print(e)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf=1000
    h,w=MI()
    ss=[[c=="#" for c in input()] for _ in range(h)]
    mx=0
    for si in range(h):
        for sj in range(w):
            bfs={}
            bfs[si,sj]=0
            vis=[[False]*w for _ in range(h)]
            vis[si][sj]=True
            while bfs:
                nxt={}
                for (i,j),d in bfs.items():
                    if d>mx:mx=d
                    for ni, nj in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
                        if ni<0 or nj<0 or ni>=h or nj>=w:continue
                        if ss[ni][nj]:continue
                        if vis[ni][nj]:continue
                        vis[ni][nj]=True
                        nxt[ni,nj]=d+1
                bfs=nxt

    print(mx)

main()

Submission status: Wrong Answer

Solution code:
import math

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

S = []

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

for i in range(H):
    tmp = list(input())
    S.append([t for t in tmp])

d = [[10000 for _ in range(H*W)] for _ in range(H*W) ]
for i in range((H)*W):
    if i == H*W-1:
        pass 
    elif i % W == W-1:
        if S[i//W][i%W] == ".":
            if S[i//W+1][i%W] == ".":
                d[i][i+W] = 1
                d[i+W][i] = 1
    elif i > (H-1)*W-1:
        if S[i//W][i%W] == ".":
            if S[i//W][i%W+1] == ".":
                d[i][i+1] = 1
                d[i+1][i] = 1

    else:
        if S[i//W][i%W] == ".":
            if S[i//W+1][i%W] == ".":
                d[i][i+W] = 1
                d[i+W][i] = 1
            if S[i//W][i%W+1] == ".":
                d[i][i+1] = 1
                d[i+1][i] = 1
n = H*W
x = warshall_floyd(d)                

ans = 0
for x_ in x:
    for xx in x_:
        if xx < 10000 and xx > ans:
            ans = xx
print(ans)

Submission status: Wrong Answer

Solution code:
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    start_row, start_col = None, None
    for row in range(H):
        for col in range(W):
            if Maze[row][col] == '.':
                start_row, start_col = row, col
                break
        else:
            continue
        break

    def bfs(start_row, start_col):
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return dist

    dist_first = bfs(start_row, start_col)

    start = []
    maximum = 0
    for row in range(H):
        for col in range(W):
            if Maze[row][col] != '#':
                if dist_first[row][col] > maximum:
                    maximum = dist_first[row][col]
                    start = [(row, col)]
                elif dist_first[row][col] == maximum:
                    start.append((row, col))

    ans = 0
    for start_row,start_col in start:
        dist = bfs(start_row,start_col)
        for row in range(H):
            for col in range(W):
                if Maze[row][col] != '#':
                    ans = max(ans, dist[row][col])
    return ans

print(d_maze_master())