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:
from collections import deque
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="#" else 0 for i in input()] for _ in range(H)]
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh==0 and dw==0:
                    continue
                hh, ww = h+dh, w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                    costs[hh][ww] = costs[h][w]
                    q.appendleft((cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="#" else 0 for i in input()] for _ in range(H)]
    q = deque([(0, (Ch-1, Cw-1))])
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = q.popleft()
        h, w = pos

        for dh, dw in product(range(-2,3), repeat=2):
            if dh==0 and dw==0:
                continue
            hh, ww = h+dh, w+dw
            if not (0<=hh<H and 0<=ww<W):
                continue
            if l[hh][ww]:
                continue
            
            if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                costs[hh][ww] = costs[h][w]
                q.appendleft((cost, (hh, ww)))
            elif costs[hh][ww] > costs[h][w]+1:
                costs[hh][ww] = costs[h][w]+1
                q.append((cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Submission status: Accepted

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

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

@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main(wall, Sx, Sy, Tx, Ty):
    INF = 1 << 30
    H, W = wall.shape
    S = Sx * W + Sy
    T = Tx * W + Ty
    dist = np.full(H * W, INF, np.int64)
    deq = np.empty(2 * H * W + 100, np.int64)
    dist[S] = 0
    deq[H * W], l, r = S, H * W, H * W + 1
    while l < r:
        v, l = deq[l], l + 1
        vx, vy = divmod(v, W)
        # そのままあるく
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            wx, wy = vx + dx, vy + dy
            if not (0 <= wx < H):
                continue
            if not (0 <= wy < W):
                continue
            if wall[wx, wy]:
                continue
            w = wx * W + wy
            if dist[w] <= dist[v]:
                continue
            dist[w] = dist[v]
            deq[l - 1], l = w, l - 1
        # ワープする
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                wx, wy = vx + dx, vy + dy
                if not (0 <= wx < H):
                    continue
                if not (0 <= wy < W):
                    continue
                if wall[wx, wy]:
                    continue
                w = wx * W + wy
                if dist[w] <= dist[v] + 1:
                    continue
                dist[w] = dist[v] + 1
                deq[r], r = w, r + 1
    ans = dist[T]
    if ans == INF:
        ans = -1
    return ans

H, W = map(int, readline().split())
Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'#'

print(main(wall, Sx, Sy, Tx, Ty))

Submission status: Accepted

Solution code:
from collections import deque

INF = 10**6
walk_area=[(1,0), (0,1), (-1,0), (0,-1)]
warp_area=[]
for i in range(-2, 3):
    for j in range(-2, 3):
        warp_area.append((i, j))
    
def walk(a, b, num, S, COST):
    m = S[a][b] 
    if m == '.':
        COST[a][b] = num
        # d.appendleft([a, b])
        return
    else:
        # d.append
        return

def warp(x,y,num, S, COST, d):
    m = S[x][y]
    if m == '.':
        COST[x][y] = num
        d.append([x, y])
        return
    if m == '#':
        return
    S[x][y] = min(num, m)
    return

def main():
    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())
    S = ['#'*(w+4)]
    S.append('#'*(w+4))
    for i in range(h):
        S.append('##'+input()+'##')
    S.append('#'*(w+4))
    S.append('#'*(w+4))
    
    # 各場所までワープ何回で辿り着くか
    COST = [[INF for i in range(w+4)] for j in range(h+4)]
    COST[ch][cw] = 0

    d = deque([[ch,cw,0]])
    d2 = deque()
    while len(d) > 0:
        t = d.popleft()
        d2.append(t)
        x = t[0]
        y = t[1]
        num = t[2] # COST[x][y]
        for dx, dy in walk_area:
            X = x + dx
            Y = y + dy
            if S[X][Y] == '#' or COST[X][Y] <= num:
                continue
        
            COST[X][Y] = num
            d.append([X, Y, num])
        if not d:
            while len(d2) > 0:
                x, y, num = d2.popleft()
                for dx, dy in warp_area:
                    X = x + dx
                    Y = y + dy
                    if S[X][Y] == '#' or COST[X][Y] <= num+1:
                        continue
                    
                    COST[X][Y] = num + 1
                    d.append([X, Y, num + 1])
    # for i in COST:
    #     print(i)
    if COST[dh][dw] == 10**6:
        print(-1)
    else:
        print(COST[dh][dw])
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
ans = 0
seen = [[-1]*W for _ in range(H)]
vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]
v2 = [[1, 1], [-1, 1], [-1, -1], [1, -1], [2, 1], [1, 2], [-1, 2], [2, -1], [-2, 1], [1, -2], [-1, -2], [-2, -1], [2, 0], [0, 2], [-2, 0], [0, -2], [2, 2], [2, -2], [-2, -2], [-2, 2]]
queue = deque()
q = deque()
queue.append([Ch-1, Cw-1])
q.append([Ch-1, Cw-1])
seen[Ch-1][Cw-1]=0

while queue:
    while queue:
        l = queue.popleft()
        q.append(l)
        h, w = l[0], l[1]
        for ll in vec:
            #コースアウト
            if h+ll[0]>=H or h+ll[0]<0 or w+ll[1]>=W or w+ll[1]<0:
                continue
            #障害物
            if S[h+ll[0]][w+ll[1]]=="#":
                continue
            #既視
            if seen[h+ll[0]][w+ll[1]]!=-1:
                continue
            queue.append([h+ll[0], w+ll[1]])
            q.append([h+ll[0], w+ll[1]])
            seen[h+ll[0]][w+ll[1]]=ans
    ans+=1
    
    while q:
        l = q.popleft()
        h, w = l[0], l[1]
        for z in v2:
            #コースアウト
            if h+z[0]>=H or h+z[0]<0 or w+z[1]>=W or w+z[1]<0:
                continue
            #障害物
            if S[h+z[0]][w+z[1]]=="#":
                continue
            #既視
            if seen[h+z[0]][w+z[1]]!=-1:
                continue
            queue.append([h+z[0], w+z[1]])
            seen[h+z[0]][w+z[1]]=ans
print(seen[Dh-1][Dw-1])

Submission status: Accepted

Solution code:
from collections import deque
 
#入力受け取り
H,W=map(int,input().split())
Ch,Cw=[int(x)-1 for x in input().split()]
Dh,Dw=[int(x)-1 for x in input().split()]
maze=[input() for i in range(H)]
 
dirs=[-2,-1,0,1,2] #ワープ移動できる縦横の範囲

#初期化
dist=[[float('inf')]*W for _ in range(H)] #distには各点への到達コストを格納
dist[Ch][Cw]=0
queue=deque()
queue.append((0,Ch,Cw)) #キューには(コスト、x座標、y座標)を追加していく
arrive=False #ゴールに到着すればTrueに変更

while queue:
    k,i,j=queue.popleft()
    if k>dist[i][j]:
        continue
    if i==Dh and j==Dw:
        arrive=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj #移動後の座標(ni,nj)
            if not (0<=ni<H and 0<=nj<W):
                continue
            if maze[ni][nj]=='#': #移動先が壁の中
                continue
            if k<dist[ni][nj]: 
                if abs(di)+abs(dj)==1: #歩行圏内(コスト:0)
                    nk=k
                    dist[ni][nj]=nk
                    queue.appendleft((nk,ni,nj))
                else: #歩行圏外(コスト:1)
                    nk=k+1
                    dist[ni][nj]=nk
                    queue.append((nk,ni,nj))   
if arrive:
    ans=dist[Dh][Dw]
else:
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
#入力受け取り
H,W=map(int,input().split())
Ch,Cw=[int(x)-1 for x in input().split()]
Dh,Dw=[int(x)-1 for x in input().split()]
maze=[input() for i in range(H)]
 
dirs=[-2,-1,0,1,2] #ワープ移動できる縦横の範囲

#初期化
dist=[[float('inf')]*W for _ in range(H)] #distには各点への到達コストを格納
dist[Ch][Cw]=0
dq=deque()
dq.append((0,Ch,Cw)) #キューには(コスト、x座標、y座標)を追加していく
ok=False

while dq:
    k,i,j=dq.popleft()
    if k>dist[i][j]:
        continue
    if i==Dh and j==Dw:
        ok=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj #移動後の座標(ni,nj)
            if not (0<=ni<H and 0<=nj<W):
                continue
            if maze[ni][nj]=='#': #移動先が壁の中
                continue
            if k<dist[ni][nj]: 
                if abs(di)+abs(dj)==1: #歩行圏内(コスト:0)
                    nk=k
                    dist[ni][nj]=nk
                    dq.appendleft((nk,ni,nj))
                else: #歩行圏外(コスト:1)
                    nk=k+1
                    dist[ni][nj]=nk
                    dq.append((nk,ni,nj))   
if ok:
    ans=dist[Dh][Dw]
else:
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
# ワープありなしでそれぞれBFSする

import sys
import itertools
from collections import deque

h, w = map(int, sys.stdin.readline().split())
cy, cx = map(lambda x: int(x)-1, sys.stdin.readline().split())
gy, gx = map(lambda x: int(x)-1, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(h)]

distance = [[10**17 for _ in range(w)] for _ in range(h)]
walk = ((1,0), (0,1), (-1, 0), (0, -1))
warp = list(itertools.product(range(-2, 3), repeat=2))

que = deque()
que.append((cy, cx))
distance[cy][cx] = 0

while que:
    y, x = que.popleft()

    # ワープなしでBFS
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (graph[ny][nx] == '.') and (distance[ny][nx] > distance[y][x]):
            distance[ny][nx] = distance[y][x]
            que.appendleft((ny, nx))

    # ワープ使用でBFS
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if (nx < 0) or (nx > w-1) or (ny < 0) or (ny > h-1): continue
        if (graph[ny][nx] == '.') and (distance[ny][nx] > distance[y][x]+1):
            distance[ny][nx] = distance[y][x]+1
            que.append((ny, nx))

print(distance[gy][gx] if distance[gy][gx] != 10**17 else -1)

Submission status: Accepted

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()

inf=1<<20
def dijkstra(edge,st):
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    q=[(0,st)]
    heapify(q)
    v=[False]*n
    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
                heappush(q,(alt,dst))
    return d

# Under construction
# To be verified by https://atcoder.jp/contests/abc176/tasks/abc176_d

class GridGraph:
    def __init__(self,h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
        self.h=h+2
        self.w=w+2
        self.n=self.h*self.w
        self.edge=[[]for i in range(self.n)]
        self.nb=[-1,1,-self.w,self.w]
        #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
        self.mp=[boundary]*self.w
        self.found={}
        for i in range(self.h-2):
            s=input()
            self.mp+=[boundary]
            for i in range(self.w-2):
                char=s[i]
                if search and char in search:
                    self.found[char]=((i+1)*self.w+i+1)
                    mp_def[char]=mp_def[replacement_of_found]
                self.mp+=[mp_def[char]]
            self.mp+=[boundary]
        self.mp+=[boundary]*self.w
        self.h,self.w,self.mp,self.found
        return

    def create_edge(self,cost_func=lambda x,y:1):
        w=self.w
        nbw=[2,2*w+1,2*w+2,w+1,w+2,+2*w,2*w-1,2*w-2,w-1,w-2]
        for i in range(self.n):
            if self.mp[i]==1:
                continue
            for di in self.nb:
                nx=i+di
                if self.mp[nx]!=1:
                    #self.edge[i].append((nx,cost_func(self.mp[i],self.mp[nx])))
                    self.edge[i].append((nx,0))
            
            for di in nbw:
                nx=i+di
                if 0<=nx<self.n and self.mp[nx]!=1:
                    self.edge[i].append((nx,1))
                    self.edge[nx].append((i,1))
            
        return self.edge


    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v

    def __str__(self):
        for i in range(self.h):
            print(self.mp[i*self.w:(i+1)*self.w])
        return ''
 
    def show_map(self,length=2):
        for i in range(self.h):
            print(*[' '*(length-(len(str(j))))+str(j) for j in self.mp[i*self.w:(i+1)*self.w]])

    def show_node_num(self,length=2):
        for i in range(self.h):
            print(*[' '*(length-(len(str(j))))+str(j) for j in range(i*self.w,(i+1)*self.w)])

    def show_map_w_node_num(self,length=2):
        for i in range(self.h):
            print(*[[' '*(length-(len(str(j))))+str(j),self.mp[j]] for j in range(i*self.w,(i+1)*self.w)])
    
    def show_edge(self,length=2):
        for i in range(self.h):
            print(*[[' '*(length-(len(str(j))))+str(j),self.edge[j]] for j in range(i*self.w,(i+1)*self.w)])


    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

show_flg=False
show_flg=True

ans=0

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

gg=GridGraph(h,w)
gg.create_edge()
d=dijkstra(gg.edge,sh*gg.w+sw)
ans=d[gh*gg.w+gw]
if ans==inf:
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
#入力受け取り
H,W=map(int,input().split())
Ch,Cw=[int(x)-1 for x in input().split()]
Dh,Dw=[int(x)-1 for x in input().split()]
maze=[input() for i in range(H)]
 
dirs=[-2,-1,0,1,2] #ワープ移動できる縦横の範囲
#初期化
dist=[[float('inf')]*W for _ in range(H)] #distには各点への到達コストを格納
dist[Ch][Cw]=0
dq=deque()
dq.append((0,Ch,Cw)) #キューには(コスト、x座標、y座標)を追加していく
ok=False

while dq:
    k,i,j=dq.popleft()
    if k>dist[i][j]:
        continue
    if i==Dh and j==Dw:
        ok=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj #移動後の座標(ni,nj)
            if not (0<=ni<H and 0<=nj<W):
                continue
            if maze[ni][nj]=='#': #移動先が壁の中
                continue
            if abs(di)+abs(dj)==1: #歩行圏内(コスト:0)
                append=dq.appendleft
                nk=k
            else: #歩行圏外(コスト:1)
                append=dq.append
                nk=k+1
            if k>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            append((nk,ni,nj))      
if ok:
    ans=dist[Dh][Dw]
else:
    ans=-1
print(ans)

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())
ch-=1
cw-=1
dh-=1
dw-=1

maze=[list(input()) for i in range(h)]

Q=deque()
Q.append((ch,cw,0))

dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,-2,-2,-2,-2,-2,1,1,1,1,-1,-1,-1,-1,0,0]
ddy=[-2,-1,0,1,2,-2,-1,0,1,2,2,1,-1,-2,2,1,-1,-2,2,-2]

dp=[[float('inf')]*w for i in range(h)]


while Q:
  p=Q.popleft()
  if p[0]==dh and p[1]==dw:
    print(p[2])
    exit()
  
  for i in range(4):
    nx=p[0]+dx[i]
    ny=p[1]+dy[i]

    if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and p[2]<dp[nx][ny]:
      Q.appendleft((nx,ny,p[2]))
      dp[nx][ny]=p[2]

  for j in range(20):
    nnx=p[0]+ddx[j]
    nny=p[1]+ddy[j]

    if 0<=nnx<h and 0<=nny<w and maze[nnx][nny]=='.' and p[2]+1<dp[nnx][nny]:
      Q.append((nnx,nny,p[2]+1))
      dp[nnx][nny]=p[2]+1


print(-1)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product


def main():
    h, w = map(int, input().split())
    c = tuple(map(lambda x: int(x)+1, input().split()))
    d = tuple(map(lambda x: int(x)+1, input().split()))
    s = ['#'*(w+4)]*2 + [f'##{input()}##' for _ in range(h)] + ['#'*(w+4)]*2

    move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
    move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

    cost = [[float('inf')] * (w+4) for _ in range(h+4)]
    cost[c[0]][c[1]] = 0
    yet = deque([(c[0], c[1], 0)])
    done = deque()

    while yet:
        y, x, m = yet.popleft()
        done.append((y, x, m))
        # Move A
        for dx, dy in move_a_area:
            hh, ww = y + dy, x + dx
            if s[hh][ww] == '#' or cost[hh][ww] <= m:
                continue
            cost[hh][ww] = m
            yet.append((hh, ww, m))
        # Move B
        if not yet:
            while done:
                y, x, m = done.popleft()
                for dx, dy in move_b_area:
                    hh, ww = y + dy, x + dx
                    if s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
                        continue
                    cost[hh][ww] = m + 1
                    yet.append((hh, ww, m + 1))

    print(v if (v := cost[d[0]][d[1]]) < float('inf') else -1)


if __name__ == '__main__':
    main()

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())

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

S = [input() for i in range(h)]

walk = [(-1, 0), (0, 1), (1, 0), (0, -1)]
warp = [(y, x) for y in range(-2, 3) for x in range(-2, 3)]

q = deque()
q.append((ch, cw))

dist = [[10**7] * w for _ in range(h)]
dist[ch][cw] = 0

while q:
    y, x = q.popleft()
    if [y, x] == [dh, dw]:
        break

    for dy, dx in walk:
        if 0 <= y+dy < h and 0 <= x+dx < w:
            if S[y+dy][x+dx] == '.':
                if dist[y][x] < dist[y+dy][x+dx]:
                    dist[y + dy][x + dx] = dist[y][x]
                    q.appendleft((y+dy, x+dx))

    for dy, dx in warp:
        if 0 <= y+dy < h and 0 <= x+dx < w:
            if S[y+dy][x+dx] == '.':
                if dist[y][x]+1 < dist[y+dy][x+dx]:
                    dist[y + dy][x + dx] = dist[y][x]+1
                    q.append((y+dy, x+dx))

print(dist[dh][dw] if dist[dh][dw] != 10**7 else -1)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)

Submission status: Accepted

Solution code:
from collections import deque

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

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Submission status: Accepted

Solution code:
import heapq
def main():
    h, w = map(int, input().split())
    strt_y, strt_x = map(int, input().split())
    goal_y, goal_x = map(int, input().split())
    stage = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == ".":
                stage[i+2][j+2] = float("inf")
    strt_y += 1
    strt_x += 1
    goal_y += 1
    goal_x += 1
    hq = [[0, strt_y, strt_x]]
    stage[strt_y][strt_x] = 0
    while len(hq) > 0:
        pt, crr_y, crr_x = heapq.heappop(hq)
        if stage[crr_y][crr_x] < pt:
            continue
        if crr_y == goal_y and crr_x == goal_x:
            break
        for i in range(crr_y-2, crr_y+2+1):
            for j in range(crr_x-2, crr_x+2+1):
                if abs(crr_y-i) + abs(crr_x-j) == 1:
                    if pt < stage[i][j]:
                        stage[i][j] = pt
                        heapq.heappush(hq, [pt, i, j])
                else:
                    if pt+1 < stage[i][j]:
                        stage[i][j] = pt+1
                        heapq.heappush(hq, [pt+1, i, j])
    if stage[goal_y][goal_x] == float("inf"):
        print(-1)
    else:
        print(stage[goal_y][goal_x])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh, dw = map(int, input().split())
dh -= 1
dw -= 1
s = [input() for _ in range(h)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dxw = [-2, -1, 0, 1, 2, -2, -1, 0, 1, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1, 0, 1, 2]
dyw = [-2, -2, -2, -2, -2, -1, -1, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

q = deque()
q.append((ch, cw, 0))
ans = [[10 ** 9] * w for _ in range(h)]
while len(q) > 0:
    x, y, c = q.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if (
            nx >= 0
            and nx < h
            and ny >= 0
            and ny < w
            and c < ans[nx][ny]
            and s[nx][ny] == "."
        ):
            q.appendleft((nx, ny, c))
            ans[nx][ny] = c
    for i in range(24):
        nx, ny = x + dxw[i], y + dyw[i]
        if (
            nx >= 0
            and nx < h
            and ny >= 0
            and ny < w
            and c + 1 < ans[nx][ny]
            and s[nx][ny] == "."
        ):
            q.append((nx, ny, c + 1))
            ans[nx][ny] = c + 1
v = ans[dh][dw]
print(-1 if v == 10 ** 9 else v)

Submission status: Accepted

Solution code:
# Fast IO (be careful about bytestring)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from collections import deque

movable = 46
blocked = 35
MAXDist = 1 << 31

def isMovable(p,q):
    if p < 0 or q < 0 or p >= H or q >= W:
        return False
    if maze[p][q] == blocked:
        return False
    return True

H,W = map(int,input().split())
sH,sW = map(int,input().split())
eH,eW = map(int,input().split())

maze = []
distance = []
for _ in range(H):
    maze.append(input())
    distance.append([MAXDist] * W)

distance[sH - 1][sW - 1] = 0
deq = deque()
deq.append((sH - 1, sW - 1, 0))

while len(deq):
    h,w,dist = deq.popleft()
    if dist > distance[h][w]:
        continue
    # no spell movement
    if isMovable(h - 1,w) and distance[h-1][w] > dist:
        distance[h-1][w] = dist
        deq.appendleft((h-1,w,dist))
    if isMovable(h + 1,w) and distance[h+1][w] > dist:
        distance[h + 1][w] = dist
        deq.appendleft((h + 1,w,dist))
    if isMovable(h,w - 1) and distance[h][w - 1] > dist:
        distance[h][w - 1] = dist
        deq.appendleft((h,w - 1,dist))
    if isMovable(h,w + 1) and distance[h][w + 1] > dist:
        distance[h][w + 1] = dist
        deq.appendleft((h,w + 1,dist))

    # spell movement
    for i in range(h - 2,h + 3):
        for j in range(w - 2, w + 3):
            if isMovable(i,j) and distance[i][j] > dist + 1:
                distance[i][j] = dist + 1
                deq.append((i,j,dist + 1))

print(distance[eH - 1][eW - 1] if distance[eH - 1][eW - 1] != MAXDist else -1)