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: Accepted

Solution code:
h,w = map(int,input().split())
c = list(map(int,input().split()))
c[0] -= 1
c[1] -= 1
d = list(map(int,input().split()))
d[0] -= 1
d[1] -= 1
p = []
q = [[None for i in range(w)]for i in range(h)]
r = [[] for i in range(10**6)]
for i in range(h):
    s = input()
    s = list(s)
    p.append(s)
from collections import deque
de = deque()
de.append([c[0],c[1]])
q[c[0]][c[1]] = 0
g = 0
while q[d[0]][d[1]] == None and g < 10**6-3:
    while de:
        v = de.popleft()
        r[g].append([v[0],v[1]])
        for i in (-1,1):
            j = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
        for j in (-1,1):
            i = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
    g += 1
    while r[g-1]:
        v = r[g-1].pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if (abs(i) == 1 and j == 0) or (abs(j) == 1 and i == 0):
                    continue
                else:
                    if 0 <= v[0]-i <= h-1:
                        if 0 <= v[1]-j <= w-1:
                            if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                                q[v[0]-i][v[1]-j] = g
                                de.append([v[0]-i,v[1]-j])
if q[d[0]][d[1]] == None:
    print(-1)
else:
    print(q[d[0]][d[1]])

Submission status: Accepted

Solution code:
from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int, input().split())
si,sj = map(int, input().split())
ti,tj = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1
s = list()
for i in range(H):
  s.append(input())

inf = 10**9
dist = [[inf] * W for i in range(H)]
q = deque()
q.appendleft([si,sj])
dist[si][sj] = 0
while(len(q) > 0):
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == "#":
      continue
    if dist[ni][nj] <= d:
      continue
    q.appendleft([ni,nj])
    dist[ni][nj] = d
    
  for ei in range(-2,3,1):
    for ej in range(-2,3,1):
      ni = i + ei
      nj = j + ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if s[ni][nj] == "#":
        continue
      if dist[ni][nj] <= d+1:
        continue
      q.append([ni,nj])
      dist[ni][nj] = d+1
      
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int, input().split())
si,sj = map(int, input().split())
ti,tj = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -=1
s = list()
for i in range(H):
  s.append(input())

inf = 10**9
dist = [[inf] * W for i in range(H)]
q = deque()
q.appendleft([si,sj])
dist[si][sj] = 0
while(len(q) > 0):
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == "#":
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
  for ei in range(-2, 3, 1):
    for ej in range(-2, 3, 1):
      ni = i + ei
      nj = j + ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if dist[ni][nj] <= d+1:
        continue
      if s[ni][nj] == "#":
        continue
      dist[ni][nj] = d+1
      q.append([ni,nj])

ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
C = list(map(lambda x: int(x)-1, input().split()))
D = list(map(lambda x: int(x)-1, input().split()))

Ss = [str(input()) for _ in range(H)]
group = [[-1 for _ in range(W)] for _ in range(H)]

moves = [[-1,0], [1,0], [0,-1], [0,1]]

from collections import deque
todo = deque()
now_group = -1
for i in range(H):
    for j in range(W):
        if group[i][j] == -1 and Ss[i][j]==".":
            todo.append([i,j])
            now_group += 1
            group[i][j] = now_group
        while len(todo) > 0:
            checking = todo.pop()
            for move in moves:
                now = [checking[0]+move[0],checking[1]+move[1]]
                if not (0 <= now[0] <H and 0 <= now[1] <W):
                    continue
                if group[now[0]][now[1]] == -1 and Ss[now[0]][now[1]]==".":
                    todo.append(now)
                    group[now[0]][now[1]] = now_group

can_waap = [set() for _ in range(now_group+1)]

for i in range(H):
    for j in range(W):
        if group[i][j] ==-1:
            continue
        for yoko in range(-2,3):
            for tate in range(-2,3):
                now = [tate+i, yoko+j]
                if not (0<=now[0]<H and 0<=now[1]<W):
                    continue
                if group[now[0]][now[1]] == -1:
                    continue
                
                if group[i][j] != group[now[0]][now[1]]:
                    can_waap[group[i][j]].add(group[now[0]][now[1]])
                    can_waap[group[now[0]][now[1]]].add(group[i][j])

start = group[C[0]][C[1]]
goal = group[D[0]][D[1]]
import sys
import copy
seen = set([start])
nows = [start]

if start==goal:
    print(0)
    sys.exit()
for step in range(now_group+1):
    pre_nows = copy.deepcopy(nows)
    nows = []
    for pre_now in pre_nows:
        for j in can_waap[pre_now]:
            if j not in seen:
                seen.add(j)
                nows.append(j)
                if j == goal:
                    print(step+1)
                    sys.exit()

print(-1)

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
import base64
import subprocess
import zlib


exe_bin = "c%1EgeSA~LmFT^aY|CIQK}=#2wkU~U?F~2<7_h)37MAb`Wbk4^vI)sWNHQq#SL7>VQUWBl6YdJ7v@hFD-){QYCfn`4wwtsseLtFQ8=DWCbh8bRwxLOzut@_FAHn&6xFn!GXYP!2buFds+kOA_CV1{SbIzHWbIzRkxHH=6@vSh3qQD=caGQY8KC22hGCXl-NB~zal)~Rx!WV>MfK3`YeL61YrshmJDqp=ph4tx7AvYB@X^~L)>8{RA1;Li#!@BODt77-hwdJH6jVk^~Q7)f>@m0-Ju~qYIIjNP^m#4gaCic(I@cNXi)2*S$r}aHKgzq2QRal?y5pq+`_m{v|Ed1dQGq13gl~+hFgz1H++zz*PL^ds|yR{=UuOreG>zmhCzi8f~x|-hZn)$R&Rz};rdL5-lc7vwQ6%2>@J;ncGZk+v(Z!Y}u?(ZC!^p)ZFUre7y+8czd-B80KaNfXVR6JGI)ce&EE^@*%2^gp4!M7K{KMIm=%7fo6<fmU(0N+~xztNB%|6BMsH4pxa1?am9;C%(!^>hLJngVhT7ofjc%wNxE3ebPKfc)JB=ywSD@v{Wp6LX(M1>}FN0Nz?aPFsQcEG<C)N`ZR*E7i~SLSwDUWn~@ZprGP6I#hfm??BLhdgV~?mRqpTED|JXb7yy#)GG&~vLp$T*WV(A!qM>NNUt1@`dgYhy1T;uz^0C{nwLN4t~Pmott81?qTLTl9pSFc@)ju^jdn*{R|O$=bz3Cb>scG2uiYKJo(N^B3wMP&yumiv;RtRCL?t;Ih{(O(pvSWoa0@mCdLu!pyH}2e1D#&K<gb-HZHpwzx*!<oqSEC0NO!LUq~SVmS44I@JX-<pU%%P`^$GU%1vW*tIvk7Py(7@uE6Lk>!cwHGz1u^@V1`=hO@WXU=;-JU=3&RC^+xhZ2z9gqJrD+@o>(+2ZH+|bSfE2!GsnW-ZCyd>!3bytbRX&VY(l;F^+`S9Xm58{pd%u0leX3ZTi1h~`I^<FHVaf1?2gIwE!vw;b8P{g`XagNTP&>w;frb891h2Pl?Z4eU7NjabyC|x$?uRn9(0q<LC8TbaR}17t_LGsA!%*6H`W=(%pi9k@SNcNQgF-tQhOi*Etfz^Velmep=tthxGy3Lo#D=4&o+i@k6^PO3M00&dn@>mgi@I!b_T$_%}q_xf|^>P+2>u}B+aj>%e*<Vuk&jbs_%E+3B+|Z^Bn@bx|Vw-N6i9lj)3EU0b;*_r6w59Rj61f0Z7GRU^i!G2`Vi<BK%in$oA*fIol>9<+s^LAOeqv<u}5=ib!M%jv)Vs;hy~RSBr55@nZ(Zu8)-BNOVNQFACZ5@qzKbg`5)M=ZyZf=k71UI=#zax%w++tl#^LpO2e-9<YxE%^@AWhZS%{hu_HPPw4RD3_hvDx2m8pro*3L^95mEE<VZdW<8$qR~EpVYjg1&=J_Ja<9Zv{;4K=wZC(~%DP*6cx2kv?>x~-x2@SqNgFmUkU#r0<HTdf^_%RKBh6X>b!C$YzTWhoR)W&-r-*K9Fg9gvzJK|?*@U2XKiIAN;;d7@3ubsqf)Zk4T{1y#fJOAy`;I;F=J`KJ^gWsjWmum34HTX#y{9X-yvIhT@24AMZ@6+I?Xz<_C;LA1m=QVh%2ESi}*UmeJH27;Y_#+zpbPb;LpEHwq(UqHQ0vQ~V4e6t#|B(4$CO^G!31p>bH^5)ZtVVc4cnfBwPNw0RJs)8-UFs->{{mq&S!#&FHzABJn|hwY*CULkOYNiZG=$M)sl61QgfN;awTr?Agt6MG9tvN+5n${}sf`r=5MeY`s+GcL5JnTF8Y%n^!f2XQErs7e7)_G0QTRB*Xo{4T!aqeAO^^~Od;nqWqN%Z~2)_t$`(Cae*E*NqkzUtE9yzxkzz~U>W>=wJl>z&=Aax8Se+6tLA=}L)v24oCpy$z|GdHW&NS<eTWkeZGo@9U(2!9K$PQJ<z6_|T~0hN$D0=fMicB=?~D#YYJv8<U$_dgK`Zm^pnuM!Dnie%Jnrv>6m6@RIvFN1Gd1|G$i{b}_nA<l!A$7hS!hTo9k_lk&eA^A5bR6I-+5JZ#%MCq{CT4urGj3icC$>?$#_C}Ul!JiHQ!OD}Q|Ew5$hd2)-X_b7lFVTUV2chz%=xfSbEy}s%y(qT-pp7_x6MK&&HrO}%5+S5}+ozmL)`Azs{iu%Z_D0~aJm<HU8U6N(<Oq}(cY`V*yAecw)dt@AoEvi8poFL5b&t~4Jc0(>X>pGwXJbL2oO`Z78b@)1X}Ku*F9;@zKADL%dK+7}G5OcvYd+<4(qKmGk@y~J#}HXiMhzRghCFfzO?~%0t_`kx4kpihmQE)JGjf%~s^~UV^xtbm-^xV)Qwb{fLh^qhjdJ+x>-gss)8{gDc<h$RRw{Ja1G4~5On-<b3x9hf<{mPq-hp!4_d3pdm1Fl3<sH)h+p$)^FHtn<8k92Se@vsoHh_%u^lO3lV=mtXz&fa!69qcQiSnL2146)=FQ_44%020m?KPHJ1JpzBIf%VJ3j@EXR^;**P)zkz;3vaZjYJtE!^zu;I6{tHmBBJa-(v#HP+%c>yOvFb1_`lSN&hkl7(gV{rwp3?*8n9Gs9XX~7%57DjYVYNg?t|!Y^Uu(@_SP4K%v5}J6!9rPtqP~MkkK1Hs|!paY40fF;QfD6;b|;DBJCXC}nn1eUQW(&1AHhMp`obX%W0vs{N&zb|7T~_}6GN?L*24ihBy*!1FB6eFQo^e?9i^=32&6PgA8tdC*LPm&o8H%iu#Mtdko`OibBHsR!&w1$FQvikbQ?$~{4Y^N=|BCPF7^52XQ_<tO3Y^2Cisl(vV~0{e6y##~5S(esrfiqGEo$q8`?=uvBlrmOI_4{LmcBA=xe9kBmM6S1Ift^Gp=Xp<XW%La!mPdsT*>)Z#D8&I<AB_k_P)l~mbBMl94RisfZ4g{i+NnF)Ze^SH-VL7{5x%*kU7*19DVJEW2RYqUpS^EoUtv4OV#c}0|OSuAt_{mcwVQM79CyiL<o%>O9(C^*i8D(Vn{aH>30hX^1mwur95}-!&2eD!&#EqS^A<&pe|EE^Vz-esez)Vzo{K=W9+p|Ameud>%k+=m@8;RFBX@zz*+*T8Ni3G<<@Ix|ux`@OZoVywp*TlX}qfT75`$yH*P{(+|{ybXrsB;Y3hApu8MhFm*r7O&q#IHe{K7_~*zx}_}2Mf8A#9yEW@WxlvdT&`#<u&fGlHqX!u{<}ds5VMIJXy8(UaCN~9B*Prl}~vm`G6TM!P+=D6U=0p1<j<U7&Y0cN4V|v)R3sTTC}u+Q4}ok3bh0TDFlu%U<(3=7|;{<*(>99_V@;SgK}gzIm_v@&vaS7e#mj&ReDGn8y=tK7;!0=T-77W8_J2{Gqc>)N#%97`E+cOa|3jcFJa^Q4}udM7G2J_W54P**~NY+UyPgVAiR+PP-_!?_WJ&DV{EUhe^f-26^R-|thbdoRp+q`z6OB}@U4`j&xUP58R8z=-leLWTLx=r4BbO}eI|y}{%09{62rqIhcHU0!Q6GPOJZ^5YmTGUN8RFB|F~!wXvRJVJXOpqd{B`%NU5mb)i9~XGWh2-U$)nRU(^!u)m__{T?I7GCxELS=>63EqpE7rVZ{^59{UiyIMKGKV@u00b&ns@3a+Rn-~xINL5~1I8#Qi$hD)}W@}L4`Z9&HvqEh_!9+K#*O0I|bRO%5rOW0{m*2C;5)%PhKdl*+=l{#uYeMxO8@x?bn48POrb^cnuhQybu**h-L@w)PClJi;Bj4)=vi1zQ8CZ@DcLHAtvOc@<8_CxaGlUUDkN_LRNzlA%e<KQ?-l-gtk^|H5<dw?Rj_!9cA+8+}|Ujr(a->ZBEF<mJk@tv%$A6!hQy*LZ-Vi$#xOs*vfsghKmfPu(J5*?$JXH8gJ62D#LcnLU&^DLATJFPMSdJ5V;_3T9~vXMH%!R+v~myRUyZkQv_f=P-z2dcs1)KZdYf>K98?&gcxY0N2ae5M^{Rq}KwhKlxHq=S<xaDx2oc-4Qde(<<u_f8xjg7=!e$|dC&&etqYbeS*|+Mh;xuaYLCC2Vvtvy{eQoL5}<7&Iat@+u{c<1NZ&EA;<S6V9r4!n8~z&evjNB=`%+F~4M{L4i(VllwnLqY*P$W>gJeTTBFoj!NJs&R<yuaETvpGP&b7KpcRqBcwlNMm_hBn=N0Of!!zw8Q%DHB+)Raj(OYd=6J)SZs*(Ee?$^>jS$pe9%mZ!#cepodYy+brdVTtcJ^tiPjCMrlg}BlTjd0b0kZ<T!5cK$8Fv+MKOe7Ju*I~X!)`M6!GL<vmzeu~m-As^$1qt6)paQkL%}C31J6N?6sHma>kmV#enzTC==5aV=u0$$rIH2$gZJ?JY_`&ZW87=libTanOP6e)ks1**<58mGpjR1Ny5wOS^27}!u|B<0F&!kzQFXp^lpGs}k$vYcpn@MM^`N`dt?8`)#$lBDcXxa$ss4>S9x##ND}WG5!jtwY=Ux5piC$&cJDj@RD-L^){jO#3Wy=%zjmMEj3z+wkM6>8im|!w;(nQ1)-b5>ys_wOTxzoH8W-uc@n2g7Zz0PAqF?~vu*LVJ`W$-*k0kdWBD|Bc+4~<Q#RXt3OT_Mgh@_i(+9H+x%_yS-@$+0vUJifyX<$UT{YTbVQS!c#y0S8UJ48$I%b;pff2z!Y-D9H30N!*dvDIvY{s9U+#t+bm`XRoOJi6s2fptV3AuP4fFs6&0(XCFsDqtkhCDO_A&q#eF&gi6VG0Pi&7q)40Pu`_JiVH*b(pKWU2O9o$-!Njj7-~9ml;Gue-GOh{cdwp0Sx69vN$=U^lnAw1DOa1`4AzW6u;w=IZ4=9sRhn32GCfWghNFz}j_&n(Or)2mHgqONsAiLu@pSP4<19M0#bTl(@{xWufB<9va7$Aujvpkcn0IF!OO4fgn8BTn-hS>lUr-y}jCm0xXy#Y|l!ITFFt{<{B8N{9=mdB0o1~b=wsIXueXu&~e_#Nnue!DHTFs<qvtq&`uK^cO*<9O<dy240Bkr=0vhf!N^Cx0-8v6F?xZ;h$J+xmgJ961FMJXAs>_<t1B2>uQvFXHqj=>ytq_-fCMU(goGOqNPkxi-EiK8+;qFN=%H0;SEQG(oWtMf(rIY{T=h#zM><UIi9GZ;)HABg#ec6F%xew52XaN4pVNOjrg!rA}EV_?%;w$F3sh=m;zl(mv%A+GB`PVNagAkWRN?452;2i^E)n-5YPPdlT;If-Al_J{9fk{8Z^NDQ2bBY#Df$nz$Jj;%_;Q^MC<?B2hMon+2KmPuz5!R{<e$_jP6$yg-`{lo98#*n2)P<#WOUH&P}qg0Z2@aok%y<Wq)JF?CeTUf>5maZfFayRR`rTA{N4GIolH7gcl2z{)Fg?JeR(FD#zTE%3*h8oo;BbFQDzt&4JMZuGnT>(pnu*EwQ&`~pyU9OqjGFL^N#mI7JJ{g=v8Z(U{dJ|&e}Pnp&Bp#5N^K@)nFk8y;(q8f4y9rBbT-s-pLhzce^^}j&XR0mogMXeLG!hSmZq^agR-bdfQ2lUhe6+cP!t{nD?qu%Nhaf8qKZj<6(D9AR9TgqEL<pMRDPchk(4^UQwU_R(oezqpzE;6-LpYl2XL!RnWMt#bMxGV6+d2n52s0BhdjIz|5PoGEocS0p%AnIW&x>=5kH3~lwsoymG02`fJomnqtwmohqsK14@pInN;AUWo7pej=<(prxv@n-PwW~+Q{{90Jen3PuVP(bx3O|%?P;D<zk06CKU2b^!ko6L8!OzP)tBshZk{pW13Ds5n^((U$2M|yAw7Nlj+o6VpSQ{MyeRc7arhwmFa-q-Ftwqp~Cx51pSO*<!~TSLQ_v2z>)z6uzu8lglOXd8|u*J4u=APGV+?mgiqQ{szN$(5g}(Wero!|JLy21}zuw!6V~r+n8)yZsph?e=K{pSZ0%2h*~B=csbzyM3sHc(awf$gAS39>U=jDsli^BI+V&t09c*>WqSnHmb9g{-H{EA6MVch_SaJI&bwROhc%}gYA3yx*q+qMHywG1)Ng(2>sF*x3pBh+M;~s9sbPdvpn|>d6Cs%5(Elg^+{^Q0Wh}DdCCX=XK5Poi6<?O`f+%79<@Ba3SZEZSBo@|G<t_m86kKizke2-DDJ^%;e+6?GGVI4m~CE_a4!QBy}|tD_qC_RIcynt2EdlY1C>7Ir#>awQa$E{8R_ao!(rS^Sc3vH{=@~1Hd-|Tld7-Hhv)#KK@Uu~9~vX0%Ne?7j3|9$fEy=D6w)3@`|y3-=NyWCr$v1A>|`ES`$u4Y>}2!bGY}4(S6h@1VyB_0Fjx%9&|yZC--HaG_%8M#u*cmHB@aWBJ!U!&gBN{|%Jv6{zAz%BQ!k>k!<b4NgWcvZU2QBohu-r^Dl_h?@#b~3t1mHoeJS0Fns+axZLqwDNaU-2kM2psJSi!q(BaO@HpiQp`G|7ar(AL?7hLIzUlUwS!kqgIZis0|{cQa{I>`38b9S|}k0=-f{EAl-3<|ZjhGn*1+nhP@r@^+lrb`l3Tzj;;6VWtnuysiY&>XoNU*RueQQp>YQ0|T{St8-*>GnXZLzV(PJ>jlUp0e@jl|xIGs7wu#zvnhvD01KZy>c{A73}Wnm2I1&fu1c5{@dovwMDw*YTMoTb=Ky$Ekp1gD6cyb0v=AbWJw?ts)8&^KG)`-$e}(9DTg=WVen!m12N(a#-+H(Mu#j*rqe%%bS9YMGf3w`+5<siJM@+pApH)cxaIRBhz&CV-t%EPT>(9->?8CjLFj<=SxD!?gzaNU&;2f)ZiKKh6PBNQAl(4zw-AP?^a{e@Hm`u3S0Jr0Wxr{O53Lo%KC5^`S&4bCSYkyy{f-3X-=fiHetJQ$Gy2-o=`=liP;OmOUb)gT`9bq8;r8p7{>1|OO`IRk992TQ%^JD*U3LTf>w!5^j5>a~b&tVaUip~ORc`Ay8P-oKuXL4LmzSHplU@8(<--WNANc4=pXJEs%J6+L!?s$>mOa<?P^*u&q~z}gp_AOe+v5||HVuK?7eG&@2MtvAmki6xE1xhfFSjL3%gd|w6uHW4A1ij1*Y}sW%X^GX#!2P%?($k!c@>ZV>2g}&^2r2bHGte&SbEbPwcjVJH3X786C@Gbpc2$`EYE(DPS44e<;lo$XJj>(w;B$BFxLcOp2_qZ=+8mMZtx!`DkM;D?KiYh9ogXD8038i@`f<ag?TH>YYktTRBm;Zn_ZKso+@xO1HW_PS1H4Nc`B1_*vj%&<90D`ZC2q&q*nO%_fY0j&<|e5FWq=x<@0sbTs~wl&N1bc*^Dw9Svy{MFP&Zmbu_)9>MVgW_ZXYXZI79NufM3d{G@0+3$?2P-*IsnuF1@AKLg$&@b4Pb#j0}ay`UxZ<qGIeyDz8HVWEI62-cNgU0cc<qxtGdW5EWH^E}AWeveJ3#pyoKL%&$Gw^Vqnr0A?!h?f@8jA?Hb{mAr<$-*;}ioQEZxH@SC#m>CxWoYY<4L6UNgo}ovVUzGp<CM5bc*NA0H$wjD`P1{K=Z}5(xf*_sW~1(KB0qn^&&Tj5b1sHG{5%Xl$CAP8V6i}2Wypm+4CZGdPO=w%7UIy&YRb=`@bg0aED1jY!Ox=b^Fe&P<YV^5tLbh`pJL_lGa-HKg`Wi(V)^_`$7KfdvmE>kj`qw1KKu+$Jv&#yW8yB>P(BagXG{25n~jrm@vWt~_2%cK`Pma*{uhK?I+!-m_K6I2mBG(5f;5A9J;xXvW%<8ju=Xs=f9J!`f9s!XnW5*fbP-Eeuyj33+gZAmrH`@nt1SH{OaCuRM_BqxmY!niC6*Rz57qoXJp4Qtf0~<`me{J+ZHjftG27yrg*CPF7Q`sz*x{(JsjaJ4v44ncJW*F~$cHy%&co;8je?vPZ_4<4F1{$^=ehXeOn=D5mt_1T7jMq^S1!IZ<Hx!9Ng037#ZS)k`&@ik?xCm*eu`ktV?U!%F4*$oEtxoyi?<3V^Wvvw?hoYRrwO}e=fhtk*sAm4D>Csa7e74{r*iSv3P<zeuglwij1UcYyvfDSz=diaeD=I`F8+oII1F1R;e)guUrO_=!bYZ_+Zp~Z8GawbI~abafU&SVGw#$d{25Ary|8V*EmIyozbjC#NmS(=wdUfB8Q!WJ&t@>Zew@2iRLkwtm3te-Pqa&z$=Roq^8lrvXx~Eh-%IJI2{ZHfNk00o(~3>>!|zc!6aC>uN?$Rd{{P1C`g*=a<xKP+T$A4jerRR#`FLZX=XYlal{)_^rT0KU&y4T|b_nyk#kd}u=!Z)T*s5&5<7YO#1@0kqGx=5~#>w#iP=NkufqN<Em>fR88De;&5#?m##wva<$(Ub$YXSTh0YB9+W5T$wy8!*Z0{DLg{EZ;TsyjdYx-tKKl2Vh}E^erG3_n(a@+Zc<I~e^gHUWt-Jf6VJ+pYrmzcHboSTplM9=`vP$v?>^D06rRE6OkDd&R2$`TaS*cT-V-{?7~G*U<J(97mdpRJ-W?c1@A$=RDqWKbMM_zul<9PUa6!GI~DG<zeU>1?n@sIRE{YxyAYI7${cDwf&h2?`QPiE>`=Uz8~QiX)DOzH9r@>zc{}?JRzuhex4QnGN1RBsCMM@d_MoHC{g9>^=2!{-(F9ND!-NaTbSY36`;SbMAhfGPX7-Tp#Qr9`0tnGzjySr0`#X?J%?C5`84QKN&b6BW#;^HZZYTYM-Aru^;uOw&V2>w2MW+<Hm9Y#?yBc|!`_IeO<tt#8hiaxTfp0fmtoefV!OHsMLZ6tB(<*f`2Bw+tys6Z$?sjW8gEYBb=PXmX77SPDCCJm3Q{-w)+~4VB&j#HN%Bh4T@ENB5|ZR@iOE>IDqEGpS9S_s0m7thA>QP{%R;_-Ns4qwx+1a=jLN-oti8P^C}i(>NphzY#QR*mf+U5yrOh4Pn*tqD2nz3&0<k_J*xlLF5thTDn#GHp_4$eLPESM%M5BRiQn*WwZWG$0fzGfLigkA4wI2;6VO4TSC27T4SBppTtahV%q~_J@BoARo;$ACA?!Q{?YVkHfUJi387eVh2Wz@T7#fmnMU-G+_`#ci8*p=O%m%^cd9024WXMREQuA#TMx};cdI8^W&S!1L2@)5n$#YIQjuqcmXei)P*2!??xc)xe$+6bC$f#mL4<ClK_6*64`Ik&1<9=jhU<@HS31O5y5@bnG*oGXC(s)l;Ir7Zy{G_1KCs3+3gBg<`$`;MAuxV@&p4Z1(z>R)4{=89O3W&SH2%{`yq(OaGIFp5wwy=5EVsLQz&r#F<pP5Z$puh%S=@D?U@GH4F!h`G+z)evencg1M^p&4D>(N5@}5$N9m6wn%>?#$f_?=I?X*!5ti-VC|-`?B@LJbz0Q@35fvf;DfGc;$JQqK(M?j_1LPkAAPFfBt{J<e1Y`yg8V;VX4>4A9f-1bNnjPth#V$bC~L3zLYNnK*xgrJ=nbYJQ7G4sCZ=iZ*y06Q?^Z`acL8@M^nzkOQ?G9pm#Qdy)hbs`CZNlPVLQcjXeE!g68NYVO?RLcQrZZek$;>tD~9<;^36II-Iu|*{i1$!e_QmQ?2RlOi#G~o7<evxi+2m{&H^Rgqq%MopN9kq;gbExA3<}7l`Z;YP!1Ra1E3<PY!Hm5X6C+O|eKvXkH{FP-sh_cZ*OH+SUc~)KreDIa|RNk?yV>K!UtzxFdjs?5(Fm#v;Ma_*%2M8(tuY!C$J|nrJs2P;0_l*igSE6wN{)Js6b2eZg>#EXlO}HQ8}nmBHUp4weZbX-xy2k)VndYQRN>8kmlB!n`5hyzY;D_-{S%`D>xy1L2RTgK_$+y-TV8y$zd=-lT&aI)1+Y$W#6HnVuiNLtaX!yE#AKr{rlB!}IM({WjxjLEV$*{Cq!?r~6ro`}+K@Ek1mmv0ljijSar<$<xca{ZYOC?iJKMbxy|jM|rwLSAT;py<brG=sC>yQF*#g$kyK|Ol<!{0>A04K77BGr~JEtUVps(1B`z;gZaKJPx*I?BF3ZV$Mt0Pw??wxZFs7^ODqTz?XT$gGyA+OwdxdZ)um7B`1yV?PxbmT>(Zxn{Cxk1r{B<h;L&Y63eV{H`92Fz_1oY2_W!ex+kg3f7*8v7?YHUpzo+9b^t(5O%7016&-b-?y3d$Puh-|xI)1+Y&C@kHdVT+SQ&8_U^J22Uqocxlee3OqSGFt~e!lN{WN!ZY>iIunb>jSdALuCKzq0^;<`Hx6-e-U3h}B;cf3*C(T~F!C=lihrx3c#9p8A)Hx%`>^A@+qy`&$9|>Th8m3OPUDr>bQ9jk@^PsN=6-<?BCaaen<acfRkz`F@OuF#dYB5rx}f4q;;aDb>_n`|M(Y_n&nQ*8AVo0{qoYtXv&~p8r1q0UZ3f"

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
from collections import deque

di = [-1, 0, 1, 0]
dj = [ 0, 1, 0,-1]

H,W = map(int, input().split())
s = list()
si,sj = map(int, input().split())
ti,tj = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1

for i in range(H):
  s.append(input())
  
q = deque()
inf = 10**9
dist = [[inf] * W for i in range(H)]
q.append([si,sj])
dist[si][sj] = 0

while(len(q) > 0):
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == "#":
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
    
  for ei in range(-2, 3, 1):
    for ej in range(-2, 3, 1):
      ni = i + ei
      nj = j + ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if s[ni][nj] == "#":
        continue
      if dist[ni][nj] <= d+1:
        continue
      dist[ni][nj] = d+1
      q.append([ni,nj])
    
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
# ABC176 D Wizard 
# 地図系。ワープ有　01BFS??

from collections import deque
H,W = map(int,input().split())
sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
sx,sy,gx,gy = sx-1,sy-1,gx-1,gy-1

C=[list(input()) for i in range(H)]
inf = float("inf")

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

d0=[[1,0],[0,1],[-1,0],[0,-1]]
d1=[[-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]]

dist = [[inf]*W for i in range(H)]
dist[sx][sy]=0
que=deque([[0,sx,sy]])

while que:
    L,x,y = que.popleft()
    for dx,dy in d0:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and L < dist[nx][ny] and C[nx][ny]==0:
            dist[nx][ny] = L
            que.appendleft([L,nx,ny])
            
    for dx,dy in d1:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and L+1 < dist[nx][ny] and C[nx][ny]==0:
            dist[nx][ny] = L+1
            que.append([L+1,nx,ny])
ans=dist[gx][gy]
if ans==inf:print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
# ABC176 D Wizard 
# 地図系。ワープ有　01BFS??

from collections import deque
H,W = map(int,input().split())
sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
sx,sy,gx,gy = sx-1,sy-1,gx-1,gy-1

C=[list(input()) for i in range(H)]
inf = float("inf")

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

d0=[[1,0],[0,1],[-1,0],[0,-1]]
d1=[[-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]]

dist = [[inf]*W for i in range(H)]
dist[sx][sy]=0
que=deque([[0,sx,sy]])

while que:
    L,x,y = que.popleft()
    for dx,dy in d0:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and L+C[nx][ny] < dist[nx][ny] and C[nx][ny]==0:
            dist[nx][ny] = L+C[nx][ny]
            que.appendleft([L,nx,ny])
            
    for dx,dy in d1:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and L+C[nx][ny]+1 < dist[nx][ny] and C[nx][ny]==0:
            dist[nx][ny] = L+C[nx][ny]+1
            que.append([L+1,nx,ny])
ans=dist[gx][gy]
if ans==inf:print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
from collections import deque

INF = 10 ** 12

class BFS:
    def __init__(self, H, W, S, C, D):
        self.H = H
        self.W = W
        self.S = S
        # 魔法使いの場所
        self.C = C
        # 目的地
        self.D = D

        # 盤面上のセルの状態
        # -1: 未到達
        # 0 : 魔法0回で到達
        # 1 : 魔法1回で到達
        # 2 : 魔法2回で到達, and so on...
        self.board_states = [[INF] * W for i in range(H)]
        self.board_states[C[0]][C[1]] = 0
        self.queue = deque([C])

    def is_legal_move(self, move):
        h = move[0]
        w = move[1]

        if h < 0 or h >= self.H or w < 0 or w >= self.W:
            return False
        return self.S[h][w] == "."

    def walk(self):
        while len(self.queue) > 0:
            move = self.queue.popleft()
            step_count = self.get_boart_states(move)

            if move == self.D:
                return

            up = (move[0]-1, move[1])
            down = (move[0]+1, move[1])
            left = (move[0], move[1]-1)
            right = (move[0], move[1]+1)

            next_moves = list(filter(self.is_legal_move, [up, down, left, right]))

            for next_move in next_moves:
                if self.get_boart_states(next_move) > step_count:
                    # self.queue.append(next_move)
                    self.queue.appendleft(next_move)
                    self.set_boart_states(next_move, step_count)

            for i in range(-2, 3):
                for j in range(-2, 3):
                    next_move = (move[0]+i, move[1]+j)
                    if not self.is_legal_move(next_move):
                        continue

                    if self.get_boart_states(next_move) > step_count + 1:
                        self.queue.append(next_move)
                        self.set_boart_states(next_move, step_count + 1)

    def set_boart_states(self, move, value):
        self.board_states[move[0]][move[1]] = value

    def get_boart_states(self, move):
        return self.board_states[move[0]][move[1]]

    def print_board_states(self):
        for l in self.board_states:
            print(l)

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1

S = [ [None] * W for i in range(H) ]
for i in range(H):
    l = input()
    for j, s in enumerate(l):
        S[i][j] = s

bfs = BFS(H, W, S, (C_h, C_w), (D_h, D_w))
bfs.walk()
goal_state = bfs.get_boart_states((D_h, D_w))
print(goal_state if goal_state != INF else -1)

Submission status: Accepted

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)]
 
INF = H * W
 
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
 
# def steppable(h,w):
#     if not (h in range(H)) or not (w in range(W)):
#         return False
#     if S[h][w] == '#':
#         return False
#     else:
#         return True
 
num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0
 
# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0
 
# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop() # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        # next_  = [
        #     (h[0] + 1, h[1], 0),
        #     (h[0] - 1, h[1], 0),
        #     (h[0], h[1] + 1, 0),
        #     (h[0], h[1] - 1, 0),]
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp
 
        # 魔法を使っていける場所を検討
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]
 
        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))
 
    num_warp += 1
 
    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] = num_warp
            queue.append((magic[0],magic[1]))
 
print(-1)

Submission status: Accepted

Solution code:
#入力
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
from sys import stdin
s=[stdin.readline() for i in range(h)]

#for i in range(h):
#  s_=list(input())
#  s.append(s_)
#幅優先探索
from collections import deque
q=deque([(ch-1,cw-1)])
used=[[float("INF")]*w for i in range(h)]
used[ch-1][cw-1]=0
X=((-1,0),(1,0),(0,1),(0,-1))
Y=((-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,1),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2))
while len(q)>0:
  y,x=q.popleft()
  for dy,dx in X:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]
        q.appendleft((ny,nx))
  for dy,dx in Y:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]+1
        q.append((ny,nx))

if used[dh-1][dw-1]==float("INF"):
  print(-1)
else:
  print(used[dh-1][dw-1])

Submission status: Accepted

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$}@2ZI7Zb5Xay1Ddw^{7GecmbIHXl_eBUX*cPeBL!m|CKK)G#x`?;gH&+u)XMQvD?@a3pFrjp(MWOakq}8cQPduWlmGd(9h>8{+;|C^M6@__S@{rb*=1QlP4uhhmX%QCU7|KECb+rqAhDvC@mMQ&>2~}8ir5rG(<>8de$=bREjG<Bnj5i$zDoR<m8tm@FA1K|5>U4LPyi{C2_?f8hZbj27BOozGXAWgN+dF^@w~!OK5>Ny*0c1`D1_C_+N<a`e6S!dDjgGgQ%_cG5+XPAi%sQ;N7~Kgp7~EiVL!D8R#|W&qSU~*Yb>=bOcdQ!k^*j6cyb^Fxh>J>Gl;WZm7sa?I-^uD01lEQYN5Q?^AEn=tP!oFbt<9k45A-^rpW$Yeu}I=`0ufxCW(Z`b^1~4)<SAIg)_0nIX48|6&TJdsx#ptaP}LewAMjG@!J8@%m=|q0mP&hLQB$Orhq<XYRR2izPZTv2eWd6UB{E>~ki>lgzp(FnFn3Z^cz5ieCRYUX-mqD32Rz>!&L38=oAqwd)_$b=1vOPSZOE~<u=U{`Bj4e=&~aN5m83^y3kx3;nvKbS_Lq4jrdb|m;eLA*GkI<k{uaUR$0#a_uoKq$9C4eG8SvOx;r|=z=g|2Rh|VGU2=PMk|1H_x$uAUJ<_p1=p*Rt|@8jQwd9e6+Se%(xki;kZ<2!!=vtwqq")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int, input().split())
si ,sj = map(int, input().split())
ti, tj = map(int, input().split())

si -= 1
sj -= 1
ti -= 1
tj -= 1
inf = 10**9
s = list()
for i in range(H):
  s.append(input())

dist = [[inf] * W for i in range(H)]
q = deque()
dist[si][sj] = 0
q.append([si,sj])

while len(q) > 0:
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == '#':
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
    
  for ei in range(-2, 3, 1):
    for ej in range(-2, 3, 1):
      ni = i + ei
      nj = j + ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if s[ni][nj] == '#':
        continue
      if dist[ni][nj] <= d+1:
        continue
      dist[ni][nj] = d+1
      q.append([ni,nj])
    
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
c = tuple(int(x)+1 for x in input().split())
d = [int(x)+1 for x in input().split()]
maze = [[-1] * (W+4), [-1] * (W+4)]

for i in range(H):
    temp = []
    s0 = input()
    s0 = '11' + s0.replace('.', '0').replace('#', '1') + '11'
    for j, s in enumerate(s0):
        temp.append(-int(s))
    maze.append(temp)
maze.append([-1] * (W+4))
maze.append([-1] * (W+4))

def check55(i, j):
    cset = {(ii, jj) for ii in range(i-2, i+3) for jj in range(j-2, j+3) if maze[ii][jj]==0}
    cset = cset - {(i-1, j), (i, j), (i+1, j), (i, j-1), (i, j+1)}
    return cset

def check(i, j, delta):
    if delta[0] != 0:
        ii = i + 3 * delta[0]
        for jj in range(j-2, j+3):
            if maze[ii][jj]==0:
                dset.add((ii, jj))

    else:
        jj = j + 3 * delta[1]
        for ii in range(i-2, i+3):
            if maze[ii][jj]==0:
                dset.add((ii, jj))

    return

#bfs

k = 1
tempbfs = deque([[c[0], c[1], k]])
flag = 0
while tempbfs:
    if flag == 1:break
    p = tempbfs.popleft()

    #dfs
    if maze[p[0]][p[1]] != 0:continue
    maze[p[0]][p[1]] = p[2]
    if p[0] == d[0] and p[1] == d[1]:
        flag = 1
        k = p[2]
        break
    temp = [(p[0], p[1])]
    dset = set()
    while temp:
        p0 = temp.pop()
        for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            y = p0[0] + delta[0]
            x = p0[1] + delta[1]
            if maze[y][x] != 0: continue
            maze[y][x] = p[2]
            if y == d[0] and x == d[1]:
                flag = 1
                k = p[2]
                break
            temp.append((y, x))
            check(p0[0], p0[1], delta)

    if flag == 1: break
    for l in dset:
        if maze[l[0]][l[1]] == 0:
            tempbfs.append([l[0], l[1], p[2]+1])
    dset = check55(p[0], p[1])
    for l in dset:
        tempbfs.append([l[0], l[1], p[2]+1])

print(k - 1 if flag else -1)