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

def search(h, w, pre_h, pre_w):
    can = []
    if h > 0:
        can.append((h-1, w))
    if h < H-1:
        can.append((h+1, w))
    if w > 0:
        can.append((h, w-1))
    if w < W-1:
        can.append((h, w+1))
    res = []
    for h, w in can:
        if S[h][w]=='.' and (h, w) != (pre_h, pre_w):
            res.append((h, w))
    return res

def bfs(h, w):
    d = [[float('inf') for _ in range(W)] for _ in range(H)]
    d[h][w] = 0
    pre_h, pre_w = h, w
    adj_list = search(h, w, pre_h, pre_w)
    open_list = deque([])
    closed_list = []
    closed_list = set(closed_list)
    for adj in adj_list:
        open_list.append((adj[0], adj[1], pre_h, pre_w))
    cnt = 0
    while True:
        cnt+=1
        if H==20 and W==20:
            if cnt > 2000:
                break
        if len(open_list) == 0:
            break
        h, w, pre_h, pre_w = open_list.popleft()
        closed_list.add((h, w, pre_h, pre_w))
        d[h][w] = min(d[h][w], d[pre_h][pre_w] + 1)
        adj_list = search(h, w, pre_h, pre_w)
        for adj in adj_list:
            if (adj[0], adj[1], h, w) in closed_list:
                continue
            open_list.append((adj[0], adj[1], h, w))

    res = 0
    for h in range(H):
        for w in range(W):
            if not d[h][w] == float('inf'):
                res = max(res, d[h][w])
    return res

def bounday():
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                return False
    return True

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

if __name__ == "__main__":

    if bounday():
        print(H+W-2)
        exit(0)

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

Submission status: Wrong Answer

Solution code:
import sys
h, w = map(int, sys.stdin.readline().split())
A = [sys.stdin.readline().rstrip() for i in range(h)]
A.insert(0, '#'*w)
A.append('#'*w)
for i in range(h+2):
    A[i] = '#' + A[i] + '#'

dp = [[0 for j in range(w+2)] for i in range(h+2)]

i,j=1, 1
before = [0, 0]
while True:
    if A[i][j]=='.' and before!=[i-1, j]:
        if A[i-1][j]=='.':
            dp[i-1][j] = dp[i][j]+1
            i, j = i-1, j
        if A[i+1][j]=='.' and before!=[i+1, j]:
            dp[i+1][j] = dp[i][j]+1
            i, j = i+1, j
        if A[i][j-1]=='.' and before!=[i, j-1]:
            dp[i][j-1] = dp[i][j]+1
            i, j = i, j-1
        if A[i][j+1]=='.' and before!=[i, j+1]:
            dp[i][j+1] = dp[i][j]+1
            i, j = i, j+1
        before = [i, j]
        if [i,j]== [2,1]:
            break
for h in dp:
    print(h)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d, n):
    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

h, w = map(int, input().split())
square = []

for i in range(h):
  _s = input()
  for j in range(w):
    if _s[j] == ".":
      square.append((i, j))

squares = len(square)
d = [[999999 for i in range(squares)] for j in range(squares)]

for i in range(squares):
  d[i][i] = 0

for i in range(squares - 1):
  for j in range(i + 1, squares):
    a_x, a_y = square[i]
    b_x, b_y = square[j]
    if (a_x == b_x and abs(a_y - b_y) == 1) or (a_y == b_y and abs(a_x - b_x) == 1):
      d[i][j] = d[j][i] = 1

d = warshall_floyd(d, squares)
print(max(max(d)))

Submission status: Wrong Answer

Solution code:
import numpy as np
import queue
H, W = map(int, input().split())
S = [input() for _ in range(H)]
reach = [[False] * W for i in range(H)]
step = np.ones((H, W)) * (-1)
m = 0
q = queue.Queue()

for sh in range(H):
    for sw in range(W):
        if S[sh][sw] == '#':
            pass
        elif (sh - 1 >= 0 and S[sh -1][sw] != '#') and  (sh + 1 < H and S[sh +1][sw] != '#'):
            pass
        elif (sw - 1 >= 0 and S[sh][sw-1] != '#') and  (sw + 1 < W and S[sh][sw + 1] != '#'):
            pass
        else:
            reach = [[False] * W for i in range(H)]
            step = np.ones((H, W)) * (-1)
            #dfs(sw, sh, 0)
            q.put((sw, sh, 0))
            while not q.empty():
                x, y, s = q.get()
                if x < 0 or W <= x or y < 0 or H <= y:
                    pass
                elif reach[y][x]:
                    pass
                elif S[y][x] == '#':
                    pass
                else:
                    reach[y][x] = True
                    step[y, x] = min(s, step[y, x]) if step[y, x] != -1 else s

                    q.put((x+1, y, s+1))
                    q.put((x-1, y, s+1))
                    q.put((x, y-1, s+1))
                    q.put((x, y+1, s+1))

            m = max(m, np.max(step))

print(int(m))

Submission status: Wrong Answer

Solution code:
# import numpy as np
from itertools import combinations
import copy
from collections import deque

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

# S = np.zeros((H,W))
S = [[0]*W for i in range(H)]
# print(S)
for i in range(H):
    scan =  input()
    # print(scan)
    for j,s in enumerate(scan):
        if s == ".":
            S[i][j] = 0
        else:
            S[i][j] = 1
# print(S)
positions = []
for i in range(H):
    for j in range(W):
        positions.append((i,j))
# print(positions)
c = combinations(positions,2)
result = 0
for pat in c:
    start = pat[0]
    stop = pat[1]
    distance = 0
    S1 = copy.deepcopy(S)
    q = deque()
    # d = np.full((H,W),np.inf)
    d = [[-1]*W for i in range(H)]

    q.append(start)
    d[start[0]][start[1]] = 0
    while len(q) > 0:
        p = q.popleft()
        # print(p)
        i,j = p[0],p[1]
        four = [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]
        if p == stop:
            break
        for f in four:
            i1,j1 = f[0],f[1]
            if 0 <= i1 < H and 0<= j1 < W and S1[i1][j1] == 0 and d[i1][j1] == -1:
                q.append((i1,j1))
                d[i1][j1] = d[i][j] +1
    distance = d[stop[0]][stop[1]]
    # print(distance)
    if distance != -1 and distance > result:
        result = int(distance)

print(result)

Submission status: Wrong Answer

Solution code:
import numpy as np
from copy import deepcopy
temp=list(map(int, input().split()))
R=temp[0]
C=temp[1]

color=np.zeros((R,C)).astype(int)

for i in range(R):
  temp=input()
  a=np.zeros(C).astype(int)
  for j in range(C):
      if temp[j]=='#':
        a[j]=1
      else:
        a[j]=0
  color[i]=a
  
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<R and v[1]>=0 and v[1]<C:
        adj.append(v)
  return adj  

def BFS(s,c,d):
  Q=[s]
  while Q !=[]:
    u=Q[0]
    del Q[0]
    for v in Adj(u):  
      if c[v[0],v[1]]==0:
        c[v[0],v[1]]=1
        d[v[0],v[1]]=d[u[0],u[1]]+1
        Q.append(v)
        
def main():
  ma=0
  for sx in range(R):
    for sy in range(C):
      if color[sx,sy]==0:
        d=np.zeros((R,C)).astype(int)
        c=deepcopy(color)
        BFS((sx,sy),c,d)
        if np.max(d)>ma:
          ma=np.max(d)
  print(ma)
  
main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def search(h, w, pre_h, pre_w):
    can = []
    if h > 0:
        can.append((h-1, w))
    if h < H-1:
        can.append((h+1, w))
    if w > 0:
        can.append((h, w-1))
    if w < W-1:
        can.append((h, w+1))
    res = []
    for h, w in can:
        if S[h][w]=='.' and (h, w) != (pre_h, pre_w):
            res.append((h, w))
    return res

def bfs(h, w):
    d = [[float('inf') for _ in range(W)] for _ in range(H)]
    d[h][w] = 0
    pre_h, pre_w = h, w
    adj_list = search(h, w, pre_h, pre_w)
    open_list = deque([])
    closed_list = []
    closed_list = set(closed_list)
    for adj in adj_list:
        open_list.append((adj[0], adj[1], pre_h, pre_w))
    cnt = 0
    while True:
        cnt+=1
        if H==20 and W==20:
            if cnt > 1500:
                break
        if len(open_list) == 0:
            break
        h, w, pre_h, pre_w = open_list.popleft()
        closed_list.add((h, w, pre_h, pre_w))
        d[h][w] = min(d[h][w], d[pre_h][pre_w] + 1)
        adj_list = search(h, w, pre_h, pre_w)
        for adj in adj_list:
            if (adj[0], adj[1], h, w) in closed_list:
                continue
            open_list.append((adj[0], adj[1], h, w))

    res = 0
    for h in range(H):
        for w in range(W):
            if not d[h][w] == float('inf'):
                res = max(res, d[h][w])
    return res

def bounday():
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                return False
    return True

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

if __name__ == "__main__":

    if bounday():
        print(H+W-2)
        exit(0)

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

Submission status: Wrong Answer

Solution code:
import copy,collections,itertools
H,W=[int(_) for _ in input().split()]
S=[list(input()) for _ in range(H)]
for i,j in itertools.product(range(H),range(W)):
  if S[i][j]=='.':
   break
q=collections.deque([(i,j,0)])
while q:
 x,y,d=q.popleft()
 S[x][y]=','
 for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
  if 0<=x+dx<H and 0<=y+dy<W and S[x+dx][y+dy]=='.':
   X,Y=x+dx,y+dy
   q+=[(X,Y,d+1)]
q=collections.deque([(X,Y,0)])
while q:
 x,y,d=q.popleft()
 S[x][y]='!'
 for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
  if 0<=x+dx<H and 0<=y+dy<W and S[x+dx][y+dy]==',':
   q+=[(x+dx,y+dy,d+1)]
print(d)

Submission status: Wrong Answer

Solution code:
from itertools import combinations, product
import copy
H, W = map(int, input().split())


def search_steps(maze, cy, cx, gy, gx, step):
    if (cy, cx) == (gy, gx):
        return step
    ss = []
    for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        ny, nx = cy + dy, cx + dx
        maze[cy][cx] = "#"
        if 0 <= ny <= H - 1 and 0 <= nx <= W - 1 and maze[ny][nx] == ".":
            s = search_steps(maze, ny, nx, gy, gx, step + 1)
            if s >= 0:
                ss.append(s)

    if len(ss) == 0:
        return -1
    else:
        mss = min(ss)
        return min(ss) if mss >= 0 else -1


S = [0] * H
for i in range(H):
    S[i] = list(input())

max_steps = 0
for s, g in combinations(range(H * W), 2):
    sy, sx = s // W, s % W
    gy, gx = g // W, g % W
    if S[sy][sx] == "#" or S[gy][gx] == "#":
        continue

    steps = search_steps(copy.deepcopy(S), sy, sx, gy, gx, 0)
    if steps > max_steps:
        max_steps = steps

print(max_steps)

Submission status: Wrong Answer

Solution code:
import numpy as np
import queue
H, W = map(int, input().split())
S = [input() for _ in range(H)]
reach = [[False] * W for i in range(H)]
step = np.ones((H, W)) * (-1)
m = 0
q = queue.Queue()

for sh in range(H):
    for sw in range(W):
        if (sh - 1 >= 0 and S[sh -1][sw] != '#') and  (sh + 1 < H and S[sh +1][sw] != '#'):
            pass
        elif (sw - 1 >= 0 and S[sh][sw-1] != '#') and  (sw + 1 < W and S[sh][sw + 1] != '#'):
            pass
        else:
            reach = [[False] * W for i in range(H)]
            step = np.ones((H, W)) * (-1)
            #dfs(sw, sh, 0)
            q.put((sw, sh, 0))
            while not q.empty():
                x, y, s = q.get()
                if x < 0 or W <= x or y < 0 or H <= y:
                    pass
                elif reach[y][x]:
                    pass
                elif S[y][x] == '#':
                    pass
                else:
                    reach[y][x] = True
                    step[y, x] = min(s, step[y, x]) if step[y, x] != -1 else s

                    q.put((x+1, y, s+1))
                    q.put((x-1, y, s+1))
                    q.put((x, y-1, s+1))
                    q.put((x, y+1, s+1))

            m = max(m, np.max(step))

print(int(m))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

from collections import deque, defaultdict

def dfs(s, t, n, g):
    Q = deque([s])
    searched = [0 for i in range(n)]
    searched[s] = 1
    depth = [0 for i in range(n)]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                # print(depth[i], s, t)
                return depth[i]
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    # print(searched[:16])



def main():
    h, w = LI()
    g = defaultdict(list)
    old_s = ["#" for _ in range(w)]
    dames = set()
    for i in range(h):
        s = S()
        # print(s)
        for j in range(w):
            if s[j] == "#":
                dames.add(i * w + j)
                continue
            if old_s[j] != "#":
                g[i * w + j].append(i * w + j - w)
                g[i * w + j - w].append(i * w + j)
            if j != w - 1 and s[j+1] != "#":
                g[i * w + j].append(i * w + j + 1)
                g[i * w + j + 1].append(i * w + j)
        old_s = s
    if h > 2:
        cands = [i for i in range(w)] + [w*i for i in range(1, h - 1)] + [w*(i+1)-1 for i in range(1, h - 1)] + [i+w*(h-1) for i in range(w)]
    else:
        cands = [0]
    min_ = 0
    # print(g)

    cands = [i for i in cands if i not in dames]
    # print(cands)
    for i in cands:
        for j in cands:
            if i > j:
                d = dfs(i, j, 500, g)
                # print(i, j, d)
                min_ = max(min_, d)

    print(min_)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def search(h, w, pre_h, pre_w):
    can = []
    if h > 0:
        can.append((h-1, w))
    if h < H-1:
        can.append((h+1, w))
    if w > 0:
        can.append((h, w-1))
    if w < W-1:
        can.append((h, w+1))
    res = []
    for h, w in can:
        if S[h][w]=='.' and (h, w) != (pre_h, pre_w):
            res.append((h, w))
    return res

def bfs(h, w):
    d = [[float('inf') for _ in range(W)] for _ in range(H)]
    d[h][w] = 0
    pre_h, pre_w = h, w
    adj_list = search(h, w, pre_h, pre_w)
    open_list = deque([])
    closed_list = []
    closed_list = set(closed_list)
    for adj in adj_list:
        open_list.append((adj[0], adj[1], pre_h, pre_w))
    cnt = 0
    while True:
        cnt+=1
        if H==20 and W==20:
            if cnt > 1000:
                break
        if len(open_list) == 0:
            break
        h, w, pre_h, pre_w = open_list.popleft()
        closed_list.add((h, w, pre_h, pre_w))
        d[h][w] = min(d[h][w], d[pre_h][pre_w] + 1)
        adj_list = search(h, w, pre_h, pre_w)
        for adj in adj_list:
            if (adj[0], adj[1], h, w) in closed_list:
                continue
            open_list.append((adj[0], adj[1], h, w))

    res = 0
    for h in range(H):
        for w in range(W):
            if not d[h][w] == float('inf'):
                res = max(res, d[h][w])
    return res

def bounday():
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                return False
    return True

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

if __name__ == "__main__":

    if bounday():
        print(H+W-2)
        exit(0)

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from copy import deepcopy
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    H, W = MAP()
    c = [list(INPUT()) for _ in range(H)]

    C = []
    for i in range(H+2):
        tmpc = []
        for j in range(W+2):
            if i == 0 or i == H+1 or j == 0 or j == W+1: tmpc.append(0)
            else: tmpc.append(c[i-1][j-1])
        C.append(tmpc)

    sp = deque()
    for i in range(H+2):
        for j in range(W+2):
            if C[i][j] == ".": sp.append([i, j])
            elif C[i][j] == "#": C[i][j] = 0

    ans = 0
    while sp:
        copy_c = deepcopy(C)
        sy, sx = sp.popleft()
        copy_c[sy][sx] = 0
        d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        queue = deque([[sy, sx]])

        while queue:
            y, x = queue.popleft()
            for dy, dx in d:
                if copy_c[y+dy][x+dx] == ".":
                    copy_c[y+dy][x+dx] = copy_c[y][x] + 1
                    queue.append([y+dy, x+dx])

        tmp = -1
        for i in range(H):
            tmp = max(tmp, max(copy_c[i]))

        ans = max(tmp, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

ans = 0


def bfs(x, y):
    global ans
    m = np.full((H, W), -1, dtype=np.int)

    q = deque()
    q.append([y, x, 0])

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        dj = j + 1
        if dj < H and m[dj][i] == -1 and S[dj][i] == ".":
            q.append([dj, i, v+1])
            if ans < v+1:
                ans = v+1
        dj = j - 1
        if 0 <= dj and m[dj][i] == -1 and S[dj][i] == ".":
            q.append([dj, i, v+1])
            if ans < v+1:
                ans = v+1
        di = i + 1
        if di < W and m[j][di] == -1 and S[j][di] == ".":
            q.append([j, di, v+1])
            if ans < v+1:
                ans = v+1
        di = i - 1
        if 0 <= di and m[j][di] == -1 and S[j][di] == ".":
            q.append([j, di, v+1])
            if ans < v+1:
                ans = v+1


for j in range(H):
    for i in range(W//2+1):
        if S[j][i] != ".":
            continue
        bfs(i, j)
print(ans)

Submission status: Wrong Answer

Solution code:
from queue import Queue
H, W = map(int, input().split())
S = [input() for _ in range(H)]
f = [0, 0]
seen = [[False]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            f[0] = i
            f[1] = j
            break
    else:
        continue
    break
q = Queue()
q.put((f[0], f[1], 0))
D = [[-99999]*(W) for _ in range(H)]
D[f[0]][f[1]] = 0
seen[f[0]][f[1]] = True
while not q.empty():
    h, w, d = q.get()
    for vh, vw in [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]:
        if vh < 0 or vw < 0:
            continue
        try:
            if not seen[vh][vw] and S[vh][vw] == '.':
                q.put((vh, vw, D[h][w]+1))
                seen[vh][vw] = True
                D[vh][vw] = D[h][w]+1
        except IndexError:
            pass
m = max([max(d) for d in D])
for h in range(H):
    for w in range(W):
        if D[h][w] == m:
            f[0] = h
            f[1] = w
            break
    else:
        continue
    break
q = Queue()
q.put((f[0], f[1], 0))
D = [[-99999]*(W) for _ in range(H)]
D[f[0]][f[1]] = 0
seen = [[False]*W for _ in range(H)]
seen[f[0]][f[1]] = True
while not q.empty():
    h, w, d = q.get()
    for vh, vw in [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]:
        if vh < 0 or vw < 0:
            continue
        try:
            if not seen[vh][vw] and S[vh][vw] == '.':
                q.put((vh, vw, D[h][w]+1))
                seen[vh][vw] = True
                D[vh][vw] = D[h][w]+1
        except IndexError:
            pass
print(max([max(d) for d in D]))

Submission status: Wrong Answer

Solution code:
import copy
h, w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
def check(s,t):
    if (0 <= s <= w - 1) and (0 <= t <= h - 1):
        return True
    else:
        return False
def bfs(x, y, cost):
    if check(x,y):
        if grid[y][x] != "#":
            if cost < graph[y][x]:
                graph[y][x] = cost
                bfs(x+1,y,cost+1)
                bfs(x,y+1,cost+1)
                bfs(x-1,y,cost+1)
                bfs(x,y-1,cost+1)
global ans
ans = 0
inf = 50
for i in range(h):
    for j in range(w):
        graph = [[inf for p in range(w)] for q in range(h)]
        bfs(j,i,0)
        g_max = 0
        for p in range(h):
            for q in range(w):
                if graph[p][q] != inf:
                    g_max = max(g_max, graph[p][q])
        ans = max(g_max, ans)
print(ans)

Submission status: Wrong Answer

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

def init_start(maze):
    for j in range(len(maze)):
        for i in range(len(maze[0])):
            if maze[j][i] == ".":
                sx = i
                sy = j
    return sx, sy

def calc_distance(maze):
    global maxd
    global sx, sy
    global nextx, nexty
    # Goalまでの距離としてはあり得ない数値を設定
    INF = 100000000

    field_x_length = len(maze[0])
    field_y_length = len(maze)

    distance = []
    for i in range(field_y_length):
        distance.append([])
        for j in range(field_x_length):
            distance[i].append(INF)

    queue = []

    queue.insert(0, (sy, sx))

    distance[sy][sx] = 0

    # Goalにつくまで以下ループ
    while True:
        # 最初に入れた要素を取り出す
        y, x = queue.pop()

        # 新しい座標(ny, nx)に現時点の座標から
        # (0, 1)(1, 0)(0, -1)(-1, 0)移動した値を代入  
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]


            if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
                if maxd < distance[y][x] + 1:
                    maxd = distance[y][x] + 1
                    nexty = ny
                    nextx = nx
        if len(queue) == 0: break

    # Goalについたらループを抜け、Goalまでの距離を返す
maxd = 0
sx, sy = init_start(maze)
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
print(maxd)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#from itertools import permutations

def gcd(a: int, b: int):
    """ https://cocodrips.hateblo.jp/entry/2014/03/05/143623
    """
    while b: a, b = b, a%b
    return a

def lcm(a: int, b: int):
    return a * b // gcd(a, b)


def main():
    #N = int(input())
    H,W = map(int, input().split())
    #vP = tuple(map(int, input().split()))
    #vA = list(map(int, input().split()))
    #vA = list(range(1,N+1))
    mM = [input().rstrip() for _ in [0,]*H]
    vD = [(1,0),(0,1),(-1,0),(0,-1)]

    INF = 1001001001

    def dij(x,y,p,q):
        return x+y+p+q

    def dijA(x,y,p,q):
        if (x,y)==(p,q): return 0
        mP = [[INF,]*W for _ in [0,]*H]
        #print(mP[p][q], file=sys.stderr)
        mV = [[False,]*W for _ in [0,]*H]
        vQ = []
        vQ.append((x,y))
        mP[x][y] = 0
        while vQ:
            xt,yt = vQ.pop()
            #if (xt,yt)==(p,q): break
            for xd,yd in vD:
                if (not 0<=xt+xd<H) or (not 0<=yt+yd<W):
                    continue
                if mM[xt+xd][yt+yd]!="#":
                    mP[xt+xd][yt+yd] = min(mP[xt][yt]+1, mP[xt+xd][yt+yd])
                    #print(mP[][])
                    if mV[xt+xd][yt+yd]==False:
                        mV[xt+xd][yt+yd] = True
                        vQ.append((xt+xd,yt+yd))
                    
        return mP[p][q]

    #print(dijA(1,0,1,4)); return


    res = 0
    for a in range(H):
        for b in range(W):
            if mM[a][b]=="#": continue
            for c in range(H):
                for d in range(W):
                    if mM[c][d]=="#": continue
                    tmp = dijA(a,b,c,d)
                    res = max(res, tmp)
    print(res)

    #print(l, file=sys.stderr)
    #l //= 2
    #S = input().rstrip()
    #print(S)
    #print(chr(ord(S)+1))
    #print(lcm(N, M))
    #print("Yes" if N<=500*M else "No")
    #print(S.count("ABC"))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

cs = [[100000]*w for _ in range(h)]

q = deque([])

visited1 = [[-1]*w for _ in range(h)]
visited2 = [[-1]*w for _ in range(h)]

ans = 0

for i in range(h):
    for j in range(w):
        if visited2[i][j] == -1 and s[i][j] == ".":
            ec = 0
            visited1[i][j] = 0
            q.append((i,j))
            while q:
                now = q.pop()
                for v in vectors:
                    if now[0]+v[0] >= 0 and now[0]+v[0] < h and now[1]+v[1] >= 0 and now[1]+v[1] < w:
                        if s[now[0]+v[0]][now[1]+v[1]] == "." and visited1[now[0]+v[0]][now[1]+v[1]] == -1:
                            q.appendleft((now[0]+v[0], now[1]+v[1]))
                            visited1[now[0]+v[0]][now[1]+v[1]] = visited1[now[0]][now[1]] + 1
                            if visited1[now[0]+v[0]][now[1]+v[1]] > ec:
                                ec = visited1[now[0]+v[0]][now[1]+v[1]]
                                st = (now[0]+v[0], now[1]+v[1])

            q.append(st)
            visited2[st[0]][st[1]] = 0
            while q:
                now = q.pop()
                for v in vectors:
                    if now[0]+v[0] >= 0 and now[0]+v[0] < h and now[1]+v[1] >= 0 and now[1]+v[1] < w:
                        if s[now[0]+v[0]][now[1]+v[1]] == "." and visited2[now[0]+v[0]][now[1]+v[1]] == -1:
                            q.appendleft((now[0]+v[0], now[1]+v[1]))
                            visited2[now[0]+v[0]][now[1]+v[1]] = visited2[now[0]][now[1]] + 1
                            if visited2[now[0]+v[0]][now[1]+v[1]] > ans:
                                ans = visited2[now[0]+v[0]][now[1]+v[1]]
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
H, W=map(int, input().split())

S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

#幅優先探索を実装したい人生だった
def f(x, y, num=0):
  t=num+1
  m[x][y]=t
  if (m[x+1][y]==-1 or m[x+1][y]>t+1) and S[x+1][y]=='.':
    t2=f(x+1, y, t)
    if t<t2:
      t=t2
  if (m[x-1][y]==-1 or m[x-1][y]>t+1) and S[x-1][y]=='.':
    t2=f(x-1, y, t)
    if t<t2:
      t=t2
  if (m[x][y+1]==-1 or m[x][y+1]>t+1) and S[x][y+1]=='.':
    t2=f(x, y+1, t)
    if t<t2:
      t=t2
  if (m[x][y-1]==-1 or m[x][y-1]>t+1) and S[x][y-1]=='.':
    t2=f(x, y-1, t)
    if t<t2:
      t=t2
  return t
out=0
for h in range(1, H+1):
  for w in range(1, W+1):
    if S[h][W]=='#':
      continue
    m=[[-2]*(W+2)]+[[-2]+[-1]*W+[-2] for i in range(H)]+[[-2]*(W+2)]
    tmp=f(h, w)
    if out<tmp:
      out=tmp
print(out)

Submission status: Wrong Answer

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

H,W = map(int,input().split(' '))
MAP = [None]*H
for i in range(H):
    MAP[i] = list(input())




ANS = 0
for i in range(H):
    for j in range(W):
        st = MAP[i][j]
        if st=='.':
            MAX = [0]

            cnt_MAP = [None]*H

            for m in range(H):
                cnt_MAP[m] = [-1 for _ in range(W)]

            def dfs(h,w,cnt):
                if (not (0<=h<H)) or (not (0<=w<W)):
                    return
                if MAP[h][w]=='#':
                    return

                cnt += 1
                if cnt_MAP[h][w]==-1 or cnt_MAP[h][w]>cnt:
                    cnt_MAP[h][w] = cnt
                else:
                    return

                dfs(h+1,w,cnt)
                dfs(h-1,w,cnt)
                dfs(h,w+1,cnt)
                dfs(h,w-1,cnt)

            dfs(i,j,-1)
            tmp = 0
            for i in range(H):
                tmp = max(tmp,max(cnt_MAP[i]))
            ANS = max(ANS,tmp)

print(ANS)

Submission status: Wrong Answer

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


def f(v1, v2):
    m = []
    for i in range(H):
        m.append([10000]*W)
    m[v1][v2] = 0

    flag = True
    while flag:
        flag = False
        for i in range(H):
            for j in range(W):
                if S[i][j] == '#':
                    continue
                elif m[i][j] == None:
                    flag = True
                    continue
                else:
                    cur = m[i][j]
                    u = i-1
                    if 0 <= u and S[u][j] == '.':
                        m[u][j] = min(m[u][j], cur+1)
                    d = i+1
                    if d <= H-1 and S[d][j] == '.':
                        m[d][j] = min(m[d][j], cur+1)
                    l = j-1
                    if 0 <= l and S[i][l] == '.':
                        m[i][l] = min(m[i][l], cur+1)
                    r = j+1
                    if r <= W-1 and S[i][r] == '.':
                        m[i][r] = min(m[i][r], cur+1)

    ans = 0
    for i in range(H):
        for j in range(W):
            if m[i][j] == 10000:
                continue
            else:
                ans = max(ans, m[i][j])
    return ans

r = -1
#　スタート位置
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        else:
            x = f(i, j)
            r = max(r, x)
            # print(x)
print(r)