Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

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().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 0), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 0), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (0, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (0, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    if (i, j) in used:
        continue
    used.add((i, j))

    if D[i][j] > d:
        D[i][j] = d
    else:
        continue

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            if S[_i][_j] == '.':
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Submission status: Wrong Answer

Solution code:
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

start = (Ch, Cw)
goal = (Dh, Dw)

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

counter = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      counter[k][j] = 1000

counter[Ch][Cw] = 0

#print(counter)
#print(S)

now = [start]
for item in now:
  x = item[0]
  y = item[1]
  counter[x][y] = 0
  if counter[x+1][y] == 1000:
    now.append((x+1, y))
  if counter[x][y+1] == 1000:
    now.append((x, y+1))
  if counter[x-1][y] == 1000:
    now.append((x-1, y))
  if counter[x][y-1] == 1000:
    now.append((x, y-1))

#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 1000:
  if len(now) == 0:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    x = item[0]
    y = item[1]
    if counter[x+2][y+2] == 1000:
      counter[x+2][y+2] = ans
      nextlist.append((x+2, y+2))
    if counter[x+2][y+1] == 1000:
      counter[x+2][y+1] = ans
      nextlist.append((x+2, y+1))
    if counter[x+2][y] == 1000:
      counter[x+2][y] = ans
      nextlist.append((x+2, y))
    if counter[x+2][y-1] == 1000:
      counter[x+2][y-1] = ans
      nextlist.append((x+2, y-1))
    if counter[x+2][y-2] == 1000:
      counter[x+2][y-2] = ans
      nextlist.append((x+2, y-2))
    if counter[x+1][y+2] == 1000:
      counter[x+1][y+2] = ans
      nextlist.append((x+1, y+2))
    if counter[x+1][y-2] == 1000:
      counter[x+1][y-2] = ans
      nextlist.append((x+1, y-2))
    if counter[x][y+2] == 1000:
      counter[x][y+2] = ans
      nextlist.append((x, y+2))
    if counter[x][y-2] == 1000:
      counter[x][y-2] = ans
      nextlist.append((x, y-2))
    if counter[x-2][y+2] == 1000:
      counter[x-2][y+2] = ans
      nextlist.append((x-2, y+2))
    if counter[x-2][y+1] == 1000:
      counter[x-2][y+1] = ans
      nextlist.append((x-2, y+1))
    if counter[x-2][y] == 1000:
      counter[x-2][y] = ans
      nextlist.append((x-2, y))
    if counter[x-2][y-1] == 1000:
      counter[x-2][y-1] = ans
      nextlist.append((x-2, y-1))
    if counter[x-2][y-2] == 1000:
      counter[x-2][y-2] = ans
      nextlist.append((x-2, y-2))
    if counter[x-1][y+2] == 1000:
      counter[x-1][y+2] = ans
      nextlist.append((x-1, y+2))
    if counter[x-1][y-2] == 1000:
      counter[x-1][y-2] = ans
      nextlist.append((x-1, y-2))
  now = nextlist  
  for item in now:
    x = item[0]
    y = item[1]
    counter[x][y] = ans
    if counter[x+1][y] == 1000:
      now.append((x+1, y))
    if counter[x][y+1] == 1000:
      now.append((x, y+1))
    if counter[x-1][y] == 1000:
      now.append((x-1, y))
    if counter[x][y-1] == 1000:
      now.append((x, y-1))
  
print(ans)

Submission status: Wrong Answer

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 = []
for i in range(H):
    s = input()
    S.append(s)

que = deque()
que.append((Ch-1, Cw-1))
checked = set()
d = {}
d[((Ch-1, Cw-1))] = 0

def check(h, w, dis, c):
    if h < 0 or h >= H or w < 0 or w >= W:
        return
    if dis == 1:
        if S[h][w] == ".":
            if (h,w) in d:
                d[(h, w)] = min(d[(h,w)], c)
            else:
                d[(h, w)] = c
                que.append((h,w))
    else:
        if S[h][w] == ".":
            if (h,w) in d:
                d[(h, w)] = min(d[(h,w)], c+1)
            else:
                d[(h, w)] = c+1
                que.append((h,w))
    

while que:
    h, w = que.popleft()
    c = d[(h,w)]
    for i in range(-2, 3):
        for j in range(-2, 3):
            check(h+i, w+j, abs(i)+abs(j), c)
if (Dh-1, Dw-1) in d:
    print(d[(Dh-1, Dw-1)])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
cmd = [[-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())
Map = [["#"]*(W+2)]
for _ in range(H):
    Map.append(["#"]+list(input())[:-1] + ["#"])
Map.append(["#"]*(W+2))
Q = deque([[ch,cw]])
Next = deque([])
visidat = [[10**6]*(W+2) for _ in range(H+2)]
num = 0
flag = 0
visidat[ch][cw] = 0
while flag == 0:
    while len(Q) != 0:
        h,w = Q.popleft()
        if h == dh and w == dw:
            print(num)
            flag = 1
            break
        for i in range(-2,3):
            for j in range(-2,3):
                p,q = h+i,w+j
                if p < 0 or q < 0 or p > H+1 or q > W+1 or ((abs(i)+abs(j))<=1):
                    continue
                if Map[p][q] == ".":
                    Next.append([p,q])
                    if visidat[p][q] > num + 1:
                        visidat[p][q] = num + 1
        for cx,cy in cmd:
            newh = cy + h
            neww = cx + w
            if Map[newh][neww] == "#":
                continue
            else:
                if visidat[newh][neww] > num :
                    visidat[newh][neww] = visidat[h][w]
                    Q.append([newh,neww])
    Q = Next
    if len(Q) == 0:
        print(-1)
        flag == 1
        break
    Next = deque([])
    num += 1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import heapq

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**5] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    d2 = (
        (-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),
    )
    hp = []

    heapq.heappush(hp, (0, (cx, cy)))
    c[cx][cy] = 0

    while hp:
        cp, (
            x,
            y,
        ) = heapq.heappop(hp)
        if (x, y) == (dx, dy):
            c[x][y] = min(cp, c[x][y])
            continue
        for i in range(4):
            nx = x + d[i][0]
            ny = y + d[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                heapq.heappush(hp, (cp, (nx, ny)))
                c[nx][ny] = cp
        cp += 1
        for i in range(20):
            nx = x + d2[i][0]
            ny = y + d2[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                c[nx][ny] = cp
                heapq.heappush(hp, (cp, (nx, ny)))

    return c[dx][dy] if c[dx][dy] < 10**5 else -1


print(bfs())

Submission status: Wrong Answer

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

H,W=map(int,input().split())
C=list(map(int,input().split()))
C[0]+=4
C[1]+=4
D=list(map(int,input().split()))
D[0]+=4
D[1]+=4
L=[]
l=["#" for i in range(W+10)]
for i in range(5):
    L.append(l)
for i in range(H):
    S=["#"]*5+list(input())+["#"]*5
    L.append(S)
for i in range(5):
    L.append(l)
#print(L)

A=[[10**20 for i in range(W+10)]for j in range(H+10)]

A[C[0]][C[1]]=0
#print(A)
Q=[]
import heapq
heapq.heapify(Q)

X=[1,-1,0,0]
Y=[0,0,1,-1]
for xy in range(4):
    if L[C[0]+X[xy]][C[1]+Y[xy]]==".":
        Q.append((A[C[0]][C[1]],C[0]+X[xy],C[1]+Y[xy]))
for h in range(-2,3):
    for w in range(-2,3):
        if L[C[0]+h][C[1]+w]=="." and A[C[0]+h][C[1]+w]==10**20:
            Q.append((A[C[0]][C[1]]+10**9,C[0]+h,C[1]+w))
#print(Q)
for i in range(10**7):
    if len(Q)==0:
        break
    d,H,W=heapq.heappop(Q)
    if A[H][W]==10**20:
        A[H][W]=d
        for xy in range(4):
            if L[H+X[xy]][W+Y[xy]]=="." and A[H+X[xy]][W+Y[xy]]==10**20:
                Q.append((d,H+X[xy],W+Y[xy]))
        for h in range(-2,3):
            for w in range(-2,3):
                if L[H+h][W+w]=="." and A[H+h][W+w]==10**20:
                    Q.append((d+10**9,H+h,W+w))
#print(A)
if A[D[0]][D[1]]==10**20:
    print(-1)
else:
    print(A[D[0]][D[1]]//(10**9))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[10**10 for _ in range(w)] for _ in range(h)]
dp[ch-1][cw-1] = 0
now = 0
visited = [[0 for _ in range(w)] for _ in range(h)]

import queue
next = queue.Queue()
next.put([ch-1, cw-1, now])

while not next.empty():
    i, j, now = next.get()
    now = dp[i][j]
    visited[i][j] = 1
    if i != 0:
        if s[i-1][j] == "." and dp[i-1][j] > now:
            dp[i-1][j] = now
        if visited[i-1][j] == 0:
            next.put([i-1, j, now])
            visited[i-1][j] = 1

    if j != 0:
        if s[i][j-1] == "." and dp[i][j-1] > now:
            dp[i][j-1] = now
        if visited[i][j-1] == 0:
            next.put([i, j-1, now])
            visited[i][j-1] = 1

    if i+1 < h:
        if s[i+1][j] == "." and dp[i+1][j] > now:
            dp[i+1][j] = now
        if visited[i+1][j] == 0:
            next.put([i+1, j, now])
            visited[i+1][j] = 1

    if j+1 < w:
        if s[i][j+1] == "."and dp[i][j+1] > now:
            dp[i][j+1] = now
        if visited[i][j+1] == 0:
            next.put([i, j+1, now])
            visited[i][j+1] = 1

    for k in range(i-2, i+3):
        for l in range(j-2, j+3):
            if 0 <= k < h and 0 <= l < w:
                if s[k][l] == "." and dp[k][l] > now+1:
                    dp[k][l] = now+1

ans = dp[dh-1][dw-1]
if ans == 10**10:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
cy, cx = map(lambda x:int(x)-1, input().split())
gy, gx = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(h)]
seen = [[-1]*w for _ in range(h)]
seen[cy][cx] = 0
def f(sy, sx):
    G = []
    que = []
    que.append((sy, sx))
    while que:
        y, x = que.pop()
        G.append((y, x))
        for dy, dx in ((-1,0),(0,-1),(1,0),(0,1)):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if seen[ny][nx] != -1:
                    continue
                if S[ny][nx] == "#":
                    continue
                seen[ny][nx] = seen[y][x]
                que.append((ny, nx))
    return G
L = [(cy, cx)]
while L:
    cy, cx = L.pop()
    G = f(cy, cx)
    if seen[gy][gx] != -1:
        print(seen[gy][gx])
        exit()
    for y, x in G:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny, nx = y+dy, x+dx
                if 0 <= ny < h and 0 <= nx < w:
                    if seen[ny][nx] != -1:
                        continue
                    if S[ny][nx] == "#":
                        continue
                    seen[ny][nx] = seen[y][x]+1
                    L.append((ny, nx))
print(-1)

Submission status: Wrong Answer

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


h,w=mdata()
ch,cw=mdata()
dh,dw=mdata()
ch-=1
dh-=1
cw-=1
dw-=1
if ch==dh and cw==dw:
    out(0)
    exit()
S=[data() for i in range(h)]
stack=[(dh,dw)]
steps=[(0,1),(1,0),(-1,0),(0,-1)]
moves={(dh,dw)}
while stack:
    a,b=stack.pop()
    for i,j in steps:
        if 0<=a+i<h and 0<=b+j<w and S[a+i][b+j]=='.' and (a+i,b+j) not in moves:
            moves.add((a+i,b+j))
            stack.append((a+i,b+j))
if (ch,cw) in moves:
    out(0)
    exit()
moves1={(ch,cw)}
stack=[(ch,cw)]
cnt=0
while stack:
    stack1=[]
    cnt+=1
    while stack:
        a, b = stack.pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if 0 <= a + i < h and 0 <= b + j < w and S[a + i][b + j] == '.' and ((a + i, b + j) not in moves1):
                    moves1.add((a + i, b + j))
                    stack1.append((a + i, b + j))
                    if (a + i, b + j) in moves:
                        out(cnt)
                        exit()
    stack=stack1
out(-1)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**6+10)


h,w=[int(_) for _ in input().split()]

ch,cw=[int(_) for _ in input().split()]
dh,dw=[int(_) for _ in input().split()]

s=[[_ for _ in input()]for j in range(h)]

t=[[-1 for i in range(w)]for j in range(h)]

def wfs(i,j,d):
    for k,l in [[0,1],[0,-1],[1,0],[-1,0]]:
        if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]<0:
            t[i+k][j+l]=d
            wfs(i+k,j+l,d)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]<0:
                t[i+k][j+l]=d+1
                wfs(i+k,j+l,d+1)

t[ch-1][cw-1]=0
wfs(ch-1,cw-1,0)
print(t[dh-1][dw-1])

# print(t)

Submission status: Wrong Answer

Solution code:
import queue
lrud = [[0, -1], [0, 1], [-1, 0], [1, 0]]
lrud2 = [[-1, -1], [1, 1], [-1, 1], [1, -1]]
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch, Cw = Ch-1, Cw-1
Dh, Dw = map(int, input().split())
Dh, Dw = Dh-1, Dw-1
S = [list(input()) for i in range(H)]
q = queue.PriorityQueue()
is_visited = [[-1 for j in range(W)]for i in range(H)]
q.put((0, (Ch, Cw)))
while not q.empty():
    cost, (x, y) = q.get()
    is_visited[x][y] = cost
    for dx, dy in lrud:
        nx, ny = x+dx, y+dy
        if 0 <= nx < H and 0 <= ny < W and is_visited[nx][ny] == -1:
            if S[x][y] == '#' and S[nx][ny] == '#':
                continue
            elif S[x][y] == '.' and S[nx][ny] == '#':
                q.put((cost+1, (nx,ny)))
            else:
                q.put((cost, (nx,ny)))
    if S[x][y] == '#':
        for dx, dy in lrud2:
            nx, ny = x+dx, y+dy
            if 0 <= nx < H and 0 <= ny < W and is_visited[nx][ny] == -1:
                if S[x][y] == '#' and S[nx][ny] == '#':
                    continue
                elif S[x][y] == '.' and S[nx][ny] == '#':
                    q.put((cost+1, (nx,ny)))
                else:
                    q.put((cost, (nx,ny)))

print(is_visited[Dh][Dw])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
h,w = map(int,input().split())
ch,cw= map(int,input().split())
dh,dw= map(int,input().split())
c = [list(input()) for i in range(h)]
count=[-1]
def dfs(x,y):
    f=0
    if not(0 <= x < h) or not(0 <= y < w)  : # 壁に当たったり、探索範囲外になった場合はreturn
        return
    if c[x][y] == "#":
        for i in range (x-2,x+3):
            for j in range(y-2,y+3):
                if i < 0 or h <= i or j < 0 or w <= j or c[i][j]=="#" :
                    return
                else:
                    x=i
                    y=j
                    f+=1
                    print(x,y)
    if x ==dh and y==dw : 
        count.append(f)
        sys.exit()
        
    c[x][y] = "#" #探索済みを示すためのマーキング
    dfs(x+1,y)
    dfs(x-1,y)
    dfs(x,y+1)
    dfs(x,y-1)


            
dfs(ch, cw)
print(min(count))

Submission status: Wrong Answer

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    D[X][Y]=min(D[X][Y],D[x][y])
                    if color[X][Y]=="white":
                        queue.append([X,Y])
                    color[X][Y]="gray"

        for i in range(max(0,x-3),min(h,x+3)):
            for j in range(max(0,y-3),min(w,y+3)):
                X,Y=i,j
                if 0<=X<h and 0<=Y<w:
                    if color[X][Y]!="black":
                        D[X][Y]=min(D[X][Y],D[x][y]+1)
                        if color[X][Y]=="white":
                            queue.append([X,Y])
                        color[X][Y]="gray"
        color[x][y]="black"

    return D[G[0]-1][G[1]-1]


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())

maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

maze2 = [[-1]*W for _ in range(H)]

def mizutamari(maze,maze2,y,x,ct):
    maze2[y][x] = ct
    stack = deque([[y,x]])
    while stack:
        i,j = stack.pop()
        for ni,nj in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not 0 <= i + ni < H or not 0 <= j + nj < W:
                continue
            if maze[i+ni][j+nj] == "." and maze2[i+ni][j+nj] == -1:
                maze2[i+ni][j+nj] = ct
                stack.append([i+ni,j+nj])
    return maze2

def func(maze,maze2):
    ct = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "." and maze2[h][w] == -1:
                maze2 = mizutamari(maze,maze2,h,w,ct)
                ct += 1
    return maze2,ct

maze2,ct = func(maze,maze2)

g = [[] for i in range(ct)]
g2 = [[0]*ct for _ in range(ct)]
for i in range(ct):
    g2[i][i] = 1
for h in range(H):
        for w in range(W):
            if maze2[h][w] != -1:
                for i in range(1,3):
                    for j in range(-2,3):
                        if not 0 <= i + h < H or not 0 <= j + w < W:
                            continue
                        if maze2[h+i][w+j] != -1 and \
                            not g2[maze2[h][w]][maze2[h+i][w+j]]:
                            g[maze2[h][w]].append((1,maze2[h+i][w+j]))
                            g[maze2[h+i][w+j]].append((1,maze2[h][w]))
                            g2[maze2[h][w]][maze2[h+i][w+j]] = 1
                            g2[maze2[h+i][w+j]][maze2[h][w]] = 1


#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)


start = maze2[sh-1][sw-1]
goal = maze2[gh-1][gw-1]

res = dijkstra_heap(start,g)

if res[goal] == float("inf"):
    print(-1)
else:
    print(res[goal])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij4=[(0,1),(1,0),(-1,0),(0,-1)]
dijx=[(1,1),(-1,1),(1,-1),(-1,-1)]
dij8=[(0,1),(1,0),(-1,0),(0,-1),(1,-1),(1,1),(-1,-1),(-1,1)]

from collections import deque

def solve():
    q = deque()
    q.append((si, sj, 0, 0))
    aa[si][sj] = 0

    while q:
        i, j, d, t = q.popleft()
        if t:
            for di, dj in dij4 + dijx:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if ss[ni][nj] == 0 and aa[ni][nj] == -1:
                    aa[ni][nj] = d
                    q.appendleft((ni, nj, d, 0))
        else:
            for di, dj in dij4:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if ss[ni][nj]:
                    if aa[ni][nj] == -1:
                        aa[ni][nj] = d + 1
                        q.append((ni, nj, d + 1, 1))
                else:
                    if aa[ni][nj] == -1:
                        aa[ni][nj] = d
                        q.appendleft((ni, nj, d, 0))
            for di, dj in dijx:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if ss[ni][nj] == 0: continue
                if aa[ni][nj] == -1:
                    aa[ni][nj] = d + 1
                    q.append((ni, nj, d + 1, 1))

    # print()
    # p2D(aa)

    print(aa[gi][gj])

h,w=MI()
si,sj=MI1()
gi,gj=MI1()
ss=[[1 if c=="#" else 0 for c in SI()] for _ in range(h)]
aa=[[-1]*w for _ in range(h)]
#p2D(ss)
solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

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 = [input() for _ in range(H)]

    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#': continue
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    if S[y][x] == '.':
                        adj[W*i + j].append(W*y + x)

    # ワープ可能な場所もadjに加える
    worp = [[] for _ in range(W*H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '#': continue
            for kx in [-2,-1,0,1,2]:
                for ky in [-2,-1,0,1,2]:
                    if kx == ky == 0: continue
                    y = i + ky
                    x = j + kx
                    if W*y + x in adj[W*i + j]: continue
                    if 0 <= y < H and 0 <= x < W:
                        if S[y][x] == '.':
                            worp[W*i + j].append(W*y + x)
    
    start = W*Ch + Cw
    goal = W*Dh + Dw
    queue = deque([start])
    visit = [-1] * (W*H)
    visit[start] = 0
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now]
            else:
                visit[u] = min(visit[u], visit[now])
        for u in worp[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now]+1
            else:
                visit[u] = min(visit[u], visit[now]+1)
    
    print(visit[goal])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 = [list(input()) for _ in range(h)]

d = deque()
d.append([ch-1, cw-1])
dist = [[float('inf')] * w for _ in range(h)]
dist[ch-1][cw-1] = 0
while d:
    x, y = d.popleft()
    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= x + i < h and 0 <= y + j < w and s[x+i][y+j] == '.':
                if i == 0 and j == 0:
                    continue
                elif (i == 1 and j == 0) or (i == 0 and j == 1) or (i == -1 and j == 0) or (i == 0 and j == -1):
                    if dist[x+i][y+j] == float('inf'):
                        d.appendleft([x+i, y+j])
                    dist[x+i][y+j] = min(dist[x+i][y+j], dist[x][y])
                else:
                    if dist[x+i][y+j] == float('inf'):
                        d.append([x+i, y+j])
                    dist[x+i][y+j] = min(dist[x+i][y+j], dist[x][y] + 1)

print(dist[dh-1][dw-1] if dist[dh-1][dw-1] != float('inf') else -1)

Submission status: Wrong Answer

Solution code:
import queue

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
nh = [1, -1, 0, 0]
nw = [0, 0, 1, -1]
maze = []
count = [[-1 for _ in range(W)] for __ in range(H)]
isReached = [[False for _ in range(W)] for __ in range(H)]
for i in range(H):
    si = input()
    maze.append(si)

q = queue.Queue()
warpQueue = queue.Queue()
q.put([ch - 1, cw - 1, 0])
warpQueue.put([ch-1, cw-1, 0])
count[ch-1][cw-1] = 0

isEnded = False

while not isEnded:
    while not q.empty():
        h, w, cnt = q.get()
        # 前後左右の移動
        for i in range(4):
            # 範囲内
            if 0 <= h + nh[i] and h + nh[i] < H and 0 <= w + nw[i] and w + nw[i] < W:
                # 調べてない + かべじゃない
                if maze[h + nh[i]][w + nw[i]] != "#" and count[h + nh[i]][w + nw[i]] == -1:
                    count[h + nh[i]][w + nw[i]] = cnt
                    q.put([h + nh[i], w + nw[i], cnt])
                    warpQueue.put([h + nh[i], w + nw[i], cnt])

    if warpQueue.empty():
        break

    while not warpQueue.empty():
        h, w, cnt = warpQueue.get()
        for ph in range(-2, 3):
            for pw in range(-2, 3):
                if 0 <= h + ph and h + ph < H and 0 <= w + pw and w + pw < W:
                    if maze[h+ph][w+pw] != "#" and count[h+ph][w+pw] == -1:
                        count[h + ph][w + pw] = cnt + 1
                        q.put([h + ph, w + pw, cnt + 1])

print(count[dh-1][dw-1])