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, 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:
## coding: UTF-8

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
'''
S = list(map(int,input().split()))
G = list(map(int,input().split()))
start = (S[0]-1) * W + (S[1]-1)
goal = (G[0]-1) * W + (G[1]-1)



c = []
for i in range(H):
    c.append(input())

fresh = [True] * (H*W)
#print(start,goal)


queue = [start]
done_at_this_step = [start]
fresh[start] = False
n = []
for i in range(H):
    for j in range(W):
        if(c[i][j] == '#'):
            fresh[i*W+j] = False
            #queue.append(i*W+j)
#print(fresh)

'''
maze = []
for i in range(-2, 3, 1):
    for j in range(-2, 3, 1):
        maze.append(i*W+j)
    #print(i)
print('maze', maze)
'''

cost = 0
#step = 0
while True:
    status = True
    while status:
        if(len(queue)>0):
            #処理を行う
            pivot = queue.pop()
            #print('pivot:{}, queue:{}, n:{}'.format(pivot, queue, n))        
            #右へ移動
            if(pivot%W != W-1 and fresh[pivot+1]):
                queue.append(pivot+1)
                done_at_this_step.append(pivot+1)
                fresh[pivot+1] = False
            #左へ移動
            if(pivot%W != 0 and fresh[pivot-1]):
                queue.append(pivot-1)
                done_at_this_step.append(pivot-1)
                fresh[pivot-1] = False
            #下へ移動
            if( int(pivot/W)<(H-1) and fresh[pivot+W]):
                queue.append(pivot+W)
                done_at_this_step.append(pivot+W)
                fresh[pivot+W] = False
            #上へ移動
            if( int(pivot/W)>0 and fresh[pivot-W] ):
                queue.append(pivot-W)
                done_at_this_step.append(pivot-W)
                fresh[pivot-W] = False
            #print('pivot:{}, queue:{}, n:{}'.format(pivot, queue, n))
        #elif(len(n)>0):
            #queue = n
            #n = []
            #歩数を増やそう
            #step += 1
            #print('step{}end,queue:{}, n:{}'.format(step, queue, n))
        else:
            status = False


    #print(queue)
    #print(done_at_this_step)
    #print(fresh)

    #fresh[goal]=Falseだったらやめる操作を書く
    if(fresh[goal] == False):
        clear = True
        break

    cost += 1

    for i in range(len(done_at_this_step)):
        pivot = done_at_this_step.pop()
        #上
        if(int(pivot/W)>0):
            one_up = True
            if(int(pivot/W)>1):
                two_up = True
            else:
                two_up = False
        else:
            one_up = False
            two_up = False
        #下
        if(int(pivot/W)<(H-1)):
            one_down = True
            if(int(pivot/W)<(H-2)):
                two_down = True
            else:
                two_down = False
        else:
            one_down = False
            two_down = False
        #左
        if(pivot%W != 0):
            one_left = True
            if(pivot%W != 1):
                two_left = True
            else:
                two_left = False
        else:
            one_left = False
            two_left = False
        #右
        if(pivot%W != W-1):
            one_right = True
            if(pivot%W != W-2):
                two_right = True
            else:
                two_right = False
        else:
            one_right = False
            two_right = False
        #print('pivot', pivot,one_up, two_up, one_down, two_down, one_left, two_left, one_right, two_right)
        if(two_up and two_left and fresh[pivot-(2*W)-2]):
            queue.append(pivot-(2*W)-2)
            fresh[pivot-(2*W)-2] = False
        if(two_up and one_left and fresh[pivot-(2*W)-1]):
            queue.append(pivot-(2*W)-1)
            fresh[pivot-(2*W)-1] = False
        if(two_up and fresh[pivot-(2*W)]):
            queue.append(pivot-(2*W))
            fresh[pivot-(2*W)] = False
        if(two_up and one_right and fresh[pivot-(2*W)+1]):
            queue.append(pivot-(2*W)+1)
            fresh[pivot-(2*W)+1] = False
        if(two_up and two_right and fresh[pivot-(2*W)+2]):
            queue.append(pivot-(2*W)+2)
            fresh[pivot-(2*W)+2] = False


        if(one_up and two_left and fresh[pivot-(1*W)-2]):
            queue.append(pivot-(1*W)-2)
            fresh[pivot-(1*W)-2] = False
        if(one_up and one_left and fresh[pivot-(1*W)-1]):
            queue.append(pivot-(1*W)-1)
            fresh[pivot-(1*W)-1] = False
        if(one_up and fresh[pivot-(1*W)]):
            queue.append(pivot-(1*W))
            fresh[pivot-(1*W)] = False
        if(one_up and one_right and fresh[pivot-(1*W)+1]):
            queue.append(pivot-(1*W)+1)
            fresh[pivot-(1*W)+1] = False
        if(one_up and two_right and fresh[pivot-(1*W)+2]):
            queue.append(pivot-(1*W)+2)
            fresh[pivot-(1*W)+2] = False

        if(two_left and fresh[pivot-2]):
            queue.append(pivot-2)
            fresh[pivot-2] = False
        if(one_left and fresh[pivot-1]):
            queue.append(pivot-1)
            fresh[pivot-1] = False
        if(fresh[pivot]):
            queue.append(pivot)
            fresh[pivot] = False
        if(one_right and fresh[pivot+1]):
            queue.append(pivot+1)
            fresh[pivot+1] = False
        if(two_right and fresh[pivot+2]):
            queue.append(pivot+2)
            fresh[pivot+2] = False

        if(one_down and two_left and fresh[pivot+(1*W)-2]):
            queue.append(pivot+(1*W)-2)
            fresh[pivot+(1*W)-2] = False
        if(one_down and one_left and fresh[pivot+(1*W)-1]):
            queue.append(pivot+(1*W)-1)
            fresh[pivot+(1*W)-1] = False
        if(one_down and fresh[pivot+(1*W)]):
            queue.append(pivot+(1*W))
            fresh[pivot+(1*W)] = False
        if(one_down and one_right and fresh[pivot+(1*W)+1]):
            queue.append(pivot+(1*W)+1)
            fresh[pivot+(1*W)+1] = False
        if(one_down and two_right and fresh[pivot+(1*W)+2]):
            queue.append(pivot+(1*W)+2)
            fresh[pivot+(1*W)+2] = False

        if(two_down and two_left and fresh[pivot+(2*W)-2]):
            queue.append(pivot+(2*W)-2)
            fresh[pivot+(2*W)-2] = False
        if(two_down and one_left and fresh[pivot+(2*W)-1]):
            queue.append(pivot+(2*W)-1)
            fresh[pivot+(2*W)-1] = False
        if(two_down and fresh[pivot+(2*W)]):
            queue.append(pivot+(2*W))
            fresh[pivot+(2*W)] = False
        if(two_down and one_right and fresh[pivot+(2*W)+1]):
            queue.append(pivot+(2*W)+1)
            fresh[pivot+(2*W)+1] = False
        if(two_down and two_right and fresh[pivot+(2*W)+2]):
            queue.append(pivot+(2*W)+2)
            fresh[pivot+(2*W)+2] = False
        
        #print(queue)

    #fresh[goal]=Falseだったらやめる操作を書く
    if(fresh[goal] == False):
        clear = True
        break
    #len(queue) == 0  でもやめる
    if(len(queue) == 0):
        clear = False
        break

if(clear):
    print(cost)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq,collections
h,w = map(int, raw_input().split())
s,t = tuple(map(lambda x:int(x)-1 , raw_input().split())), tuple(map(lambda x:int(x)-1 , raw_input().split()))
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = [(u[0] + i,u[1] + j) for i in [-2,-1,0,+1,+2] for j in [-2,-1,0,+1,+2]]
	return [v for v in ret if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.' and v != u and abs(v[0] - u[0]) + abs(v[1] - u[1])>= 3]
def f(s,t,mat):
	heap,r = [(0,s)], {} 
	while(heap):
		d,u = heapq.heappop(heap)
		r[u] = min(r[u] if u in r else +float('inf'), d)
		if u == t: return d

		for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d: 
					r[v] = d
					heapq.heappush(heap,(d,v))
					
		for v in neighbors(u,mat):
			if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
				if (v not in r) or r[v] > d + 1: 
					r[v] = d + 1
					heapq.heappush(heap,(d+1,v))
	return -1

print f(s,t,mat)

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(maze, seen, Ch, Cw, Dh, Dw):
    count = 0
    start = [Ch-1, Cw-1]
    stack = deque([start])
    seen[start[0]][start[1]] = 1
    while stack:
        h, w = stack.pop()
        #print(h, w)
        if h == Dh-1 and w == Dw-1:
            return count
        c = 0
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                c += 1
                continue
            elif maze[new_h][new_w] != '#' and seen[new_h][new_w] == 0:
                seen[new_h][new_w] = 1
                stack.append([new_h, new_w])
            elif maze[new_h][new_w] == '#':
                c +=1 
        if c == 4:
            count += 1
            #do warp
            for j, k in ([1, 1], [-1, 1], [-1, 1], [-1, -1], [2, 0], [-2, 0], [0, 2], [0, -2], [2, 2], [2, -2], [-2, 2], [-2, -2], [2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]):
                
                new_h, new_w = h+j, w+k
                
                if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                    continue
                elif maze[new_h][new_w] != '#' and seen[new_h][new_w] == 0:
                    seen[new_h][new_w] = 1
                    stack.append([new_h, new_w])
            
    return -1


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

Ch, Cw = map(int,input().split())

Dh, Dw = map(int,input().split())

maze = [input() for _ in range(H)]
seen = [[0] * W for _ in range(H)]

g = dfs(maze, seen, Ch, Cw, Dh, Dw)


print(g)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from pprint import pprint
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 = [False for i in range(N)]
    ans = -1
    q = deque()
    visited[start_id-1] = True
    q.append((start_id-1, 0))
    while q:
        u, d = q.pop()
        if u == goal_id-1:
            ans = d
            break
        for v in G[u]:
            if not visited[v]:
                visited[v] = True
                q.append((v, d+1))
    return ans


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

Submission status: Wrong Answer

Solution code:
# 2020/08/22
# AtCoder Beginner Contest 176 - D

# Input
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
sl = list()
sl.append(['#'] * (w+2))
for i in range(h):
    s = list('#' + input())
    s.append('#')
    sl.append(s)
sl.append(['#'] * (w+2))

wcnt = 0
findflg = False
posq = list()
tl = [[0] * (w+2) for i in range(h+2)]
tl[ch][cw] = 1
posq.append([ch, cw])
passq = list()

loopmax = (h // 2) * (w // 2)

for i in range(loopmax):
    while(len(posq) > 0):
        th, tw = posq.pop()
        if th == dh and tw == dw:
            findflg = True
            break
            
        passq.append([th, tw])
    
        if sl[th-1][tw] == '.' and tl[th-1][tw] == 0:
            posq.append([th-1, tw])
            tl[th-1][tw] = 1
        elif sl[th][tw-1] == '.' and tl[th][tw-1] == 0:
            posq.append([th, tw-1])
            tl[th][tw-1] = 1
        elif sl[th+1][tw] == '.' and tl[th+1][tw] == 0:
            posq.append([th+1, tw])
            tl[th+1][tw] = 1
        elif sl[th][tw+1] == '.' and tl[th][tw+1] == 0:
            posq.append([th, tw+1])
            tl[th][tw+1] = 1

    if findflg == True:
        break

    while(len(passq) > 0):
        ph, pw = passq.pop()
        
        for i in range(ph-2, ph+3):
            for j in range(pw-2, pw+3):
                if i > 0 and i <= h and j > 0 and j <= w:
                    if sl[i][j] == '.' and tl[i][j] == 0:
                        posq.append([i, j])
                        tl[i][j] = 1
    wcnt = wcnt + 1
    if len(posq) == 0:
        break

# Output
if findflg == True:
    ans = wcnt
else:
    ans = -1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij4=[(0,1),(1,0),(-1,0),(0,-1)]
dijx=[(1,1),(-1,1),(1,-1),(-1,-1)]

def solve():
    q = []
    q.append((si, sj, 0))
    aa[si][sj] = 0
    wall=[]

    while q:
        while q:
            i, j, d = q.pop()
            for di, dj in dij4:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if aa[ni][nj]!=-1:continue
                if ss[ni][nj]:
                    aa[ni][nj]=d+1
                    wall.append((ni,nj,d+1))
                else:
                    aa[ni][nj]=d
                    q.append((ni,nj,d))
            for di, dj in dijx:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if aa[ni][nj] != -1: continue
                if ss[ni][nj]:
                    aa[ni][nj] = d + 1
                    wall.append((ni, nj, d + 1))

        while wall:
            i, j, d = wall.pop()
            for di, dj in dij4+dijx:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if aa[ni][nj]!=-1:continue
                if ss[ni][nj]:continue
                aa[ni][nj]=d
                q.append((ni,nj,d))

    #p2D(aa)
    print(aa[gi][gj])


h,w=MI()
si,sj=MI1()
gi,gj=MI1()
ss=[[1 if c=="#" else 0 for c in SI()] for _ in range(h)]
aa=[[-1]*w for _ in range(h)]
#p2D(ss)
solve()

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
import sys
import os
from operator import mul
from collections import deque


sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

H,W = LI()
C = LI()
D = LI()
maze = [list(_S()) for i in range(H)]

def bfs():
    ans = -1
    # すべての点を INF で初期化
    d = [[float("inf")] * W for i in range(H)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    sx = C[0]-1
    sy = C[1]-1
    gx = D[0]-1
    gy = D[1]-1

    # スタート地点をキューに入れ、ワープ数を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    que2 = deque([])
    que2.append((sx, sy))

    while que: 
        # キューが空になるまでループ
        while que:
            # キューの先頭を取り出す
            p = que.popleft()
            # 取り出してきた状態がゴールなら探索をやめる
            if p[0] == gx and p[1] == gy:
                ans = d[p[0]][p[1]]
                break
            # 移動4方向をループ
            for i in range(4):
                # 移動した後の点を (nx, ny) とする
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                # 移動が可能かの判定とすでに訪れたことがあるかの判定
                # d[nx][ny] != INF なら訪れたことがある
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    # 移動できるならキューに入れ、その点のワープ回数を p からのワープ回数 +1 で確定する
                    que.append((nx, ny))
                    que2.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]
        dx = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0, 1, 1,  1,  1, 2, 2, 2,  2, 2]
        dy = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, 2, 1, -1, -2, 2, 1, 0, -1, -2]
        while que2:
            # キューの先頭を取り出す
            p = que2.popleft()
            for i in range(len(dx)):
                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"):
                    # 移動できるならキューに入れ、その点のワープ回数を p からのワープ回数 +1 で確定する
                    que.append((nx, ny))
                    que2.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]+1    
            # print(que)
    return ans

print(bfs())

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 = [input() for i in range(H)]
INF = 100000
T = [[INF]*W for i in range(H)]
dh = [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, -1, -1, -1, -1, -1, -2, -2, -2, -2, -2]
dw = [-2, -1, 0, 1, 2, -2, -1, 0, 1, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1, 0, 1, 2]
wf = [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
que1 = deque([])
que2 = deque([])
que1.append((Ch-1, Cw-1))
T[Ch-1][Cw-1] = 0
wp = 0
ans = -1
while que1:
    p = que1.popleft()
    if p[0] == Dh -1 and p[1] == Dw - 1:
        ans = wp
        break
    for i in range(24):
        nh = p[0] + dh[i]
        nw = p[1] + dw[i]
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and T[nh][nw] > wp:
            if wf[i] == 0:
                que1.append((nh,nw))
                T[nh][nw] = wp 
            else:
                que2.append((nh,nw))
                T[nh][nw] = wp + 1
    if len(que1) == 0:
        if len(que2) != 0:
            wp += 1
            que1 = que2
            que2 = deque([])
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
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 = []
for i in range(h):
   s.append(input())
d = [[-1 for i in range(w)] for j in range(h)]
q = queue.Queue()

#通常移動ベクトル
dx = (-1,0,1,0)
dy = (0,-1,0,1)
#ワープベクトル
wx = (-2,-1, 0, 1, 2,-2,-1, 1, 2,-2,2,-2,-1,1,2,-2,-1,0,1,2)
wy = (-2,-2,-2,-2,-2,-1,-1,-1,-1, 0,0, 1, 1,1,1, 2, 2,2,2,2)
q.put((ch,cw))
d[ch][cw] = 0

while not q.empty():
  p = q.get()
  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 and nx < h and 0<= ny and ny < w and s[nx][ny]=="." and (d[nx][ny]==-1 or d[nx][ny]>d[p[0]][p[1]]):
      q.put((nx,ny))
      d[nx][ny]=d[p[0]][p[1]]
  for i in range(20): #ワープ移動
    nx = p[0] + wx[i]
    ny = p[1] + wy[i]
    if 0 <= nx and nx < h and 0<= ny and ny < w and s[nx][ny]=="." and (d[nx][ny]==-1 or d[nx][ny]>(d[p[0]][p[1]]+1)):
      q.put((nx,ny))
      d[nx][ny]=d[p[0]][p[1]]+1
print(d[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

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

cost = [[0] * W for _ in range(H)]


dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(ch-1, cw-1, 0)])
used = {(ch-1, cw-1)}
warp = [(ch-1, cw-1)]
ddd = []
for i in range(-2,3):
    for j in range(-2,3):
        if i == j == 0:
            continue
        ddd.append((i,j))    

idx = 0
while que:
    while que:
        s, t, cost = que.popleft()
        if s == dh-1 and t == dw-1: 
            print(cost)
            sys.exit()
            break
        for di, dj in dd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost))
            warp.append((xi,yj)) 
            
    while idx <= len(warp) - 1:
        s, t = warp[idx]
        for di, dj in ddd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost+1))
            warp.append((xi,yj))
        idx += 1
        break

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from heapq import heappop as hpp, heappush as hp
q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
e = 10**-9

for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(e)
data = []
rs = []
cs = []
for pu in range(n):
    ux,uy = divmod(pu,w)
    if ss[ux][uy]=="#":
        continue
    for xx,yy,vv in zip(dx,dy,vvs):
        x,y = ux+xx, uy+yy
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
        u = x*w + y
        data.append(vv)
        rs.append(pu)
        cs.append(u)
        data.append(vv)
        rs.append(u)
        cs.append(pu)
    
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n, n))
ans = scipy.sparse.csgraph.dijkstra(m, indices=start, directed=False) # startからの最短路木を求める
if ans[goal]>10**9:
    print(-1)
else:
    print(int(ans[goal]))
# if val is None:
#     print(-1)
# else:
#     print(val)

Submission status: Wrong Answer

Solution code:
from math import trunc
import sys
import copy
from collections import deque
import collections
import itertools
stdin = sys.stdin
import math

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


h, w = na()
sh, sw = na()
gh, gw = na()

map = []
for _ in range(h):
    s = ns()
    map.append([0 if i=="." else 1 for i in s])

visited = [[100000 for j in range(w)] for i in range(h)]

def warp(nh, nw, now_warp):
    next_p = []
    topleft = [nh-2, nw-2]
    for i in range(5):
        for j in range(5):
            neh = topleft[0]+i
            new = topleft[1]+j
            if check_position(neh, new, now_warp):
                if visited[neh][new] > (now_warp+1):
                    next_p.append([neh, new])
    return next_p


def check_position(hi, wi, now_warp):
    if hi<0 or hi>=h or wi<0 or wi>=w or map[hi][wi]==1:
        return False
    return True


positions = deque()
positions.append([sh-1, sw-1, 0])
while len(positions)>0:
    warp_positions = deque()
    while len(positions)>0:
        nh, nw, now_warp = positions.popleft()

        if now_warp >= visited[nh][nw]:
            continue

        visited[nh][nw] = now_warp
        move_cnt = 0
        if check_position(nh+1, nw, now_warp):
            positions.append([nh+1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw+1, now_warp):
            positions.append([nh, nw+1, now_warp])
            move_cnt += 1
        
        if check_position(nh-1, nw, now_warp):
            positions.append([nh-1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw-1, now_warp):
            positions.append([nh, nw-1, now_warp])
            move_cnt += 1

        if move_cnt<4:
            warp_positions.append([nh, nw, now_warp])
    
    while len(warp_positions)>0:
        nh, nw, now_warp = warp_positions.popleft()
        next_warps = warp(nh, nw, now_warp)
        for p in next_warps:
            positions.append([p[0], p[1], now_warp+1])

print(-1 if visited[gh-1][gw-1]==100000 else visited[gh-1][gw-1])