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
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque
H,W = map(int,input().split())

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

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

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

ans = H*W

chk = [[0 for i in range(W)] for j in range(H)]

def dfs(h,w,S,chk,tmp):
    chk[h][w]=tmp
    if (h+1)<H:
        if S[h+1][w]!="#":
            if chk[h+1][w]==0:
                chk[h+1][w]=tmp
                dfs(h+1,w,S,chk,tmp)
    if (h-1)>-1:
        if S[h-1][w]!="#":
            if chk[h-1][w]==0:
                chk[h-1][w]=tmp
                dfs(h-1,w,S,chk,tmp)
    if (w+1)<W:
        if S[h][w+1]!="#":
            if chk[h][w+1]==0:
                chk[h][w+1]=tmp
                dfs(h,w+1,S,chk,tmp)
    if (w-1)>-1:
        if S[h][w-1]!="#":
            if chk[h][w-1]==0:
                chk[h][w-1]=tmp
                dfs(h,w-1,S,chk,tmp)
    return
cnt = 1
for h in range(H):
    for w in range(W):
        if S[h][w]!="#":
            if chk[h][w]==0:
                dfs(h,w,S,chk,cnt)
                cnt += 1

if chk[Ch-1][Cw-1]==chk[Dh-1][Dw-1]:
    print(0)
    exit()
"""
for i in range(H):
    print(*chk[i])
"""
#2回目はBFS
l = [-2,-1,0,1,2]
#5×5の走査の関数
def bfs(h,w,chk,L,l):
    for ud in l:
        if (h+ud)>-1 and (h+ud)<H:
            pass
        else:
            continue
        for lr in l:
            if (w+lr)>-1 and (w+lr)<W:
                pass
            else:
                continue
            if chk[h+ud][w+lr]==0:
                continue
            if chk[h+ud][w+lr]!=chk[h][w]:
                L[chk[h][w]].append(chk[h+ud][w+lr])
    return

L = [[] for i in range(cnt)]
for h in range(H):
    for w in range(W):
        if chk[h][w]==0:
            continue
        bfs(h,w,chk,L,l)
#print(L)
X =[]
for i in range(cnt):
    X.append(set(L[i]))

start = chk[Ch-1][Cw-1]
goal = chk[Dh-1][Dw-1]

#ダイクストラ法でstartからgoalまでの最短経路を考える。
def dijkstra(s,X):
    que = deque()
    que.append((0,s))
    dist = [10**7]*cnt
    dist[s]= 0
    check = [0 for i in range(cnt)]
    while(que):
        p,v = que.pop()
        check[v]=1
        if dist[p]+1>=dist[v]:
            pass
        else:
            dist[v]=dist[p]+1
        for tmp in X[v]:
            if check[tmp]==1:
                continue
            que.append((v,tmp))
        #print(que)
    return dist

res = dijkstra(start,X)
if res[goal]==10**7:
    print(-1)
else:
    print(res[goal])

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/08/25

@author: harurun
'''
def main():
  from collections import deque
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  H,W=map(int,pin().split())
  sy,sx=map(int,pin().split())
  gy,gx=map(int,pin().split())
  S=[]
  cnt=0
  for _ in [0]*H:
    t=pin()[:-1]
    S.append(list(t))
    cnt+=t.count(".")
  q=deque([])
  q.append([sx-1,sy-1])
  d=[[10000000]*W for __ in [0]*H]
  m=[[0,1],[0,-1],[1,0],[-1,0]]
  chokudai=0
  e=[[-2,2],[-1,2],[0,2],[1,2],[2,2],[-2,1],[-1,1],[1,1],[2,1],[-2,0],[2,0],[-2,-1],[-1,-1],[1,-1],[2,-1],[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2]]
#   for v in e:
#     print(f"{v[0]}:{v[1]}")
#   return
  r=deque([])
  r.append([sx-1,sy-1])
  while True:
    while q:
      f=q.popleft()
      x=f[0]
      y=f[1]
      for i in m:
        nx=x+i[0]
        ny=y+i[1]
        if 0<=nx and nx<W and 0<=ny and ny<H :
          if S[ny][nx]!="#" and d[ny][nx]>chokudai:
            q.append([nx,ny])
            r.append([nx,ny])
            d[ny][nx]=chokudai
    p=deque([])
#     print(chokudai,r)
    while r:
      g=r.popleft()
      x2=g[0]
      y2=g[1]
      for j in e:
        mx=x2+j[0]
        my=y2+j[1]
        if 0<=mx and mx<W and 0<=my and my<H:
          if S[my][mx]!="#" and d[my][mx]>chokudai:
            p.append([mx,my])
            d[my][mx]=chokudai+1
    q=p
    r=deque([])
#     print(chokudai,p)
    chokudai+=1
    if not q:
      break
  if d[gy-1][gx-1]==10000000:
    print(-1)
    return
  print(d[gy-1][gx-1])
#   for rt in d:
#     print(rt)
  return
main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from functools import reduce
from queue import Queue
from collections import deque
H, W = list(map(int, input().split(" ")))
current_h, current_w = list(map(int, input().split(" ")))
current_h -= 1
current_w -= 1
goal_h, goal_w = list(map(int, input().split(" ")))
goal_h -= 1
goal_w -= 1

table = [list(input()) for _ in range(H)]

class ZeroOneBFS:

    def __init__(self, table):
        self.table = table
        self.cost_table = []
        for _ in range(H):
            self.cost_table.append([-1 for _ in range(W)])

    def delta(self, h, w):
        res = [(h+1, w),
               (h, w-1), (h, w+1),
               (h-1, w)]
        return res

    def warp(self, h, w):
        res = []
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    pass
                else:
                    res.append((h+dh, w+dw))
        return res

    def bfs(self, start_h, start_w):
        dq = deque()
        dq.appendleft((start_h, start_w, 0))
        while dq:
            now_h, now_w, now_c = dq.pop()
            if self.table[now_h][now_w] == "#" or self.cost_table[now_h][now_w] != -1:
                pass
            else:
                for h, w in self.delta(now_h, now_w):
                    if 0 <= h < H and 0 <= w < W and self.table[h][w] != "#":
                        dq.append((h, w, now_c))
                for h, w in self.warp(now_h, now_w):
                    if 0 <= h < H and 0 <= w < W and self.table[h][w] != "#":
                        dq.appendleft((h, w, now_c+1))
            self.cost_table[now_h][now_w] = now_c
        return self.cost_table[goal_h][goal_w]


bfs = ZeroOneBFS(table)
print(bfs.bfs(current_h, current_w))

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        cnt=visited[y][x]
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if (0<=my<tate and 0<=mx<yoko) and maze[my][mx]=="." and visited[my][mx]>cnt:
                queue.append([my,mx])
                visited[my][mx]=cnt # visitedは距離も兼ねてる
        for dy in range(y-2,y+3):
            for dx in range(x-2,x+3):
                my,mx=y+dy,x+dx
                if (0<=my<tate and 0<=mx<yoko) and maze[my][mx]==".":
                    if visited[my][mx]>cnt+1:
                        queue.append([my,mx])
                        visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
c=0
bfs()

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y)])
    near = product(range(-2, 3), repeat=2)

    while len(que) > 0:
        x, y = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for dx, dy in near:
            cnt = (abs(dx) + abs(dy) >= 2)
            i, j = x + dx, y + dy
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    else:
        return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))

Submission status: Wrong Answer

Solution code:
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    frag = [[sij == '#' for sij in sj] for sj in s]
    dist[y][x] = 0
    que = deque([(x, y)])

    while len(que) > 0:
        x, y = que.popleft()
        frag[y][x] = 1
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for i, j in product(range(-2, 3), repeat=2):
            cnt = (abs(i) + abs(j) >= 2)
            i, j = x + i, y + j
            if (0 <= i < w and 0 <= j < h and frag[j][i] == 0):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()


def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    # calc
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


show_flg=False
show_flg=True

ans=0

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

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='#'for i in s]+[1]
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h


nbw=[-2*w+1,-2*w+2,-w+1,-w+2,2,2*w+1,2*w+2,w+1,w+2,+2*w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-2,2*w-1,2*w-2,w-1,w-2]
nb=[1,-1,w,-w]
d=[-1]*n
g=[[]for i in range(n)]
for i in range(n):
    for di in nbw:
        nx=i+di
        if 0<=nx<n and m[nx]!=1!=m[i]:
            g[i]+=(nx,1),
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1!=m[i]:
            g[i]+=(nx,0),

d,_=dijkstra(g,sh*w+sw)
print(d[gh*w+gw])

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
# Verified by
# https://atcoder.jp/contests/arc033/submissions/me
# https://atcoder.jp/contests/abc174/tasks/abc174_f
#
# speed up TIPS: delete update of el. non-use of getitem, setitem.
#
# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get bound of index where x1+x2+...+xi<w

class Bit: # 1-indexed
    def __init__(self,n,init=None):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        self.el=[0]*(2**self.m+1)
        if init!=None:
            for i in range(len(init)):
                self.add(i,init[i])
                self.el[i]=init[i]

    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        if not 0<i<=self.size:return NotImplemented
        self.el[i]+=x
        while i<=self.size:
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        if not 0<=i<=self.size:return NotImplemented
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def __getitem__(self,key):
        return self.el[key]
        return self.sum(key+1)-self.sum(key)

    def __setitem__(self,key,value):
        self.add(key,value-self.sum(key+1)+self.sum(key))

    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
class Bit0(Bit): # 0-indexed
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)

def compress(L):
    dc={v:i for i,v in enumerate(sorted(set(L)))}
    return [dc[i] for i in L]


show_flg=False
show_flg=True

ans=0

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

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='#'for i in s]+[1]
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h

dc=dict()
cn=0
def bfs(x):
    global cn
    q=[x]
    v[x]=x
    dc[x]=cn
    cn+=1
    while q:
        c=q.pop()
        for nx in [c+1,c-1,c+w,c-w]:
            if 0<=nx<n and m[nx]!=1 and v[nx]==-1:
                q+=nx,
                v[nx]=x
    return        
            
for i in range(n):
    if m[i]!=1 and v[i]==-1:
        bfs(i)

g=[set()for i in range(cn)]
nbw=[-2*w+1,-2*w+2,-w+1,-w+2,2,2*w+1,2*w+2,w+1,w+2,+2*w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-2,2*w-1,2*w-2,w-1,w-2]
nb=[1,-1,w,-w]
d=[-1]*n
v=[0]*n
vw=[0]*n
q=deque([sh*w+sw])
d[sh*w+sw]=0
vw[sh*w+sw]=1
while q:
    i=q.pop()
    if m[i]==1:
        continue
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1 and d[nx]==-1:
            if d[nx]==-1 or d[nx]<d[i]:
                d[nx]=d[i]
            q.append(nx)

    for di in nbw:
        nx=i+di
        if 0<=nx<n and m[nx]!=1 and d[nx]==-1:
            q.appendleft(nx)
            d[nx]=d[i]+1
print(d[gh*w+gw])

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, list(input().split()))
Ch, Cw = map(int, list(input().split()))
Ch -= 1
Cw -= 1
Dh, Dw = map(int, list(input().split()))
Dh -= 1
Dw -= 1
S = [list(input()) for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

seen = [[None] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

for dh2 in range(-2, 3):
    for dw2 in range(-2, 3):
        if dh2 == 0 and dw2 == 0:
            continue
        nh = Ch + dh2
        nw = Cw + dw2
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] is not None and seen[nh][nw] <= seen[Ch][Cw] + 1:
            continue
        seen[nh][nw] = seen[Ch][Cw] + 1
        q.append([nh, nw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] is not None and seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
        for dh2 in range(-2, 3):
            for dw2 in range(-2, 3):
                if dh2 == 0 and dw2 == 0:
                    continue
                nh2 = nh + dh2
                nw2 = nw + dw2
                if nh2 < 0 or nh2 > H - 1 or nw2 < 0 or nw2 > W - 1:
                    continue
                if S[nh2][nw2] == '#':
                    continue
                if seen[nh2][nw2] is not None and seen[nh2][nw2] <= seen[nh][nw] + 1:
                    continue
                seen[nh2][nw2] = seen[nh][nw] + 1
                q.append([nh2, nw2])

if seen[Dh][Dw] is not None:
    print(seen[Dh][Dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, list(input().split()))
Ch, Cw = map(int, list(input().split()))
Ch -= 1
Cw -= 1
Dh, Dw = map(int, list(input().split()))
Dh -= 1
Dw -= 1
S = [list(input()) for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

seen = [[None] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

for dh2 in range(-2, 3):
    for dw2 in range(-2, 3):
        if dh2 == 0 and dw2 == 0:
            continue
        nh = Ch + dh2
        nw = Cw + dw2
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] is not None and seen[nh][nw] <= seen[Ch][Cw] + 1:
            continue
        seen[nh][nw] = seen[Ch][Cw] + 1
        q.append([nh, nw])

while q:
    th, tw = q.popleft()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] is not None and seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
        for dh2 in range(-2, 3):
            for dw2 in range(-2, 3):
                if dh2 == 0 and dw2 == 0:
                    continue
                nh2 = nh + dh2
                nw2 = nw + dw2
                if nh2 < 0 or nh2 > H - 1 or nw2 < 0 or nw2 > W - 1:
                    continue
                if S[nh2][nw2] == '#':
                    continue
                if seen[nh2][nw2] is not None and seen[nh2][nw2] <= seen[nh][nw] + 1:
                    continue
                seen[nh2][nw2] = seen[nh][nw] + 1
                q.append([nh2, nw2])

if seen[Dh][Dw] is not None:
    print(seen[Dh][Dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit((i8,i8,i8,i8,i8,i8,b1[:, :]), cache=True)
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-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)]

  while True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      if seen[h][w]:
        continue
      seen[h][w] = True
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
    while j<len(que2):
      h,w = que2[j]
      j += 1
      if seen[h][w]:
        continue
      seen[h][w] = True
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = np.array([[c=='.' for c in readline()] for _ in range(H)])
solve(H,W,C_h,C_w,D_h,D_w,S)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from sys import stdin
from collections import deque


read = stdin.buffer.read
readline = stdin.buffer.readline
readlines = stdin.buffer.readlines

q = deque()

h, w = map(int, readline().split())
ch, cw = map(int, readline().split())
dh, dw = map(int, readline().split())

ch -= 1
cw -= 1
dh -= 1
dw -= 1

INF = 10 ** 18
org_list = deque()
cost_list = [[INF]*w for i in range(h)]

# for i in range(h):
#   # 文字列の入力
#   s = stdin.readline()
#   org_list.append(s)


org_list=list(map(lambda x: list(x.decode()), readlines()))

cost_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
# ido_h = [-1, 0, 1, 0]
# ido_w = [0, 1, 0, -1]
ido_x = [[-1, 0], [0, 1], [1, 0], [0, -1]]

magic = [[-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]]
# print(len(magic))

# loopc = 3
# while 0 < loopc:
while q:

  ph, pw = q.popleft()
  cost = cost_list[ph][pw]


  for nh, nw in ido_x:
    # nh = ph + ido_h[i]
    # nw = pw + ido_w[i]


  # for i in range(4):
  #   nh = ph + ido_h[i]
  #   nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = org_list[nh][nw]
    val_cost = cost_list[nh][nw]


    if val == "#" or val_cost <= cost:
      continue

    cost_list[nh][nw] = cost
    q.appendleft([nh, nw])


  # ワープ
  for ih, iw in magic:
    nh = ph + ih
    nw = pw + iw
    if nh < 0 or h -1 < nh:
      continue
    if nw < 0 or w -1 < nw:
      continue
    if cost_list[nh][nw] <= cost:
      continue

    if org_list[nh][nw] == ".":
      cost_list[nh][nw] = cost + 1
      q.append([nh, nw])

result = cost_list[dh][dw]
if result == INF:
  result = -1

# # 最後デバッグ
# for li in org_list:
#   print(li)
# for li in cost_list:
#   print(li)


print(result)

Submission status: Wrong Answer

Solution code:
import sys
import copy
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
#read = sys.stdin.buffer.read

digtmp = [(0, 1), (1, 0), (0, -1), (-1, 0)]
area = [
    (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
    (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
    (0, -2), (0, -1), (0, 1), (0, 2),
    (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
    (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)
]

def warp(a:int, b:int, cnt:int):
    ans = []
    for i, j in area:
        x, y = a+i, b+j
        if 0 <= x < H and 0 <= y < W:
            if field[x][y] == '.' and check[x][y] == -1:
                ans.append((x, y))
    return ans


def main():
    global field, check, H, W
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    field = []
    check = [[-1] * W for _ in range(H)] 
    for h in range(H):
        tmp = list(input()[:-1])
        field.append(tmp)
    
    
    cnt = 0
    que = deque([(Ch-1, Cw-1)])
    for i in range(H*W):
        # BFS
        magic = []
        for _ in range(H*W):
            a, b = que.popleft()
            check[a][b] = cnt
            magic.append((a, b))
            for dx, dy in digtmp:
                x = a + dx
                y = b + dy
                if not (0 <= x < H and 0 <= y < W):
                    continue
                if check[x][y] != -1 or field[x][y] == '#':
                    continue
                check[x][y] = cnt
                que.append((x, y))
            if len(que) == 0:
                break
        # magic
        quetmp = []
        for _ in range(H*W):
            a, b = magic.pop()
            tmp = warp(a, b, cnt)
            quetmp += tmp 
            if len(magic) == 0:
                break
        cnt += 1
        que = deque(quetmp)
        
        if check[Dh-1][Dw-1] != -1:
            print(check[Dh-1][Dw-1])
            return
        if len(que) == 0:
            print(check[Dh-1][Dw-1])
            return


if __name__ == "__main__":
    main()