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 queue


class Solution:

    def solve(self, H: int, W: int, S) -> int:

        def onEdge(pos):
            i = pos[0]
            j = pos[1]
            if 0 < i and i < H - 1 and 0 < j and j < W - 1:
                return False
            else:
                return True

        def bfs(start):
            INF = H*W+1
            dist = {}
            for i in range(H):
                for j in range(W):
                    dist[(i, j)] = INF

            max_dist = 0

            dist[start] = 0
            nexts = queue.Queue()
            nexts.put(start)

            while not nexts.empty():
                __next = nexts.get()

                if onEdge(__next):
                    max_dist = max(dist[__next], max_dist)

                for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    h = __next[0] + delta[0]
                    w = __next[1] + delta[1]

                    if h < 0 or h > H - 1 or w < 0 or w > W - 1:
                        continue

                    if S[h][w] != "#":
                        if dist[(h, w)] == INF:
                            nexts.put((h, w))
                            dist[(h, w)] = dist[__next] + 1

            return max_dist

        ans = 0
        for i in range(H):
            for j in range(W):

                # skip if (i,j) is not on the edge
                if not onEdge((i, j)):
                    continue

                # skip if (i,J) is a wall
                if S[i][j] == "#":
                    continue

                ans = max(bfs((i, j)), ans)

        return ans


if __name__ == '__main__':

    # standard input
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        S.append(input())

    # solve
    solution = Solution()
    print(solution.solve(H, W, S))

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(maze, x, y):
    m = [1, 0, -1, 0]
    n = [0, 1, 0, -1]
    queue = deque([])
    queue.append([x, y])
    seen = [[False] * (w + 2) for _ in range(h + 2)]
    seen[x][y] = True
    count = 0

    while queue:
        sx, sy = queue.popleft()
        if maze[sx][sy] == 'goal':
            break

        for dx, dy in zip(m, n):
            nx = sx + dx
            ny = sy + dy
            if maze[nx][ny] != '#' and not seen[nx][ny]:
                seen[nx][ny] = True
                queue.append([nx, ny])
                count += 1

    return count


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

maze = [['#'] * (w + 2)]
for i in range(h):
    maze.append(['#'] + list(map(str, input())) + ['#'])

maze.append(['#'] * (w + 2))

ans = 0
for sy in range(1, w + 1):
    for sx in range(1, h + 1):
        for gy in range(1, w + 1):
            for gx in range(1, h + 1):
                if maze[gx][gy] == '.' and maze[sx][sy] == '.':
                    maze[gx][gy] = 'goal'
                    ans = max(ans, bfs(maze, sx, sy))
                    maze[gx][gy] = '.'

print(ans)

Submission status: Wrong Answer

Solution code:
import queue


class Solution:

    def solve(self, H: int, W: int, S) -> int:
        INF = H*W+1
        dist = {}
        for i in range(H):
            for j in range(W):
                dist[(i, j)] = INF

        def onEdge(pos):
            i = pos[0]
            j = pos[1]
            if 0 < i and i < H - 1 and 0 < j and j < W - 1:
                return False
            else:
                return True

        def bfs(start):

            max_dist = 0

            dist[start] = 0
            nexts = queue.Queue()
            nexts.put(start)

            while not nexts.empty():
                __next = nexts.get()

                if onEdge(__next):
                    max_dist = max(dist[__next], max_dist)

                for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    h = __next[0] + delta[0]
                    w = __next[1] + delta[1]

                    if h < 0 or h > H - 1 or w < 0 or w > W - 1:
                        continue

                    if S[h][w] != "#":
                        if dist[(h, w)] == INF:
                            nexts.put((h, w))
                            dist[(h, w)] = dist[__next] + 1

            return max_dist

        ans = 0
        for i in range(H):
            for j in range(W):

                # skip if (i,j) is not on the edge
                if not onEdge((i, j)):
                    continue

                # skip if (i,J) is a wall
                if S[i][j] == "#":
                    continue

                # skip if (i,j) is already visited
                if dist[(i, j)] < INF:
                    continue

                ans = max(bfs((i, j)), ans)

        return ans


if __name__ == '__main__':

    # standard input
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        S.append(input())

    # solve
    solution = Solution()
    print(solution.solve(H, W, S))

Submission status: Wrong Answer

Solution code:
import queue


class Solution:

    def solve(self, H: int, W: int, S) -> int:
        INF = H*W+1
        dist = {}
        for i in range(H):
            for j in range(W):
                dist[(i, j)] = INF

        def bfs(__start):

            # for i in range(H):
            #     s = ""
            #     for j in range(W):
            #         s += str(dist[(i, j)]) + ","
            #     print(s)
            # print("-----")

            goals = []
            goals.append(__start)
            dist[__start] = 0
            __nexts = queue.Queue()

            __nexts.put(__start)

            while not __nexts.empty():
                __next = __nexts.get()

                __is_node = True

                for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    h = __next[0] + delta[0]
                    w = __next[1] + delta[1]
                    if h < 0 or h > H - 1:
                        continue

                    if w < 0 or w > W - 1:
                        continue

                    if S[h][w] != "#" and dist[(h, w)] == INF:
                        __nexts.put((h, w))
                        dist[(h, w)] = dist[__next] + 1
                        __is_node = False

                if __is_node:
                    goals.append(__next)

            return goals

        ans = 0
        for i in range(H):
            for j in range(W):

                # skip if (i,j) is not on the edge
                if 0 < i and i < H - 1 and 0 < j and j < W - 1:
                    continue

                # skip if (i,J) is a wall
                if S[i][j] == "#":
                    continue

                # skip if (i,j) is already visited
                if dist[(i, j)] < INF:
                    continue

                goals = bfs((i, j))

                dists = [dist[goal] for goal in goals]
                dists.sort()

                max_dist = 0
                if len(dists) > 1:
                    max_dist = dists[-1] + dists[-2]

                if ans < max_dist:
                    ans = max_dist

        return ans


if __name__ == '__main__':

    # standard input
    H, W = map(int, input().split())
    S = []
    for h in range(H):
        S.append(input())

    # solve
    solution = Solution()
    print(solution.solve(H, W, S))

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np


def bfs(maze, sx, sy):
    q = deque([(sx, sy)])
    visited = set([(sx, sy)])
    H, W = maze.shape

    res = -1
    while q:
        res += 1

        n = len(q)
        for _ in range(n):
            x, y = q.pop()
            for dx, dy in [[1,0],[0,1],[-1,0],[0,-1]]:
                nx = x + dx
                ny = y + dy
                if nx < 0 or nx >= H or ny < 0 or ny >= W:
                    continue
                if (nx, ny) not in visited and maze[nx, ny] == 1:
                    q.append((nx, ny))
                    visited.add((nx, ny))
    return res


def main():
    H, W = [int(x) for x in input().split()]

    maze = np.zeros((H, W), dtype=int)

    for i in range(H):
        s = input()
        for j in range(len(s)):
            maze[i, j] = int(s[j] == ".")

    ans = 0
    for sx, sy in [(x, y) for x in range(H) for y in range(W)]:
        if maze[sx, sy] == 0:
            continue
        ans = max(ans, bfs(maze, sx, sy))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np


def bfs(maze, sx, sy):
    q = deque([(sx, sy)])
    visited = set()

    res = -1
    while q:
        res += 1

        n = len(q)
        for _ in range(n):
            x, y = q.pop()
            for dx, dy in [[1,0],[0,1],[-1,0],[0,-1]]:
                nx = x + dx
                ny = y + dy
                if nx < 0 or nx >= maze.shape[0] or ny < 0 or ny >= maze.shape[1]:
                    continue
                if (nx, ny) not in visited and maze[nx, ny] == 1:
                    q.append((nx, ny))
                    visited.add((nx, ny))
    return res


def main():
    H, W = [int(x) for x in input().split()]

    maze = np.zeros((H, W), dtype=int)

    for i in range(H):
        s = input()
        for j in range(len(s)):
            maze[i, j] = int(s[j] == ".")

    ans = 0
    for sx, sy in [(x, y) for x in range(H) for y in range(W)]:
        if maze[sx, sy] == 0:
            continue
        ans = max(ans, bfs(maze, sx, sy))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np


def bfs(maze, sx, sy):
    q = deque([(sx, sy)])
    visited = set()

    res = -1
    while q:
        res += 1

        n = len(q)
        for _ in range(n):
            x, y = q.pop()
            for dx, dy in [[1,0],[0,1],[-1,0],[0,-1]]:
                nx = x + dx
                ny = y + dy
                if nx < 0 or nx >= maze.shape[0] or ny < 0 or ny >= maze.shape[1]:
                    continue
                if (nx, ny) not in visited and maze[nx, ny] == 1:
                    q.append((nx, ny))
                    visited.add((nx, ny))
    return res


def main():
    H, W = [int(x) for x in input().split()]

    maze = np.zeros((H, W), dtype=int)

    for i in range(H):
        s = input()
        for j in range(len(s)):
            maze[i, j] = int(s[j] == ".")

    ans = 0
    for sx, sy in [(x, y) for x in range(H) for y in range(W)]:
        ans = max(ans, bfs(maze, sx, sy))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
lst = []
for _ in range(H):
	S = list(map(str, input()))
	lst.append(S)
	
distance_ord = [[400 for _ in range(W)] for _ in range(H)]
for i in range(H):
	for j in range(W):
		if lst[i][j] == "#":
			distance_ord[i][j] = -1
	
ans = 0


# 入力: 座標、かかってる時間
# 出力: 最深部に到達するまでにかかる時間
def bfs(sh, sw):
	distance = copy.deepcopy(distance_ord)
	Q = deque([[sh, sw, 0]])
	while Q:
		ch, cw, time = Q.popleft()
		if distance[ch][cw] < time: # すでにもっと早い道が存在
			continue
		for move_h, move_w in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			new_h, new_w = ch + move_h, cw + move_w 
			if 0 <= new_h and new_h <= H - 1 and 0 <= new_w and new_w <= W - 1:
				if lst[new_h][new_w] == "#": continue
				Q.append([new_h, new_w, time + 1])
				distance[new_h][new_w] = min(distance[new_h][new_w], time + 1)
	res = 0
	for i in range(H):
		res = max(res, max(distance[i]))
	
	return res
	
# スタート位置全通り
for sh in range(H):
	for sw in range(W):
		if lst[sh][sw] == "#": continue # 壁の時はスキップ
		ans = max(ans, bfs(sh, sw))
		
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


class Graph():
    def __init__(self):
        self.value = defaultdict(list)
        self.res = {}

    def addConnection(self, parent, child):
        self.value[parent].append(child)

    def addWays(self, node):
        for item in node:
            self.res[item] = 0

    def BFS(self, start):
        visited = [start]
        queue = [start]
        while queue:
            x = queue.pop(0)
            # print(x, end=" ")
            for item in self.value[x]:
                if item not in visited:
                    queue.append(item)
                    visited.append(item)
                    self.res[item] = self.res[x] + 1
        if not self.res:
            return []
        return self.res


h, w = list(map(int, input().split()))
s = [["#" for _ in range(w + 2)]]
for _ in range(h):
    s.append(["#"] + list(input()) + ["#"])
s.append(["#" for _ in range(w + 2)])
node = [i for i in range((h + 2) * (w + 2))]
size = len(node)
g_list = [Graph() for _ in node]
for ii in range(1, h + 1):
    for jj in range(1, w + 1):
        convd_index = ii * (w + 2) + jj
        g_list[convd_index].addWays(node)
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                convd = i * (w + 2) + j
                if s[i + 1][j] == ".":
                    g_list[convd_index].addConnection(
                        convd, ((i + 1) * (w + 2) + j))
                if s[i - 1][j] == ".":
                    g_list[convd_index].addConnection(
                        convd, ((i - 1) * (w + 2) + j))
                if s[i][j + 1] == ".":
                    g_list[convd_index].addConnection(
                        convd, (i * (w + 2) + j + 1))
                if s[i][j - 1] == ".":
                    g_list[convd_index].addConnection(
                        convd, (i * (w + 2) + j - 1))
res = 0
for start in range(size):
    bfs_list = g_list[start].BFS(start)
    if not bfs_list:
        continue
    for goal in range(size):
        bfs = bfs_list[goal]
        if bfs > res:
            res = bfs
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
 
 
def bfs(start, s):
    h = len(s)
    w = len(s[0])
    distance = 0
    maze = [[-1] * w for _ in range(h)]
    maze[start[0]][start[1]] = 0
    s[start[0]][start[1]] = "#"
    drcs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    q = deque()
    q.append(start)
    while(q):
        cr, cc = q.popleft()
        for dr, dc in drcs:
            nr, nc = cr + dr, cc + dc
            if nr < 0 or nc < 0 or nr >= h or nc >= w:
                continue
            if s[nr][nc] == ".":
                q.append([nr, nc])
                s[nr][nc] = "#"
                maze[nr][nc] = maze[cr][cc] + 1
                if maze[nr][nc] > distance:
                    distance = maze[nr][nc]
                    goal = [nr, nc]
    return goal, distance
 
 
def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    for r in range(h):
        if "." in s[r]:
            start = [r, s[r].index(".")]
    goal, distance = bfs(start, copy.deepcopy(s))
    #_, res = bfs(goal, s)
    print(distance)
 
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0

for i in range(h):
    for j in range(w):
        dist=[[inf for _ in range(w)] for _ in range(h)]
        dist[i][j]=0
        que=deque([(i,j)])
        while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                if 0<=ni<=h-1 and 0<=nj<=w-1 and S[ni][nj]!="#":
                    if dist[ni][nj]>dist[si][sj]+1:
                        dist[ni][nj]=dist[si][sj]+1
                        ans=max(ans,dist[si][sj]+1)
                        que.append((ni,nj))

print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import copy

def replace(s, n, c):
    if n < 0 or n >= len(s):
        return s
    return s[:n]+c[0]+s[n+1:]

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

def dist(m, x1, y1):
    q = queue.Queue()
    q.put((x1, y1, 0))
    checked=[[False for _ in range(w)] for __ in range(h)]
    count = 0
    while not q.empty():
        x, y, count = q.get()
        if x > 0 and m[y][x-1] == "." and checked[y][x-1] == False:
            checked[y][x-1] = True
            q.put((x-1, y, count+1))
        if y > 0 and m[y-1][x] == "." and checked[y-1][x] == False:
            checked[y-1][x] = True
            q.put((x, y-1, count+1))
        if x < w-1 and m[y][x+1] == "." and checked[y][x+1] == False:
            checked[y][x+1] = True
            q.put((x+1, y, count+1))
        if y < h-1 and m[y+1][x] == "." and checked[y+1][x] == False:
            checked[y+1][x] = True
            q.put((x, y+1, count+1))
    return count

ans = 0
for i in range(h):
    for j in range(w):
        if l[i][j] == ".":
            ans = max(ans, dist(l, j, i))
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import copy

def replace(s, n, c):
    if n < 0 or n >= len(s):
        return s
    return s[:n]+c[0]+s[n+1:]

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

def dist(m, x1, y1):
    q = queue.Queue()
    q.put((x1, y1, 0))
    checked=[[False for _ in range(w)] for __ in range(h)]
    while not q.empty():
        x, y, count = q.get()
        if x > 0 and m[y][x-1] == "." and checked[y][x-1] == False:
            checked[y][x-1] = True
            q.put((x-1, y, count+1))
        if y > 0 and m[y-1][x] == "." and checked[y-1][x] == False:
            checked[y-1][x] = True
            q.put((x, y-1, count+1))
        if x < w-1 and m[y][x+1] == "." and checked[y][x+1] == False:
            checked[y][x+1] = True
            q.put((x+1, y, count+1))
        if y < h-1 and m[y+1][x] == "." and checked[y+1][x] == False:
            checked[y+1][x] = True
            q.put((x, y+1, count+1))
    return count

ans = 0
for i in range(h):
    for j in range(w):
        if l[i][j] == ".":
            ans = max(ans, dist(l, j, i))
print(ans)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,copy,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  for i in range(h//2):
    for j in range(w):
      for k in range(i,h):
        for l in range(w):
          q=collections.deque()
          if field[i][j]=='#' or field[k][l]=='#':
            continue
          q.append((k,l,0))
          for _i in range(h):
            for _j in range(w):
              visited[_i][_j]=-1
          while len(q)>0:
            y,x,c=q.popleft()
            visited[y][x]=c
            if y==i and x==j:
              ans=max(ans,c)
              break

            for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
              ny=y+dy
              nx=x+dx
              if 0<=ny<h and 0<=nx<w:
                if field[ny][nx]=='#':
                  continue
                if visited[ny][nx]!=-1:
                  continue
                q.append((ny,nx,c+1))

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,bisect,sys,copy,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1]*w for _ in range(h)]

  for i in range(h):
    for j in range(w):
      for k in range(h):
        for l in range(w):
          q=collections.deque()
          if field[i][j]=='#' or field[k][l]=='#':
            continue
          q.append((k,l,0))
          for i in range(h):
            for j in range(w):
              visited[i][j]=-1
          while len(q)>0:
            y,x,c=q.popleft()
            visited[y][x]=c
            if y==i and x==j:
              ans=max(ans,c)
              break

            for dy,dx in dd:
              ny=y+dy
              nx=x+dx
              if 0<=ny and 0<=nx and ny<h and nx<w:
                if field[ny][nx]=='#':
                  continue
                if visited[ny][nx]!=-1:
                  continue
                q.append((ny,nx,c+1))

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque
def dfs(maze,sx,sy):
    q = deque([(sx, sy, 0)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and maze[i-1][j] == '.':
            q.append((i-1, j, d+1))
        if i < h - 1 and maze[i+1][j] == '.':
            q.append((i+1, j, d+1))
        if j > 0 and maze[i][j-1] == '.':
            q.append((i, j-1, d+1))
        if j < w - 1 and maze[i][j+1] == '.':
            q.append((i, j + 1, d + 1))
    else:
        return d-1

h,w = map(int,input().split())
maze = [list(input()) for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,dfs(maze,i,j))
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

h, w = map(int, input().split())
s = [[""]*(w+2)]
for _ in range(h):
    _s = list(input())
    _s.insert(0, "")
    _s.append("")
    s.append(_s)
s.append([""]*(w+2))

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

ans = 0

for _h in range(1, h+1):
    for _w in range(1, w+1):
        q = collections.deque([[_h, _w]])

        a = [[-1]*(w+2) for _ in range(h+2)]
        a[_h][_w] = 0

        while 0 < len(q):
            cx, cy = q.pop()
            for _dx, _dy in zip(dx, dy):
                x = cx + _dx
                y = cy + _dy

                if s[x][y] == "." and a[x][y] == -1:
                    a[x][y] = a[cx][cy] + 1
                    q.appendleft([x, y])

        for _a in a:
            ans = max(ans, max(_a))

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
ab.append(list('#'*w))
mx = 0

for i in range(h):
    for j in range(w):
        if ab[i][j] == '.':
            dp = [[0 for i in range(w)] for j in range(h)]
            step = [[i, j]]

            while len(step) > 0:
                y, x = step.pop(0)
                if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
                    step.append([y+1, x])
                    dp[y+1][x] = dp[y][x] + 1
                if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
                    step.append([y, x+1])
                    dp[y][x+1] = dp[y][x] + 1
                if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
                    step.append([y-1, x])
                    dp[y-1][x] = dp[y][x] + 1
                if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
                    step.append([y, x-1])
                    dp[y][x-1] = dp[y][x] + 1
            mx = max([mx, max(list(itertools.chain.from_iterable(dp)))])

print(mx)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import itertools

h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
ab.append(list('#'*w))
mx = 0

for i in range(h):
    for j in range(w):
        dp = [[0 for i in range(w)] for j in range(h)]
        step = [[i, j]]

        while len(step) > 0:
            y, x = step.pop(0)
            if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
                step.append([y+1, x])
                dp[y+1][x] = dp[y][x] + 1
            if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
                step.append([y, x+1])
                dp[y][x+1] = dp[y][x] + 1
            if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
                step.append([y-1, x])
                dp[y-1][x] = dp[y][x] + 1
            if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
                step.append([y, x-1])
                dp[y][x-1] = dp[y][x] + 1
        mx = max([mx, max(list(itertools.chain.from_iterable(dp)))])

print(mx)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(x, y):
    Max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    start = [x, y]
    distance = [[41]*W for i in range(H)]
    distance[y][x] = 0
    Q = deque()
    Q.append(start)

    while len(Q) != 0:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            
            if 0 <= nx < W and 0 <= ny < H:
                if Maze[ny][nx]=="." and distance[ny][nx]==41:
                    Q.append([nx, ny])
                    distance[ny][nx] = distance[p[1]][p[0]] + 1
    
    for i in range(H):
        for j in range(W):
            if distance[i][j]!=41 and  distance[i][j] > Max:
                Max = distance[i][j]
    return Max

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

MaxDistance = 0
for i in range(H):
    for j in range(W):
        d = bfs(j, i)
        if d > MaxDistance:
            MaxDistance = d


print(MaxDistance)

Submission status: Wrong Answer

Solution code:
from collections import deque

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


def bfs(sty, stx):
    visited = [[-1]*W for _ in range(H)]
    q = deque()
    visited[sty][stx] = 0
    q.append((sty, stx, 0))


    def is_ok(y, x):
        if not 0 <= y <= H - 1:
            return False
        if not 0 <= x <= W - 1:
            return False
        if visited[y][x] != -1:
            return False
        if maze[y][x] == '#':
            return False
        return True


    while q:
        y, x, lv = q.popleft()
        for i in (-1, 1):
            if is_ok(y+i, x):
                visited[y+i][x] = lv+1
                q.append((y+i, x, lv+1))
            if is_ok(y, x+i):
                visited[y][x+i] = lv + 1
                q.append((y, x+i, lv+1))

    return max(max(r) for r in visited)

res = 0
c = 1
for i in range(H):
    for j in range(W):
        print(c)
        c += 1
        if maze[i][j] == '.':
            res = max(res, bfs(i, j))

print(res)

Submission status: Wrong Answer

Solution code:
import sys
import socket
import numpy
from itertools import product

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'd2.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    h, w = read_int_list()
    a = [read_str() for _ in range(h)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    inf = 10 ** 3
    d = numpy.full(shape=(h, w, h, w), fill_value=inf)
    for i, j in product(range(h), range(w)):
        d[i][j][i][j] = 0

    for i, j in product(range(h), range(w)):
        if a[i][j] == '#':
            continue
        for di, dj in zip(dx, dy):
            k = i + di
            l = j + dj
            if not (0 <= k < h and 0 <= l < w):
                continue
            if a[k][l] == '#':
                continue
            d[i][j][k][l] = 1

    for k, kk in product(range(h), range(w)):
        for i, ii in product(range(h), range(w)):
            for j, jj in product(range(h), range(w)):
                if d[i][ii][j][jj] > d[i][ii][k][kk] + d[k][kk][j][jj]:
                    d[i][ii][j][jj] = d[i][ii][k][kk] + d[k][kk][j][jj]


    res = 0
    for i, ii in product(range(h), range(w)):
        for j, jj in product(range(h), range(w)):
            if d[i][ii][j][jj] == inf:
                continue
            if res < d[i][ii][j][jj]:
                res = d[i][ii][j][jj]
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
c = [input() for _ in range(h)]
ans = -1

def bfs(sx, sy):
    que = deque([[sy, sx]])
    d = [[0] * w for _ in range(h)]
    d[sy][sx] = 1
    while que:
        y, x = que.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            nx, ny = x+i, y+j
            if 0 <= nx and nx < w and 0 <= ny and ny < h and d[ny][nx] == 0 and c[ny][nx] != "#":
                nx_, ny_ = nx-i, ny-j
                d[ny][nx] = d[ny_][nx_] + 1
                que.append([ny, nx])
    return max(max(d))

for i_ in range(h):
    for j_ in range(w):
        if c[i_][j_] != "#":
            ans = max(ans, bfs( j_, i_))

print(ans-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = -1

def bfs(sx, sy):
    que = deque([[sy, sx]])
    d = [[0] * w for _ in range(h)]
    d[sy][sx] = 1
    while que:
        y, x = que.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            nx, ny = x+i, y+j
            if 0 <= nx and nx < w and 0 <= ny and ny < h and d[ny][nx] == 0 and c[ny][nx] != "#":
                nx_, ny_ = nx-i, ny-j
                d[ny][nx] = d[ny_][nx_] + 1
                que.append([ny, nx])
    return max(max(d))

for i_ in range(h):
    for j_ in range(w):
        if c[i_][j_] != "#":
            ans = max(ans, bfs( j_, i_))

print(ans-1)