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:
#151d
#幅優先探索、二次元入力、番兵、門番、行列
from collections import deque

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

edge = [["#" for _ in range(W+2)]]
center = [["#"] + list(input()) + ["#"] for i in range(H)]
c_array = edge + center + edge

caluclated_edge = [[1 for _ in range(W+2)]]
caluclated_center = [[1] + [0 for _ in range(W)] + [1] for i in range(H)]
is_caluclated = caluclated_edge + caluclated_center + caluclated_edge

def visited_print():
    print("$$$$$$$$$$$$$$$$$$$$$$")
    for i in range(0,H+2):
        print(is_visited[i][0:W+2])

def map_print():
    print("######################")
    for i in range(0,H+2):
        print(distance_from_start[i][1:W+1])

def get_farthest_dead_end(sy,sx): #function 幅優先探索(v)
    distance_from_start = [["?"] * (W+2) for i in range(H+2)] #startからの距離

    iv_edge = [[1 for _ in range(W+2)]]
    iv_center = [[1] + [0 for _ in range(W)] + [1] for i in range(H)]
    is_visited = iv_edge + iv_center + iv_edge

    search_target_deque = deque() #    Q ← 空のキュー
    is_visited[sy][sx] = 1 #    v に訪問済みの印を付ける
    search_target_deque.append((sy,sx)) #    v を Q に追加
    distance_from_start[sy][sx] = 0

    farthest_dead_end_y = sy
    farthest_dead_end_x = sx
    farthest_dead_end_distance = 0

    while len(search_target_deque) != 0: #    while Q が空ではない do
        node = search_target_deque.popleft() #        v ← Q から取り出す
        #        v を処理する
        node_y = node[0]
        node_x = node[1]

        near_nodes = [(node[0]+1,node[1]),(node[0],node[1]+1),(node[0]-1,node[1]),(node[0],node[1]-1)]
        maybe_dead_end_flag = True

        for near_node in near_nodes: #        for each v に接続している頂点 i do
            near_node_y = near_node[0]
            near_node_x = near_node[1]

            if is_visited[near_node_y][near_node_x] == 0: #            if i が未訪問 then
                is_visited[near_node_y][near_node_x] = 1 #                i に訪問済みの印を付ける
                if c_array[near_node_y][near_node_x] == ".":
                    search_target_deque.append(near_node) #                i を Q に追加
                    distance_from_start[near_node_y][near_node_x] = distance_from_start[node_y][node_x] + 1
                    maybe_dead_end_flag = False

        #行き止まり判定
        if maybe_dead_end_flag == True:
            now_distance = distance_from_start[node_y][node_x]
            for near_node in near_nodes:
                #周囲に未訪問マスがある or 自分より遠いマスがある ならば行き止まりでない 
                near_node_y = near_node[0]
                near_node_x = near_node[1]

                if (distance_from_start[near_node_y][near_node_x] != "?" and  now_distance < distance_from_start[near_node_y][near_node_x]):
                    break
                if is_visited[near_node_y][near_node_x]==0:
                    break
            else:
                if farthest_dead_end_distance < distance_from_start[node_y][node_x]:
                    farthest_dead_end_distance = distance_from_start[node_y][node_x]
                    farthest_dead_end_y = node_y
                    farthest_dead_end_x = node_x

    return farthest_dead_end_y,farthest_dead_end_x


def get_ans(sy,sx): #function 幅優先探索(v)
    distance_from_start = [["?"] * (W+2) for i in range(H+2)] #startからの距離

    iv_edge = [[1 for _ in range(W+2)]]
    iv_center = [[1] + [0 for _ in range(W)] + [1] for i in range(H)]
    is_visited = iv_edge + iv_center + iv_edge

    search_target_deque = deque() #    Q ← 空のキュー
    is_visited[sy][sx] = 1 #    v に訪問済みの印を付ける
    is_caluclated[sy][sx] = 1

    search_target_deque.append((sy,sx)) #    v を Q に追加
    distance_from_start[sy][sx] = 0

    ans = 0

    while len(search_target_deque) != 0: #    while Q が空ではない do
        node = search_target_deque.popleft() #        v ← Q から取り出す
        #        v を処理する
        node_y = node[0]
        node_x = node[1]
                
        near_nodes = [(node[0]+1,node[1]),(node[0],node[1]+1),(node[0]-1,node[1]),(node[0],node[1]-1)]
        maybe_dead_end_flag = True

        for near_node in near_nodes: #        for each v に接続している頂点 i do
            near_node_y = near_node[0]
            near_node_x = near_node[1]

            if is_visited[near_node_y][near_node_x] == 0: #            if i が未訪問 then
                is_visited[near_node_y][near_node_x] = 1 #                i に訪問済みの印を付ける
                is_caluclated[near_node_y][near_node_x] = 1
                if c_array[near_node_y][near_node_x] == ".":
                    search_target_deque.append(near_node) #                i を Q に追加
                    distance_from_start[near_node_y][near_node_x] = distance_from_start[node_y][node_x] + 1
                    maybe_dead_end_flag = False

        #行き止まり判定
        if maybe_dead_end_flag == True:
            now_distance = distance_from_start[node_y][node_x]
            for near_node in near_nodes:
                #周囲に未訪問マスがある or 自分より通りマスがある ならば行き止まりでない 
                near_node_y = near_node[0]
                near_node_x = near_node[1]

                if (distance_from_start[near_node_y][near_node_x] != "?" and  now_distance < distance_from_start[near_node_y][near_node_x]):
                    break
                if is_visited[near_node_y][near_node_x]==0:
                    break
            else:
                if ans < distance_from_start[node_y][node_x]:
                    ans = distance_from_start[node_y][node_x]

    return ans

#行き止まりを求めて、一番遠いところから広げてみる。
ans = 0

#仮スタートを決める
for i in range(1,H+1):
    for j in range(1,W+1):
        if c_array[i][j]=="." and is_caluclated[i][j]==0:
            sy = i
            sx = j
            sy,sx = get_farthest_dead_end(sy,sx)
            temp_ans = get_ans(sy,sx)
            if ans < temp_ans:
                ans = temp_ans

print(ans)

Submission status: Wrong Answer

Solution code:
#151d
#幅優先探索、二次元入力、番兵、門番、行列
from collections import deque

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

edge = [["#" for _ in range(W+2)]]
center = [["#"] + list(input()) + ["#"] for i in range(H)]
c_array = edge + center + edge

caluclated_edge = [[1 for _ in range(W+2)]]
caluclated_center = [[1] + [0 for _ in range(W)] + [1] for i in range(H)]
is_caluclated = caluclated_edge + caluclated_center + caluclated_edge

def visited_print():
    print("$$$$$$$$$$$$$$$$$$$$$$")
    for i in range(0,H+2):
        print(is_visited[i][0:W+2])

def map_print():
    print("######################")
    for i in range(0,H+2):
        print(distance_from_start[i][1:W+1])

def get_farthest_dead_end(sy,sx): #function 幅優先探索(v)
    distance_from_start = [["?"] * (W+2) for i in range(H+2)] #startからの距離

    iv_edge = [[1 for _ in range(W+2)]]
    iv_center = [[1] + [0 for _ in range(W)] + [1] for i in range(H)]
    is_visited = iv_edge + iv_center + iv_edge

    search_target_deque = deque() #    Q ← 空のキュー
    is_visited[sy][sx] = 1 #    v に訪問済みの印を付ける
    search_target_deque.append((sy,sx)) #    v を Q に追加
    distance_from_start[sy][sx] = 0

    farthest_dead_end_y = sy
    farthest_dead_end_x = sx
    farthest_dead_end_distance = 0

    while len(search_target_deque) != 0: #    while Q が空ではない do
        node = search_target_deque.popleft() #        v ← Q から取り出す
        #        v を処理する
        node_y = node[0]
        node_x = node[1]

        near_nodes = [(node[0]+1,node[1]),(node[0],node[1]+1),(node[0]-1,node[1]),(node[0],node[1]-1)]
        maybe_dead_end_flag = True

        for near_node in near_nodes: #        for each v に接続している頂点 i do
            near_node_y = near_node[0]
            near_node_x = near_node[1]

            if is_visited[near_node_y][near_node_x] == 0: #            if i が未訪問 then
                is_visited[near_node_y][near_node_x] = 1 #                i に訪問済みの印を付ける
                if c_array[near_node_y][near_node_x] == ".":
                    search_target_deque.append(near_node) #                i を Q に追加
                    distance_from_start[near_node_y][near_node_x] = distance_from_start[node_y][node_x] + 1
                    maybe_dead_end_flag = False

        #行き止まり判定
        if maybe_dead_end_flag == True:
            now_distance = distance_from_start[node_y][node_x]
            for near_node in near_nodes:
                #周囲に未訪問マスがある or 自分より通りマスがある ならば行き止まりでない 
                near_node_y = near_node[0]
                near_node_x = near_node[1]

                if (distance_from_start[near_node_y][near_node_x] != "?" and  now_distance < distance_from_start[near_node_y][near_node_x]):
                    break
                if is_visited[near_node_y][near_node_x]==0:
                    break
            else:
                if farthest_dead_end_distance < distance_from_start[node_y][node_x]:
                    farthest_dead_end_distance = distance_from_start[node_y][node_x]
                    farthest_dead_end_y = node_y
                    farthest_dead_end_x = node_x

    return farthest_dead_end_y,farthest_dead_end_x


def get_ans(sy,sx): #function 幅優先探索(v)
    distance_from_start = [["?"] * (W+2) for i in range(H+2)] #startからの距離

    iv_edge = [[1 for _ in range(W+2)]]
    iv_center = [[1] + [0 for _ in range(W)] + [1] for i in range(H)]
    is_visited = iv_edge + iv_center + iv_edge

    search_target_deque = deque() #    Q ← 空のキュー
    is_visited[sy][sx] = 1 #    v に訪問済みの印を付ける
    is_caluclated[sy][sx] = 1

    search_target_deque.append((sy,sx)) #    v を Q に追加
    distance_from_start[sy][sx] = 0

    ans = 0

    while len(search_target_deque) != 0: #    while Q が空ではない do
        node = search_target_deque.popleft() #        v ← Q から取り出す
        #        v を処理する
        node_y = node[0]
        node_x = node[1]
                
        near_nodes = [(node[0]+1,node[1]),(node[0],node[1]+1),(node[0]-1,node[1]),(node[0],node[1]-1)]
        maybe_dead_end_flag = True

        for near_node in near_nodes: #        for each v に接続している頂点 i do
            near_node_y = near_node[0]
            near_node_x = near_node[1]

            if is_visited[near_node_y][near_node_x] == 0: #            if i が未訪問 then
                is_visited[near_node_y][near_node_x] = 1 #                i に訪問済みの印を付ける
                is_caluclated[near_node_y][near_node_x] = 1
                if c_array[near_node_y][near_node_x] == ".":
                    search_target_deque.append(near_node) #                i を Q に追加
                    distance_from_start[near_node_y][near_node_x] = distance_from_start[node_y][node_x] + 1
                    maybe_dead_end_flag = False

        #行き止まり判定
        if maybe_dead_end_flag == True:
            now_distance = distance_from_start[node_y][node_x]
            for near_node in near_nodes:
                #周囲に未訪問マスがある or 自分より通りマスがある ならば行き止まりでない 
                near_node_y = near_node[0]
                near_node_x = near_node[1]

                if (distance_from_start[near_node_y][near_node_x] != "?" and  now_distance < distance_from_start[near_node_y][near_node_x]):
                    break
                if is_visited[near_node_y][near_node_x]==0:
                    break
            else:
                if ans < distance_from_start[node_y][node_x]:
                    ans = distance_from_start[node_y][node_x]

    return ans

#行き止まりを求めて、一番遠いところから広げてみる。
ans = 1

#仮スタートを決める
break_flag = False
for i in range(1,H+1):
    for j in range(1,W+1):
        if c_array[i][j]=="." and is_caluclated[i][j]==0:
            sy = i
            sx = j
            sy,sx = get_farthest_dead_end(sy,sx)
            temp_ans = get_ans(sy,sx)
            if ans < temp_ans:
                ans = temp_ans

print(ans)

Submission status: Wrong Answer

Solution code:
import queue

h, w = map(int, input().split())
mat = ["#"*(w+2)]
for y in range(h):
  mat.append("#"+input()+"#")
mat.append("#"*(w+2))

d_mat1 = [[-1]*(w+2) for i in range(h+2)]
d_mat2 = [[-1]*(w+2) for i in range(h+2)]
q = queue.Queue()
flag = True
for x in range(1, w+1):
  if flag:
    for y in range(1, h+1):
      if mat[y][x] == ".":
        start = (y, x)
        d_mat1[y][x] = 0
        flag = False
        break
q.put(start)

while not q.empty():
  x, y = q.get()
  d = d_mat1[x][y]
  if mat[x-1][y] == "." and d_mat1[x-1][y] == -1:
    d_mat1[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat1[x+1][y] == -1:
    d_mat1[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat1[x][y-1] == -1:
    d_mat1[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat1[x][y+1] == -1:
    d_mat1[x][y+1] = d+1
    q.put((x, y+1))

end = (x,y)

d_mat2[x][y] = 0
q.put(end)
while not q.empty():
  x, y = q.get()
  d = d_mat2[x][y]
  if mat[x-1][y] == "." and d_mat2[x-1][y] == -1:
    d_mat2[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat2[x+1][y] == -1:
    d_mat2[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat2[x][y-1] == -1:
    d_mat2[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat2[x][y+1] == -1:
    d_mat2[x][y+1] = d+1
    q.put((x, y+1))

print(d_mat2[x][y])

Submission status: Wrong Answer

Solution code:
import queue

h, w = map(int, input().split())
mat = ["#"*(w+2)]
for y in range(h):
  mat.append("#"+input()+"#")
mat.append("#"*(w+2))

d_mat1 = [[-1]*(w+2) for i in range(h+2)]
d_mat2 = [[-1]*(w+2) for i in range(h+2)]
q = queue.Queue()
for x in range(1, w+1):
  for y in range(1, h+1):
    if mat[y][x] == ".":
      start = (y, x)
      d_mat1[y][x] = 0
      break
q.put(start)

while not q.empty():
  x, y = q.get()
  d = d_mat1[x][y]
  if mat[x-1][y] == "." and d_mat1[x-1][y] == -1:
    d_mat1[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat1[x+1][y] == -1:
    d_mat1[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat1[x][y-1] == -1:
    d_mat1[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat1[x][y+1] == -1:
    d_mat1[x][y+1] = d+1
    q.put((x, y+1))

end = (x,y)
d_mat2[x][y] = 0
q.put(end)
while not q.empty():
  x, y = q.get()
  d = d_mat2[x][y]
  if mat[x-1][y] == "." and d_mat2[x-1][y] == -1:
    d_mat2[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat2[x+1][y] == -1:
    d_mat2[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat2[x][y-1] == -1:
    d_mat2[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat2[x][y+1] == -1:
    d_mat2[x][y+1] = d+1
    q.put((x, y+1))

print(d_mat2[x][y])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

start=[[j,i] for i in range(W) for j in range(H)]
res=0

for pt in start:
    v=[[0]*W for _ in range(H)]
    q=deque([pt+[0]])
    dist=0

    while len(q)>0:
        h,w,cnt=q.popleft()
        
        if v[h][w]==1:
            continue
        else:
            v[h][w]=1

        dist=max(dist,cnt)

        for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
            nh=h+dh
            nw=w+dw
            if 0>nh or nh>=H or 0>nw or nw>=W or S[nh][nw]=='#':
                continue
            q.append([nh,nw,cnt+1])
    
    res=max(res,dist)

print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

start=[[j,i] for i in range(W) for j in range(H)]
res=0

for pt in start:
    v=[[0]*W for _ in range(H)]

    q=deque([pt+[0]])
    dist=0

    while len(q)>0:
        h,w,cnt=q.popleft()
        dist=max(dist,cnt)

        for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
            nh=h+dh
            nw=w+dw
            if 0>nh or nh>=H or 0>nw or nw>=W or S[nh][nw]=='#' or v[nh][nw]==1:
                continue
            v[nh][nw]=1
            q.append([nh,nw,cnt+1])
    
    res=max(res,dist)

print(res)

Submission status: Wrong Answer

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

def mapping(m, n):
  
  if not(0 <= m < h) or not(0 <= n < w):
    return
  if (maze[m][n] == "#") or judge[m][n]:
    return
  
  if (0 <= m+1 < h):
    if not(maze[m+1][n] == "#"):
      MAP[m+1][n] = min(abs(MAP[m+1][n]), MAP[m][n]+1)
  if (0 <= m-1 < h):
    if not(maze[m-1][n] == "#"):
      MAP[m-1][n] = min(abs(MAP[m-1][n]), MAP[m][n]+1)
  if (0 <= n+1 < w):
    if not(maze[m][n+1] == "#"):
      MAP[m][n+1] = min(abs(MAP[m][n+1]), MAP[m][n]+1)
  if (0 <= n-1 < w):
    if not(maze[m][n-1] == "#"):
      MAP[m][n-1] = min(abs(MAP[m][n-1]), MAP[m][n]+1)
  print(MAP)    
  judge[m][n] = True
  
  mapping(m+1, n)
  mapping(m-1, n)
  mapping(m, n+1)
  mapping(m, n-1)
      
ans = 0

for i in range(h):
  for j in range(w):
    if maze[i][j] == ".":
      MAP = [[-float('inf')]*w for i in range(h)]
      judge = [[False]*w for i in range(h)]
      MAP[i][j] = 0
      can = 0
      mapping(i, j)
      for k in range(h):
        for l in range(w):
          can = max(can, MAP[k][l])
      ans = max(ans, can)

print(ans)

Submission status: Wrong Answer

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

def mapping(m, n):
  
  if not(0 <= m < h) or not(0 <= n < w):
    return
  if (maze[m][n] == "#") or judge[m][n]:
    return
  
  if (0 <= m+1 < h):
    if not(maze[m+1][n] == "#"):
      MAP[m+1][n] = min(abs(MAP[m+1][n]), MAP[m][n]+1)
  if (0 <= m-1 < h):
    if not(maze[m-1][n] == "#"):
      MAP[m-1][n] = min(abs(MAP[m-1][n]), MAP[m][n]+1)
  if (0 <= n+1 < w):
    if not(maze[m][n+1] == "#"):
      MAP[m][n+1] = min(abs(MAP[m][n+1]), MAP[m][n]+1)
  if (0 <= n-1 < w):
    if not(maze[m][n-1] == "#"):
      MAP[m][n-1] = min(abs(MAP[m][n-1]), MAP[m][n]+1)
      
  judge[m][n] = True
  
  mapping(m+1, n)
  mapping(m-1, n)
  mapping(m, n+1)
  mapping(m, n-1)
      
ans = 0

for i in range(h):
  for j in range(w):
    if maze[i][j] == ".":
      MAP = [[-float('inf')]*w for i in range(h)]
      judge = [[False]*w for i in range(h)]
      MAP[i][j] = 0
      can = 0
      mapping(i, j)
      for k in range(h):
        for l in range(w):
          can = max(can, MAP[k][l])
      ans = max(ans, can)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
area = ['#']*(W+2)
for i in range(H):
    area += ['#']+list(input())+['#']
area += ['#']*(W+2)
H+=2
W+=2
move = [-1, 1, W, -W]
ans = 0
for i in range(H):
    for j in range(W):
        st = W*i+j
        if area[st]=='#': continue
        dq = deque([])
        dist = [-1]*(H*W)
        dq.append(st)
        dist[st] = 0
        while dq:
            now = dq.popleft()
            for dx in move:
                nxt = now+dx
                if dist[nxt]>0 or area[nxt]=='#': continue
                dist[nxt] = dist[now]+1
                ans = max(ans, dist[nxt])
                dq.append(nxt)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
area = ['#']*(W+2)
for i in range(H):
    area += ['#']+list(input())+['#']
area += ['#']*(W+2)
H+=2
W+=2
move = [-1, 1, W, -W]
dq = deque([])
ans = 0
for i in range(H):
    for j in range(W):
        st = W*i+j
        if area[st]=='#': continue
        dist = [-1]*(H*W)
        dq.append(st)
        dist[st] = 0
        while dq:
            now = dq.popleft()
            for dx in move:
                nxt = now+dx
                if dist[nxt]>0 or area[nxt]=='#': continue
                dist[nxt] = dist[now]+1
                ans = max(ans, dist[nxt])
                dq.append(nxt)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import queue

INF = 10 ** 10

def solve(H: int, W: int, S: list):

    # right, bottom, left, top
    h_move = [0, 1, 0, -1]
    w_move = [1, 0, -1, 0]

    max_distance = 0
    for h_start in range(H):
        for w_start in range(W):
            distance = []
            for _ in range(H):
                l = [INF] * W
                distance.append(l)
            q = queue.Queue()
            q.put((h_start, w_start)) # スタート地点
            distance[h_start][w_start] = 0

            while not q.empty():
                h, w = q.get()
                for i in range(4):
                    h_next = h + h_move[i]
                    w_next = w + w_move[i]
                    # マップ外・壁・訪問済みを除外
                    if (h_next < 0 or h_next >= H or w_next < 0 or w_next >= W or S[h_next][w_next] != "." or distance[h_next][w_next] != INF):
                        continue
                    q.put((h_next, w_next))
                    distance[h_next][w_next] = min(distance[h][w] + 1, distance[h_next][w_next])
                    max_distance = max(max_distance, distance[h_next][w_next])

    print(max_distance)
    return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))
    W = int(next(tokens))
    S = [next(tokens) for _ in range(H)]
    solve(H, W, S)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import queue
import copy

INF = 10 ** 10

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

maze = [[-1] * (W+2)]
for _ in range(H):
    maze.append( [-1] + list( map(lambda c: INF if c == '.' else -1, input()) ) + [-1] )
maze.append([-1] * (W+2))

maze_backup = copy.deepcopy(maze)
maxpath = 0
for start_y in range(1, H+1):
    for start_x in range(1, W+1):
        if maze[start_y][start_x] == -1:
            continue
        
        counter = 0
        mincounter = 2
        for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            if maze[start_y+dy][start_x+dx] == INF:
                counter += 1
        if counter > mincounter:
            break
        else:
            mincounter = counter

        bfs_q = queue.Queue()
        bfs_q.put( (start_y, start_x) )
        maze[start_y][start_x] = 0

        while not bfs_q.empty():
            y, x = bfs_q.get()
            for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
                if maze[y+dy][x+dx] > maze[y][x] + 1:
                    maze[y+dy][x+dx] = maze[y][x] + 1
                    bfs_q.put( (y+dy, x+dx) )

        maxpath = max(maxpath, max(max(row) for row in maze))
        maze = copy.deepcopy(maze_backup)

print(maxpath)

Submission status: Wrong Answer

Solution code:
import queue
import copy

INF = 10 ** 10

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

maze = [[-1] * (W+2)]
for _ in range(H):
    maze.append( [-1] + list( map(lambda c: INF if c == '.' else -1, input()) ) + [-1] )
maze.append([-1] * (W+2))

maze_backup = copy.deepcopy(maze)
maxpath = 0
for start_y in range(1, H+1):
    for start_x in range(1, W+1):
        if maze[start_y][start_x] == -1:
            break
            
        bfs_q = queue.Queue()
        bfs_q.put( (start_y, start_x) )
        maze[start_y][start_x] = 0

        while not bfs_q.empty():
            y, x = bfs_q.get()
            for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
                if maze[y+dy][x+dx] > maze[y][x] + 1:
                    maze[y+dy][x+dx] = maze[y][x] + 1
                    bfs_q.put( (y+dy, x+dx) )

        maxpath = max(maxpath, max(max(row) for row in maze))
        maze = copy.deepcopy(maze_backup)

print(maxpath)

Submission status: Wrong Answer

Solution code:
import queue
import copy

INF = 10 ** 10

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

maze = [[-1] * (W+2)]
for _ in range(H):
    maze.append( [-1] + list( map(lambda c: INF if c == '.' else -1, input()) ) + [-1] )
maze.append([-1] * (W+2))

maze_backup = copy.deepcopy(maze)
maxpath = 0
for start_y in range(1, H+1):
    for start_x in range(1, W+1):
        if maze[start_y][start_x] == -1:
            break
            
        bfs_q = queue.Queue()
        bfs_q.put( (start_y, start_x) )
        maze[start_y][start_x] = 0

        while not bfs_q.empty():
            y, x = bfs_q.get()
            for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
                if maze[y+dy][x+dx] > maze[y][x] + 1:
                    maze[y+dy][x+dx] = maze[y][x] + 1
                    bfs_q.put( (y+dy, x+dx) )

        maxpath = max(maxpath, max(max(row) for row in maze))
        maze = copy.deepcopy(maze_backup)

print(maxpath)

Submission status: Wrong Answer

Solution code:
import queue
import copy

INF = 10 ** 10

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

maze = [[-1] * (W+2)]
for _ in range(H):
    maze.append( [-1] + list( map(lambda c: INF if c == '.' else -1, input()) ) + [-1] )
maze.append([-1] * (W+2))

maze_backup = copy.deepcopy(maze)
maxpath = 0
for start_y in range(1, H+1):
    for start_x in range(1, W+1):
        if maze[start_y][start_x] == -1:
            break
        
        counter = 0
        mincounter = 2
        for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            if maze[start_y+dy][start_x+dx] == INF:
                counter += 1
        if counter > mincounter:
            break
        else:
            mincounter = counter

        bfs_q = queue.Queue()
        bfs_q.put( (start_y, start_x) )
        maze[start_y][start_x] = 0

        while not bfs_q.empty():
            y, x = bfs_q.get()
            for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
                if maze[y+dy][x+dx] > maze[y][x] + 1:
                    maze[y+dy][x+dx] = maze[y][x] + 1
                    bfs_q.put( (y+dy, x+dx) )

        maxpath = max(maxpath, max(max(row) for row in maze))
        maze = copy.deepcopy(maze_backup)

print(maxpath)

Submission status: Wrong Answer

Solution code:
import queue

INF = 10 ** 10

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

maze = [[-1] * (W+2)]
for _ in range(H):
    maze.append( [-1] + list( map(lambda c: INF if c == '.' else -1, input()) ) + [-1] )
maze.append([-1] * (W+2))

bfs_q = queue.Queue()
bfs_q.put( (1, 1) )
maze[1][1] = 0

while not bfs_q.empty():
    y, x = bfs_q.get()
    for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        if maze[y+dy][x+dx] > maze[y][x] + 1:
            maze[y+dy][x+dx] = maze[y][x] + 1
            bfs_q.put( (y+dy, x+dx) )

print(maze[H][W])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
x = [''.join(["#"]*(w+2))]
s = x+["#"+input()+"#" for _ in range(h)]+x
ans = 0
checked_ = [[False]*(w+2) for _ in range(h+2)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        checked=checked_.copy()
        checked[i][j]=True
        stack=[[i,j]]
        stack_=[]
        count = 1
        while stack:
            pair=stack.pop()
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                if s[pair[0]+x][pair[1]+y]=="." and checked[pair[0]+x][pair[1]+y] == False:
                    stack_.append([pair[0]+x,pair[1]+y])
                    checked[pair[0]+x][pair[1]+y] = True
            if stack==[]:
                stack = stack_.copy()
                stack_ = []
                count += 1

        ans = max(ans,count)
        
print(ans-2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 19:30:35 2020

@author: Kanaru Sato
"""
import collections as col

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

"""
for i in range(len(Map)):
    print(Map[i])
""" 

def bfs(start, goal):
    #print("bfs",start,goal)
    around = [[1,0],[0,1],[-1,0],[0,-1]]
    
    dic = {}
    dic[tuple(start)] = 0
    
    q = col.deque([start])
    
    while tuple(goal) not in dic:
        #print("queue is",q)
        now = q.popleft()
        for dif in around:
            np = [now[0]+dif[0],now[1]+dif[1]]
            if tuple(np) not in dic:
                if Map[np[0]][np[1]] == ".":
                    dic[tuple(np)] = dic[tuple(now)]+1
                    q.append(np)
                else:
                    dic[tuple(np)] = "no"
    return dic[tuple(goal)]

Maxlength = -1

for start0 in range(1,h):
    for start1 in range(1,w):
        for goal0 in range(start0+1,h+1):
            for goal1 in range(start1+1,w+1):
                start = [start0, start1]
                goal = [goal0, goal1]
                if Map[start0][start1] == "." and Map[goal0][goal1] == ".":
                    length = bfs([start0,start1],[goal0,goal1])
                    if Maxlength < length:
                        Maxlength = length

print(Maxlength)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
ans = 0
def bfs(dist, s, queue):
    ret = 0
    while len(queue) > 0:
        y, x = queue.pop(0)
        for i, j in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
            h, w = y + i, x + j
            if 0 <= h < H and 0 <= w < W:
                if s[h][w] == "." and dist[h][w] == 0:
                    dist[h][w] = dist[y][x] + 1
                    queue.append([h, w])
    for i in range(H):
        ret = max(ret, max(dist[i]))
    return ret

for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            dist = [[0] * W for _ in range(H)]
            queue = [(i, j)]
            ans = max(ans, bfs(dist, s, queue))

print(ans)

Submission status: Wrong Answer

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

grid=[]

m=10**9+7

for i in range(H):
    a= list(input())
    grid.append(a)

dp=[ [0]*(W+3) for _ in range(H+3)]

for i in reversed(range(H)):
    for j in reversed(range(W)):
        dp[i][j] = dp[i+1][j] + dp[i][j+1]
        dp[H-1][W-1]=1
        if grid[i][j]=="#":
            dp[i][j]=0
print(dp[0][0]%m)