Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

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

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
  d = [[float('inf')]*w for i in range(h)]
  
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]
  ex = [2, 1, 0, -1, -2, 2, -2, 2, -2, 2, -2, 2, 1, 0, -1, -2, 1, 1, -1, -1]
  ey = [2, 2, 2, 2, 2, 1, 1, 0, 0, -1, -1, -2, -2, -2, -2, -2, 1, -1, 1, -1]
  
  que = deque([])
  que.append((ch, cw))
  d[ch][cw] = 0
  
  while que:
    p = que.popleft()
    if p[0]==dh and p[1]==dw:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==float('inf'):
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]]
      elif 0<=nx<h and 0<=ny<w and maze[nx][ny]=='#'and d[nx][ny]==float('inf'):
        for j in range(19):
          nx = p[0] + ex[j]
          ny = p[1] + ey[j]
          if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==float('inf'):
            que.append((nx, ny)) 
            d[nx][ny] = min(d[nx][ny], d[p[0]][p[1]]+1)
            
              
  return d[dh][dw]
        
  
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
maze = [list(input()) for i in range(h)]

if bfs()==float('inf'):
  print(-1)
else:
  print(bfs())

Submission status: Wrong Answer

Solution code:

import numpy as np
H, W = map(int, input().split(" "))
Ch, Cw = map(int, input().split(" "))
Dh, Dw = map(int, input().split(" "))

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1


Ss = [list(input()) for _ in range(H)]
Ss = np.array(Ss)

Ss_num = np.zeros(Ss.shape, dtype=int)
warp_counts = np.zeros(Ss.shape, dtype=int)
unvisiteds = np.zeros(Ss.shape, dtype=int)


for i in range(H):
    for j in range(W):
        Ss_num[i][j] = 1 if Ss[i][j] == "." else 0
        unvisiteds[i][j] = 1 if Ss[i][j] == "." else 0






from collections import deque
queue = deque()





queue.append((Ch, Cw))

def valid_pos(pos):
    return 0 <= pos[0] and pos[0] < H and\
        0 <= pos[1] and pos[1] < W

def pos_around(pos):
    return [
        (pos[0]-1, pos[1]),
        (pos[0],   pos[1]-1),
        (pos[0]+1, pos[1]),
        (pos[0],   pos[1]+1),
    ]

current_warp_count = 0
while True:
    
    edges = set()
    while len(queue) > 0:
        pos = queue.popleft()
        unvisiteds[pos] = 0
        warp_counts[pos] = current_warp_count

        if pos[0] == Dh and pos[1] == Dw:
            print(current_warp_count)
            exit(0)
        
        for new_pos in pos_around(pos):
            
            if valid_pos(new_pos)==False:
                continue

            
            if Ss_num[new_pos] == 1 and unvisiteds[new_pos]==1:
                queue.append(new_pos)

            if Ss_num[new_pos] == 0:
                # print(new_pos, pos)
                edges.add(pos)

        
    # print(edges)
    warp_candidate = set()
    # search can go '.' with warp  
    for edge in edges:
        edge_h = edge[0]
        edge_w = edge[1]
        
        hmin=max(0,edge_h-2)
        hmax=min(H,edge_h+3)
        wmin=max(0,edge_w-2)
        wmax=min(W,edge_w+3)
        Ss_num_area = Ss_num[hmin:hmax,wmin:wmax]
        unvisited_area = unvisiteds[hmin:hmax,wmin:wmax]
        # print(edge)
        # print(Ss_num_area)
        # print(unvisited_area)
        mul =  Ss_num_area * unvisited_area
        

        if mul.sum().sum()>0:
            for i in range(mul.shape[0]):
                for j in range(mul.shape[1]):
                    if mul[i][j] == 1:
                        warp_candidate.add((i,j))

        
    if len(warp_candidate) == 0:
        print(-1)
        exit(0)
    
    for candidate in warp_candidate:
        queue.append(candidate)
    current_warp_count += 1

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [list(map(str, input().split())) for i in range(H)]
inf = float("inf")
dp = [[inf for i in range(W)] for i in range(H)]
dp[Ch-1][Cw-1] = 0
move = [[-1, 0], [0, -1], [0, 1], [1, 0]]

for i in range(Ch-1, H):
  for j in range(Cw-1, W):
    if maze[i][0][j] == "#":
      continue
    for k,l in move:
      if 0 <= i+k <= H-1 and 0 <= j+l <= W-1:
        if maze[i+k][0][j+l] == ".":
          dp[i][j] = min(dp[i+k][j+l], dp[i][j])      
    for m in range(-2, 3):
      for n in range(-2, 3):
        if not m and not n:
          continue
        if 0 <= i+m <= H-1 and 0 <= j+n <= W-1:
          if maze[i+m][0][j+n] == ".":
            dp[i][j] = min(dp[i+m][j+n]+1, dp[i][j])

          
print(dp[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))

# from collections import defaultdict
from queue import Queue

path = dict()
cache = set()

Cur = (Cw-1, Ch-1)
Q = Queue()
Q.put(Cur)
cache.add(Cur)

path[Cur] = 0
G = (Dw - 1, Dh - 1)

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

wdx = []
wdy = []

while not Q.empty():
    node = Q.get()
    cx, cy = node

    # move
    for di in range(4):
        nx = cx + dx[di]
        ny = cy + dy[di]

        if W > nx >= 0 and H > ny >= 0:
            nt = (nx, ny)
            if S[ny][nx] == '.':
                if nt not in cache:
                    # 移動可能
                    Q.put(nt)
                    cache.add(nt)
                    path[nt] = path[node]

                elif nt in path.keys() and path[node] < path[nt]:
                    path[nt] = path[node]
    
    # warp
    for wdx in range(-2, 3, 1):
        for wdy in range(-2, 3, 1):

            nx = cx + wdx
            ny = cy + wdy
            nt = (nx, ny)

            if W > nx >= 0 and H > ny >= 0 and S[ny][nx] == '.':
                if nt not in cache:
                    Q.put(nt)
                    cache.add(nt)
                    path[nt] = path[node] + 1
                elif nt in path.keys() and path[node] + 1 < path[nt]:
                    path[nt] = path[node] + 1

print(path[G] if G in path.keys() else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
sh, sw = map(int, input().split())
sh -= 1
sw -= 1
gh, gw = list(map(int, input().split()))
gh -= 1
gw -= 1
lst = []
for _ in range(H):
    lst.append(list(str(input())))
    
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
visited = [[0]*W for _ in range(H)]

def dfs(sh, sw):
    global visited
    global flg
    flg = 0
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    c = 0
    while stack:
        sh, sw = stack.pop()
        if sh == gh and sw  == gw:
            flg = 1
            break
        for i in range(4):
            nx = sh + dx[i]
            ny = sw + dy[i]
            if 0 > nx or nx >= H or 0 > ny or ny >= W:
                continue
            else:
                if lst[nx][ny] == '#' or visited[nx][ny] == 1:
                    continue
                else:
                    visited[nx][ny] = 1
                    stack.append([nx, ny])

c = lst.count('.')
ans = 0

dfs(sh, sw)

if visited[gh][gw]:
    print(ans)
    
for h in range(H):
    for w in range (W):
        if visited[h][w] == 0 and lst[h][w] != '#':
            arr = np.array(visited)[max(0, h-2):min(H, h+3),max(0, w-2):min(W, w+3)].tolist()
            if sum(arr, []).count(1) >= 1:
                ans += 1
                dfs(h,w)
                if flg:
                    break

                
for h in range(H):
    for w in range (W):
        if visited[h][w] == 0 and lst[h][w] != '#':
            arr = np.array(visited)[max(0, h-2):min(H, h+3),max(0, w-2):min(W, w+3)].tolist()
            if sum(arr, []).count(1) >= 1:
                ans += 1
                dfs(h,w)
                if flg:
                    break

                
if visited[gh][gw]:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
"""連続する場所をそれぞれ付番
それぞれの領域からワープで飛べる先をリストで保存
いる場所から順に0, 1, 2と幅優先"""
H, W = [int(i) for i in input().split()]
Ci, Cj = [int(i)-1 for i in input().split()]
Di, Dj = [int(i)-1 for i in input().split()]
S = []
for i in range(H):
    S.append([i for i in input()])


def append_label_4(i, j, n):
    ret = 0
    labeling_list = [[i, j]]
    while labeling_list:
        i, j = labeling_list[-1]
        labeling_list = labeling_list[:-1]
        S[i][j] = n
        if i != 0 and S[i-1][j] != '#' and S[i-1][j] != n:
            labeling_list.append([i-1, j])
            S[i-1][j] = n
        if i != H-1 and S[i+1][j] != '#' and S[i+1][j] != n:
            labeling_list.append([i+1, j])
            S[i+1][j] = n
        if j != 0 and S[i][j-1] != '#' and S[i][j-1] != n:
            labeling_list.append([i, j-1])
            S[i][j-1] = n
        if j != W-1 and S[i][j+1] != '#' and S[i][j+1] != n:
            labeling_list.append([i, j+1])
            S[i][j+1] = n
        for ii in range(max(0, i-2), min(H-1, i+2)+1):
            for jj in range(max(0, j-2), min(W-1, j+2)+1):
                if S[ii][jj] == '.':
                    S[ii][jj] = n+1
                    ret = n+1
    return ret


hops = append_label_4(Ci, Cj, 0)
change = 1
while change:
    change = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == hops:
                ret = append_label_4(i, j, hops)
                if ret == hops + 1:
                    change = 1

if S[Di][Dj] == '.':
    print(-1)
else:
    print(S[Di][Dj])

Submission status: Wrong Answer

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


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "#":
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def dijkstra(N, G, start, INF=10**7):
    h = []
    heapq.heappush(h, (start, 0))
    D = [INF] * N
    D[start] = 0
    while h:
        v, cost = heapq.heappop(h)
        if cost > D[v]:
            continue
    for u, d in G[v].items():
        tmp = d + cost[v]
        if tmp < cost[u]:
            cost[u] = tmp
            heapq.heappush(h, (tmp, u))
    return D

def bellman_ford(N, G, start, INF=10**7):
    D = [INF] * N
    D[start] = 0
    for k in range(N):
        for i in range(N):
            for j, v in G[i].items():
                if D[j] > D[i] + v:
                    D[j] = D[i] + v
    return D


def solve(H, W, CH, CW, DH, DW, S, INF=10**7):
    DIR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    # 島を作る
    id = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == -1:
                id += 1
                S[i][j] = id
                q = deque()
                q.append((i, j))
                while q:
                    y, x = q.popleft()
                    for dy, dx in DIR:
                        ny, nx = y+dy, x+dx
                        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                            S[ny][nx] = id
                            q.append((ny, nx))

    start_id = S[CH-1][CW-1]
    goal_id = S[DH-1][DW-1]
    if start_id == goal_id:
        return 0

    # id: 島の数
    N = id
    G = [dict() for i in range(N)]

    # 島を連結する
    for i in range(H):
        for j in range(W):
            source_id = S[i][j]
            if source_id > 0:
                for k in range(i-2, i+3):
                    for l in range(j-2, j+3):
                        if 0 <= k < H and 0 <= l < W:
                            target_id = S[k][l]
                            if target_id > 0 and source_id != target_id:
                                G[source_id-1][target_id-1] = 1
                                G[target_id-1][source_id-1] = 1
    
    visited = [-1 for i in range(N)]
    q = deque()
    visited[start_id-1] = 0
    q.append((start_id-1, 0))
    while q:
        u, d = q.pop()
        if u == goal_id-1:
            break
        for v in G[u]:
            if visited[v] == -1:
                visited[v] = d+1
                q.append((v, d+1))
    return visited[goal_id-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

Cx,Cy = map(int,input().split())
Cx,Cy = Cx-1,Cy-1
Dx,Dy = map(int,input().split())
Dx,Dy = Dx-1,Dy-1
S = [input() for _ in range(H)]
vec = [(1,0),(0,1),(-1,0),(0,-1)]
visited = [[0 for i in range(W)] for j in range(H)]
costs = [[0 for i in range(W)] for j in range(H)]

warp = [(2,0),(-2,0),(2,0),(0,2),(1,1),(1,-1),(-1,1),(-1,-1),(2,2),(2,-2),(-2,2),(-2,-2)]
def search():

    que = deque()##x,y,warp
    que.append([Cx,Cy,0])
    visited[Cx][Cy] = 1
    costs[Dx][Dy] = float("inf")

    ##一回Visitedにしておく
    while que:

        x,y,cost = que.popleft()

        for i,j in vec:
            dx = x + i
            dy = y + j

            ##移動
            if 0 <= dx < H and 0 <= dy < W:
                if not visited[dx][dy] and S[dx][dy] == ".":
                    visited[dx][dy] = 1
                    costs[dx][dy] = min(costs[dx][dy],cost)
                    que.append((dx,dy,cost))
            ##壁超え+斜めワープ
            for s,t in warp:
                ddx = x + s
                ddy = y + t

                if 0 <= ddx < H and 0 <= ddy < W:
                    if not visited[ddx][ddy] and S[ddx][ddy] == "." :
                        visited[ddx][ddy] = 1
                        costs[ddx][ddy] = min(costs[ddx][ddy],cost+1)
                        que.append((ddx,ddy,cost+1))
    return costs[Dx][Dy]

ans = search()

if ans == float("inf"):
    print(-1)
else:
    print(ans-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

C = list(map(int,input().split()))
D = list(map(int,input().split()))

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

ido = [[1,0],[0,1],[-1,0],[0,-1]]

warp = [[2,2],[2,1],[1,2],[0,2],[2,0],[-2,-2],[-2,-1],[-1,-2],[0,-2],[-2,0],[2,-2],[2,-1],[1,-2],[-2,2],[-2,1],[-1,2],[1,1],[1,-1],[-1,1],[-1,-1]]

d = deque()
d.append([C[1]-1,C[0]-1])
cost = [[10000000 for i in range(W)] for j in range(H)]
flg = [[-1 for i in range(W)] for j in range(H)]

cost[C[0]-1][C[1]-1] = 0
flg[C[0]-1][C[1]-1] = 1

while d:
    x,y = d.popleft()
    for dx, dy in ido:
        nx = x + dx
        ny = y + dy

        if 0>nx or W<=nx or 0>ny or H<=ny:
            continue

        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x],cost[ny][nx])
        if flg[ny][nx] != -1 :
            continue
        d.append([nx,ny])
        flg[ny][nx] = 1

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 > nx or W <= nx or 0 > ny or H <= ny:
            continue
        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x]+1, cost[ny][nx])
        if flg[ny][nx] != -1:
            continue
        d.append([nx, ny])
        flg[ny][nx] = 1

answer = cost[D[0]-1][D[1]-1]
if answer == 10000000:
    print(-1)
else:
    print(answer)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
field = set()

cnt = 0
for i in range(h):
  s = input()
  for j in range(w):
    if s[j] == ".":
      field.add((i, j))
      cnt += 1

ans = 0
dq = deque()

while (dh - 1, dw - 1) in field:
  field2 = set()
  dq.append((ch - 1, cw - 1))
  field2.add((ch - 1, cw - 1))
  while len(dq) > 0:
    now_h, now_w = dq.popleft()
    if (now_h, now_w) in field:
      field.remove((now_h, now_w))
      cnt -= 1
    if (now_h - 1, now_w) in field:
      dq.append((now_h - 1, now_w))
      field2.add((now_h - 1, now_w))
    if (now_h + 1, now_w) in field:
      dq.append((now_h + 1, now_w))
      field2.add((now_h + 1, now_w))
    if (now_h, now_w - 1) in field:
      dq.append((now_h, now_w - 1))
      field2.add((now_h + 1, now_w))
    if (now_h, now_w + 1) in field:
      dq.append((now_h, now_w + 1))
      field2.add((now_h, now_w + 1))
  
  if (dh - 1, dw - 1) in field:
    flag = False
    for _h, _w in field2:
      if flag:
        break
      for i in range(-2, 3):
        if flag:
          break
        for j in range(-2, 3):
          if (_h + i, _w + j) in field:
            ans += 1
            ch, cw = _h + i + 1, _w + j + 1
            flag = True
            break

print(ans if cnt == 0 else -1)

Submission status: Wrong Answer

Solution code:
import collections
h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
s = [input() for _ in range(h)]
table = [[float('inf') for _ in range(w)] for _ in range(h)]
table[Ch][Cw] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
used = [[0 for _ in range(w)] for _ in range(h)]
used[Ch][Cw] = 1
que = collections.deque()
que.append([Ch, Cw])

def bfs(Q):
    while Q:
        # print(Q)
        v = Q.popleft()
        i = v[0]
        j = v[1]
        for k in range(4):
            if 0 <= i+dy[k] < h and 0 <= j+dx[k] < w:
                if s[i+dy[k]][j+dx[k]] == '.':
                    if used[i+dy[k]][j+dx[k]] == 0:
                        table[i+dy[k]][j+dx[k]] = table[i][j]
                        used[i+dy[k]][j+dx[k]] = 1
                        Q.append([i+dy[k], j+dx[k]])
                        # magic
        for a in range(-2, 3):
            for b in range(-2, 3):
                if 0 <= i+a < h and 0 <= j+b < w:
                    if s[i+a][j+b] == '.':
                        table[i+a][j+b] = min(table[i][j]+1, table[i+a][j+b])
        # print(*table, sep='\n')
        # print(*used, sep='\n')
        # print(*s, sep='\n')

bfs(que)
while True:
    for i in range(h):
        for j in range(w):
            if used[i][j] == 0 and table[i][j] != float('inf'):
                que = collections.deque()
                que.append([i, j])
                bfs(que)
    break

if table[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(table[Dh][Dw])
                # print(*table, sep='\n')
                # print(*used, sep='\n')
                # print(*s, sep='\n')

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
cy,cx = map(int,input().split())
dy,dx = map(int,input().split())
cx,cy = cx-1,cy-1
dx,dy = dx-1,dy-1

field = []
w_count = []
for h in range(H):
    line = input()
    line = [ p for p in line]
    field.append(line)
    line_c = [ H*W for i in line]
    w_count.append(line_c)
w_count[cy][cx] = 0

visited = set()
que = [(cx,cy)]
while len(que)!=0:
    x,y = que.pop(0)
    if (x,y) in visited:
        continue
    visited.add((x,y))
    x_min = x-2 if x>=2 else 0
    x_max = x+2 if x<=W-3 else W-1 
    y_min = y-2 if y>=2 else 0
    y_max = y+2 if y<=H-3 else H-1 
    for new_x in range(x_min,x_max+1):
        for new_y in range(y_min,y_max+1):
            if field[new_y][new_x]=='#':
                continue

            if ((new_x==x) and (new_y==y-1)) or ((new_x==x-1) and (new_y==y)) or ((new_x==x) and (new_y==y+1)) or ((new_x==x+1) and (new_y==y)):
                que.append((new_x,new_y))
                w_count[new_y][new_x] = min(w_count[y][x],w_count[new_y][new_x])
            else:
                que.append((new_x,new_y))
                w_count[new_y][new_x] = min(w_count[y][x]+1,w_count[new_y][new_x])




ans = -1 if w_count[dy][dx]==H*W else w_count[dy][dx]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [list(input()) for _ in range(h)]



def clear_maze(h, w, ch, cw, dh, dw, S):
    visited = [[-1] * w for _ in range(h)]
    visited[ch - 1][cw - 1] = 0
    queue = deque([[ch - 1 , cw - 1]])
    while queue:
        y, x = queue.popleft()
        if [y, x] == [dh - 1, dw - 1]:
            return visited[y][x]
        num = 0
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y = y + i
            n_x = x + j
            if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.':
                if visited[n_y][n_x] == -1:
                    visited[n_y][n_x] = visited[y][x]
                    queue.append([n_y, n_x])
                else:
                    # if visited[y][x] < visited[n_y][n_x]:
                    #     queue.append([n_y, n_x])
                    visited[n_y][n_x] = min(visited[n_y][n_x], visited[y][x])
        for i in range(-2, 2 + 1):
            for j in range(-2, 2 + 1):
                if not [i, j] in ([1, 0], [-1, 0], [0, 0], [0, 1], [0, -1]):
                    n_y = y + i
                    n_x = x + j
                    if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.':
                        if visited[n_y][n_x] == -1:
                            visited[n_y][n_x] = visited[y][x] + 1
                            queue.append([n_y, n_x])
                        else:
                            # if visited[y][x] + 1 < visited[n_y][n_x]:
                            #     queue.append([n_y, n_x])
                            visited[n_y][n_x] = min(visited[n_y][n_x], visited[y][x] + 1)
    return -1

print(clear_maze(h, w, ch, cw, dh, dw, S))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

h, w = map(int, input().split(" "))
ch, cw = map(int, input().split(" "))
ch -= 1
cw -= 1
dh, dw = map(int, input().split(" "))
dh -= 1
dw -= 1

map_ = []
for hi in range(h):
    s = input()
    line = [None if s[wi] == "." else "#" for wi in range(w)]
    map_.append(line)        

#print(map_)

def umeru(x, y, cur_cost, cur_kabe):
    map_[y][x] = cur_cost
    global cur_kabes
    tonaris = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]

    for nx, ny in tonaris:
        if 0 <=nx<w and 0<=ny<h:
            if map_[ny][nx] is None:
                map_[ny][nx] = cur_cost
                umeru(nx, ny, cur_cost, cur_kabe)
            elif map_[ny][nx] == cur_kabe:
                #print((x, y), (nx, ny))
                #map_[ny][nx] -= 1
                map_[ny][nx] = "$"
                cur_kabes.append([nx, ny])

    tonaris = [[x-1, y-1], [x-1, y+1], [x+1, y-1], [x+1, y+1]]
    for nx, ny in tonaris:
        if 0 <=nx<w and 0<=ny<h:
            if map_[ny][nx] == cur_kabe:
                #print((x, y), (nx, ny))
                #map_[ny][nx] -= 1
                map_[ny][nx] = "$"
                cur_kabes.append([nx, ny])

def find_ins(x, y):
    tonaris = [[nx, ny] for nx in [x-1, x, x+1] for ny in [y-1, y, y+1]]
    ins = []
    
    for nx, ny in tonaris:
        if 0 <=nx<w and 0<=ny<h:
            if map_[ny][nx] is None:
                ins.append([nx, ny])
    return ins


                
                
ins = [[cw, ch]]
cur_cost = 0
cur_kabe = "#"
while True:
    cur_kabes = []
    for inw, inh in ins:
        umeru(inw, inh, cur_cost, cur_kabe)

    ins = []
    for x, y in cur_kabes:
        ins += find_ins(x, y)

    if len(ins) == 0:
        break
        
    cur_cost += 1
    #cur_kabe -= 1

if False:
    for m in map_:
        line = []
        for c in m:
            if c is None:
                c = "."
            elif isinstance(c, int):
                c = str(c)
            line.append(c)
        print("".join(line))

out = map_[dh][dw]
if out is None:
    out = -1
print(out)

Submission status: Wrong Answer

Solution code:
def resolve():
    from collections import deque

    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    c_h -= 1
    c_w -= 1
    d_h, d_w = map(int, input().split())
    d_h -= 1
    d_w -= 1

    C = []
    for _ in range(h):
        C.append(list(input()))
    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([(c_h, c_w, 0)])

    def magic(x, y):
        ret = []
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if abs(dx) + abs(dy) > 1 and -1 < x + dx < h and -1 < y + dy < w:
                    if C[x + dx][y + dy] == '.':
                        ret.append((x + dx, y + dy))
        return ret

    A = []
    while queue:
        (x, y, m) = queue.popleft()
        if x == d_h and y == d_w:
            A.append(m)

        C[x][y] = '#'
        for (dx, dy) in D:
            new_x, new_y = x + dx, y + dy
            if -1 < new_x < h and -1 < new_y < w:
                if C[new_x][new_y] == '.':
                    queue.append((new_x, new_y, m))
                else:
                    L = magic(x, y)
                    if len(L) > 0:
                        for l in L:
                            queue.append((l[0], l[1], m + 1))
                    else:
                        A.append(10**16)

    ans = min(A)
    if ans == 10**16:
        ans = -1
    print(ans)
    
resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

C = list(map(int,input().split()))
D = list(map(int,input().split()))

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

ido = [[1,0],[0,1],[-1,0],[0,-1]]

warp = [[2,2],[2,1],[1,2],[0,2],[2,0],[-2,-2],[-2,-1],[-1,-2],[0,-2],[-2,0],[2,-2],[2,-1],[1,-2],[-2,2],[-2,1],[-1,2],[1,1],[1,-1],[-1,1],[-1,-1]]

d = deque()
d.append([C[1]-1,C[0]-1])
cost = [[100000 for i in range(W)] for j in range(H)]
flg = [[-1 for i in range(W)] for j in range(H)]

cost[C[0]-1][C[1]-1] = 0
flg[C[0]-1][C[1]-1] = 1

while d:
    x,y = d.popleft()
    for dx, dy in ido:
        nx = x + dx
        ny = y + dy

        if 0>nx or W<=nx or 0>ny or H<=ny:
            continue

        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x],cost[ny][nx])
        if flg[ny][nx] != -1 :
            continue
        d.append([nx,ny])
        flg[ny][nx] = 1

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 > nx or W <= nx or 0 > ny or H <= ny:
            continue
        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x]+1, cost[ny][nx])
        if flg[ny][nx] != -1:
            continue
        d.append([nx, ny])
        flg[ny][nx] = 1
        
answer = cost[D[0]-1][D[1]-1]
if answer == 100000:
    print(-1)
else:
    print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

def show_merio(meiro):
    for i in meiro:
        print(i)

def check(area1, area2):
    area2_set = set(map(tuple, area2))
    new_area1 = []
    for p in area1:
        for i in range(p[0]-2, p[0] + 3):
            for j in range(p[1]-2, p[1] + 3):
                new_area1.append((i, j))
        if len(set(new_area1) & area2_set) != 0:
            return True
    return False
        
    
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    s_meiro = []
    for i in range(h):
        s_meiro.append(list(input()))
    print(s_meiro)

    area = [[0 for j in range(w)] for i in range(h)]
    area_dict = {}
    area_id = 1
    for i in range(h):
        for j in range(w):
            show_merio(area)
            if s_meiro[i][j] == '.':
                if i != 0:
                    up_id = area[i-1][j]
                else:
                    up_id = 0
                if j != 0:
                    left_id = area[i][j-1]
                else:
                    left_id = 0
                # if i == 0 and j== 0:
                #     area[i][j] = area_id
                #     area_id += 1
                print(str(i+1) + ':' +str(j+1))
                print(up_id, end=' ')
                print(left_id)
                print('------------')
                if up_id == 0 and left_id == 0:
                    area[i][j] = area_id
                    if not area_id in area_dict.keys():
                        area_dict[area_id] = [[i+1, j+1]]
                    else:
                        area_dict[area_id].append([i+1, j+1])
                    area_id += 1
                else:
                    if up_id == left_id:
                        area[i][j] = up_id
                        if not up_id in area_dict.keys():
                            area_dict[up_id] = [[i+1, j+1]]
                        else:
                            area_dict[up_id].append([i+1, j+1])
                    elif up_id*left_id == 0:
                        area[i][j] = max(up_id, left_id)
                        if not area[i][j] in area_dict.keys():
                            area_dict[area[i][j]] = [[i+1, j+1]]
                        else:
                            area_dict[area[i][j]].append([i+1, j+1])
                    else:
                        area[i][j] = min(up_id, left_id)
                        area_dict[area[i][j]] += area_dict[max(up_id, left_id)]
                        area_dict.pop(max(up_id, left_id))
    area_list = [[0 for j in range(w)] for i in range(h)]
    keys = list(area_dict.keys())
    for i in range(len(keys)-1):
        for j in range(i+1, len(keys)):
            if check(area_dict[keys[i]], area_dict[keys[j]]):
                print('yes')
        
    print(area_dict)
                        
                

if __name__ == '__main__':
    main()