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

input = sys.stdin.readline


class Solution:
    def main(self):
        H, W = map(int, input().split())
        S = [list(input().rstrip()) for _ in range(H)]

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

        ans = 0
        for i in range(1, H + 1):
            for j in range(1, W + 1):
                if S[i][j] == "#":
                    continue
                for n in range(1, H + 1):
                    for m in range(1, W + 1):
                        if S[n][m] == "#":
                            continue
                        v = self.min_move(S, (i, j), (n, m))
                        ans = max(ans, v)
        print(ans)

    def min_move(self, map, start, goal):
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))

        q = queue.Queue()
        q.put((start, 0))

        while q:
            pos, cnt = q.get()
            for move in moving_range:
                i, j = pos[0] + move[0], pos[1] + move[1]
                if (i, j) == goal:
                    return cnt + 1
                if map[i][j] == ".":
                    q.put(((i, j), cnt + 1))


# Run main
if __name__ == '__main__':
    Solution().main()

Submission status: Wrong Answer

Solution code:
h, w = map(int,input().split())
grid = []
grid.append('#' * (w+2))
for _ in range(h):
    grid.append('#' + input().rstrip() + '#')
grid.append('#' * (w+2))
            
from collections import deque
import sys
sys.setrecursionlimit(1000000)


def flatten_2dim(array):
    return [item for sublist in array for item in sublist]
def all_argmax_2dim(array):
    flat_array = flatten_2dim(array)

    row_num = len(array)
    max_value = max(flat_array)

    for i, elem in enumerate(flat_array):
        if elem == max_value:
            yield i // row_num, i % row_num

maxstep = 0

step = [[-1] * (w+2) for _ in range(h+2)]
def bfs():
    global maxstep

    dy = [1, 0, -1, 0]
    dx = [0, 1, 0, -1]
    
    que = deque([])
    que.append((s_y, s_x))
    step[s_y][s_x] = 0
    
    while que:
        y, x = que.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if step[ny][nx] == -1 and grid[ny][nx] != "#":
                que.append((ny, nx))
                step[ny][nx] = step[y][x] + 1

        maxstep = max(max(flatten_2dim(step)), maxstep)
    
for i in range(h+2):
    for j in range(w+2):
        if grid[i][j] == ".":
            s_y, s_x = i, j
            bfs()
            break

print(maxstep)

Submission status: Wrong Answer

Solution code:
import queue

def solve(maze, start):
    if maze[start[0]][start[1]] == '#':
        return 0

    q = queue.Queue()
    q.put((start, 0))

    h = len(maze)
    w = len(maze[0])

    memo = [[False] * w for _ in range(h)]

    ans = 0

    while not q.empty():
        p, i = q.get()
        ans = i

        if p[0] < h-1 and not memo[p[0] + 1][p[1]] and maze[p[0] + 1][p[1]] == '.':
            q.put(((p[0] + 1, p[1]), i + 1))
            memo[p[0] + 1][p[1]] = True

        if p[0] > 0 and not memo[p[0] - 1][p[1]] and maze[p[0] - 1][p[1]] == '.':
            q.put(((p[0] - 1, p[1]), i + 1))
            memo[p[0] - 1][p[1]] = True

        if p[1] < w-1 and not memo[p[0]][p[1] + 1] and maze[p[0]][p[1] + 1] == '.':
            q.put(((p[0], p[1] + 1), i + 1))
            memo[p[0]][p[1] + 1] = True

        if p[1] > 0 and not memo[p[0]][p[1] - 1] and maze[p[0]][p[1] - 1] == '.':
            q.put(((p[0], p[1] - 1), i + 1))
            memo[p[0]][p[1] - 1] = True

    return ans


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

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

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, solve(maze, (i, j)))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
def solve(maze, start, end):
  memo = []
  q = deque()
  q.append([start,[]])
  ans = 0
  while q:
    cur, path = q.popleft()
    if cur == end:
      ans = path
      break
    elif cur in memo:
      continue
    else:
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],copy.deepcopy(path)+[cur]])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    memo = [[False]*(W+2) for _ in range(H+2)]
    for ey in range(H+1, sy,-1):
      for ex in range(1, W+1):
        if Maze[ey][ex] == "#" or memo[ey][ex]:
          continue
        P = solve(Maze, [sy, sx], [ey,ex])
        Ans = max(Ans, len(P))
        for p in P:
          memo[p[0]][p[1]] = True
print(Ans)

Submission status: Wrong Answer

Solution code:
import sys
import queue
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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

H,W = LI()
S = [list(input()) for _ in range(H)]

def bfs(s):
    dist = [[-1]*W for _ in range(H)]
    h,w = s
    dist[h][w] = 0
    que = queue.Queue()
    que.put(s)
    while(not(que.empty())):
        h,w = que.get_nowait()
        for dh,dw in d:
            nh,nw = h+dh,w+dw
            if 0<=nh<H and 0<=nw<W and dist[nh][nw]==-1 and S[nh][nw]=='.':
                dist[nh][nw] = dist[h][w] + 1
                que.put([nh,nw])
    return dist[h][w]

def main():
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans,bfs([h,w]))
#            if S[h][w] == '.':
#                if (((h==0 or S[h-1][w]=='#') or (h==H-1 or S[h+1][w]=='#')) and 
#                        ((w==0 or S[h][w-1]=='#') or (w==W-1 or S[h][w+1]=='#'))):
#                    ans = max(ans,bfs([h,w]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

from collections import deque
from copy import deepcopy


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 Gh in range(H):
    for Gw in range(W):
        if S[Gh][Gw]=="#":continue
        for h in range(H):
            for w in range(W):
                if Gh==h and Gw==w:continue
                if S[h][w]=="#":continue
                chk=deepcopy(S)
                q=deque([[h,w,0]])
                chk[h][w]=1
                f=True
                while q and f:
                    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]==".":
                            c+=1

                            chk[y+dh][x+dw]="#"
                            q.append([y+dh,x+dw,c])
                            mx=max(mx,c)
                            if y+dh==Gh and x+dw==Gw:
                                f=False
                                break

print(mx)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[INF for j in range(V + 1)] for i in range(V + 1)]
    for i, j in E:
        d[i][j] = 1
        d[j][i] = 1
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k] + d[k][j]
                if d[i][j] > dk:
                    d[i][j] = dk
                    d[j][i] = dk
    return d


h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
n = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            n += 1
            s[i][j] = n
        else:
            s[i][j] = 0


E = []
for i in range(h):
    for j in range(w):
        p = s[i][j]
        if p > 0:
            if j < w - 1:
                p1 = s[i][j + 1]
                if p1 > 0:
                    E.append([p, p1])
            if i < h - 1:
                p2 = s[i + 1][j]
                if p2 > 0:
                    E.append([p, p2])

ans = 0
INF = 10 ** 9
D = warshall_floyd(n, E)
for di in D:
    for dij in di:
        if dij >= INF:
            continue
        ans = max(ans, dij)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
i8 = np.int64
i4 = np.int32
dot = 46

stdin = open(0).read().split(sep='\n', maxsplit=1)
H, W = map(int, stdin[0].split())
s = np.frombuffer(np.array(stdin[1]), dtype=i4).reshape(H, W+1)
s = np.vstack((s, np.zeros(W + 1, i4)))
g = np.zeros((H * W, H * W), i8)
for i in range(H):
    for j in range(W):
        if s[i, j] == dot:
            if s[i, j + 1] == dot:
                g[W * i + j, W * i + j + 1] = 1
                g[W * i + j + 1, W * i + j] = 1
            if s[i + 1, j] == dot:
                g[W * i + j, W * (i + 1) + j] = 1
                g[W * (i + 1) + j, W * i + j] = 1

dist_matrix = floyd_warshall(g)
print(int(np.max(dist_matrix[dist_matrix < 40])))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
 
H,W = map(int,input().split())

town = []
visited = [[0 for i in range(W)] for j in range(H)]
 
for i in range(H): 
    c = input().strip()
    w = list(c)
    town.append(w)

def getpreStart(h,w):
    for i in range(h):
        for j in range(w):
            if town[i][j] == '.' :
                return i,j
            
def bfs(x,y) :
    q = deque()
    q.append([x,y,0])
    max_dist=0
    s=x
    t=y
    while q : #キューが空でない場合
        tx,ty,dist = q.popleft()
        if visited[ty][tx] == 0 :
            visited[ty][tx] = 1
            if town[ty][tx] == '#' :
                pass
            else :
                #周辺4マスを調べる
                for r in range (4):
                    nx = tx + dx[r]
                    ny = ty + dy[r]
                    count=0
                    if 0 <= nx < W and 0 <= ny < H and visited[ny][nx] == 0:
                        q.append([nx,ny,dist+1])
                        count+=1
                    if count==0 and dist>max_dist:
                        max_dist=dist
                        s=tx
                        t=ty
    return s,t,max_dist
                        
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
sy,sx=getpreStart(H,W)
sx,sy,max_dist=bfs(sx,sy)
visited = [[0 for i in range(W)] for j in range(H)]
sx,sy,max_dist=bfs(sx,sy)
print(max_dist)

Submission status: Wrong Answer

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

H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

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

def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    Visit[start]=1
    L=defaultdict(lambda: float("inf"))    #距離
    L[start]=0

    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and (to_x,to_y) not in Visit:
                    Visit[to_x,to_y]=1
                    L[(to_x,to_y)]=min(L[(to_x,to_y)],L[(fro_x,fro_y)]+1)
                    q.append((to_x,to_y))
    if len(L.values())==0:
        return 0
    else:
        return max(L.values())

ans=0
for h in range(H):
    for w in range(W):
        ans=max(ans,bfs((h,w)))

print ans

Submission status: Wrong Answer

Solution code:
import sys
import queue
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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

H,W = LI()
S = [list(input()) for _ in range(H)]

def bfs(s):
    dist = [[-1]*W for _ in range(H)]
    h,w = s
    dist[h][w] = 0
    que = queue.Queue()
    que.put(s)
    while(not(que.empty())):
        h,w = que.get_nowait()
        for dh,dw in d:
            nh,nw = h+dh,w+dw
            if 0<=nh<H and 0<=nw<W and dist[nh][nw]==-1 and S[nh][nw]=='.':
                dist[nh][nw] = dist[h][w] + 1
                que.put([nh,nw])
    return dist[h][w]

def main():
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                if (((h==0 or S[h-1][w]=='#') or (h==H-1 or S[h+1][w]=='#')) and 
                        ((w==0 or S[h][w-1]=='#') or (w==W-1 or S[h][w+1]=='#'))):
                    ans = max(ans,bfs([h,w]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
from queue import Queue
h,w=map(int,input().split())
S=[input() for _ in range(h)]

def bfs(q):
  x,y,cnt=q.get()
  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.put([x-1,y,cnt+1])
    q.put([x+1,y,cnt+1])
    q.put([x,y-1,cnt+1])
    q.put([x,y+1,cnt+1])

ans=0
for x in range(h//2+1):
  for y in range(w//2+1):
    q=Queue()
    q.put([x,y,0])
    memo=[[-1]*w for _ in range(h)]
    while not q.empty():
      bfs(q)
    ans=max(ans,max(max(memo)))
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
visited = [[0 for _ in range(w)] for _ in range(h)]
disList = [[[[0 for _ in range(w)] for _ in range(h)] for _ in range(w)] for _ in range(h)]
# print(s)
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            visited[i][j] = 1
import copy

ans = 0
for i in range(h):
    for j in range(w):
        nowdis = 0
        now = 0
        next_point = [[i, j, nowdis]]
        thisVisited = copy.deepcopy(visited)
        while now < len(next_point):
            nowi = next_point[now][0]
            nowj = next_point[now][1]
            nowdis = next_point[now][2]
            disList[i][j][nowi][nowj] = nowdis

            if nowi != 0:
                if thisVisited[nowi - 1][nowj] == 0:
                    next_point.append([nowi - 1, nowj, nowdis + 1])
                    thisVisited[nowi - 1][nowj] = 1

            if nowi != h - 1:
                if thisVisited[nowi + 1][nowj] == 0:
                    next_point.append([nowi + 1, nowj, nowdis + 1])
                    thisVisited[nowi + 1][nowj] = 1

            if nowj != w - 1:
                if thisVisited[nowi][nowj + 1] == 0:
                    next_point.append([nowi, nowj + 1, nowdis + 1])
                    thisVisited[nowi][nowj + 1] = 1

            if nowj != 0:
                if thisVisited[nowi][nowj - 1] == 0:
                    next_point.append([nowi, nowj - 1, nowdis + 1])
                    thisVisited[nowi][nowj - 1] = 1
            now += 1

# print(disList)
ans = 0
for i in disList:
    for j in i:
        for k in j:
            # print(k)
            ans = max(ans, max(k))

print(ans)

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:
import queue
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        x=[[inf for i_sub in range(w)] for j_sub in range(h)]
        q=queue.Queue()
        d=0
        q.put([i,j])
        while q.qsize()!=0:
            d+=1
            l=q.qsize()
            for t in range(l):
                I,J=q.get()
                if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                    q.put([I-1,J])
                    x[I-1][J]=d
                if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                    q.put([I+1,J])
                    x[I+1][J]=d
                if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                    q.put([I,J-1])
                    x[I][J-1]=d
                if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                    q.put([I,J+1])
                    x[I][J+1]=d
        ma_sub=0
        for k in range(h):
            for l in range(w):
                if x[k][l]!=inf:
                    ma_sub=max(ma_sub,x[k][l])
        ma.append(ma_sub)
print(max(ma))

Submission status: Wrong Answer

Solution code:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def dfs(maze, visited, sh, sw, gh, gw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.pop()
        # ゴールの条件
        if h == gh and w == gw:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    stack.append([new_h, new_w])
    
    return visited[gh][gw]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if maze[sh][sw] != "#" and maze[gh][gw] != "#" and vd[sh][sw][gh][gw] == 0 and vd[gh][gw][sh][sw] == 0 and not (gh == sh and gw == sw):
                        vd[sh][sw][gh][gw] = 1
                        vd[gh][gw][sh][sw] = 1
                        visited = [[-1] * W for _ in range(H)]
                        step_cnt = dfs(maze, visited, sh, sw, gh, gw)
                        ans = max(ans, step_cnt)

    print(ans - 1)

Submission status: Wrong Answer

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

S = [list(input()) for _ in range(H)]

check = [[False]*W for _ in range(H)]

res = 0


for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            check[i][j] = True
        if check[i][j]:
            continue

        mc = [[-1]*W for _ in range(H)]
        mc[i][j] = 0

        q = [(i, j)]
        first = True
        while q:
            y, x = q.pop(0)
            for a, b in [(-1,0), (0,-1), (0,1), (1,0)]:
                if y+a < 0 or y+a >= H or x+b < 0 or x+b >= W:
                    continue

                if S[y+a][x+b] == "#":
                    continue


                if mc[y+a][x+b] == -1 or mc[y+a][x+b] > mc[y][x]+1:
                    mc[y+a][x+b] = mc[y][x]+1

                    res = max(res, mc[y+a][x+b])
                    q.append([y+a, x+b])

                    if not first:
                        check[y][x] = True
            first = False

"""
for row in check:
    s = ""
    for x in row:
        if x:
            s += "#"
        else:
            s += "."
    print(s)
"""

print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def bfs(s, t):
    dist = [[None] * W for _ in range(H)]
    que = deque([(s, t)])
    dist[s][t] = 0
    while que:
        u, v = que.popleft()
        d = dist[u][v]
        G = []
        if u > 0 and S[u-1][v] == ".":
            G.append((u-1, v))
        if u < H - 1 and S[u+1][v] == ".":
            G.append((u+1, v))
        if v > 0 and S[u][v-1] == ".":
            G.append((u, v-1))
        if v < W - 1 and S[u][v+1] == ".":
            G.append((u, v+1))
        for w, x in G:
            if dist[w][x] is None:
                dist[w][x] = d + 1
                que.append((w, x))
    d = 0
    A = []
    for i in range(H):
        for j in range(W):
            if dist[i][j] is not None:
                if dist[i][j] == d:
                    A.append((i, j))
                elif dist[i][j] > d:
                    d = dist[i][j]
                    A = [(i, j)]
    return (d, A)

for i in range(H):
    j = S[i].find(".")
    if j >= 0:
        _, A = bfs(i, j)
        print(max(bfs(u, v)[0] for u, v in A))
        break

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
maze = []

def mazecal(hs,ws):
    calmaze = [[0 for _ in range(w)] for _ in range(h)]
    def bfs(h1,w1,step):
        if calmaze[h1][w1] > 0 and calmaze[h1][w1] <= step:pass
        else:
            calmaze[h1][w1] = step
            if h1>0:
                if maze[h1-1][w1] == 0:
                    bfs(h1-1,w1,step+1)
            if h1<h-1:
                if maze[h1+1][w1] == 0:
                    bfs(h1+1,w1,step+1)
            if w1>0:
                if maze[h1][w1-1] == 0:
                    bfs(h1,w1-1,step+1)
            if w1<w-1:
                if maze[h1][w1+1] == 0:
                    bfs(h1,w1+1,step+1)
    bfs(hs,ws,0)
    smax = 0
    for i in range(h):smax = max(smax,max(calmaze[i]))
    return smax

for i in range(h):
    s = input()
    line = [0 if c=='.' else 1 for c in s]
    maze.append(line)

gmax = 0
for i in range(h):
    for j in range(w):
        if maze[i][j]==0:gmax = max(gmax,mazecal(i,j))
        else:pass
print(gmax)

Submission status: Wrong Answer

Solution code:
import copy
def dfs(x,y,z,grid,H,W):
    if(x-1>=0):
        if(grid[y][x-1]>z or grid[y][x-1]==0):
            grid[y][x-1]=z+1
            dfs(x-1,y,z+1,grid,H,W)
    if(x+1<W):
        if(grid[y][x+1]>z or grid[y][x+1]==0):
            grid[y][x+1]=z+1
            dfs(x+1,y,z+1,grid,H,W)
    if(y-1>=0):
        if(grid[y-1][x]>z or grid[y-1][x]==0):
            grid[y-1][x]=z+1
            dfs(x,y-1,z+1,grid,H,W)
    if(y+1<H):
        if(grid[y+1][x]>z or grid[y+1][x]==0):
            grid[y+1][x]=z+1
            dfs(x,y+1,z+1,grid,H,W)
    return 0

    
H,W=map(int,input().split())
grid=[]
tmp=[]
for i in range(H):
    S=str(input())
    tmp=[]
    for j in range(W):
        if(S[j]=="."):
            tmp.append(0)
        else:
            tmp.append(-1)
    grid.append(tmp)
ans=0
result=0
for i in range(W):
    for j in range(H):
        if(grid[j][i]==0):
            dataset=copy.deepcopy(grid)
            dfs(i,j,0,dataset,H,W)
            ans=max(dataset)
            ans=max(ans)
            result=max(result,ans)
print(result)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S    = [None] * H # S[h][w]
for h in range(H):
    S[h] = list(input())

# find temporary start
is_break = False
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            is_break = True
            break
    if is_break:
        break

h_init, w_init = h, w

# find goal
STEPs                 = [[-1 for w in range(W)] for h in range(H)] # STEPs[x][y]
STEPs[h_init][w_init] = 0
max_STEP              = 0

Q = [(h_init, w_init)]

while len(Q) > 0:
    Q_new = []
    for q in Q:
        step     = STEPs[q[0]][q[1]]
        max_STEP = max(max_STEP, step)
        for h, w in [(q[0]-1, q[1]), (q[0], q[1]-1), (q[0], q[1]+1), (q[0]+1, q[1])]:
            if (h < 0 or w < 0) or (h >= H or w >= W) or (STEPs[h][w] != -1) or S[h][w] != '.':
                continue
            else:
                STEPs[h][w] = step+1
                Q_new.append((h, w))
    Q = Q_new

Q_start = []
for h in range(H):
    for w in range(W):
        if STEPs[h][w] == max_STEP:
            Q_start.append((h, w))

answer = 0

# find start
for h_goal, w_goal in Q_start:
    STEPs                 = [[-1 for w in range(W)] for h in range(H)] # STEPs[x][y]
    STEPs[h_goal][w_goal] = 0
    max_STEP              = 0

    Q = [(h_goal, w_goal)]
    while len(Q) > 0:
        Q_new = []
        for q in Q:
            step     = STEPs[q[0]][q[1]]
            max_STEP = max(max_STEP, step)
            for h, w in [(q[0]-1, q[1]), (q[0], q[1]-1), (q[0], q[1]+1), (q[0]+1, q[1])]:
                if (h < 0 or w < 0) or (h >= H or w >= W) or (STEPs[h][w] != -1) or S[h][w] != '.':
                    continue
                else:
                    STEPs[h][w] = step+1
                    Q_new.append((h, w))
        Q = Q_new
    answer = max(answer, max_STEP)

print(answer)

Submission status: Wrong Answer

Solution code:

H, W = map(int, input().split())
edges = [[None for i in range(W)] for i in range(H)]

for i in range(H):
  s = list(map(str, input()))
  for j in range(W):
    edges[i][j] = s[j] 


def find_next(i, j):
  next = []
  if i > 0 and edges[i-1][j] == ".":
    next.append((i-1, j))
  if i < H - 1 and edges[i+1][j] == ".":
    next.append((i+1, j))
  if j > 0 and edges[i][j-1] == ".":
    next.append((i, j-1))
  if j < W - 1 and edges[i][j+1] == ".":
    next.append((i, j+1))
  return next

inf = 9999999999999999999

def dfs(i, j):
  colors = [[["white"] for i in range(W)] for j in range(H)]
  stack = [(i, j)]
  distance = [[inf for i in range(W)] for j in range(H)]
  distance[i][j] = 0

  while stack:
    i, j = map(int, stack.pop())
    colors[i][j] = "black"
    for (x, y) in find_next(i, j):
      if colors[x][y] != "black":
        distance[x][y] = min(distance[i][j] + 1, distance[x][y])
        stack.append((x, y))
  
  return distance


import itertools
ans = -1
for i in range(H):
  for j in range(W):
    if edges[i][j] == "#": 
      continue

    L = list(itertools.chain.from_iterable(dfs(i, j)))
    m = max(list(filter(lambda x: x != inf, L)))
    ans = max(ans, m)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
def solve(maze, start, end):
  memo = []
  q = deque()
  q.append([start,[]])
  ans = 0
  while q:
    cur, path = q.popleft()
    if cur == end:
      ans = path
      break
    elif cur in memo:
      continue
    else:
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],copy.deepcopy(path)+[cur]])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    memo = [[False]*(W+2) for _ in range(H+2)]
    for ey in range(sy, H+1,-1):
      for ex in range(1, W+1):
        if Maze[ey][ex] == "#" or memo[ey][ex]:
          continue
        P = solve(Maze, [sy, sx], [ey,ex])
        Ans = max(Ans, len(P))
        for p in P:
          memo[p[0]][p[1]] = True
print(Ans)

Submission status: Wrong Answer

Solution code:
# ABC151 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from collections import deque
def bfs(sy,sx,gy,gx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        if [y,x]==[gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="#":
                continue
            if path[ny][nx]=="." and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
h,w=nm()
path=[input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=0,0
ans=0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                if path[i][j]=='#' or path[k][l]=='#':
                    continue
                sy,sx=i,j
                gy,gx=k,l
                visited = [[-1]*w for i in range(h)]
                bfs(sy,sx,gx,gy)
                if visited[gy][gx]==-1:
                    visited[gy][gx]=0
                ans=max(visited[gy][gx],ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

sys.setrecursionlimit(10**7)

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

S = []
for _ in range(H):
    S.extend(list(input()))

dxs = [-1, 1, -W, W]

sx, sy = 0, 0


def f(sx, sy):
    dist = [-1] * (H * W)
    s = sx * W + sy
    # print('s', s)
    if S[s] == '#':
        return -1
    q = [s]
    dist[s] = 0
    while q:
        qq = []
        for x, dx in itertools.product(q, dxs):
            if x % W == 0 and dx == -1:
                continue
            if x % W == W - 1 and dx == 1:
                continue
            y = x + dx
            # print('y', y)
            if y >= len(S) or y < 0:
                continue
            if S[y] == '#':
                continue
            if dist[y] != -1:
                continue
            dist[y] = dist[x] + 1
            qq.append(y)
        # print('qq', qq)
        q = qq
    # return dist, max(dist)
    return max(dist)


ans = 0
for r in range(H):
    for c in range(W):
        # _, v = f(r, c)
        v = f(r, c)
        # print('rcv', r, c, v)
        if ans < v:
            ans = v
print(ans)