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

def agent(maze,ori):
    global H
    global W

    hi=ori[0]
    wi=ori[1]
    root=[]
    if hi > 0:
        root.append([hi-1,wi])
    if hi < H-1:
        root.append([hi+1,wi])
    if wi > 0:
        root.append([hi,wi-1])
    if wi < W-1:
        root.append([hi,wi+1])
    
    for h,w in root:
        if maze[h][w]==".":
            maze[h][w]=maze[hi][wi]+1
            agent(maze,[h,w])
        elif maze[h][w]=="#":
            pass
        else:
            if maze[h][w] > maze[hi][wi]+1:
                maze[h][w]=maze[hi][wi]+1
                agent(maze,[h,w])


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

maze=[]
for h in range(H):
    maze_w=list(input())
    lis=[]
    for e in maze_w:
        if e =="#":
            lis.append(-1)
        else:
            lis.append(e)

    maze.append(lis)

maze_ori=copy.deepcopy(maze)
maxd=0

for h in range(H):
    for w  in range(W):
        maze=copy.deepcopy(maze_ori)
        if maze[h][w]==".":
            maze[h][w]=0
            agent(maze,[h,w])
            maxd=max(maxd,max(max(maze)))
            print(maze)
        else:
            pass


print(maxd)

Submission status: Wrong Answer

Solution code:
INF=10**9+7
H,W=map(int,input().split())
S=list()
q=list()

S.append(["#"]*(W+2))
for i in range(H):
  S.append(["#"]+list(input())+["#"])
S.append(["#"]*(W+2))


m=0
for y in range(1,H+1):
  for x in range(1,W+1):
    D=[[INF]*(W+2) for _ in range(H+2)]
    D[y][x]=0
    q.clear()
    q.append([x,y])
    while len(q)>0:
      c=list(q.pop(0))
      for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
        ny,nx=c[1]+dy,c[0]+dx
        if S[ny][nx]=="." and D[ny][nx]>D[c[1]][c[0]]+1:
          D[ny][nx]=D[c[1]][c[0]]+1
          q.append([nx,ny])
          m=max(m,D[ny][nx])
print(m)

Submission status: Wrong Answer

Solution code:
import sys
from queue import Queue


def get_costs(S):
    costs = [[0 for w in range(len(S[0]))] for h in range(len(S))]
    for h in range(len(S)):
        for w in range(len(S[0])):
            if S[h][w] == '#':
                costs[h][w] = -1
    return costs


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_h in range(H):
        for start_w in range(W):
            costs = get_costs(S)
            queue = Queue()
            queue.put((start_h, start_w, 1))
            cost = 1
            while not queue.empty():
                (y, x, c) = queue.get()
                if not (0 <= y < len(costs) and 0 <= x < len(costs[0])):
                    continue
                if costs[y][x] != 0:
                    continue
                print("({},{}): {}".format(y, x, c))
                costs[y][x] = c
                cost = c
                queue.put((y - 1, x, c + 1))
                queue.put((y, x + 1, c + 1))
                queue.put((y + 1, x, c + 1))
                queue.put((y, x - 1, c + 1))
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
INF=10**9+7
H,W=map(int,input().split())
S=list()

S.append(["#"]*(W+2))
for i in range(H):
  S.append(["#"]+list(input())+["#"])
S.append(["#"]*(W+2))
q=list()

m=0
for y in range(1,H+1):
  for x in range(1,W+1):
    D=[[INF]*(W+2) for _ in range(H+2)]
    D[y][x]=0
    q.clear()
    q.append([x,y])
    while len(q)>0:
      c=list(q.pop(0))
      for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
        ny,nx=c[1]+dy,c[0]+dx
        if S[ny][nx]=="." and D[ny][nx]==INF:
          D[ny][nx]=D[c[1]][c[0]]+1
          q.append([nx,ny])
          m=max(m,D[ny][nx])
print(m)

Submission status: Wrong Answer

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

from queue import Queue

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

sum_sharp = sum([A[i].count('#') for i in range(H)])
exit(0)
fin_d_max = 1

for s_i in range(H):
    for s_j in range(W):
        d_max = 0
        q_i = Queue()
        q_j = Queue()
        D = [[-1]*W for i in range(H)]
        #flag = [[0]*W for i in range(H)]
        flag = 1

        if A[s_i][s_j] == '.':
            D[s_i][s_j] = 0
            q_i.put(s_i)
            q_j.put(s_j)
            #while sum(map(sum, flag)) != W*H - sum_sharp:
            while flag < W*H - sum_sharp:
                i = q_i.get()
                j = q_j.get()
                #flag[i][j] =1
                for x in range(4):
                    ni = i+di[x]
                    nj = j+dj[x]
                    if ni<0 or ni>=H or nj<0 or nj>=W or A[ni][nj]== '#' or (D[ni][nj]>=0 and D[ni][nj]<D[i][j]+1):
                    #if ni<0 or ni>=H or nj<0 or nj>=W:
                        continue
                    #elif A[ni][nj]== '#' or D[ni][nj] < D[i][j]+1:
                        #flag[ni][nj] = 1
                        #continue
                    else:
                        if D[ni][nj] == -1:
                            flag += 1
                        D[ni][nj] = D[i][j]+1
                        d_max = max(d_max, D[ni][nj])
                        q_i.put(ni)
                        q_j.put(nj)
        fin_d_max = max(fin_d_max, d_max)
                
print(fin_d_max)

Submission status: Wrong Answer

Solution code:
import copy
import sys


def walk(y, x, cost, costs):
    if not (0 <= y < len(costs) and 0 <= x < len(costs[0])):
        return -1
    if costs[y][x] != 0:
        return -1
    costs = copy.deepcopy(costs)
    costs[y][x] = cost
    max_cost = cost
    for (next_y, next_x) in [(y - 1, x), (y, x + 1), (y + 1, x), (y, x - 1)]:
        cost1 = walk(next_y, next_x, cost + 1, costs)
        if cost1 > max_cost:
            max_cost = cost1
    return max_cost


def get_costs(S):
    costs = [[0 for w in range(len(S[0]))] for h in range(len(S))]
    for h in range(len(S)):
        for w in range(len(S[0])):
            if S[h][w] == '#':
                costs[h][w] = -1
    return costs


def print_costs(costs):
    for c in costs:
        print(c)


def solve(inp):
    (H, W) = map(int, inp.readline().strip().split(' '))
    S = [list(inp.readline().strip()) for i in range(H)]

    max_cost = 0
    for start_h in range(H):
        for start_w in range(W):
            costs = get_costs(S)
            cost = walk(start_h, start_w, 1, costs)
            if cost > max_cost:
                max_cost = cost
            # print("--- cost={}".format(max_cost))
            # print_costs(costs)
            # print()

    return str(max_cost - 1)


def main():
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    main()

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 is_kabe(v1, v2):
    if S[v1][v2] == '#':
        return True
    else:
        return False

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

    m[v1][v2] = 0
    q = [[v1, v2]]
    while q:
        mass = q.pop(0)
        # print('mass', mass)
        # print('--', m)
        a = mass[0]
        b = mass[1]
        next_cost = m[a][b] + 1
        if a - 1 >= 0:
            up = m[a-1][b]
            if not is_kabe(a-1, b) and up is None:
                m[a-1][b] = next_cost
                q.append([a-1, b])
        if a + 1 < H:
            down = m[a+1][b]
            if not is_kabe(a+1, b) and down is None:
                m[a+1][b] = next_cost
                q.append([a+1, b])
        if b - 1 >= 0:
            left = m[a][b-1]
            if not is_kabe(a, b-1) and left is None:
                m[a][b-1] = next_cost
                q.append([a, b-1])
        if b + 1 < W:
            right = m[a][b+1]
            if not is_kabe(a, b+1) and right is None:
                m[a][b+1] = next_cost
                q.append([a, b+1])

    # print(m)
    mx = 0
    for i in range(H):
        for j in range(W):
            cost = m[i][j]
            if cost is not None:
                mx = max(mx, cost)
    return mx


r = 0
for i in range(H):
    for j in range(W):
        x = bfs(i, j)
        r = max(r, x)
print(r)

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 is_kabe(v1, v2):
    if S[v1][v2] == '#':
        return True
    else:
        return False

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

    m[v1][v2] = 0
    q = [[v1, v2]]
    while q:
        mass = q.pop(0)
        # print('mass', mass)
        # print('--', m)
        a = mass[0]
        b = mass[1]
        next_cost = m[a][b] + 1
        if a - 1 >= 0:
            up = m[a-1][b]
            if not is_kabe(a-1, b) and up is None:
                m[a-1][b] = next_cost
                q.append([a-1, b])
        if a + 1 < H:
            down = m[a+1][b]
            if not is_kabe(a+1, b) and down is None:
                m[a+1][b] = next_cost
                q.append([a+1, b])
        if b - 1 >= 0:
            left = m[a][b-1]
            if not is_kabe(a, b-1) and left is None:
                m[a][b-1] = next_cost
                q.append([a, b-1])
        if b + 1 < W:
            right = m[a][b+1]
            if not is_kabe(a, b+1) and right is None:
                m[a][b+1] = next_cost
                q.append([a, b+1])

    # print(m)
    mx = 0
    for i in range(H):
        for j in range(W):
            cost = m[i][j]
            if cost:
                mx = max(mx, cost)
    return mx


r = 0
for i in range(H):
    for j in range(W):
        x = bfs(i, j)
        r = max(r, x)
print(r)

Submission status: Wrong Answer

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

for y in range(H):
  for x in range(W):
    if S[y][x]=="#":
      continue
    D=[[400]*W for i in range(H)]
    D[y][x]=0
    q=[]
    q.append([x,y])
    while len(q)>0:
      c=list(q.pop(0))
      for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
        if c[1]+dy<0 or c[1]+dy>=H:
          continue
        if c[0]+dx<0 or c[0]+dx>=W:
          continue
        if S[c[1]+dy][c[0]+dx]==".":
          if D[c[1]+dy][c[0]+dx]>D[c[1]][c[0]]+1:
            D[c[1]+dy][c[0]+dx]=D[c[1]][c[0]]+1
            q.append([c[0]+dx,c[1]+dy])
    A=[[D[y][x] if D[y][x]!=400 else -1 for x in range(W)] for y in range(H)]
    m=max(m,max(max(A)))
print(m)

Submission status: Wrong Answer

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

for y in range(H):
  for x in range(W):
    if S[y][x]=="#":
      continue
    D=[[400]*W for i in range(H)]
    D[y][x]=0
    q=[]
    q.append([x,y])
    while len(q)>0:
      c=list(q.pop(0))
      for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
        if c[1]+dy<0 or c[1]+dy>=H:
          continue
        if c[0]+dx<0 or c[0]+dx>=W:
          continue
        if S[c[1]+dy][c[0]+dx]==".":
          if D[c[1]+dy][c[0]+dx]>D[c[1]][c[0]]+1:
            D[c[1]+dy][c[0]+dx]=D[c[1]][c[0]]+1
            q.append([c[0]+dx,c[1]+dy])
        else:
          D[c[1]+dy][c[0]+dx]=-1
    m=max(m,max(max(D)))
print(m)

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

@mt
def slv(H, W, S):
    def cand(v):
        i, j = v
        r = []
        if i > 0 and S[i-1][j] == '.':
            r.append((i-1, j))

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

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

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

        return r

    def bfs(s):
        q = deque()
        q.append(s)
        d = {}
        d[s] = 0
        while q:
            u = q.popleft()
            for v in cand(u):
                if v not in d:
                    d[v] = d[u] + 1
                    q.append(v)
        return max(d.values())

    ans = 0
    for i in range(H):
        for j in range(W):
            l = bfs((i, j))
            ans = max(ans, l)
    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 sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    H, W = map(int, input().split())
    S = [['#'] * (W+2)] + [['#'] + list(input()) + ['#'] for _ in range(H)] + [['#'] * (W+2)]
    direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    ans = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            init = (i, j)
            que = deque()
            que.append(init)
            dist = [[-1 for _ in range(W+2)] for _ in range(H+2)]
            dist[i][j] = 0

            while que:
                qh, qw = que.popleft()
                for dh, dw in direction:
                    h = qh + dh
                    w = qw + dw
                    if S[h][w] == '#' or dist[h][w] >= 0:
                        continue
                    dist[h][w] = dist[qh][qw] + 1
                    que.append((h, w))
            ans = max(ans, max([max(i) for i in dist]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import queue
import copy
D = ((0, -1), (0, 1), (-1, 0), (1, 0))

def bfs(S, s):
    M = copy.deepcopy(S)
    q = queue.Queue()
    q.put((s[0], s[1], 0))
    dis = 0

    while not q.empty():
        cur = q.get()

        for d in D:
            x = cur[0] + d[0]
            y = cur[1] + d[1]
            if M[y][x] != '#':
                M[y][x] = '#'
                q.put((x, y, cur[2]+1))
                dis = max(dis, cur[2] + 1)

    return dis


H, W = map(int, input().split())
S = [None]*(H+2)

S[0] = ['#'] * (W + 2)
for h in range(1, H+1):
    S[h] = ['#'] + [c for c in input()] + ['#']
S[-1] = ['#'] * (W + 2)

ans = 0
for sy in range(1, H+1):
    for sx in range(1, W+1):
        if S[sy][sx] != '#':
            ans = max(ans, bfs(S, (sx, sy)))

print(ans)

Submission status: Wrong Answer

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

#output
import numpy as np
INF = -1
dp = np.full((H, W), INF)

dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

        while len(q):
            x, y = q.pop()

            if x == gx and y == gy:
                break

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

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

L = []
for h1 in range(H):
    for h2 in range(H):
        for w1 in range(W):
            for w2 in range(W):
                if h1 != "#" and h2 != "#" and w1 != "#" and w2 != "#":
                    dp = np.full((H, W), INF)
                    p = clear_maze(h1, w1, h2, w2, S)
                    if p != INF:
                        L.append(p)
print(max(L))

Submission status: Wrong Answer

Solution code:
from collections import deque
 
# (sx, sy) から 全点への最短距離を求める
# 辿り着けないと INF
def bfs(maze, sx, sy, n, m):
    # すべての点を 0 で初期化
    d = [[0] * m for i in range(n)]
 
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
 
    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
 
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
 
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
 
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == 0:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
 
    return max(max(d))
 
 
n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
 
#print(maze)
 
bfs_list = [0]
 
for i in range(n):
  for j in range(m):
    # スタートとゴールの座標を探す
      sx = i
      sy = j
      if maze[sx][sy] == "#":
      	continue
      bfs_list.append(bfs(maze, sx, sy, n, m))
 
print(max(bfs_list))

Submission status: Wrong Answer

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

#output
import numpy as np
INF = 10**5
dp = np.full((H, W), INF)

dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

        while len(q):
            x, y = q.pop()

            if x == gx and y == gy:
                break

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

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

L = []
for h1 in range(H):
    for h2 in range(H):
        for w1 in range(W):
            for w2 in range(W):
                if h1 != "#" and h2 != "#" and w1 != "#" and w2 != "#":
                    dp = np.full((H, W), INF)
                    p = clear_maze(h1, w1, h2, w2, S)
                    if p != INF:
                        L.append(p)
print(max(L))

Submission status: Wrong Answer

Solution code:
from collections import deque
 
# (sx, sy) から 全点への最短距離を求める
# 辿り着けないと INF
def bfs(maze, sx, sy, n, m):
    # すべての点を 0 で初期化
    d = [[0] * m for i in range(n)]
 
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
 
    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
 
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる

        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
 
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == 0:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
 
    return max(max(d))
 
 
n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
 
#print(maze)
 
bfs_list = [0]
 
for i in range(n):
  for j in range(m):
    # スタートとゴールの座標を探す
      sx = i
      sy = j
      bfs_list.append(bfs(maze, sx, sy, n, m))

print(max(bfs_list))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 10**9 + 7


def to_graph(maze):
    H, W = len(maze), len(maze[0])

    g = [[INF] * (H * W) for _ in range(H * W)]

    for i, line in enumerate(maze):
        for j, s in enumerate(line):
            if i == j:
                g[i * W + j][i * W + j] = 0
            if s == '.':
                for neigh in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                    px, py = i + neigh[0], j + neigh[1]
                    if maze[px][py] == '.':
                        g[i * W + j][px * W + py] = 1

    return g


def main():
    H, W = map(int, input().split())
    maze = []
    maze.append(['#' for _ in range(W + 2)])
    for _ in range(H):
        maze.append(['#'] + list(input()) + ['#'])
    maze.append(['#' for _ in range(W + 2)])

    g = to_graph(maze)

    n = len(g)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])

    current_max = 0
    for line in g:
        for v in line:
            if v < INF and v > current_max:
                current_max = v

    print(current_max)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

N, M, = map(int, input().split())
L = [list(input().strip())  for _ in range(N)]

ans = 0
for _i in range(N):
    for _j in range(M):
        for _k in range(N):
            for _l in range(M):
                if _i == _k and _j == _l:
                    continue

                m = [[10 ** 18 for _ in range(M)] for _ in range(N)]
                def bfs(i, j, c):
                    if m[i][j] <= c:
                        return
                    if L[i][j] == "#":
                        return

                    m[i][j] = c
                    if L[i][j] == "G":
                        return
                    if i + 1 < N:
                        bfs(i + 1, j, c + 1)
                    if i - 1 >= 0:
                        bfs(i - 1, j, c + 1)
                    if j + 1 < M:
                        bfs(i, j + 1, c + 1)
                    if j - 1 >= 0:
                        bfs(i, j - 1, c + 1)

                if L[_i][_j] == "#" or L[_k][_l] == "#":
                    continue

                L[_i][_j] = "S"
                L[_k][_l] = "G"

                bfs(_i, _j, 0)
                if m[_k][_j] != 10 ** 18:
                    ans = max(ans, m[_k][_l])
                
                L[_i][_j] = "."
                L[_k][_l] = "."

print(ans)

Submission status: Wrong Answer

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

#output
import numpy as np
INF = 10**5
dp = np.full((H, W), INF)

dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

        while len(q):
            x, y = q.pop()

            if x == gx and y == gy:
                break

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

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

L = []
for h1 in range(H):
    for h2 in range(H):
        for w1 in range(W):
            for w2 in range(W):
                dp = np.full((H, W), INF)
                p = clear_maze(h1, w1, h2, w2, S)
                if p != INF:
                    L.append(p)

print(max(L))

Submission status: Wrong Answer

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

#output
import numpy as np
INF = 10**10
dp = np.full((H, W), INF)

dx = [1, 0, -1, 0]
dy = [0, 1, 0 ,-1]

def clear_maze(sx, sy, gx, gy, maze):
    def bfs():
        q = []
        q.insert(0, (sx, sy))
        dp[sx, sy] = 0

        while len(q):
            x, y = q.pop()

            if x == gx and y == gy:
                break

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

                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and dp[nx, ny] == INF:
                    q.insert(0, (nx, ny))
                    dp[nx, ny] = dp[x, y] + 1
        return dp[gx, gy]
    return bfs()

L = []
for h1 in range(H):
    for h2 in range(H):
        for w1 in range(W):
            for w2 in range(W):
                dp = np.full((H, W), INF)
                p = clear_maze(h1, w1, h2, w2, S)
                if p != INF:
                    L.append(p)

print(max(L))

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
flag=0
st=(-1,-1)
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            flag=1
            st=(i,j)
            break
    if flag==1:
        break
q=deque([st])
dx=[1,-1,0,0]
dy=[0,0,1,-1]
dist=[[-1 for j in range(W)] for i in range(H)]
dist[st[0]][st[1]]=0
while(len(q)>0):
    r=q.popleft()
    x,y=r
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<H and 0<=ny<W:
            if dist[nx][ny]==-1 and S[nx][ny]==".":
                dist[nx][ny]=dist[x][y]+1
                q.append((nx,ny))
for i in range(H):
    for j in range(W):
        if dist[st[0]][st[1]]<dist[i][j]:
            st=(i,j)
q=deque([st])
dx=[1,-1,0,0]
dy=[0,0,1,-1]
dist=[[-1 for j in range(W)] for i in range(H)]
dist[st[0]][st[1]]=0
while(len(q)>0):
    r=q.popleft()
    x,y=r
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<H and 0<=ny<W:
            if dist[nx][ny]==-1 and S[nx][ny]==".":
                dist[nx][ny]=dist[x][y]+1
                q.append((nx,ny))
print(max([max(i) for i in dist]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        print(deque)
        x, y = queue.popleft()
        print(x, y)
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))


answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
import copy

def cha(maze,h,w):
    maze = copy.deepcopy(maze)
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                maze[i][j] = math.inf
            if maze[i][j] == "#":
                maze[i][j] = -1
    return maze

def bfs(maze,sy,sx):
    maze = copy.deepcopy(maze)
    maze[sy][sx] = 0
    que = deque([[sy,sx]])
    while que:
        y,x = que.popleft()
        for next_y,next_x in [(y+1,x),(y-1,x),(y,x+1),(y,x-1)]:
            if maze[next_y][next_x] == -1:
                continue
            dist = maze[next_y][next_x]
            if dist > maze[y][x] + 1:
                maze[next_y][next_x] = maze[y][x] + 1
                que.append([next_y,next_x])
    return maze

def search(maze):
    c = 0
    for i in maze:
        i.append(c)
        c = max(i)
    return c

def _main():
    h,w = map(int,input().split())
    maze = [["#"]*w]
    for _ in range(h):
        maze.append(list(input()))
    maze.append(["#"]*w)
    for i in range(h+2):
        maze[i].insert(0,"#")
        maze[i].insert(w+1,"#")
    C = 0
    for sy in range(h+2):
        for sx in range(w+2):
            if maze[sy][sx] == ".":
                C = max((search(bfs(cha(maze,h+2,w+2),sy,sx)),C))
    print(C)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

  ans = 0
  for si in range(H):
    for sj in range(W):
      if S[si][sj] == '#':
        continue

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

      start = (si, sj)
      if dist[si][sj] == -1:
        dist[si][sj] = 0
        q.append(start)

      while q:
        qi, qj = q.popleft()
        for di, dj in (-1, 0), (0, -1), (1, 0), (0, 1):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= H:
            continue
          if nj < 0 or nj >= W:
            continue
          if S[ni][nj] == '#':
            continue
          if dist[ni][nj] == -1:
            dist[ni][nj] = dist[qi][qj]+1
            q.append((ni, nj))
          ans = max(ans, dist[qi][qj])
    return ans


if __name__ == "__main__":
  print(main())