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:
import collections

def WizMove(sh,sw,cost):
    q.append([sh,sw])
    s[sh][sw] = cost
    nextQ.append([sh,sw])

h,w = list(map(int,input().split()))

c = list(map(int,input().split()))
c = [c[0] - 1,c[1] - 1]
d = list(map(int,input().split()))
d = [d[0] - 1,d[1] - 1]

s = []

for i in range(h):
    s.append(list(input()))

q = collections.deque()
nextQ = collections.deque()

q.append(c)
nextQ.append(c)
s[c[0]][c[1]] = 0
cost = 0

while len(nextQ) > 0:
    while len(q) > 0:
        wiz = q.popleft()
        if wiz[0] > 0:
            if s[wiz[0] - 1][wiz[1]] == ".":
                WizMove(wiz[0] - 1 , wiz[1] , cost)
        if wiz[0] < h - 1:
            if s[wiz[0] + 1][wiz[1]] == ".":
                WizMove(wiz[0] + 1 , wiz[1] , cost)
        if wiz[1] > 0:
            if s[wiz[0]][wiz[1] - 1] == ".":
                WizMove(wiz[0] , wiz[1] - 1 , cost)
        if wiz[1] < w - 1:
            if s[wiz[0]][wiz[1] + 1] == ".":
                WizMove(wiz[0] , wiz[1] + 1 , cost)
    cost += 1
    count = len(nextQ)
    for k in range(count):
        wiz = nextQ.popleft()
        for i in range(max(0,wiz[0]-2),min(h,wiz[0] + 3)):
            for j in range(max(0,wiz[1]-2),min(w,wiz[1] + 3)):
                if s[i][j] == ".":
                    WizMove(i,j,cost)

ans = s[d[0]][d[1]]
if ans == ".":
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from _collections import deque


h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy,0]])
while len(data)>0:
  xy=data.popleft()
  x,y=xy[0],xy[1]
  if xy[2]==dep[x][y]:
    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.appendleft([x-1,y,dep[x][y]])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.appendleft([x + 1,y,dep[x][y]])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.appendleft([x,y-1,dep[x][y]])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.appendleft([x,y+1,dep[x][y]])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j,dep[x][y]+1])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Submission status: Accepted

Solution code:
from _collections import deque


h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy,0]])
while len(data)>0:
  xy=data.popleft()
  x,y=xy[0],xy[1]
  if xy[2]==dep[x][y]:
    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.appendleft([x-1,y,dep[x][y]])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.appendleft([x + 1,y,dep[x][y]])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.appendleft([x,y-1,dep[x][y]])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.appendleft([x,y+1,dep[x][y]])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j,dep[x][y]+1])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Submission status: Accepted

Solution code:
from _collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    s[i+1]=x
s[0]=s[-1]=["#"]*(w+2)


dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
data2=deque([])
while len(data)>0:
    while len(data)>0:
        xy=data.popleft()
        x,y=xy[0],xy[1]
        data2.append([x,y])
        if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
            dep[x-1][y]=dep[x][y]
            data.append([x-1,y])

        if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
            dep[x+1][y] = dep[x][y]
            data.append([x + 1,y])

        if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
            dep[x][y-1] = dep[x][y]
            data.append([x,y-1])

        if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
            dep[x][y+1] = dep[x][y]
            data.append([x,y+1])


    while len(data2)>0:
        xy=data2.popleft()
        x,y=xy[0],xy[1]
        for i in range(5):
            for j in range(5):
                if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                    dep[x-2+i][y-2+j]=dep[x][y]+1
                    data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -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:
H,W=map(int,input().split())
CH,CW=map(lambda x:int(x)-1,input().split())
DH,DW=map(lambda x:int(x)-1,input().split())
maze=[input() for i in range(H)]
di=[[-1 for _ in range(W)] for _ in range(H)]
adj=[]
for i in range(-1,2):
  for j in range(-1,2):
    if i==0 or j==0:
      adj.append((i,j))
warp=[]
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) not  in adj:
      warp.append((i,j))
adj.remove((0,0))
from collections import deque
dq=deque([(CH,CW,0)])
while dq:
  h,w,d=dq.popleft()
  if 0<=h<H and 0<=w<W and di[h][w]<0 and maze[h][w]=='.':
    di[h][w]=d
  else:
    continue
  for i in range(len(adj)):
    dq.appendleft((h+adj[i][0],w+adj[i][1],d))
  for i in range(len(warp)):
    dq.append((h+warp[i][0],w+warp[i][1],d+1))
print(di[DH][DW])

Submission status: Accepted

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 _ in range(H)]

used = [[-1]*W for _ in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
q = deque()
flag = True
num = 0
for k in range(H):
    for l in range(W):
        if S[k][l] == "#" or used[k][l] >= 0:
            continue
        used[k][l] = num
        q.append((num, k, l))
        while q:
            temp = q.popleft()
            num = temp[0]
            i = temp[1]
            j = temp[2]

            if i > 0 and S[i-1][j] == "." and used[i-1][j] == -1:
                used[i-1][j] = num
                q.append((num, i-1, j))
            if j > 0 and S[i][j-1] == "." and used[i][j-1] == -1:
                used[i][j-1] = num
                q.append((num, i, j-1))
            if i < H-1 and S[i+1][j] == "." and used[i+1][j] == -1:
                used[i+1][j] = num
                q.append((num, i+1, j))
            if j < W-1 and S[i][j+1] == "." and used[i][j+1] == -1:
                used[i][j+1] = num
                q.append((num, i, j+1))
        num += 1

E = [[] for _ in range(num)]
for i in range(H):
    for j in range(W):
        for k in range(i-2, i+3):
            for l in range(j-2, j+3):
                if k < 0 or k > H-1 or l < 0 or l > W-1:
                    continue
                if S[k][l] == "#" or S[i][j] == "#":
                    continue
                if used[i][j] != used[k][l] and used[i][j] not in E[used[k][l]]:
                    E[used[i][j]].append(used[k][l])
                    E[used[k][l]].append(used[i][j])


dist = [10**6]*num
q = deque()
q.append((0, used[Ch][Cw]))
dist[used[Ch][Cw]] = 0
while q:
    temp = q.popleft()
    d = temp[0]
    i = temp[1]
    for e in E[i]:
        if dist[e] > d+1:
            dist[e] = d+1
            q.append((d+1, e))
if num == 1:
    print(0)
elif dist[used[Dh][Dw]] == 10**6:
    print(-1)
else:
    print(dist[used[Dh][Dw]])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    maze = [input() for _ in range(H)]

    INF = 10**12
    path = [[INF] * W for _ in range(H)] # 各マスへの移動コスト
    
    # walk:移動A, warp:移動B
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[ch][cw] = 0
    q.append((ch, cw, 0))

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk: #移動A
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s)) # なぜleft?

        for dx, dy in warp: #移動B
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s+1)) # なぜright?

    ans = path[dh][dw] if path[dh][dw] != INF else "-1"
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
h,w = map(int,input().split())
sx,sy = map(int,input().split())
sx -= 1
sy -= 1
gx,gy = map(int,input().split())
gx -= 1
gy -= 1
route = []
for i in range(h):
  lst = list(input())
  route.append(lst)
  
brock = [['#']*w for i in range(h)]

que = deque([])
dx = [-1,0,1,0]
dy = [0,-1,0,1]

brock[sx][sy] = 0
que.append((sx,sy))



while que:
  
  (p,q) = que.popleft()
  if (p,q) == (gx,gy):
    print(brock[gx][gy])
    sys.exit()
  for i in range(4):
    p2,q2 = p+dx[i],q+dy[i]
    if 0 <= p2 < h and 0<= q2 < w and route[p2][q2] == '.' and (brock[p2][q2] == '#' or brock[p2][q2] > brock[p][q]):
      brock[p2][q2] = brock[p][q]
      que.appendleft((p2,q2))
  
  for j in range(-2,3):
    for k in range(-2,3):
      p3 = p+j
      q3 = q+k
      if 0 <= p3 < h and 0<= q3 < w and route[p3][q3] == '.' and brock[p3][q3] == '#':
        brock[p3][q3] = brock[p][q]+1
        que.append((p3,q3))
        
        
            
                  
              
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
C_h, C_w = map(lambda x:int(x) - 1,input().split())
D_h, D_w = map(lambda x:int(x) - 1,input().split())
S = [input() for _ in range(H)]

waiting = deque()
went = [[10**9]*W for _ in range(H)]
waiting.append([0, C_h, C_w])

ans = -1
while len(waiting) > 0:
    n, cur_h, cur_w = waiting.popleft()
    if cur_h == D_h and cur_w == D_w:
        ans = n
        break
    if went[cur_h][cur_w] > n:
        went[cur_h][cur_w] = n
        for i in range(-2, 3):
            for j in range(-2, 3):
                next_h = cur_h + i
                next_w = cur_w + j
                if 0 <= next_h < H and 0 <= next_w < W:
                    if (i == 0 and j == -1) or (i == 0 and j == 1) or (i == -1 and j == 0) or (i == 1 and j == 0):
                        if went[next_h][next_w] > n and S[next_h][next_w] == '.':
                            waiting.appendleft([n, next_h, next_w])
                    else:
                        if went[next_h][next_w] > n + 1 and S[next_h][next_w] == '.':
                            waiting.append([n + 1, next_h, next_w])

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
INF = float("inf")
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF] * W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        b = dist[x][y]
        if (x, y) == (gx, gy):
            return b
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > b and c[nx][ny] == ".":
                dist[nx][ny] = b
                q.appendleft((nx, ny))
        b += 1
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > b and c[nx][ny] == ".":
                    dist[nx][ny] = b
                    q.append((nx, ny)) 
    return -1

H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
sx, sy, gx, gy = cx - 1, cy - 1, dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
INF = 10**7
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF] * W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        b = dist[x][y]
        if (x, y) == (gx, gy):
            return b
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > b and c[nx][ny] == ".":
                dist[nx][ny] = b
                q.appendleft((nx, ny))
        B = b + 1
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > B and c[nx][ny] == ".":
                    dist[nx][ny] = B
                    q.append((nx, ny)) 
    return -1

H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
sx, sy, gx, gy = cx - 1, cy - 1, dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

graph = [0] + [0] * h
for i in range(h):
    graph[i + 1] = '0' + input().strip()

from collections import deque

def bfs(graph, queue, dist):
    while queue:
        current_h, current_w = queue.popleft()

        for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            next_h, next_w = current_h + dh, current_w + dw
            if not ((1 <= next_h <= h) and (1 <= next_w <= w)):
                continue
            if graph[next_h][next_w] == '#':
                continue
            if dist[next_h][next_w] != -1 and dist[next_h][next_w] <= dist[current_h][current_w]:
                continue
            else:
                dist[next_h][next_w] = dist[current_h][current_w]
                queue.appendleft((next_h, next_w))

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                next_h, next_w = current_h + dh, current_w + dw
                if not ((1 <= next_h <= h) and (1 <= next_w <= w)):
                    continue
                if graph[next_h][next_w] == '#':
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                else:
                    dist[next_h][next_w] = dist[current_h][current_w] + 1
                    queue.append((next_h, next_w))

queue = deque([(ch, cw)])
dist = [-1] + [0] * h
for i in range(h):
    dist[i + 1] = [0] + [-1] * w
dist[ch][cw] = 0
bfs(graph, queue, dist)
print(dist[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
c = list(map(int,input().split()))
d = list(map(int,input().split()))
s = []
for i in range(h):
  s += [input()]
t = [[h*w]*w for i in range(h)]
t[c[0]-1][c[1]-1] = 0
p = deque([[c[0]-1,c[1]-1]])
while p:
  q = p.popleft()
  u = t[q[0]][q[1]]
  for i in range(-2,3):
    if 0 <= q[0]+i and q[0]+i < h:
      for j in range(-2,3):
         if 0 <= q[1]+j and q[1]+j < w:
            if s[q[0]+i][q[1]+j] == ".":
              if abs(i) + abs(j) == 1:
                if t[q[0]+i][q[1]+j] > u:
                  t[q[0]+i][q[1]+j] = u
                  p.appendleft([q[0]+i,q[1]+j])
              else:
                if t[q[0]+i][q[1]+j] > u+1:
                  t[q[0]+i][q[1]+j] = u+1
                  p.append([q[0]+i,q[1]+j])
ans = t[d[0]-1][d[1]-1]
if ans == h*w:
  ans = -1
print(ans)

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.pop()
        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]])