Problem:


Score : 400 points

Problem Statement

Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.

The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is #, and a "road" square if S_{ij} is ..

From a road square, you can move to a horizontally or vertically adjacent road square.

You cannot move out of the maze, move to a wall square, or move diagonally.

Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.

Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.

In this situation, find the maximum possible number of moves Aoki has to make.

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

Any road square can be reached from any road square in zero or more moves.

Input

Input is given from Standard Input in the following format:

H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

Output

Print the maximum possible number of moves Aoki has to make.

Sample Input 1

3 3
...
...
...

Sample Output 1

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Sample Input 2

3 5
...#.
.#.#.
.#...

Sample Output 2

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Wrong Answer

Solution code:
from collections import deque

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


def successors(x, y):
    locations = []
    # 下に行けるかの判定
    if (x + 1 < H) and (maze[x + 1][y] != '#'):
        locations.append((x + 1, y))
    # 上に行けるかの判定
    if (x - 1 >= 0) and (maze[x - 1][y] != '#'):
        locations.append((x - 1, y))
    # 右に行けるかの判定
    if (y + 1 < W) and (maze[x][y + 1] != '#'):
        locations.append((x, y + 1))
    # 左に行けるかの判定
    if (y - 1 >= 0) and (maze[x][y - 1] != '#'):
        locations.append((x, y - 1))
    return locations


def bfs(initial, goal, successors):
    frontier = deque()
    frontier.append((initial, None))
    # tuple
    explored = {initial}

    while len(frontier):
        current_node = frontier.popleft()
        current_state = current_node[0]
        if current_state == goal:
            return current_node
        for child in successors(*current_state):
            if str(child) in [str(i) for i in explored]:
                continue
            explored.add(child)
            frontier.append((child, current_node))
    return None


def node_to_path_count(node):
    counter = 0
    while node[1] is not None:
        counter += 1
        node = node[1]
    return counter


ans = 0
for x in range(H):
    for y in range(W):
        if maze[x][y] == '.':
            for gx in range(H):
                for gy in range(W):
                    if (x != gx and y != gy) and maze[gx][gy] == '.':
                        solution = bfs((x, y), (gx, gy), successors)
                        counter = node_to_path_count(solution)
                        if ans < counter:
                            ans = counter

print(ans)

Submission status: Wrong Answer

Solution code:
import queue


def solve(maze, init_y, init_x, H, W):
    distances = [[-1 for _ in range(W)] for _ in range(H)]

    distances[init_y][init_x] = 0

    def is_inside(y, x):
        return 0 <= x < W and 0 <= y < H

    def need_to_search(y, x):
        return maze[y][x] != "#" and distances[y][x] == -1

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

    q = queue.Queue()

    for dy, dx in four_directions:
        ny, nx = init_y+dy, init_x+dx
        if not is_inside(ny, nx):
            continue
        if need_to_search(ny, nx):
            q.put([ny, nx])
            distances[ny][nx] = 1

    while not q.empty():
        y, x = q.get()
        d = distances[y][x]

        for dy, dx in four_directions:
            ny, nx = y+dy, x+dx
            if not is_inside(ny, nx):
                continue
            if need_to_search(ny, nx):
                q.put([ny, nx])
                distances[ny][nx] = d+1

    return max(max(distances))


def main():
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    farthest = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == "#":
                continue
            distance = solve(maze, i, j, H, W)
            farthest = max(distance, farthest)

    print(farthest)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import copy
from collections import deque

n, m = map(int, input().split())

# マス目と距離保存のための箱を作成
d = []
mas = []
for i in range(n):
    mas.extend(list(map(list, input().split())))
    d.append([float("nan")] * m)


def tansaku(sx, sy, d):
    local_d = copy.deepcopy(d)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    local_d[sx][sy] = 0
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        for i in range(4):
            # 移動4方向をループ
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and mas[nx][ny] != "#"
                and not local_d[nx][ny] == local_d[nx][ny]
            ):
                # 移動できるならキューに入れ，その点の距離を p からの距離 +1 で確定する．最後Nan判定
                que.append((nx, ny))
                local_d[nx][ny] = local_d[p[0]][p[1]] + 1
    d_max = max(list([max(local_d[0]), max(local_d[n - 1])]))
    for i in range(n):
        d_max = max([local_d[i][0], local_d[i][m - 1], d_max])
    return d_max


dis = 0
for i in range(n):
    dis_i = tansaku(i, 0, d)
    if dis_i > dis:
        dis = copy.copy(dis_i)
    dis_i = tansaku(i, m - 1, d)
    if dis_i > dis:
        dis = copy.copy(dis_i)


for i in range(m):
    dis_i = tansaku(0, i, d)
    if dis_i > dis:
        dis = copy.copy(dis_i)

    dis_i = tansaku(n - 1, i, d)
    if dis_i > dis:
        dis = copy.copy(dis_i)


print(dis)

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 for _ in range(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])

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

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


def successors(x, y):
    locations = []
    # 下に行けるかの判定
    if (x + 1 < H) and (maze[x + 1][y] != '#'):
        locations.append((x + 1, y))
    # 上に行けるかの判定
    if (x - 1 >= 0) and (maze[x - 1][y] != '#'):
        locations.append((x - 1, y))
    # 右に行けるかの判定
    if (y + 1 < W) and (maze[x][y + 1] != '#'):
        locations.append((x, y + 1))
    # 左に行けるかの判定
    if (y - 1 >= 0) and (maze[x][y - 1] != '#'):
        locations.append((x, y - 1))
    return locations


def bfs(initial, goal, successors):
    frontier = deque()
    frontier.append((initial, None))
    # tuple
    explored = {initial}

    while len(frontier):
        current_node = frontier.popleft()
        current_state = current_node[0]
        if current_state == goal:
            return current_node
        for child in successors(*current_state):
            if str(child) in [str(i) for i in explored]:
                continue
            explored.add(child)
            frontier.append((child, current_node))
    return None


def node_to_path_count(node):
    counter = 0
    while node[1] is not None:
        counter += 1
        node = node[1]
    return counter


ans = 0
for x in range(H):
    for y in range(W):
        for gx in range(H):
            for gy in range(W):
                if (x != gx and y != gy) and maze[x][y] == '.' and maze[gx][gy] == '.':
                    solution = bfs((x, y), (gx, gy), successors)
                    counter = node_to_path_count(solution)
                    if ans < counter:
                        ans = counter

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 for _ in range(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)
    print()
    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:
from collections import deque
from itertools import combinations

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
d = {(x, y): [] for x in range(h) for y in range(w)}

for x in range(h):
    for y in range(w):
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w:
                if s[nx][ny] == '.':
                    d[(x, y)].append((nx, ny))

node = {k: d[k] for k in d if len(d[k])}
ans = 0
for (start, goal) in combinations(node, 2):
    queue = deque([(start, 0)])
    closed = {}
    while len(queue):
        pos, dist = queue.popleft()
        closed[pos] = dist
        if pos == goal:
            ans = max(dist, ans)
            break
        for neighbor in node[pos]:
            if neighbor not in closed:
                queue.append((neighbor, dist + 1))

print(ans)

Submission status: Wrong Answer

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

import copy
from collections import deque

n, m = map(int, input().split())

# マス目と距離保存のための箱を作成
d = []
mas = []
for i in range(n):
    mas.extend(list(map(list, input().split())))
    d.append([float("nan")] * m)


def tansaku(sx, sy, d):
    local_d = copy.deepcopy(d)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    local_d[sx][sy] = 0
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        for i in range(4):
            # 移動4方向をループ
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and mas[nx][ny] != "#"
                and not local_d[nx][ny] == local_d[nx][ny]
            ):
                # 移動できるならキューに入れ，その点の距離を p からの距離 +1 で確定する．最後Nan判定
                que.append((nx, ny))
                local_d[nx][ny] = local_d[p[0]][p[1]] + 1
    d_max = max(list([max(local_d[0]), max(local_d[n - 1])]))
    for i in range(n):
        d_max = max([local_d[i][0], local_d[i][m - 1], d_max])
    return d_max


dis = 0
for i in range(n):
    dis_i = tansaku(i, 0, d)
    if dis_i > dis:
        dis = dis_i
    dis_i = tansaku(i, m - 1, d)
    if dis_i > dis:
        dis = dis_i

for i in range(m):
    dis_i = tansaku(0, i, d)
    if dis_i > dis:
        dis = dis_i
    dis_i = tansaku(n - 1, i, d)
    if dis_i > dis:
        dis = dis_i

print(dis)

Submission status: Wrong Answer

Solution code:
import queue

q = queue.Queue()

H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
ans = 0
vec_x = [1,0,-1,0]
vec_y = [0,1,0,-1]

def bfs(sx,sy):
    #最短距離を格納する配列
    d = [[0 for i in range(W)] for j in range(H)]
    q.put([sx,sy])
    while not q.empty():
        current_xy = q.get()
        #4方向のループ
        for i in range(4):
            nx = current_xy[0] + vec_x[i]
            ny = current_xy[1] + vec_y[i]

            #移動が可能か
            if( (nx >= 0 and nx < W ) and (ny >= 0 and ny < H ) ):
                if S[ny][nx] != "#":
                    #すでにおとずれていないか
                    if d[ny][nx] == 0:
                        q.put([nx,ny])
                        d[ny][nx] = d[current_xy[1]][current_xy[0]] + 1
    return d[current_xy[1]][current_xy[0]]

for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == "#":
            continue
        if ans <= bfs(sx,sy):
            ans = bfs(sx,sy)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
for i in range(H):
    maze.append(list(input()))
def bfs(sx,sy):
    INF = -1
    cost = [[INF]*W for _ in range(H)]
    P = deque()
    P.append([sx,sy])
    cost[sx][sy] = 0
    while len(P) != 0:
        p = P.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == INF:
                P.append([nx,ny])
                cost[nx][ny] = cost[p[0]][p[1]]+1
    return cost
def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            sx,sy = i,j
            cs = bfs(sx,sy)
            for k in range(len(cs)):
                if max(cs[k]) > ans:
                    ans = max(cs[k])
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

h,w=map(int,input().split())
d=[]
for i in range(h):
    s=input()
    d.append(s)
#p={}
x=h*w
p=[[500]*x for i in range(x)]
for i in range(x):
    for j in range(x):
        ih,iw=i//w,i%w
        jh,jw=j//w,j%w
        if "."==d[ih][iw]==d[jh][jw] and ih==jh and abs(iw-jw)==1:
            p[i][j]=1
            p[j][i]=1
        if "."==d[ih][iw]==d[jh][jw] and iw==jw and abs(ih-jh)==1:
            p[i][j]=1
            p[j][i]=1
for i in range(x):
    for j in range(x):
        for k in range(x):
            ih,iw=i//w,i%w
            jh,jw=j//w,j%w
            kh,kw=k//w,k%w
            p[j][k]=min(p[j][k],p[j][i]+p[i][k])
ans=0
for i in p:
    for j in i:
        if j!=500:
            ans=max(ans,j)
print(ans)

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:]]

    count = 0
    Q = deque()

    for y in range(h):
        for x in range(w):
            if walls[y][x]:
                continue

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

                passed[y][x] = True
                count = max(c, count)

                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))

    return str(count)


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

Submission status: Wrong Answer

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


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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
h, w = list(map(int, input().split()))
 
s = []
for i in range(h):
    line = input()
    s.append(line)
 
ans = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        d = [[1<<10 for x in range(w)] for y in range(h)]
 
        stack = []
        stack.append((i, j))
        d[i][j] = 0
        while stack:
            y, x = stack.pop()
            if y > 0 and s[y-1][x] == '.' and d[y-1][x] > d[y][x]+1:
                d[y-1][x] = d[y][x] + 1
                stack.append((y-1, x))
            if x < w-1 and s[y][x+1] == '.' and d[y][x+1] > d[y][x]+1:
                d[y][x+1] = d[y][x] + 1
                stack.append((y, x+1))
            if y < h-1 and s[y+1][x] == '.' and d[y+1][x] > d[y][x]+1:
                d[y+1][x] = d[y][x] + 1
                stack.append((y+1, x))
            if x > 0 and s[y][x-1] == '.' and d[y][x-1] > d[y][x]+1:
                d[y][x-1] = d[y][x] + 1
                stack.append((y, x-1))
        ma = 0
        for y in range(h):
            for x in range(w):
                if d[y][x] > ma:
                    ma = d[y][x]

        ans.append(ma)
ans.sort()
print(ans[-1])

Submission status: Wrong Answer

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


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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + [input() for _ in range(H)] + ["#" * (W+2)]

ans = 0

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


def bfs(x, y):
    m = [[-1] * (W+2) for _ in range(H+2)]

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

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


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

Submission status: Wrong Answer

Solution code:
import collections

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

m = []
for _ in range(h):
    m.append(list(input()))


ans = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == '#':
            continue

        checked = [[False]*w for _ in range(h)]
        q = collections.deque()
        q.append((i, j, 0))
        while True:
            x, y, s = q.popleft()
            #print(q)

            if x > 0 and m[x-1][y] != '#' and checked[x-1][y] == False:
                q.append((x-1, y, s+1))
                checked[x-1][y] = True

            if x < h-1 and m[x+1][y] != '#' and checked[x+1][y] == False:
                q.append((x+1, y, s+1))
                checked[x+1][y] = True

            if y > 0 and m[x][y-1] != '#' and checked[x][y-1] == False:
                q.append((x, y-1, s+1))
                checked[x][y-1] = True

            if y < w-1 and m[x][y+1] != '#' and checked[x][y+1] == False:
                q.append((x, y+1, s+1))
                checked[x][y+1] = True

            ans = max(ans, s)

            if len(q) == 0:
                break

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]

def bfs(q):
  x,y,cnt=q.popleft()
  if x<0 or x>=w or y<0 or y>=h:
    return
  elif S[y][x]=='#':
    return
  elif memo[y][x]<0:
    memo[y][x]=cnt
    q.append([x-1,y,cnt+1])
    q.append([x+1,y,cnt+1])
    q.append([x,y-1,cnt+1])
    q.append([x,y+1,cnt+1])

ans=0
for x in range(w):
  for y in range(h):
    q=deque([(x,y,0)])
    memo=[[-1]*w for _ in range(h)]
    while q:
      bfs(q)
    ans=max(ans,max(max(memo)))
print(ans)

Submission status: Wrong Answer

Solution code:

from collections import deque



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

step=[[1,0],[-1,0],[0,1],[0,-1]]

mx=0
for h in range(H):
    for w in range(W):
        if S[h][w]=="#":continue
        chk=[[False]*W for i in range(H)]
        q=deque([[h,w,0]])
        chk[h][w]=True
        while q:
            y,x,c=q.popleft()
            for dh,dw in step:
                if y+dh<0 or y+dh>=H:continue
                if x+dw<0 or x+dw>=W:continue
                if chk[y+dh][x+dw]==False and S[y+dh][x+dw]==".":
                    c+=1
                    chk[y+dh][x+dw]=True
                    q.append([y+dh,x+dw,c])
                else:
                    mx=max(mx,c)

print(mx)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
S = np.array([list(readline().decode('utf-8').rstrip()) for _ in range(H)])


def adjacent_4(h, w):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        h_ = h + dh
        w_ = w + dw

        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


def bfs(S, visited, h, w, cnt):

    que = deque()
    for adj in adjacent_4(h, w):
        que.append([adj, cnt])

    while len(que) != 0:
        target, cnt_ = que.popleft()
        if (visited[target[0]][target[1]] !=
                -1) | (S[target[0]][target[1]] == '#'):
            continue
        visited[target[0]][target[1]] = cnt_
        for adj in adjacent_4(target[0], target[1]):
            que.append([adj, cnt_ + 1])


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

        visited = np.full(S.shape, -1)
        visited[h][w] = 0
        bfs(S, visited, h, w, 1)
        ans = max(ans, visited.max())

print(ans)

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(sx, sy):
    # すべての点を 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(h, w):
          # 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:
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:
from collections import deque

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


def successors(x, y):
    locations = []
    # 下に行けるかの判定
    if (x + 1 < H) and (maze[x + 1][y] != '#'):
        locations.append((x + 1, y))
    # 上に行けるかの判定
    if (x - 1 >= 0) and (maze[x - 1][y] != '#'):
        locations.append((x - 1, y))
    # 右に行けるかの判定
    if (y + 1 < W) and (maze[x][y + 1] != '#'):
        locations.append((x, y + 1))
    # 左に行けるかの判定
    if (y - 1 >= 0) and (maze[x][y - 1] != '#'):
        locations.append((x, y - 1))
    return locations


def bfs(initial, goal, successors):
    frontier = deque()
    frontier.append((initial, None))
    # tuple
    explored = {initial}

    while len(frontier):
        current_node = frontier.popleft()
        current_state = current_node[0]
        if current_state == goal:
            return current_node
        for child in successors(*current_state):
            if str(child) in [str(i) for i in explored]:
                continue
            explored.add(child)
            frontier.append((child, current_node))
    return None


def node_to_path_count(node):
    path = [node[0]]
    counter = 0
    while node[1] is not None:
        counter += 1
        node = node[1]
        path.append(node[0])
    path.reverse()
    #return path, counter
    return counter


ans = 0
for x in range(H):
    for y in range(W):
        for gx in range(H):
            for gy in range(W):
                if (x != gx and y != gy) and maze[x][y] == '.' and maze[gx][gy] == '.':
                    solution = bfs((x, y), (gx, gy), successors)
                    counter = node_to_path_count(solution)
                    if ans < counter:
                        ans = counter

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = [int(v) for v in input().split()]

maze = []
for i in range(h):
    maze.append(list(input()))


def find(maze):
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '.':
                return (i, j)
    return None

def contains(maze, closed, i, j):
    if i < 0 or i >= h:
        return False
    if j < 0 or j >= w:
        return False
    key = (i, j)
    if key in closed:
        return False
    closed.add(key)

    return True

def far(maze, p):
    q = deque([])

    i0 = p[0]
    j0 = p[1]
    q.append((i0, j0, 0))

    closed = set()
    closed.add((i0, j0))
    max_dist = 0
    max_p = None
    while len(q) > 0:
        e = q.popleft()
        
        i = e[0]
        j = e[1]
        cost = e[2] + 1
        for n in ((0, 1), (1, 0), (-1, 0), (0, -1)):
            ni = i + n[0]
            nj = j + n[1]
            nkey = (ni, nj)
            if not contains(maze, closed, ni, nj):
                continue
            if maze[ni][nj] != '.':
                continue
            q.append((ni, nj, cost))
            if max_dist < cost:
                max_dist = cost
                max_p = nkey
    return max_p, max_dist
    

p0 = find(maze)


p1, dist  = far(maze, p0)

while True:
    p2, max_dist = far(maze, p1)
    if dist == max_dist:
        break
    dist = max_dist
    p1 = p2

print(max_dist)