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:
H, W = list(map(int, input().split()))
Ch, Cw = list(map(lambda x:int(x)+1, input().split()))
Dh, Dw = list(map(lambda x:int(x)+1, input().split()))
S = []

S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))
for i in range(H):
    S.append(list('#'*2+input()+'#'*2))
S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))



from collections import deque

q1 = deque()
q2 = deque()
inf = 10**6


#cost
T = []
for w in S:
    T_W = [-1 if s=='#' else inf for s in w]
    T.append(T_W)

# print(T)

move2 = [(i-2,j-2) for j in range(5) for i in range(5)]
d = 0
h, w = Ch, Cw
T[Ch][Cw] = d
q1.append((h,w))
q2.append((h,w))

while len(q2)>0 or len(q1)>0:
    while len(q1)>0:
        v = q1.popleft()
        if v == (Dh,Dw):
            print(d)

            break
        for t in [(0,1),(1,0),(-1,0),(0,-1)]:
            if T[v[0]+t[0]][v[1]+t[1]] > d:
                T[v[0]+t[0]][v[1]+t[1]] = d
                q1.append((v[0]+t[0], v[1]+t[1]))
                q2.append((v[0]+t[0], v[1]+t[1]))
    d += 1
    while len(q2)>0:
        v = q2.popleft()
        if v == (Dh,Dw):
            print(d)

            break
        for t in move2:
            if T[v[0]+t[0]][v[1]+t[1]] > d:
                T[v[0]+t[0]][v[1]+t[1]] = d
                q1.append((v[0]+t[0], v[1]+t[1]))
    q2.extend(q1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持
    reached = set()

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if (h, w) in reached:
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        reached.add((h, w))

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if (new_h, new_w) not in reached:
                        qu.append((new_h, new_w, warps + 1))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if (new_h, new_w) not in reached:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
elif icase==1:
    h,w=4,4
    ch,cw=1,1
    dh,dw=4,4
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['..#.', '..#.', '.#..', '.#..']   
elif icase==2:
    h,w=4,4
    ch,cw=1,4
    dh,dw=4,1
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['.##.', '####', '####', '.##.']  
elif icase==3:
    h,w=4,5
    ch,cw=1,2
    dh,dw=2,5
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['#.###', '####.', '#..##', '#..##'] 
elif icase==4:
    h,w=4,4
    ch,cw=2,2
    dh,dw=3,3
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['....', '....', '....', '....']
        
icnt=-1
pair=[-1]*(h*w)
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            idx=i*w+j
#            pair.append(idx)
            pair[idx]=idx
#print("A",pair)
               
def root(x):
    if x==-1:
        return -1
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x
        
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                pair[idx1]=idx
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                pair[idx1]=idx

for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                unite(idx,idx1)
            if i>0 and s[i-1][j]==".":
                idx1=(i-1)*w+j
                unite(idx,idx1)
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                unite(idx,idx1)
            if j>0 and s[i][j-1]==".":
                idx1=i*w+j-1
                unite(idx,idx1)

#print("B:",pair)
l=[root(ii) for ii in range(len(pair))]
#print("l:",l)
ll=list(set(l))    
ll.sort()
ll=ll[1:]
if len(ll)<1:
    print(0)
    sys.exit()

gg=[[] for i in range(max(ll)+1)]
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if root(idx)!=-1:
            gg[root(idx)].append((i,j))        

ggg=[[] for i in range(max(ll)+1)]
for gi in gg:
    for gi2 in gg:
        if gi==gi2:
            continue
        for i,j in gi:
            idx=i*w+j
            for i2,j2 in gi2:
                idx2=i2*w+j2
                if root(idx2) in ggg[root(idx)]:
                    continue
                if abs(i-i2)<=2 and abs(j-j2)<=2:
                    ggg[root(idx)].append(root(idx2))
                    ggg[root(idx2)].append(root(idx))
sys.exit()
#print("ll:",ll)
lenpair=len(ll)    
lenpair=max(ll)+1

qst=root(ch*w+cw)
qed=root(dh*w+dw)
q=deque([qst])

stack=[qst]
parent=[-1]*lenpair
parent[qst]=0
dist=[-1]*lenpair
dist[qst]=0
while q:
    state = q.popleft()
#    print("--- q:",q,"state:",state,"g:",g[state],"p:",parent)
    for v in ggg[state]:
#        print("  state:",state,"v:",v,"q:",q)
#        if parent[state] == v:
        if parent[v] !=-1:
            continue
        else:
#            print("parent:",parent,"xx:",xx,"stack",stack)
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
            if v==qed:
                print(dist[qed])   
                sys.exit()
#            print(" state:",state,"v:",v,"parent:",parent,"stack",stack,"dist[v]",dist[v])
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
elif icase==1:
    h,w=4,4
    ch,cw=1,1
    dh,dw=4,4
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['..#.', '..#.', '.#..', '.#..']   
elif icase==2:
    h,w=4,4
    ch,cw=1,4
    dh,dw=4,1
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['.##.', '####', '####', '.##.']  
elif icase==3:
    h,w=4,5
    ch,cw=1,2
    dh,dw=2,5
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['#.###', '####.', '#..##', '#..##'] 
elif icase==4:
    h,w=4,4
    ch,cw=2,2
    dh,dw=3,3
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['....', '....', '....', '....']
        
icnt=-1
pair=[-1]*(h*w)
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            idx=i*w+j
#            pair.append(idx)
            pair[idx]=idx
#print("A",pair)
               
def root(x):
    if x==-1:
        return -1
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x
        
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                pair[idx1]=idx
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                pair[idx1]=idx

for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                unite(idx,idx1)
            if i>0 and s[i-1][j]==".":
                idx1=(i-1)*w+j
                unite(idx,idx1)
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                unite(idx,idx1)
            if j>0 and s[i][j-1]==".":
                idx1=i*w+j-1
                unite(idx,idx1)

#print("B:",pair)
l=[root(ii) for ii in range(len(pair))]
#print("l:",l)
ll=list(set(l))    
ll.sort()
ll=ll[1:]
if len(ll)<1:
    print(0)
    sys.exit()

gg=[[] for i in range(max(ll)+1)]
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if root(idx)!=-1:
            gg[root(idx)].append((i,j))        
sys.exit()
ggg=[[] for i in range(max(ll)+1)]
for gi in gg:
    for gi2 in gg:
        if gi==gi2:
            continue
        for i,j in gi:
            idx=i*w+j
            for i2,j2 in gi2:
                idx2=i2*w+j2
                if root(idx2) in ggg[root(idx)]:
                    continue
                if abs(i-i2)<=2 and abs(j-j2)<=2:
                    ggg[root(idx)].append(root(idx2))
                    ggg[root(idx2)].append(root(idx))

#print("ll:",ll)
lenpair=len(ll)    
lenpair=max(ll)+1

qst=root(ch*w+cw)
qed=root(dh*w+dw)
q=deque([qst])

stack=[qst]
parent=[-1]*lenpair
parent[qst]=0
dist=[-1]*lenpair
dist[qst]=0
while q:
    state = q.popleft()
#    print("--- q:",q,"state:",state,"g:",g[state],"p:",parent)
    for v in ggg[state]:
#        print("  state:",state,"v:",v,"q:",q)
#        if parent[state] == v:
        if parent[v] !=-1:
            continue
        else:
#            print("parent:",parent,"xx:",xx,"stack",stack)
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
            if v==qed:
                print(dist[qed])   
                sys.exit()
#            print(" state:",state,"v:",v,"parent:",parent,"stack",stack,"dist[v]",dist[v])
print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(1000000)

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    vis = [[False] * w for _ in range(h)]

    def fill(nx, c):
        if len(nx) == 0:
            return
        q = deque(nx)
        wall = []
        while q:
            i, j = q.pop()
            vis[i][j] = True
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= i + di < h and 0 <= j + dj < w:
                    if (i + di, j + dj) == goal:
                        print(c)
                        exit()
                    if vis[i + di][j + dj]:
                        continue
                    if maze[i + di][j + dj] == '#':
                        wall.append((i + di, j + dj))
                    else:
                        q.append((i + di, j + dj))

        jump(wall, c + 1)

    def jump(wall, c):
        nx = []
        q = deque(wall)
        while q:
            i, j = q.pop()
            vis[i][j] = True
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    if 0 <= i + di < h and 0 <= j + dj < w:
                        if (i + di, j + dj) == goal:
                            print(c)
                            exit()
                        if vis[i + di][j + dj]:
                            continue
                        if maze[i + di][j + dj] == '.':
                            nx.append((i + di, j + dj))

        fill(nx, c)

    fill([start], 0)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq

(h, w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]
(c_h, c_w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]
(d_h, d_w) = [int(x) for x in sys.stdin.readline().strip().split(" ")]

maze = []
for line in sys.stdin:
    maze.append(list(line.strip())) 

def isReachable(i, j):
    if i < 1 or i > h or j < 1 or j > w:
        return False

    c = maze[i-1][j - 1]
    if c == '#':
        return False
    else:
        return True

def distance(fp, tp):
    if not isReachable(tp[1], tp[2]):
        return None

    h_diff = math.fabs(tp[1] - fp[1])
    w_diff = math.fabs(tp[2] - fp[2])

    if h_diff + w_diff < 2:
        return 0

    if h_diff < 3 or w_diff < 3:
        return 1

def adjacents(current):
    adjs = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            dst = (None, current[1] + i, current[2] + j)
            dist = distance(current, dst)
            if dist is not None:
                dst = (dist, dst[1], dst[2])
                adjs.append(dst)

    return adjs

def dijkstra(results, start):
    """Calcualte the distance from start points to all the node
    """
    cur_dist = 0
    results[start[1] - 1][start[2] -1] = cur_dist
    heap = [ (p[0] + cur_dist, p[1], p[2]) for p in  adjacents(start) ]
    heapq.heapify(heap)

    while len(heap) > 0:
        visited = heapq.heappop(heap)
        if results[visited[1] - 1][visited[2] -1] is not None:
            continue

        results[visited[1] - 1][visited[2] -1] = visited[0]
        cur_dist = visited[0]

        adjs = list(filter(lambda x: results[x[1] - 1][x[2] - 1] is None, adjacents(visited)))

        for a in [(p[0] + cur_dist, p[1], p[2]) for p in adjs]:
            heapq.heappush(heap, a)

    for i in range(0, len(results)):
        for j in range(0, len(results[0])):
            print(results[i][j], end=",")
        print()

results = [[None] * w for i in range(0, h)]
start = (0, c_h, c_w)

dijkstra(results, start)

if results[d_h - 1][d_w -1] is None:
    print(-1)
else:
    print(results[d_h - 1][d_w -1])

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
Ch, Cw = list(map(lambda x:int(x)+1, input().split()))
Dh, Dw = list(map(lambda x:int(x)+1, input().split()))
S = []

S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))
for i in range(H):
    S.append(list('#'*2+input()+'#'*2))
S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))



from collections import deque

q1 = deque()
q2 = deque()
inf = 10**6


#cost
T = []
for w in S:
    T_W = [-1 if s=='#' else inf for s in w]
    T.append(T_W)

# print(T)

move2 = [(i-2,j-2) for j in range(5) for i in range(5)]
d = 0
h, w = Ch, Cw
T[Ch][Cw] = d
q1.append((h,w))
q2.append((h,w))

while len(q2)>0 or len(q1)>0:
    while len(q1)>0:
        v = q1.popleft()
        if v == (Dh,Dw):
            print(d)

            break
        for t in [(0,1),(1,0),(-1,0),(0,-1)]:
            if T[v[0]+t[0]][v[1]+t[1]] > d:
                T[v[0]+t[0]][v[1]+t[1]] = d
                q1.append((v[0]+t[0], v[1]+t[1]))
                q2.append((v[0]+t[0], v[1]+t[1]))
    d += 1
    while len(q2)>0:
        v = q2.popleft()
        if v == (Dh,Dw):
            print(d)

            break
        for t in move2:
            if T[v[0]+t[0]][v[1]+t[1]] > d:
                T[v[0]+t[0]][v[1]+t[1]] = d
                q1.append((v[0]+t[0], v[1]+t[1]))

print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(1000000)

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    cost = [[float('Inf')] * w for _ in range(h)]
    cost[start[0]][start[1]] = 0
    vis = [[False] * w for _ in range(h)]

    def fill(nx, c):
        if len(nx) == 0:
            return
        q = deque(nx)
        wall = []
        while q:
            i, j = q.pop()
            cost[i][j] = c
            vis[i][j] = True
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= i + di < h and 0 <= j + dj < w:
                    if (i + di, j + dj) == goal:
                        print(c)
                        exit()
                    if vis[i + di][j + dj]:
                        continue
                    if maze[i + di][j + dj] == '#':
                        wall.append((i + di, j + dj))
                    else:
                        q.append((i + di, j + dj))

        jump(wall, c + 1)

    def jump(wall, c):
        nx = []
        q = deque(wall)
        while q:
            i, j = q.pop()
            vis[i][j] = True
            cost[i][j] = c
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    if 0 <= i + di < h and 0 <= j + dj < w:
                        if (i + di, j + dj) == goal:
                            print(c)
                            exit()
                        if vis[i + di][j + dj]:
                            continue
                        if maze[i + di][j + dj] == '.':
                            cost[i + di][j + dj] = c
                            nx.append((i + di, j + dj))

        fill(nx, c)

    fill([start], 0)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 参考: White_Pie_46
# https://atcoder.jp/contests/abc176/submissions/16168825
from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  # 座標とワープ回数を保持
    reached = set()

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if (h, w) in reached:
            # 同じマスを複数回キューに追加しているかもしれない。
            # 短距離で調査済みなら再調査は不要。
            continue
        reached.add((h, w))

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if (h, w) not in reached:
                    if grid[new_h][new_w] == '.':
                        qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if (h, w) not in reached:
                    if grid[new_h][new_w] == '.':
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

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 = [list(input()) for _ in range(H)]

num = 0
if S[0][0] == '#':
    S[0][0] = -1
else:
    num += 1
    S[0][0] = num

for i in range(1, H):
    if S[i][0] == '#':
        S[i][0] = -1
    elif S[i-1][0] > 0:
        S[i][0] = S[i-1][0]
    else:
        num += 1
        S[i][0] = num

for j in range(1, W):
    if S[0][j] == '#':
        S[0][j] = -1
    elif S[0][j-1] > 0:
        S[0][j] = S[0][j-1]
    else:
        num += 1
        S[0][j] = num

for i in range(1, H):
    for j in range(1, W):
        if S[i][j] == '#':
            S[i][j] = -1
        elif S[i-1][j] < 0 and S[i][j-1] < 0:
            num += 1
            S[i][j] = num
        elif S[i-1][j] < 0:
            S[i][j] = S[i][j-1]
        elif S[i][j-1] < 0:
            S[i][j] = S[i-1][j]
        else:
            S[i][j-1] = min(S[i-1][j], S[i][j-1])
            S[i-1][j] = min(S[i-1][j], S[i][j-1])
            S[i][j] = min(S[i-1][j], S[i][j-1])

G = [{} for _ in range(num)]

for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue

        start_i = max(0, i-2)
        start_j = max(0, j-2)
        end_i = min(H, i+3)
        end_j = min(W, j+3)
        for x in range(start_i, end_i):
            for y in range(start_j, end_j):
                if S[x][y] > 0 and S[x][y] != S[i][j]:
                    G[S[x][y]-1][S[i][j]-1] = 1
                    G[S[i][j]-1][S[x][y]-1] = 1

from heapq import heapify, heappop, heappush
def dijkstra(s):
    dist = [float('inf')] * num
    dist[s] = 0

    heap = [(s, 0)]
    heapify(heap)
    while heap:
        v, c = heappop(heap)
        if c > dist[v]: continue
        for u, d in G[v].items():
            tmp = d + dist[v]
            if tmp < dist[u]:
                dist[u] = tmp
                heappush(heap, (u, tmp))

    return dist

start = S[Ch-1][Cw-1]-1
end = S[Dh-1][Dw-1]-1
dist = dijkstra(start)

ans = -1 if dist[end] == float('inf') else dist[end]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [[] for i in range(H)]
for i in range(H):
  st = input()
  for j in range(W):
    maze[i].append(st[j])
walk_queue = deque([[Ch-1, Cw-1]])
magic_queue = deque([[Ch-1, Cw-1]])
all_queue = deque([[Ch-1, Cw-1]])

walk_move = [[-1, 0], [0, -1], [1, 0], [0, 1]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

ans = 0
while True:
  while len(walk_queue) != 0:
    new_walk_queue = deque()
    for x1,y1 in walk_queue:
      for i,j in walk_move:
        if 0 <= x1+i <= H-1 and  0 <= y1+j <= W-1 and maze[x1+i][y1+j] == ".":
          if not [x1+i, y1+j] in all_queue:
            new_walk_queue.append([x1+i, y1+j])
            all_queue.append([x1+i, y1+j])
            magic_queue.append([x1+i, y1+j])
    walk_queue = copy.copy(new_walk_queue)

  walk_queue.clear()
  for x2,y2 in magic_queue:
    for k,l in magic_move:
      if 0 <= x2+k <= H-1 and  0 <= y2+l <= W-1 and maze[x2+k][y2+l] == ".":
        if not [x2+k, y2+l] in all_queue:
          walk_queue.append([x2+k, x2+l])
          all_queue.append([x2+k, x2+l])
          
  if not len(walk_queue):
    if [Dh-1, Dw-1] in all_queue:
      break
    else:
      ans = "-1"
      break
  else:
    ans += 1

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(1000000)

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    cost = [[float('Inf')] * w for _ in range(h)]
    cost[start[0]][start[1]] = 0
    vis = [[False] * w for _ in range(h)]

    def fill(nx, c):
        if len(nx) == 0:
            return
        q = deque(nx)
        wall = []
        while q:
            i, j = q.pop()
            cost[i][j] = c
            vis[i][j] = True
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= i + di < h and 0 <= j + dj < w:
                    if (i + di, j + dj) == goal:
                        print(c)
                        exit()
                    if vis[i + di][j + dj]:
                        continue
                    if maze[i + di][j + dj] == '#':
                        wall.append((i + di, j + dj))
                    else:
                        q.append((i + di, j + dj))

        jump(wall, c + 1)

    def jump(wall, c):
        nx = []
        q = deque(wall)
        while q:
            i, j = q.pop()
            cost[i][j] = c
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    if 0 <= i + di < h and 0 <= j + dj < w:
                        if (i + di, j + dj) == goal:
                            print(c)
                            exit()
                        if vis[i + di][j + dj]:
                            continue
                        if maze[i + di][j + dj] == '.':
                            cost[i + di][j + dj] = c
                            nx.append((i + di, j + dj))

        fill(nx, c)

    fill([start], 0)
    print(-1)


if __name__ == '__main__':
    main()