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:
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
M = list( list(input()) for _ in range(H) )

if ch==dh and cw==dw:
  print(0)
  exit()

INF = 10**18

for h in range(H):
  for w in range(W):
    if M[h][w] == ".": M[h][w] = INF
    # if M[h][w] == "#": M[h][w] = -1

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

M[ch][cw] = 0
# M[dh][dw] = "G"

# _pa(M)


from collections import deque
Q = deque()
Q.append((ch,cw))

ans = INF

while Q:
  h,w = Q.popleft()

  for ih,iw in [(1,0), (-1,0), (0,1), (0,-1)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "#": continue

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w], M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w] < M[nh][nw]:
      M[nh][nw] = M[h][w]
      # Q.appendleft((nh,nw))
      Q.append((nh,nw))
      continue

    if M[h][w] > M[nh][nw]:
      M[h][w] = M[nh][nw]
      # Q.appendleft((h,w))
      Q.append((h,w))

  for ih,iw in [(1,1), (1,-1), (-1,1), (-1,-1), (2,0), (2,1), (2,2), (2,-1), (2,-2), (1,2), (1,-2), (0,2), (0,-2), (-1,2), (-1,-2), (-2,0), (-2,1), (-2,-2), (-2,-1), (-2,-2)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "#": continue

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w]+1, M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w]+1 < M[nh][nw]:
      M[nh][nw] = M[h][w]+1
      Q.append((nh,nw))
      continue

    if M[h][w] > M[nh][nw]+1:
      M[h][w] = M[nh][nw]+1
      Q.append((h,w))

# _pa(M)

if ans == INF: ans = -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())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x]
                        queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x] + 1
                        queue.appendleft((y+j, x+i))


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10000000)
    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)]
    wall = ['#'] * (w + 2)
    s.insert(0, wall)
    s.append(wall)

    visited = [[False for _ in range(w + 2)] for _ in range(h + 2)]
    group = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
    gd = defaultdict(list)

    def dfs(i, j, g):
        if visited[i][j]:
            return
        visited[i][j] = True
        group[i][j] = g
        gd[g].append((i, j))
        for p, q in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            if s[i + p][j + q] == '#':
                continue
            dfs(i + p, j + q, g)

    # define group
    g = 1
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if s[i][j] == '#':
                continue
            dfs(i, j, g)
            g += 1

    visited = [[False for _ in range(w + 2)] for _ in range(h + 2)]
    cost = {i: float('Inf') for i in range(1, g + 1)}

    def search(i, j, gfrom, c):
        visited[i][j] = True
        g = group[i][j]
        if g != gfrom:
            c += 1
        cost[g] = min(cost[g], c)
        cij = cost[g]

        for p in range(-2, 3):
            for q in range(-2, 3):
                if not 1 <= i + p <= h + 1:
                    continue
                if not 1 <= j + q <= w + 1:
                    continue
                if visited[i + p][j + q] or s[i + p][j + q] == '#':
                    continue
                search(i + p, j + q, g, cij)

    gc = group[ch][cw]
    search(ch, cw, gc, 0)
    gg = group[dh][dw]
    ans = cost[gg] if cost[gg] != float('Inf') else -1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

INF = h + w + 1
cost = [[INF] * w for _ in range(h)]
dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
dxy2 = [(i, j) for i in [-2, 2]
        for j in range(-2, 3)] + [(i, j) for j in [-2, 2]
                                  for i in range(-1, 2)]
q = [(0, ch, cw)]
cost[ch][cw] = 0
while q:
    c, x, y = heappop(q)
    if cost[x][y] < c:
        continue

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c:
            continue
        cost[nx][ny] = c
        heappush(q, (c, nx, ny))

    for dx_, dy_ in dxy2:
        nx = x + dx_
        ny = y + dy_
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c + 1:
            continue
        cost[nx][ny] = c + 1
        heappush(q, (c + 1, nx, ny))

ans = -1 if cost[dh][dw] == INF else cost[dh][dw]
print(ans)
# print(*cost, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys, math, heapq

# input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [[1 if s=='.' else 0 for s in input()] for _ in range(H)]
costs = [[math.inf]*W for _ in range(H)]
costs[Ch-1][Cw-1] = 0
hq = [(0, Ch-1, Cw-1)]
heapq.heapify(hq)

while len(hq)>0:
    c, h, w = heapq.heappop(hq)
    for i, j in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
        if i < 0 or j < 0 or i>=H or j>=W:
            continue
        if i == Dh - 1 and j == Dw - 1:
            print(c)
            sys.exit()
        if S[i][j] and costs[i][j] > c:
            costs[i][j] = c
            heapq.heappush(hq, (c, i, j))
    for dw in [-2, -1, 0, 1, 2]:
        for dh in [-2, -1, 0, 1, 2]:
            if w+dw < 0 or h+dh < 0 or w+dw>=W or h+dh>=H:
                continue
            if w+dw == Dw-1 and h+dh==Dh-1:
                print(c+1)
                sys.exit()
            if S[h+dh][w+dw] and costs[h+dh][w+dw] > c+1:
                costs[h+dh][w+dw] = c+1
                heapq.heappush(hq, (c+1, h+dh, w+dw))

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 
    f=0
    if s[a+1,b]=='.':
        f=1
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    if s[a,b+1]=='.':
        f=1
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    if s[a-1,b]=='.':
        f=1
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    if s[a,b-1]=='.':
        f=1
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])
    if f==0:
        for ii in range(-2,3):
            for jj in range(-2,3):
                if s[a+ii,b+jj]=='.':
                    wq.append([a+ii,b+jj])
                    s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        bfs(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return


H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def main():

    input = sys.stdin.readline

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

    S=[list(map(str,list(input()[:-1]))) for i in range(H)]
    F=[ [-1] * W for i in range(H)]
    dist=[ [10000000] * W for i in range(H)]

    dh = (1, 0, -1, 0)
    dw = (0, 1, 0, -1)
    warph = (2, 2, 2, 2 ,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2)
    warpw = (-2, -1, 0, 1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2)

    d = deque()

    d.append((Ch-1,Cw-1))

    F[Ch-1][Cw-1] = 0
    dist[Ch-1][Cw-1] = 0

    while len(d) > 0:
        Ph,Pw = d.popleft()

        # if (Ph == Dh-1) & (Pw == Dw-1):
        #     goal = True
        #     break

        for i in range(4):
            nh = Ph + dh[i]
            nw = Pw + dw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.appendleft((nh,nw))
                F[nh][nw] = 0
            elif dist[nh][nw] < dist[Ph][Pw]:
                d.appendleft((nh,nw))
                dist[nh][nw] = min(dist[nh][nw],dist[Ph][Pw])

        for i in range(20):
            nh = Ph + warph[i]
            nw = Pw + warpw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.append((nh,nw))
                F[nh][nw] = 0
            dist[nh][nw] = min(dist[nh][nw],dist[Ph][Pw]+1)

    if dist[Dh-1][Dw-1] >= 10000000:
        print("-1")
    else:
        print(dist[Dh-1][Dw-1])
         

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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

WALL = -100
INI = -1
PASSED = 0

S = [[0] * w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        if tmp[j] == '#':
            S[i][j] = WALL
        else:
            S[i][j] = INI

S[Ch][Cw] = 0
direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]


def dfs(y, x, d):
    d.append((y, x))
    if y == Dh and x == Dw:
        print(S[y][x])
        exit()
    for dy, dx in direction:
        next_y = y + dy
        next_x = x + dx
        if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
            continue
        if S[next_y][next_x] == INI:
            #print("y = ", y, "x = ", x, "next_y = ", next_y, "next_x = ", next_x)
            S[next_y][next_x] = S[y][x]
            dfs(next_y, next_x, d)

def bfs(y, x, d):
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            next_y = y + dy
            next_x = x + dx
            if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
                continue
            if S[next_y][next_x] == INI:
                d.append((next_y, next_x))
                #print("S[u][x] = ", S[y][x])
                S[next_y][next_x] = S[y][x] + 1
    return False



d = deque()
d.append((Ch, Cw))
is_goal = False
from pprint import pprint
while len(d):
    y, x = d.popleft()
    d2 = deque()
    dfs(y, x, d2)
    while len(d2):
        y2, x2 = d2.popleft()
        #print("y2 = ", y2, "x2 = ", x2)
        bfs(y2, x2, d)


if is_goal:
    print(S[Dh][Dw])
else:
    print(-1)

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())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([-1 if i =="." else i for i in s])

dq = deque()
dq.append((Ch,Cw))
S[Ch][Cw]=0

while dq:
  a=dq.pop()
  if a[0]-1>=0 and (S[a[0]-1][a[1]]==-1 or (S[a[0]-1][a[1]]!="#" and S[a[0]-1][a[1]]>S[a[0]][a[1]])):
    S[a[0]-1][a[1]]=S[a[0]][a[1]]
    dq.appendleft((a[0]-1,a[1]))
  if a[0]+1<H and (S[a[0]+1][a[1]]==-1 or (S[a[0]+1][a[1]]!="#" and S[a[0]+1][a[1]]>S[a[0]][a[1]])):
    S[a[0]+1][a[1]]=S[a[0]][a[1]]
    dq.appendleft((a[0]+1,a[1]))
  if a[1]-1>=0 and (S[a[0]][a[1]-1]==-1 or (S[a[0]][a[1]-1]!="#" and S[a[0]][a[1]-1]>S[a[0]][a[1]])):
    S[a[0]][a[1]-1]=S[a[0]][a[1]]
    dq.appendleft((a[0],a[1]-1))
  if a[1]+1<W and (S[a[0]][a[1]+1]==-1 or (S[a[0]][a[1]+1]!="#" and S[a[0]][a[1]+1]>S[a[0]][a[1]])):
    S[a[0]][a[1]+1]=S[a[0]][a[1]]
    dq.appendleft((a[0],a[1]+1))
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and S[a[0]-2+i][a[1]-2+j]==-1:
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]+1
        dq.append((a[0]-2+i,a[1]-2+j))

print(S[Dh][Dw])

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

d = [[10**15 for _ in range(W)] for _ in range(H)]    
d[Ch-1][Cw-1] = 0

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

cnt = 0
def dfs(ch, cw):   
    stack = deque()
    stack.append((ch, cw))
    z = 0
    while stack:
        x, y = stack.popleft()
        grid[x][y] = "#"
    
        if(x == Dh-1 and y == Dw-1):
            return d[x][y]
    
        for dx, dy in direction:
            nx = x + dx
            ny = y + dy
        
            if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                continue
            if(grid[nx][ny] == "#"):
                continue
            d[nx][ny] = d[x][y]
            stack.append((nx, ny))
        
        for i in range(-2, 3):
            for j in range(-2, 3):
                if(x+i < 0 or x+i >= H or y+j < 0 or y+j >= W):
                    continue
                if(grid[x+i][y+j] == "#"):
                    continue
                if(d[x][y] + 1 >= d[x+i][y+j]):
                    continue
                d[x+i][y+j] = d[x][y] + 1
                stack.append((x+i, y+j))
    return -1
                    
print(dfs(Ch-1, Cw-1))

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

def bfs(x,y,z):
    if x == Dh and y == Dw:
        print(z)
        exit()
    F = 0
    dist[x][y] = 1
    que = deque([[x, y]])
    while que:
        h, w = que.pop()
        for dh, dw in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dh
            nw = w + dw
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if maze[nh][nw] == '#':
                F = 1
                continue
            if dist[nh][nw] == -1:
                if nh == Dh and nw == Dw:
                    print(z)
                    exit()
                dist[nh][nw] = 1
                que.appendleft([nh, nw])
        if F == 1 and (h,w,z) not in li:
            li.append((h,w,z))
            que2.append((h,w,z))

H,W = I()
Ch,Cw = I()
Dh,Dw = I()
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
li = deque([])
maze = [list(s()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
dist[Ch][Cw] = 1
que = deque([[Ch, Cw]])
while que:
    F = 0
    h, w = que.pop()
    for dh, dw in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            F = 1
            continue
        if dist[nh][nw] == -1:
            if nh == Dh and nw == Dw:
                print(0)
                exit()
            dist[nh][nw] = 1
            que.appendleft([nh, nw])
    if F == 1:
        li.append((h,w,0))
que2 = copy(li)
lis = [[2,2],[2,-2],[-2,2],[-2,-2],[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2],[2,0],[-2,0],[0,2],[0,-2],[1,1],[1,-1],[-1,1],[-1,-1]]
while que2:
    h,w,n = que2.pop()
    for dh, dw in lis:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            continue
        if dist[nh][nw] == -1:
            bfs(nh,nw,n+1)
print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


# MAGIC = ((-2, -2), (-1, -2), (1, -2), (2, -2),
#          (-2, -1), (-1, -1),  (1, -1), (2, -1),
#          (-2, 1), (-1, 1), (1, 1), (2, 1),
#          (-2, -2), (-1, 2), (1, 2), (2, 2))

MAGIC = ((-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2),
         (-2, -1), (-1, -1),          (1, -1), (2, -1),
         (-2, 0),                              (2, 0),
         (-2, 1), (-1, 1),             (1, 1), (2, 1),
         (-2, -2), (-1, 2), (0, 2), (1, 2), (2, 2))
H, W = zz()

c_h, c_w = zz()
d_h, d_w = zz()
board = []
c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
for i in range(H):
    tmp = S()
    # N += tmp.count('.')
    board.append(tmp)

# print(board)
que = deque([[c_h, c_w]])
visited = defaultdict(list)
visited_all = []
magic_visited = []
dist = {}
# bfs()
magic = 0
visited[magic].append((c_h, c_w))
while visited[magic]:
    # print((visited[magic]))
    while que:
        tmp = que.popleft()
        h, w = tmp
        if ((h, w) == (d_h, d_w)):
            if (magic == 0):
                print(magic)
            else:
                print(magic - 1)
            exit()
        visited[magic].append((h, w))
        visited_all.append((h, w))
        dist[(h, w)] = magic
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if board[new_h][new_w] == '.' and ((new_h, new_w) not in visited_all):
                que.append((new_h, new_w))

    magic += 1
    for h, w in visited[magic-1]:
        if ((h, w) == (d_h, d_w)):
            if (magic == 0):
                print(magic)
            else:
                print(magic-1)
            exit()
        for dy, dx in MAGIC:
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if board[new_h][new_w] == '.' and ((new_h, new_w) not in visited_all):
                visited[magic].append((new_h, new_w))
                visited_all.append((new_h, new_w))
try:
    # print(dist)
    print(dist[(d_h, d_w)])
except:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys, math, heapq
import numpy as np

# input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = np.array([[1 if s=='.' else 0 for s in input()] for _ in range(H)])
costs = np.ones((H, W), dtype=int)*np.inf
costs[Ch-1, Cw-1] = 0
hq = [(0, Ch-1, Cw-1)]
heapq.heapify(hq)

while len(hq)>0:
    c, h, w = heapq.heappop(hq)
    for i, j in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
        if i < 0 or j < 0 or i>=H or j>=W:
            continue
        if i == Dh - 1 and j == Dw - 1:
            print(c)
            sys.exit()
        if S[i, j] and costs[i, j] > c:
            costs[i, j] = c
            heapq.heappush(hq, (c, i, j))
    for dw in [-2, -1, 0, 1, 2]:
        for dh in [-2, -1, 0, 1, 2]:
            if w+dw < 0 or h+dh < 0 or w+dw>=W or h+dh>=H:
                continue
            if w+dw == Dw-1 and h+dh==Dh-1:
                print(c+1)
                sys.exit()
            if S[h+dh, w+dw] and costs[h+dh, w+dw] > c+1:
                costs[h+dh, w+dw] = c+1
                heapq.heappush(hq, (c+1, h+dh, w+dw))

print(-1)

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

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]
ans[ch-1][cw-1]=0
dx=[0,1,0,-1]
dy=[1,0,-1,0]
count=0

def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    if dh-1==y and dw-1==x:
      ans[y][x]=ans[y][x]-1
      break

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if (x==i and y==j):
          continue
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
            if (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1):
              qu.append([i,j])
              ans[j][i] = ans[y][x]
            elif ans[j][i]>ans[y][x]+1 or ans[j][i]==-1:
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)

Submission status: Wrong Answer

Solution code:
import queue
import heapq

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

def bfs(ch,cw):
    q = []
    S[ch][cw] = 0
    cd = 0
    heapq.heappush(q,(cd,[ch,cw]))
    while q:
        p = heapq.heappop(q)[1]
        if p[0]==dh and p[1]==dw:
            break
            
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > cd:
                S[next_p[0]][next_p[1]] = cd
                heapq.heappush(q,(cd,next_p))
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > cd+1:
                    S[next_p[0]][next_p[1]] = cd+1
                    heapq.heappush(q,(cd,next_p))
                    
            
    return 
        
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 = [list(input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1


bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

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

def BFS(maze,s,g):
  q1,q2 = deque([s]),deque()
  checked = []
  while len(q1)>0 or len(q2)>0:
    if len(q1)>0: h,w,n = q1.popleft()
    elif len(q2)>0: h,w,n = q2.popleft()
    if (h,w)==g: return n
    dp = [(i-2,j-2) for i in range(5) for j in range(5) if (i-2,j-2)!=(0,0)]
    for i in dp:
      if (h+i[0],w+i[1]) in checked: continue
      else:
        if (0<h+i[0]<len(maze)) and (0<w+i[1]<len(maze[0])) and maze[h+i[0]][w+i[1]]==".":
          checked.append((h+i[0],w+i[1]))
          if i[0]%2==0 or i[1]%2==0: q2.append((h+i[0],w+i[1],n+1))
          else: q1.append((h+i[0],w+i[1],n))
  return -1

print(BFS(maze,(CH-1,CW-1,0),(DH-1,DW-1)))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
c = [int(i) + 1 for i in input().split()]
d = [int(i) + 1 for i in input().split()]

s = []
s.append('#'*(W+4))
s.append('#'*(W+4))
for i in range(H):
    a = input()
    s.append('##' + a + '##')
s.append('#'*(W+4))
s.append('#'*(W+4))

q = deque([]) # 探索開始点
qq = deque([])
q.append((c[0], c[1], 0))
visited = [[False for __ in range(W+4)] for _ in range(H+4)]

while q:
    xx, yy, kaisuu = q.popleft()
    if visited[xx][yy] == True:
        continue
    qq.append((xx, yy, kaisuu))
    ls = []
    while qq:
        x, y, kaisuu = qq.popleft()
        visited[x][y] = True
        ls.append((x, y, kaisuu))
        if x == d[0] and y == d[1]:
            print(kaisuu)
            sys.exit()
        if s[x+1][y] == '.' and visited[x+1][y] == False:
            qq.append((x+1, y, kaisuu))
        if s[x-1][y] == '.' and visited[x-1][y] == False:
            qq.append((x-1, y, kaisuu))
        if s[x][y+1] == '.' and visited[x][y+1] == False:
            qq.append((x, y+1, kaisuu))
        if s[x][y-1] == '.' and visited[x][y-1] == False:
            qq.append((x, y-1, kaisuu))
    for u in ls:
        a, b, e = u
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if abs(i) == 1 and abs(j) == 1:
                    continue
                if s[a+i][b+j] == '.' and visited[a+i][b+j] == False:
                    q.append((a+i, b+j, e+1))
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
def input():return sys.stdin.readline().strip()
def main():
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1; sw -= 1
    start = (sh+2)*(W+4) + 2 + sw
    dh, dw = map(int, input().split())
    dh -= 1; dw -= 1
    goal = (dh+2)*(W+4) + 2 + dw

    field = "#"*(W+4)*2
    field += "##" + "####".join([ input() for _ in range(H)]) + "##"
    field += "#"*(W+4)*2

    move = [-1, 1, -(W+4), W+4]
    ex_left = [-2*(W+4)-2, -(W+4)-2, -2, (W+4)-2, 2*(W+4)-2]
    ex_right = [-2*(W+4)+2, -(W+4)+2, +2, (W+4)+2, 2*(W+4)+2]
    ex_up = [-2*(W+4)-2, -2*(W+4)-1, -2*(W+4), -2*(W+4)+1, -2*(W+4)+2]
    ex_down = [2*(W+4)-2, 2*(W+4)-1, 2*(W+4), 2*(W+4)+1, 2*(W+4)+2]

    INF = 10 ** 18
    num = [INF] * (H+4) * (W+4)
    warped = [False] * (H+4) * (W+4)

    def bfs(s):
        q = deque()
        num[s] = 0
        q.append((s, 0))
    
        while q:
            now, cost = q.popleft()
            if cost > num[now]:
                continue
            else:
                num[now] = cost

            if now == goal:
                return

            for i, dx in enumerate(move):
                nx = now + dx
                if field[nx] == "." and num[nx] == INF:
                    q.appendleft((nx, cost))
                    num[nx] = cost

                elif field[nx] == "#":
                    # if i == 0:
                    #     ex = ex_left
                    # elif i == 1:
                    #     ex = ex_right
                    # elif i == 2:
                    #     ex = ex_up
                    # else:
                    #     ex = ex_down

                    for dx2 in ex_left:
                        nx2 = now + dx2
                        if field[nx2] == "." and num[nx2] == INF and not warped[nx2]:
                            q.append((nx2, cost+1))
                            warped[nx2] = True
                    for dx2 in ex_right:
                        nx2 = now + dx2
                        if field[nx2] == "." and num[nx2] == INF and not warped[nx2]:
                            q.append((nx2, cost+1))
                            warped[nx2] = True
                    for dx2 in ex_up:
                        nx2 = now + dx2
                        if field[nx2] == "." and num[nx2] == INF and not warped[nx2]:
                            q.append((nx2, cost+1))
                            warped[nx2] = True
                    for dx2 in ex_down:
                        nx2 = now + dx2
                        if field[nx2] == "." and num[nx2] == INF and not warped[nx2]:
                            q.append((nx2, cost+1))
                            warped[nx2] = True
    
    bfs(start)

    if num[goal] == INF:
        print(-1)
    else:
        print(num[goal])

    
    # for i in range(0, (H+4)*(W+4), W+4):
    #     print(field[i:i+W+4])
    
    # print(start)
    # print(start//(W+4), start%(W+4))
    # print(goal)
    # print(goal//(W+4), goal%(W+4))
    


if __name__ == "__main__":
    main()