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

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:
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
d = [list(input()) for l in range(a[0])]
gcan = 0
minwarp = 100000

import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
h,w = a[0],a[1]



def dfs(x,y,z):
    global minwarp
    global gcan
    if not(0 <= x < h) or not(0 <= y < w): # 壁に当たったり、探索範囲外になった場合はreturn
        return
    elif d[x][y] == "#":
        mx = x - 2
        if mx < 0:
            mx = 0
        my = y - 2
        if my < 0:
            my = 0
        px = x + 2
        if px >= h:
            px = h
        py = y + 2
        if py >= w:
            py = w
        pz = z
        for i in range(mx, px):
            for j in range(my, py):
                if d[i][j] == ".":
                    x = i
                    y = j
                    z = pz + 1
                    dfs(x,y,z)
        return
    if x == c[0] - 1 and y == c[1] - 1: # ゴールを見つけたら”Yes”を出力して終了
        if minwarp > z:
            minwarp = z
        gcan += 1
        return
        
    d[x][y] = "#" #探索済みを示すためのマーキング
    dfs(x+1,y,z)
    dfs(x-1,y,z)
    dfs(x,y+1,z)
    dfs(x,y-1,z)

sx, sy = b[0], b[1] # スタート位置
sz = 0
dfs(sx, sy, sz)
if gcan == 0:
    print("-1")
else:
    print(str(minwarp - 2))

Submission status: Wrong Answer

Solution code:
import sys, math

# input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


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


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]


groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue
        g = []
        for s in S[i:i+1]:
            g += s[j:j + 1]
            # g += s[max(0, j - 2):j + 3]

        g = set(g)
        if -1 in g:
            g.remove(-1)
        for k in g:
            can_reach[S[i][j]][k] = True
            can_reach[k][S[i][j]] = True
"""
can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()

reached = [s]
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    new_reached = []
    ans += 1
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[k]:
                new_reached.append(k)
    reached = list(set(new_reached))
print(-1)
"""

Submission status: Wrong Answer

Solution code:

# lrud = [[0, -1], [0, 1], [-1, 0], [1, 0], \
#     [1, -1], [1, 1], [-1, -1], [-1, 1]]
lrud = [[0, -1], [0, 1], [-1, 0], [1, 0]]
lrud2 = [[-1, -1], [1, 1], [-1, 1], [1, -1]]
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch, Cw = Ch-1, Cw-1
Dh, Dw = map(int, input().split())
Dh, Dw = Dh-1, Dw-1
S = [list(input()) for i in range(H)]

is_visited = [[float('inf') for j in range(W)]for i in range(H)]
is_visited[Ch][Cw] = 0
for i in range(2):
    for x in range(H):
        for y in range(W):
            cost = int(S[x][y] == '#')
            for dx, dy in lrud:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and (not (cost and S[nx][ny]=='#')):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
            for dx, dy in lrud2:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and (cost != int(S[nx][ny]=='#')):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
    for x in range(H-1, -1, -1):
        for y in range(W-1, -1, -1):
            cost = int(S[x][y] == '#')
            for dx, dy in lrud:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and (not (cost and S[nx][ny]=='#')):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
            for dx, dy in lrud2:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and (cost != int(S[nx][ny]=='#')):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
# print(is_visited)
if is_visited[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(is_visited[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
ch-=1
cw-=1
dh,dw=nii()
dh-=1
dw-=1
s=[list(input()) for i in range(h)]

dist=[[-1]*w for i in range(h)]

def BFS(que):
  while que:
    y,x=que.popleft()

    if y==dh and x==dw:
      print(dist[y][x])
      exit()

    t_cnt=0
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
        que.append((ny,nx))
        s[ny][nx]='#'
        dist[ny][nx]=dist[y][x]
        t_cnt+=1
    if t_cnt==0:
      for dy,dx in [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
                    [-1,-2],[-1,-1],[-1,1],[-1,2],\
                    [0,-2],[0,2],\
                    [1,-2],[1,-1],[1,1],[1,2],\
                    [2,-2],[2,-1],[2,0],[2,1],[2,2]]:
        ny=y+dy
        nx=x+dx
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==-1:
          que.append((ny,nx))
          s[ny][nx]='#'
          dist[ny][nx]=dist[y][x]+1

dist[ch][cw]=0

que=deque()
que.append((ch,cw))

BFS(que)

print(-1)

Submission status: Wrong Answer

Solution code:
def main2():
    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()
    arrived = [[0 for i in range(W)] for j in range(H)]
    arrived[Ch][Cw] = 1

    for i in range(H):
        maze.append(list(input()))

    ans = 0
    for i in range(10**7):
        if Ch == Dh and Cw == Dw:
            print(ans)
            exit()

        update_flag = 0
        if Cw + 1 < W and maze[Ch][Cw + 1] == "." and arrived[Ch][Cw + 1] == 0:
            Cw += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch + 1 < H and maze[Ch + 1][Cw] == "." and arrived[Ch + 1][Cw] == 0:
            Ch += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Cw - 1 > 0 and maze[Ch][Cw - 1] == "." and arrived[Ch][Cw - 1] == 0:
            Cw -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch - 1 > 0 and maze[Ch - 1][Cw] == "." and arrived[Ch - 1][Cw] == 0:
            Ch -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1

        if update_flag == 0:
            find = 0
            for i in range(2, -3, -1):
                for j in range(2, -3, -1):
                    x = Cw + j
                    y = Ch + i

                    if 0 <= y < H and 0 <= x < W:
                        if y == Dh and x == Dw:
                            Ch = Dh
                            Cw = Dw
                            find = 1
                            ans += 1
                            break

                        elif maze[y][x] == "." and arrived[y][x] == 0:
                            Ch = y
                            Cw = x
                            find = 1
                            ans += 1
                            break

                if find == 1:
                    break

            if find == 0:
                print(-1)
                exit()


if __name__ == "__main__":
    main2()

Submission status: Wrong Answer

Solution code:
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

start = (Ch, Cw)

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

counter = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      counter[k][j] = 10**6

counter[Ch][Cw] = 0

#print(counter)
#print(S)

now = [start]
for item in now:
  x = item[0]
  y = item[1]
  if counter[x+1][y] == 10**6:
    counter[x+1][y] = 0
    now.append((x+1, y))
  if counter[x][y+1] == 10**6:
    counter[x][y+1] = 0
    now.append((x, y+1))
  if counter[x-1][y] == 10**6:
    counter[x-1][y] = 0
    now.append((x-1, y))
  if counter[x][y-1] == 10**6:
    counter[x][y-1] = 0
    now.append((x, y-1))

#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 10**6:
  if len(now) == 0:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    x = item[0]
    y = item[1]
    if counter[x+2][y+2] > ans:
      counter[x+2][y+2] = ans
      nextlist.append((x+2, y+2))
    if counter[x+2][y+1] > ans:
      counter[x+2][y+1] = ans
      nextlist.append((x+2, y+1))
    if counter[x+2][y] > ans:
      counter[x+2][y] = ans
      nextlist.append((x+2, y))
    if counter[x+2][y-1] > ans:
      counter[x+2][y-1] = ans
      nextlist.append((x+2, y-1))
    if counter[x+2][y-2] > ans:
      counter[x+2][y-2] = ans
      nextlist.append((x+2, y-2))
    if counter[x+1][y+2] > ans:
      counter[x+1][y+2] = ans
      nextlist.append((x+1, y+2))
    if counter[x+1][y-2] > ans:
      counter[x+1][y-2] = ans
      nextlist.append((x+1, y-2))
    if counter[x][y+2] > ans:
      counter[x][y+2] = ans
      nextlist.append((x, y+2))
    if counter[x][y-2] > ans:
      counter[x][y-2] = ans
      nextlist.append((x, y-2))
    if counter[x-2][y+2] > ans:
      counter[x-2][y+2] = ans
      nextlist.append((x-2, y+2))
    if counter[x-2][y+1] > ans:
      counter[x-2][y+1] = ans
      nextlist.append((x-2, y+1))
    if counter[x-2][y] > ans:
      counter[x-2][y] = ans
      nextlist.append((x-2, y))
    if counter[x-2][y-1] > ans:
      counter[x-2][y-1] = ans
      nextlist.append((x-2, y-1))
    if counter[x-2][y-2] > ans:
      counter[x-2][y-2] = ans
      nextlist.append((x-2, y-2))
    if counter[x-1][y+2] > ans:
      counter[x-1][y+2] = ans
      nextlist.append((x-1, y+2))
    if counter[x-1][y-2] > ans:
      counter[x-1][y-2] = ans
      nextlist.append((x-1, y-2))
  if len(nextlist) == 0:
    print(-1)
    exit()
  
  for item in nextlist:
    x = item[0]
    y = item[1]
    if counter[x+1][y] > ans:
      counter[x+1][y] = ans
      nextlist.append((x+1, y))
    if counter[x][y+1] > ans:
      counter[x][y+1] = ans
      nextlist.append((x, y+1))
    if counter[x-1][y] > ans:
      counter[x-1][y] = ans
      nextlist.append((x-1, y))
    if counter[x][y-1] > ans:
      counter[x][y-1] = ans
      nextlist.append((x, y-1))
  now = nextlist
  if ans > 10**6:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
HW = [list(input()) for _ in range(H)]


def check(ny, nx):
    if 0 <= ny < H and 0 <= nx < W and HW[ny][nx] != "#":
        return True
    else:
        return False


def check2(ny, nx):
    if 0 <= ny < H and 0 <= nx < W and HW[ny][nx] == ".":
        return True
    else:
        return False


HW[ch - 1][cw - 1] = "#"
dist = [[float("inf")] * W for _ in range(H)]
# print("dist")
# pl(dist)
dist[ch - 1][cw - 1] = 0


deq = deque()
deq.append([(ch - 1, cw - 1)])  # insert indices
ddy = [-1, 0, 1, 0]
ddx = [0, -1, 0, 1]
warpy = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
warpx = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
step = 0
found = False
cnt = 0
while deq[0]:
    nqueue = []
    cqueue = deq.popleft()
    # pl(HW)
    # pl(dist)
    for val in cqueue:
        y, x = val
        # if val == (gy - 1, gx - 1):
        #     found = True
        #     break
        for dy, dx in zip(ddy, ddx):
            chky = set()
            chkx = set()
            ny, nx = y + dy, x + dx
            if check(ny, nx):
                if dy != 0:
                    chky.add(dy)
                    chky.add(dy * 2)
                if dx != 0:
                    chkx.add(dx)
                    chkx.add(dx * 2)
                HW[ny][nx] = "#"
                if dist[y][x] < dist[ny][nx]:
                    dist[ny][nx] = dist[y][x]
                # dist[ny][nx] = min(dist[ny][nx], dist[y][x])
                nqueue.append((ny, nx))
        for dy, dx in zip(warpy, warpx):
            if (dy in chky) or (dx in chkx):
                continue
            # cnt += 1
            ny, nx = y + dy, x + dx
            if check2(ny, nx):
                HW[ny][nx] = "X"
                if dist[y][x] + 1 < dist[ny][nx]:
                    dist[ny][nx] = dist[y][x] + 1
                # dist[ny][nx] = min(dist[ny][nx], dist[y][x] + 1)
                nqueue.append((ny, nx))
    # if found:
    #     break
    deq.append(nqueue)
    # step += 1
# print(cnt)
val = dist[dh - 1][dw - 1]
if val == float("inf"):
    print(-1)
else:
    print(val)
# print(dist[dh - 1][dw - 1])

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    H,W = LMIIS()
    Ch,Cw = LMIIS()
    Ch -= 1
    Cw -= 1
    Dh,Dw = LMIIS()
    Dh -= 1
    Dw -= 1
    S = []
    for i in range(H):
        S.append(input())
    
    num_warp = []
    for i in range(H):
        num_warp.append([-1]*W)
    num_warp[Ch][Cw] = 0
    
    targets_walk = deque([(Ch,Cw)])
    targets_warp = deque([(Ch,Cw)])

    def check_and_move(y,x,n):
        if 0 <= y < H and 0 <= x < W and num_warp[y][x] == -1 and S[y][x] == '.':
            num_warp[y][x] = n
            return True
        return False




    # BFS


    #　歩いて行ける範囲を全部いく
    while targets_walk:
        y,x = targets_walk.pop()
        num_currrent_warp = num_warp[y][x]
        for y2,x2 in [(y-1,x),(y,x+1),(y+1,x),(y,x-1)]:
            if check_and_move(y2,x2,num_currrent_warp):
                    # 歩きの探索対象に追加
                    targets_walk.append((y2,x2))
                    # ワープの探索対象に追加
                    targets_warp.append((y2,x2))


    # 一回ワープ -> 歩いて行ける範囲を全部潰す
    while targets_warp:
            y,x = targets_warp.popleft()
            num_currrent_warp = num_warp[y][x]
            for y2,x2 in[
                    (y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),
                    (y-1,x-2),(y-1,x-1),(y-1,x+1),(y-2,x+2),
                    (y,x-2),(y,x+2),
                    (y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),
                    (y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2)
                ]:
                if check_and_move(y2,x2,num_currrent_warp+1):
                    targets_walk = deque([(y2,x2)])
                    while targets_walk:
                        y3,x3 = targets_walk.popleft()
                        for y4,x4 in [(y3-1,x3),(y3,x3+1),(y3+1,x3),(y3,x3-1)]:
                            if check_and_move(y4,x4,num_currrent_warp+1):
                                targets_walk.append((y4,x4))
                                targets_warp.append((y4,x4))





                if check_and_move(y2,x2,num_currrent_warp+1):
                    # 歩きの探索対象に追加
                    targets_walk.append((y2,x2))









    ans = num_warp[Dh][Dw]
    print(-1 if ans == INF else ans)


    
main()

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [list(input()) for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))
    while q:
        cnt = 0
        cost, px, py = heappop(q)
        # for xi, yj in dxy:
        #     x = px + xi
        #     y = py + yj
        #     if x >= h or y >= w or x < 0 or y < 0 or s[x][y] == "#":
        #         continue
        #     cnt += 1
        #     if dp[x][y] > cost:
        #         dp[x][y] = cost
        #         heappush(q, (cost, x, y))
        
        for xi in dx:
            x = px + xi
            if x >= h or x < 0:
                continue
            sx = s[x]
            dpx = dp[x]
            for yj in dy:
                y = py + yj
                if y >= w or y < 0 or sx[y] == "#":
                    continue
                cnt += 1
                if dpx[y] > cost:
                    dpx[y] = cost
                    heappush(q, (cost, x, y))
                
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                sx = s[x]
                dpx = dp[x]
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or sx[y] == "#":
                        continue
                    if dpx[y] > cost:
                        dpx[y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
class G:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.range = 0

    
H, W = [int(i) for i in input().split()]
Ch, Cw = [int(i)-1 for i in input().split()]
Dh, Dw = [int(i)-1 for i in input().split()]
S = [['.' for j in range(W)] for i in range(H) ]
for i in range(H):
    tmp = list(input())
    for j in range(W):
        S[i][j] = G(tmp[j])

def neighbors(y, x):
    s = []
    if x != 0:
        if S[y][x-1].reached == False and S[y][x-1].c == '.':
            s.append((y, x-1))
    if x != W-1:
        if S[y][x+1].reached == False and S[y][x-1].c == '.':
            s.append((y, x+1))
    if y != 0:
        if S[y-1][x].reached == False  and S[y][x-1].c == '.':
            s.append((y-1, x))
    if y != H-1:
        if S[y+1][x].reached == False  and S[y][x-1].c == '.':
            s.append((y+1, x))
    return s

def jump(x, y, d):
    for i in range(max(x-2, 0), min(x+3, W)):
        for j in range(max(y-2, 0), min(y+3, H)):
            if S[j][i].reached == False and S[j][i].c == '.':
                d.append((j, i))

def DFS(S, d):
    while True:
        if len(d) == 0:
            break
        q = d.popleft()
        S[q[0]][q[1]].reached = True
        for each in neighbors(q[0], q[1]):
            S[each[0]][each[1]].reached = True
            if S[each[0]][each[1]].c == '.':
                d.append(each)

counter = 0
d = deque([])
S[Ch][Cw].reached = True
d.append((Ch, Cw))
flag = False
while True:
    DFS(S, d)
    if S[Dh][Dw].reached:
        break
    counter += 1
    for i in range(H):
        for j in range(W):
            if S[i][j].reached and S[i][j].c == '.':
                jump(j, i, d)

    if len(d) == 0:
        flag = True
        break

if flag:
    print(-1)
else:
    print(counter)

Submission status: Wrong Answer

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if color[X][Y]=="white":
                    D[X][Y]=0
                    queue.append([X,Y])
                    color[X][Y]="gray"
        color[x][y]="black"

    return D


def Check():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if D[i][j]==inf:
                color[i][j]="black"

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if D[i][j]==0 and color[i][j]=="white":
                queue.append([i,j])
                while len(queue)>0:
                    x,y=queue.popleft()
                    for a,b in [[1,0],[0,1],[0,-1],[-1,0]]:
                        X,Y=x+a,y+b
                        if 0<=X<h and 0<=Y<w:
                            if color[X][Y]=="white":
                                color[X][Y]="gray"
                                queue.append([X,Y])
                    color[x][y]="black"
                point +=1

    return point


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
ans=True if D[G[0]-1][G[1]-1]!=inf else False
if ans==False:print(-1);exit()
print(Check()-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "#":
				continue
			for i in range(-2, 2+1):
				for j in range(-2, 2+1):
					if (i, j) == (0, 0):
						continue
					if getMaze(x + i, y + j) == ".":
						if (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
							graph[y][x].append((x + i, y + j, 0))
						else:
							graph[y][x].append((x + i, y + j, 1))


	log.print(graph)
	stack = deque([(cw-1, ch-1)])
	dist = [[-1]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		if dist[y][x] == -1:
			dist[y][x] = 0
		d = dist[y][x]
		nexts = graph[y][x]
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] != -1:
				dist[ny][nx] = min(dist[ny][nx], d + cost)
				continue
			dist[ny][nx] = d + cost
			stack.append((nx, ny))
	log.print(dist)
	print(dist[dh-1][dw-1])
	
	


main()

Submission status: Wrong Answer

Solution code:
def abc176d_wizard_in_maze():
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start[0] -= 1
    start[1] -= 1
    goal[0] -= 1
    goal[1] -= 1
    maze = []
    for i in range(h):
        maze.append(input())
    dp = [[float('inf')] * w for _ in range(h)]

    dp[start[0]][start[1]] = 0
    q = [[0, start[0], start[1]]]

    while len(q) != 0:
        v = q.pop()
        x, y = v[1], v[2]
        if v[0] == dp[goal[0]][goal[1]]:
            print(dp[goal[0]][goal[1]])
            return

        for dx, dy in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
            if 0 <= x + dx < h and 0 <= y + dy < w and maze[x + dx][y + dy] != '#' and dp[x][y] < dp[x + dx][y + dy]:
                dp[x + dx][y + dy] = dp[x][y]
                q.append([dp[x + dx][y + dy], x + dx, y + dy])

        for dx in [-2, 1, 0, 1, 2]:
            if not 0 <= x + dx < h:
                continue
            for dy in [-2, 1, 0, 1, 2]:
                if 0 <= y + dy < w and maze[x + dx][y + dy] != '#' and dp[x][y] + 1 < dp[x + dx][y + dy]:
                    dp[x + dx][y + dy] = dp[x][y] + 1
                    q.append([dp[x + dx][y + dy], x + dx, y + dy])
        q.sort(key=lambda x: x[0], reverse=True)
    if dp[goal[0]][goal[1]] == float('inf'):
        print('-1')
    else:
        print(dp[goal[0]][goal[1]])


abc176d_wizard_in_maze()