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

def input():
    return sys.stdin.readline().strip()

def main():
    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)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.appendleft((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.appendleft((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]
    V = [[-1]*W for i in range(H)]  # 頂点i
    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy][sx] = v
        que.append((sy, sx))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h][next_w] != -1:
                    continue
                if A[next_h][next_w] == '#':
                    continue
                V[next_h][next_w] = v
                que.append((next_h, next_w))

    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" or V[h][w] != -1:
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))

    # for h in range(H):
    #     print(V[h])

    # for i in range(vertex):
    #     print(G[i])

    s = V[Ch][Cw]
    g = V[Dh][Dw]
    que = deque([0])

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)

    print(dist[g])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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
map = [list(input()) for i in range(H)]
cost_map = [[10**6]*W for i in range(H)]
d = deque()
cost_map[sx][sy] = 0
d.append([sx, sy])
while d:
    cx, cy = d.pop()
    if cx==gx and cy==gy:
        break
    ccost = cost_map[cx][cy]
    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and ccost < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost
                d.append([nx, ny])
    dxy = [[-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]]
    for dx, dy in dxy:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and (ccost + 1) < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost + 1
                d.appendleft([nx, ny])
if cost_map[gx][gy] == 10**6:
    print("-1")
else:
    print(int(cost_map[gx][gy]))

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict

sys.setrecursionlimit(10000)

H, W = map(int, input().split())
C = tuple(map(int, input().split()))
D = tuple(map(int, input().split()))
S = [list(input()) for _ in range(H)]

d = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def dfs(h, w, i):
    S[h][w] = i

    for dh, dw in d:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if S[nh][nw] != '.':
            continue
        dfs(nh, nw, i)


# 領域毎に番号を振る
count = 1
for h in range(H):
    for w in range(W):
        if S[h][w] != '.':
            continue
        dfs(h, w, count)
        count += 1

# 各領域をノードとしてグラフを構築
graph = defaultdict(set)
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = h + dh
                nw = w + dw
                if nh < 0 or nh >= H or nw < 0 or nw >= W:
                    continue
                if S[nh][nw] == '#':
                    continue
                graph[S[h][w]].add(S[nh][nw])

start = S[C[0]-1][C[1]-1]
goal = S[D[0]-1][D[1]-1]


def shortest_dist(graph, start, goal):
    queue = deque([start])
    visited = set()
    visited.add(start)
    dist = defaultdict(int)
    dist[start] = 0
    while queue:
        current_vertex = queue.popleft()
        if current_vertex == goal:
            return dist[goal]
        for v in graph[current_vertex]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
                dist[v] = dist[current_vertex] + 1
    return -1

# 最短距離を求める
ans = shortest_dist(graph, start, goal)

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


def main():
	H, W = MAP()
	Ch, Cw = MAP()
	Dh, Dw = MAP()
	S = [input() for _ in range(H)]

	cnt = [[INF]*W for _ in range(H)]
	cnt[Ch-1][Cw-1] = 0

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

	q = deque([(Ch-1, Cw-1, 0)])
	while q:
		y, x, c = q.popleft()
		if cnt[y][x] != c:
			continue
		flg = True
		for i in range(24):
			if i == 4 and flg:
				break
			ny = y + dy[i]
			nx = x + dx[i]
			if ny < 0 or nx < 0 or H <= ny or W <= nx:
				continue
			elif i < 4:
				if S[ny][nx] == "." and c < cnt[ny][nx]:
					cnt[ny][nx] = c
					q.appendleft((ny, nx, c))
				elif S[ny][nx] == "#":
					flg = False
			elif 4 <= i and S[ny][nx] == "." and c+1 < cnt[ny][nx]:
				cnt[ny][nx] = c+1
				q.append((ny, nx, c+1))


	if cnt[Dh-1][Dw-1] == INF:
		print(-1)
	else:
		print(cnt[Dh-1][Dw-1])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
S = [input() for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in d:
        ny, nx = y+h, x+w
        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and worp < worps[ny][nx]:
            worps[ny][nx] = worp
            q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h < H and 0 <= w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.append([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def solve():
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]

    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Sss = ['#'*(W+4)] + ['#'*(W+4)] + ['##'+input().rstrip()+'##' for _ in range(H)] + ['#'*(W+4)] + ['#'*(W+4)]

    Ch, Cw, Dh, Dw = Ch+1, Cw+1, Dh+1, Dw+1

    usedss = [[0]*(W+4) for _ in range(H+4)]
    for x in range(H+4):
        for y in range(W+4):
            if Sss[x][y] == '#':
                usedss[x][y] = 1

    ans = 0
    vs = set([(Ch, Cw)])
    vNews = set([(Ch, Cw)])
    usedss[Ch][Cw] = 1
    while True:
        while vs:
            v2s = set()
            for x, y in vs:
                for dx, dy in dxys:
                    x2, y2 = x+dx, y+dy
                    if usedss[x2][y2]: continue
                    v2s.add((x2, y2))
                    vNews.add((x2, y2))
                    usedss[x2][y2] = 1
            vs = v2s

        if usedss[Dh][Dw]:
            print(ans)
            break

        if not vNews:
            print(-1)
            break

        vs = set()
        for x, y in vNews:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    x2, y2 = x+dx, y+dy
                    if usedss[x2][y2]: continue
                    vs.add((x2, y2))
                    usedss[x2][y2] = 1

        ans += 1
        vNews = set(vs)


solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    S = [input().strip("\n") for _ in range(H)]

    q = deque()
    P = [[-1 for _ in range(W)] for h in range(H)]
    q.append((0, sh, sw))
    while q:
        d, h, w = q.popleft()
        if P[h][w] == -1:
            P[h][w] = d
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and P[h+dh][w+dw] == -1:
                        if abs(dh) + abs(dw) == 1:
                            q.appendleft((d, h+dh, w+dw))
                        else:
                            q.append((d+1, h+dh, w+dw))
    print(P[fh][fw])
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import heapq
import math
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())

tobool = lambda s: s == "#"

S = [
  list(map(tobool, input())) for _ in range(H)
]
visited_m = [[False for w in range(W) ] for h in range(H)]
cost_m = [[math.inf for w in range(W) ] for h in range(H)]

def enum_moveA(Ch, Cw):
  return [(Ch-1, Cw), (Ch+1, Cw), (Ch, Cw-1), (Ch, Cw+1)]

def enum_moveB(Ch, Cw):
  return [
    (Ch-2, Cw-2), (Ch-2, Cw-1), (Ch-2, Cw), (Ch-2, Cw+1), (Ch-2, Cw+2),
    (Ch-1, Cw-2), (Ch-1, Cw-1), (Ch-1, Cw+1), (Ch-1, Cw+2),
    (Ch, Cw-2), (Ch, Cw+2),
    (Ch+1, Cw-2), (Ch+1, Cw-1), (Ch+1, Cw+1), (Ch+1, Cw+2),
    (Ch+2, Cw-2), (Ch+2, Cw-1), (Ch+2, Cw), (Ch+2, Cw+1), (Ch+2, Cw+2),
  ]

d = deque()
d.appendleft((0, Ch, Cw))
while True:
  if len(d) == 0:
    break
  visited_m[Ch][Cw] = True
  c_cost, Ch, Cw = d.popleft()
  if Ch == Dh and Cw == Dw:
    break
  for h, w in enum_moveA(Ch, Cw):
    if 0 <= h <H and 0 <= w <W:
      tmp_cost = cost_m[h][w]
      visited = visited_m[h][w]
      kabe = S[h][w]
      if c_cost + 0 < tmp_cost and not visited and not kabe:
        cost_m[h][w] = c_cost + 0
        d.appendleft((c_cost + 0, h, w))
        
  for h, w in enum_moveB(Ch, Cw):
    if 0 <= h <H and 0 <= w <W:
      tmp_cost = cost_m[h][w]
      visited = visited_m[h][w]
      kabe = S[h][w]
      if c_cost + 1 < tmp_cost and not visited and not kabe:
        cost_m[h][w] = c_cost + 1
        d.append((c_cost + 1, h, w))
    
total_cost = cost_m[Dh][Dw]
if total_cost < math.inf:
  print(total_cost)
else:
  print(-1)

Submission status: Accepted

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


h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict, deque

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0

q = deque([(0, start)]) # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = q.popleft()
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            if vv==0:
                q.appendleft((num, u))
            else:
                q.append((num,u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def main():
    H, W = mapint()
    ch, cw = mapint()
    dh, dw = mapint()
    maze = [list(input()) for _ in range(H)]
    
    dirc = ((-1, 0), (1, 0), (0, -1), (0, 1))
    magic = ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2))
    from collections import deque
    Q = deque([(ch-1, cw-1)])
    
    dist = [[10**18]*W for _ in range(H)]
    dist[ch-1][cw-1] = 0
    while Q:
        y, x = Q.popleft()
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]:
                dist[ny][nx] = dist[y][x]
                Q.appendleft((ny, nx))
        
        for dy, dx in magic:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.append((ny, nx))
    if dist[dh-1][dw-1]>=10**17:
        print(-1)
    else:
        print(dist[dh-1][dw-1])
main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**7)
H,W=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

sx,sy=sx-1,sy-1
gx,gy=gx-1,gy-1

maze=[[i for i in input()] for _ in range(H)]

visited = [[-1]*W for _ in range(H)]
queue = deque([])
queue.append((sx,sy))
visited[sy][sx] = 0
def bfs(v,queue,gx,gy,maze):
    check=deque([])



    while len(queue) != 0:
        n = queue.popleft()
        x,y = n[0], n[1]
        flag=0

        if n == (gx,gy):
            print(v)
            exit()

        for i, j in [(1,0), (0,1), (-1,0), (0,-1)]:
            if (x+i < 0) or (x+i >=W) or (y+j < 0) or (y+j >=H):
                continue
            if maze[y+j][x+i] == '.' and visited[y+j][x+i] == -1:
                queue.append((x+i,y+j))
                visited[y+j][x+i] = v
            elif maze[y+j][x+i] == '#':
                flag=1
        if flag==1:
            check.append((x,y))

    while len(check) != 0:
        n=check.popleft()
        x,y=n[0],n[1]
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i < 0) or (x+i >=W) or (y+j < 0) or (y+j >=H):
                    continue
                if maze[y+j][x+i] == '.' and visited[y+j][x+i] == -1:
                    queue.append((x+i,y+j))
                    visited[y+j][x+i] = v+1

    if len(queue)!=0:
        bfs(v+1,queue,gx,gy,maze)



bfs(0,queue,gx,gy,maze)
print(-1)

Submission status: Accepted

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


h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from queue import deque 
q = deque([(0, start)]) # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = q.popleft()
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            if vv==0:
                q.appendleft((num, u))
            else:
                q.append((num,u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

Submission status: Accepted

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


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "#":
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S, INF=10**7):
    DIR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    # 島を作る
    id = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == -1:
                id += 1
                S[i][j] = id
                q = deque()
                q.append((i, j))
                while q:
                    y, x = q.popleft()
                    for dy, dx in DIR:
                        ny, nx = y+dy, x+dx
                        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                            S[ny][nx] = id
                            q.append((ny, nx))

    start_id = S[CH-1][CW-1]
    goal_id = S[DH-1][DW-1]
    if start_id == goal_id:
        return 0

    # id: 島の数
    N = id
    G = [dict() for i in range(N)]

    # 島を連結する
    for i in range(H):
        for j in range(W):
            source_id = S[i][j]
            if source_id > 0:
                for k in range(i-2, i+3):
                    for l in range(j-2, j+3):
                        if 0 <= k < H and 0 <= l < W:
                            target_id = S[k][l]
                            if target_id > 0 and source_id != target_id:
                                G[source_id-1][target_id-1] = 1
                                G[target_id-1][source_id-1] = 1
    
    visited = [-1 for i in range(N)]
    q = deque()
    visited[start_id-1] = 0
    q.append(start_id-1)
    while q:
        u = q.popleft()
        if u == goal_id-1:
            break
        for v in G[u].keys():
            if visited[v] == -1:
                visited[v] = visited[u] + 1
                q.append(v)
    return visited[goal_id-1]


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

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
field = [["#"] * (w + 4)] + \
        [["#"] * (w + 4)] + \
        [list("##" + input() + "##") for i in range(h)] + \
        [["#"] * (w + 4)] + \
        [["#"] * (w + 4)]
sy += 1
sx += 1
gy += 1
gx += 1          
          
dxy1 = [(0,1), (0,-1), (1,0), (-1,0)]
dxy2 = [(1,1), (1,-1), (-1,1), (-1,-1), \
        (-2,-2), (-1,-2), (0,-2), (1,-2), (2,-2), \
        (-2,-1), (2,-1), (-2,0), (2,0), (-2,1), (2,1), \
        (-2,2), (-1,2), (0,2), (1,2), (2,2)]


goal = False
INF = 10**9
cnt = [[INF]*(w+4) for i in range(h+4)]

q = deque()
q.append([sy, sx])
cnt[sy][sx] = 0

while goal == False and q:
    y, x = q.pop()
    now = cnt[y][x]
    flg = False
    for dy, dx in dxy1:
        ny, nx = y + dy, x + dx
        if ny == gy and nx == gx:
            cnt[ny][nx] = now
            goal = True
            flg = True
            break
        if field[ny][nx] == '#':
            continue
        if field[ny][nx] == '.' and cnt[ny][nx] > now:
            q.append([ny, nx])
            cnt[ny][nx] = now
            flg = True
    if goal:
        break
    for dy, dx in dxy2:
        ny, nx = y + dy, x + dx
        if field[ny][nx] == '#':
            continue
        if field[ny][nx] == '.' and cnt[ny][nx] > now + 1:
            q.appendleft([ny, nx])
            cnt[ny][nx] = now + 1
print(cnt[gy][gx]) if cnt[gy][gx] < INF else print(-1)

Submission status: Accepted

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

mod = 10**9+7

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


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

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

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

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


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


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

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

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

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

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

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    di, dj = D
    dist[di][dj] = 0
    q = deque([(di, dj, 0)])
    while q:
        i, j, d = q.popleft()
        if d > dist[i][j]: continue
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.appendleft((ni, nj, d))
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    if dni[nj] > d + 1:
                        dni[nj] = d + 1
                        q.append((ni, nj, d + 1))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    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().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

    warp = [[-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]]

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.appendleft((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc + 1:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()