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
import math

h, w = list(map(int, input().split()))
SHWs = [input() for i in range(h)]
#print(SHWs)


def bfs(sy, sx, gy, gx):
    visited = [[-1]*w for i in range(h)]
    visited[sy][sx] = 0
    que = deque([[sy, sx]])
    while que:
        
        y,x = que.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_y, next_x = y+i, x+j
            # print(visited)
            if next_y < 0 or next_x < 0 or next_y > h-1 or next_x > w-1:
                continue
            if SHWs[next_y][next_x] == '.' and (visited[next_y][next_x] == -1 or visited[next_y][next_x] > visited[y][x]+1):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
    
    return visited[gy][gx]

            
ans = 0
for sy in range(h):
    for sx in range(w):
        for gy in range(h):
            for gx in range(w):
                if sy == gy and sx == gx:
                    continue
                count = bfs(sy=sy, sx=sx, gy=gy, gx=gx) 
                if count > ans:
                    ans = count


print(ans)

Submission status: Wrong Answer

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

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

def bfs(S, H, W, start, goal):
    INF = 100000000
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        if (x, y) == goal:
            break
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == INF:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return distance[goal[1]][goal[0]]

ans = 0
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                if (i, j) == (k, l) or S[i][j] == "#" or S[k][l] == "#":
                    continue
                if i < H/2 or j < W/2 or k < H/2 or l < W/2:
                    continue
                start = (j, i)
                goal = (l, k)
                ans = max(ans, bfs(S, H, W, start, goal))
print(ans)

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:
def main():
    H, W = [int(s) for s in input().split()]
    MAP = []
    for h in range(H):
        row = input()
        MAP.append(list(row))

    points = []
    for h in range(H):
        for w in range(W):
            if MAP[h][w] == '.':
                points.append((h, w))

    max_step = 0
    for start_i in range(len(points) - 1):
        for goal_i in range(start_i + 1, len(points)):
            max_step = max(max_step, count_step(MAP, points[start_i], points[goal_i]))

    print(max_step)


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


def count_step(MAP, start, goal):
    candidates = [(start, get_distance(start, goal), 0)]

    checked = {}
    while True:
        pos, _, step = candidates.pop(0)
        for m in MOVES:
            next_pos = (pos[0] + m[0], pos[1] + m[1])
            if next_pos in checked:
                continue
            if not is_valid(MAP, next_pos):
                continue
            checked[next_pos] = True
            distance = get_distance(next_pos, goal)
            if distance == 0:
                return step + 1
            candidates.append((next_pos, distance, step + 1))
        candidates.sort(key=lambda x: x[1] + x[2])


def get_distance(p, goal):
    return abs(p[0] - goal[0]) + abs(p[1] - goal[1])


def is_valid(MAP, pos):
    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= len(MAP) or pos[1] >= len(MAP[0]):
        return False

    if MAP[pos[0]][pos[1]] == '#':
        return False
    return True


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    walls = [[c == '#' for c in s] for s in args[1:]]

    head = None
    for y in range(h):
        for x in range(w):
            if not walls[y][x]:
                head = (x, y)
                break
        if head:
            break

    tail = None
    cur, prev, count = 0, -1, 0

    while cur != prev:
        passed = [[False]*w for _ in range(h)]
        Q = deque([head+(0,)])
        prev = cur
        while Q:
            x, y, c = Q.popleft()
            if walls[y][x] or passed[y][x]:
                continue

            passed[y][x] = True
            if count < c:
                count = max(c, count)
                tail = (x, y)

            if 0 < x:
                Q.append((x-1, y, c+1))
            if x+1 < w:
                Q.append((x+1, y, c+1))
            if 0 < y:
                Q.append((x, y-1, c+1))
            if y+1 < h:
                Q.append((x, y+1, c+1))
        cur = count
        head = tail

    return str(count)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

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

Q=deque()
D=[[-1 for __ in range(W) ] for _ in range(H)]
dl=[]
def bfs():
    global M,D,Q
    d_max=1
    while Q:
        i,j,d=Q.popleft()
        nc=0
        for ni,nj in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if ni<0 or nj<0 or ni>=H or nj>=W:
                continue
            if M[ni][nj]=='.' and D[ni][nj]<0:
                D[ni][nj]=d+1
                d_max=max(dmax,d+1)
                M[ni][nj]='x'
                Q.append((ni,nj,d+1))
    return d_max

ans=0
for i in range(H):
    for j in range(W):
        if M[i][j]=='.':
            dmax=0
            D[i][j]=0
            M[i][j]='x'
            for ni,nj in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
                if ni<0 or nj<0 or ni>=H or nj>=W:
                    continue
                if M[ni][nj]=='.' and D[ni][nj]<0:
                    D[ni][nj]=1
                    M[ni][nj]='x'
                    Q.append((ni,nj,1))
                    dmax+=bfs()
            ans=max(dmax,ans)

print(ans)

Submission status: Wrong Answer

Solution code:

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)
ans = 1
inf = 70
for i in range(h):
    for j in range(w):
        graph = [[inf for _ in range(w)] for l 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)
sx, sy = nextx, nexty
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
print(maxd)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque


def solve(S, s):
    if S[s[0]][s[1]] != ".":
        return -1
    queue = deque([s])
    visited = [[-1]*W for _ in range(H)]
    visited[s[0]][s[1]] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1,0], [-1,0], [0,1], [0,-1]):
            new_y, new_x = y+j, x+k
            if new_x in range(W) and new_y in range(H) and S[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
#    for v in visited:
#        print(v)
    return max(max(visited))


H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        ans = max(ans, solve(S, [i, l]))
print(ans)

Submission status: Wrong Answer

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


def calc_dist(s, start_i, start_j, goal_i, goal_j, h, w):
    from collections import deque

    result = 0
    d = deque()
    d.append((start_i, start_j))
    dist = [[0 for _ in range(w)] for _ in range(h)]
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[start_i][start_j] = True
    dxy = [(1, 0), (-1, 0), (0, -1), (0, 1)]

    while d:
        hd, wd = d.popleft()

        for dx, dy in dxy:
            nx = wd + dx
            ny = hd + dy

            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue

            if s[ny][nx] == '#':
                continue

            if visited[ny][nx]:
                continue

            visited[ny][nx] = True
            dist[ny][nx] = dist[hd][wd] + 1
            d.append((ny, nx))

            if nx == goal_j and ny == goal_i:
                for i in range(h):
                    for j in range(w):
                        result = max(result, dist[i][j])

                return result

    return result


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    ans = h - 1 + w - 1

    for start_i in range(h):
        for start_j in range(w):
            for goal_i in range(h):
                for goal_j in range(w):
                    if s[start_i][start_j] == '#':
                        continue

                    if s[goal_i][goal_j] == '#':
                        continue

                    ans = max(ans, calc_dist(s, start_i, start_j, goal_i, goal_j, h, w))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import copy
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))
grid_c = copy.deepcopy(grid)
res = 0
kouho = []
for i in range(h):
    for j in range(w):
        if grid_c[i][j] != '.':
            continue
        kouho.append((i, j))
        queue = [(i, j, 0)]
        while queue:
            c_i, c_j, level = queue.pop(0)
            grid_c[c_i][c_j] = '#'
            changed = False
            for n_i, n_j in ((c_i - 1, c_j), (c_i + 1, c_j), (c_i, c_j - 1), (c_i, c_j + 1)):
                if 0 <= n_i < h and 0 <= n_j < w and grid_c[n_i][n_j] == '.':
                    queue.append((n_i, n_j, level + 1))
                    changed = True
            if changed == False:
                kouho.append((c_i, c_j))
res = 0
for i, j in kouho:
    if grid[i][j] != '.':
        continue
    visited = []
    queue = [(i, j, 0)]
    while queue:
        c_i, c_j, level = queue.pop(0)
        visited.append((c_i, c_j))
        for n_i, n_j in ((c_i - 1, c_j), (c_i + 1, c_j), (c_i, c_j - 1), (c_i, c_j + 1)):
            if 0 <= n_i < h and 0 <= n_j < w and grid[n_i][n_j] == '.' and (n_i, n_j) not in visited:
                queue.append((n_i, n_j, level + 1))
    res = max(res, level)
print(res)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())                                   # ノードの訪問済みフラグ
a = [['#']+[i for i in input()]+['#'] for j in range(H)]
a = [['#' for i in range(W+2)]]+a+[['#' for i in range(W+2)]]
b=[x for x in a if "." in x] # "#"が入っている行のみ抽出した2次元配列 右辺の意味合いとしては，「aの各行を代入したxについて，もしx内に#があればリストに加える」
c=zip(*[y for y in zip(*b) if "." in y]) # yは各列を示しており，"#"が入っている列のみを抽出した2次元配列
graph = []
for d in c:
  graph.append(list(d))
H = len(graph)
W = len(graph[0])
for i in range(H):
  graph[i].append('#')
  graph[i].insert(0,'#')
graph = [['#' for i in range(W+2)]] + graph + [['#' for i in range(W+2)]]
import copy
# dfs:ノードvについて、エッジで接続した未訪問のノードを浅いほうから訪問(LILO)
def dfs(start):
    visited = [[False for i in range(W+2)] for j in range(H+2)]
    step = 0
    queue = [start]
    queue_2 = []
    steps = []
    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]] 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 step-1
  
hidariue = [1,1]
migiue = [1,W]
hidarisita = [H,1]
migisita = [H,W]
while True:
  if graph[hidariue[0]][hidariue[1]]=='#':
    hidariue[0]+=1
  elif graph[migiue[0]][migiue[1]]=='#':
    migiue[0]+=1
  elif graph[hidarisita[0]][hidarisita[1]]=='#':
    hidarisita[0]-=1
  elif graph[migisita[0]][migisita[1]]=='#':
    migisita[0]-=1
  else:
    break

a = dfs(hidariue)
b = dfs(hidarisita)
c = dfs(migiue)
d = dfs(migisita)
print(max(a,b,c,d))

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

maxd = 0
sx, sy = init_start(maze)
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
sx, sy = nextx, nexty
distance = calc_distance(maze)
print(maxd)

Submission status: Wrong Answer

Solution code:
# import sys, re, os
# from collections import deque, defaultdict, Counter
# from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from itertools import permutations, combinations, product, accumulate
# from operator import itemgetter, mul
# from copy import deepcopy
# from string import ascii_lowercase, ascii_uppercase, digits
# from fractions import gcd
 
# def input(): return sys.stdin.readline().strip()
# def INT(): return int(input())
# def MAP(): return map(int, input().split())
# def S_MAP(): return map(str, input().split())
# def LIST(): return list(map(int, input().split()))
# def S_LIST(): return list(map(str, input().split()))
 
# sys.setrecursionlimit(10 ** 9)
# INF = float('inf')
# mod = 10 ** 9 + 7

# # 最大公約数 
# def gcd(a, b):
#   if a < b:
#       a, b = b, a
#   while a % b != 0:
#       a, b = b, a % b
#   return b

# # 最小公倍数
# def lcm(a, b):
#   y = a*b / gcd(a, b)
#   return int(y)

# H, W = MAP()


# L = []
# for i in range(m):
#   l = list(input())
#   L.append(l)
# print(L)


from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
# print(maze)
n = H
m = W

# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sy, sx):
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]

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

    # for i in range(n):
    #     for j in range(m):
    #         # スタートとゴールの座標を探す
    #         if maze[i][j] == "S":
    #             sx = i
    #             sy = j
    #         if maze[i][j] == "G":
    #             gx = i
    #             gy = j

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        # if p[0] == gx and p[1] == gy:
        #     break
        # 移動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] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d



ans = 0
l = []
for h in range(H):
    for w in range(W):
        # ans = max(ans, bfs(w, h, w1, h1))
        # s = bfs(w, h)
        for s in bfs(w, h):
          # print(s)
          for j in s:
              if j != float("inf"):

                    l.append(j)
print(max(l))

# print(ans)
# print(bfs())

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right, bisect_left
from itertools import groupby, permutations, combinations
from fractions import gcd
import numpy as np
from sys import stdin, stderr
from collections import deque


def lcm(x, y):
    return (x * y) // gcd(x, y)


def movement_max(start_h, start_w, maze):
    H, W = len(maze), len(maze[0])
    score = []
    unvisited = deque()
    visited = []
    # unvisited.add(start_h + start_w*100)
    for h in range(H):
        score.append([1000] * W)
        visited.append([False] * W)
        # for w in range(W):
        #     if maze[h][w] == "#":
        #         visited.add(h + w*100)
    score[start_h][start_w] = 0
    unvisited.append([start_h, start_w])
    ret = 0
    while len(unvisited) > 0:
        h, w = unvisited.pop()
        # hw = unvisited.pop()
        # h = hw % 100
        # w = hw // 100
        # visited.add(hw)
        visited[h][w] = True
        if maze[h][w] == "#":
            continue
        s = score[h][w] + 1
        if h > 0:
            score[h-1][w] = min(s, score[h-1][w])
            if not visited[h-1][w]:
                unvisited.append([h-1, w])
            # if (h-1 + w*100) not in visited:
            #     unvisited.add(h-1 + w*100)

        if h < H - 1:
            score[h+1][w] = min(s, score[h+1][w])
            if not visited[h+1][w]:
                unvisited.append([h+1, w])
            # if (h+1 + w*100) not in visited:
            #     unvisited.add(h+1 + w*100)
        if w > 0:
            score[h][w-1] = min(s, score[h][w-1])
            if not visited[h][w-1]:
                unvisited.append([h, w-1])
            # if (h + (w-1)*100) not in visited:
            #     unvisited.add(h + (w-1)*100)
        if w < W - 1:
            score[h][w+1] = min(s, score[h][w+1])
            if not visited[h][w+1]:
                unvisited.append([h, w+1])
            # if (h + (w+1)*100) not in visited:
            #     unvisited.add(h + (w+1)*100)
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                continue
            ret = max(score[h][w], ret)
    return ret


def main():
    H, W = [int(x) for x in input().split()]
    maze = [""] * H
    score = []
    for i in range(H):
        maze[i] = input()
        score.append([-1] * W)
    result = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                continue
            score[h][w] = movement_max(h, w, maze)
            result = max(result, movement_max(h, w, maze))
            # print(result)
        # print(score[h])
    return result


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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())

move = [[0 for i in range(W)]for i in range(H)]

S = ["#" for i in range(H)]

M = 0

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

print(S)





def keisoku(sx,sy,ex,ey):
    global W
    global H
    end = False

    count = 1

    kyori = [[-1 for i in range(W)]for i in range(H)]
    kyori[ey][ex] == 0
    if ey < H-1:
        
        if S[ey+1][ex] == ".":
            kyori[ey+1][ex] = 1
    if ey >= 1:
        if S[ey-1][ex] == ".":
            kyori[ey-1][ex] = 1
    if ex < W -1:
            
        if S[ey][ex+1] == ".":
            kyori[ey][ex+1] = 1
    if ex >= 1:
        if S[ey][ex-1] == ".":
            kyori[ey][ex-1] = 1

    while(not end):
        for x in range(W):
            for y in range(H):
                if kyori[y][x] == count:
                    
                    if y < H -1:
                            
                        if S[y+1][x] == ".":
                            kyori[y+1][x] = count +1
                    if y >= 1:
                            
                        if S[y-1][x] == ".":
                            kyori[y-1][x] = count +1
                    if x < W -1:
                            
                        if S[y][x+1] == ".":
                            kyori[y][x+1] = count +1

                    if x >= 1:
                            
                        if S[y][x-1] == ".":
                            kyori[y][x-1] = count +1

        
        if kyori[sy][sx] != -1:
            end = True
        count += 1
    
    return kyori[sy][sx]
                    
for sx in range(W):
    for sy in range(H):
        for ex in range(W):
            for ey in range(H):
                if S[sy][sx] == "#" or S[ey][ex] == "#" or (sx == ex and sy == ey):
                    continue

                newmax = keisoku(sx,sy,ex,ey)
                if newmax > M:
                    M = newmax 

print(M)

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 > 2200:
                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 defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop


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

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

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


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

    return False


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

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

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

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

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


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

if l == -1:
    l = 0

print(l)