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
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh, gw = map(int, readline().split())
    gh -= 1
    gw -= 1
    S = read().split()
    dist = [[INF] * W for _ in range(H)]
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(1, 1), (1, -1), (-1, 1), (-1, -1), \
            (2, 0), (2, 1), (2, 2), (2, -1), (2, -1), (2, -2), \
            (-2, 0), (-2, 1), (-2, 2), (-2, -1), (-2, -1), (-2, -2), \
            (0, 2), (1, 2), (-1, 2), (0, -2), (1, -2), (-1, -2)]
    Q = deque()
    Q.append((sh, sw))
    dist[sh][sw] = 0
    while Q:
        h, w = Q.popleft()
        if h == gh and w == gw:
            break
        flag = False
        for dh, dw in walk:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] != '#':
                    if dist[nh][nw] > dist[h][w]:
                        dist[nh][nw] = dist[h][w]
                        Q.append((nh,nw))
                else:
                    flag = True
        if flag:
            for dh, dw in warp:
                nh = h + dh
                nw = w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if dist[nh][nw]==INF:
                        dist[nh][nw] = dist[h][w] + 1
                        Q.append((nh,nw))

    if dist[gh][gw]==INF:
        print(-1)
    else:
        print(dist[gh][gw])




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_left, bisect_right

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
C = LIST()
D = LIST()
S = [input() for i in range(H)]

visited = [[False] * W for i in range(H)]
dist = [[INF] * W for i in range(H)]
q = deque([(C[0]-1, C[1]-1)])

dist[C[0]-1][C[1]-1] = 0
visited[C[0]-1][C[1]-1] = True
dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]
warp = [[-1] * W for i in range(H)]
warp[C[0]-1][C[1]-1] = 0
warp_time = 0
warp_stock = deque([[C[0]-1, C[1]-1]])

while q:
    while q:
        ch, cw = q.popleft()
        warp_stock.append([ch, cw])
        dh = [0, 1, 0, -1]
        dw = [1, 0, -1, 0]
        for i in range(4):
            nh = ch + dh[i]
            nw = cw + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if visited[nh][nw] == False and S[nh][nw] != "#":
                    # dist[nh][nw] = dist[ch][cw] + 1
                    visited[nh][nw] = True
                    warp[nh][nw] = warp_time
                    warp_stock.append([nh, nw])
                    q.append([nh, nw])
        # print(warp_stock)
    while warp_stock:
        ch, cw = warp_stock.popleft()
        for dh in [-2, -1, 0, 1, 2]:
            for dw in [-2, -1, 0, 1, 2]:
                nh = ch + dh
                nw = cw + dw
                if 0 <= nh < H and 0 <= nw < W:
                    if visited[nh][nw] == False and S[nh][nw] != "#":
                        # dist[nh][nw] = dist[ch][cw]
                        visited[nh][nw] = True
                        q.append([nh, nw])
                        warp[nh][nw] = warp[ch][cw] + 1
print(warp[D[0]-1][D[1]-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
start = list(map(int, input().split()))
goal = list(map(int, input().split()))
L = [list(input()) for _ in range(H)]
result = {}
def part(x, y, i, mem):
  if not (0<=x<H) or not (0<=y<W) or L[x][y]!=".":
    return
  L[x][y]=i
  mem.append((x,y))
  part(x-1, y, i, mem)
  part(x+1, y, i, mem)
  part(x, y-1, i, mem)
  part(x, y+1, i, mem)
mark = 0
for h in range(H):
  for w in range(W):
    if L[h][w]==".":
      mem = []
      part(h, w, mark, mem)
      result[mark]=mem
      mark += 1
dic = {i:10**8 for i in range(mark+1)}
s = L[start[0]-1][start[1]-1]
dic[0]=0
g = L[goal[0]-1][goal[1]-1]
queue = deque([s])
while queue:
    now = queue.popleft()
    if now==g:
        print(dic[now])
        exit()
    for (x,y) in result[now]:
        for i in range(max(x-2, 0), min(x+3, H)):
            for j in range(max(y-2, 0), min(y+3, W)):
              key = L[i][j]
              if str(key)=="#":
                continue
              if key != now and dic[key] == 10**8:
                dic[key]= dic[now]+1
                queue.append(key)             
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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 = {}
for i in range(1, count):
    graph[i] = 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 bfs(start, goal, visited=None):
    queue = deque([start])
    visited = set()
    visited.add(start)
    depth = 0
    while queue:
        current_vertex = queue.popleft()
        if current_vertex == goal:
            return depth
        depth += 1
        for v in graph[current_vertex]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
    return -1

ans = bfs(start, goal)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int,input().split())
curX,curY = map(int,input().split())
goalX,goalY =  map(int,input().split())
goalX -= 1
goalY -= 1

graph = []
for _ in range(H):
  r = list(input())
  graph.append(r)

ans = float('inf')
q = deque([(curX-1,curY-1,0)])
visited = [ [False]*W for _ in range(H) ]
while q:
  new_q = deque()

  for _ in range(len(q)):
    r,c,hop = q.popleft()
    if r==goalX and c==goalY:
      ans = min(ans, hop)
      continue
    visited[r][c] = True

    # if be able to move 1 step
    for x,y in [(-1,0),(0,-1),(1,0),(0,1)]:
      nr,nc = r+x,c+y
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if graph[nr][nc] == "#": continue
      if visited[nr][nc]: continue
      new_q.append((nr,nc,hop))

    for i in range(-2, 3):
      for j in range(-2, 3):
        nr,nc = r+i,c+j
        if nr<0 or nc<0 or nr>=H or nc>=W: continue
        if graph[nr][nc] == "#": continue
        if visited[nr][nc]: continue
        new_q.append((nr,nc,hop+1))

  q = new_q

if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(h, w, maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx, 0]])
    visited[sy][sx] = 0
    worps = []
    while queue:
        y, x, worp = queue.popleft()
        # print(y, x, worp)
        if [y, x] == [gy, gx]:
            worps.append(worp)
        walkable = False
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + k
            if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w:
                continue
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x, worp])
                walkable = True

        if walkable is False:
            for s, t in (
                [1, 1],
                [1, -1],
                [-1, 1],
                [-1, -1],
                [2, 0],
                [2, 1],
                [2, -1],
                [2, 2],
                [2, -2],
                [1, 2],
                [1, -2],
                [0, 2],
                [0, -2],
                [-1, 2],
                [-1, -2],
                [-2, 0],
                [-2, 1],
                [-2, -1],
                [-2, 2],
                [-2, -2],
            ):
                new_y, new_x = y + s, x + t
                if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w:
                    continue
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x, worp + 1])
    return min(worps) if len(worps) > 0 else -1


if __name__ == "__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 = [list(input()) for i in range(h)]
    visited = [[-1] * w for j in range(h)]
    print(bfs(h, w, s, visited, ch, cw, dh, dw))

Submission status: Wrong Answer

Solution code:
print(2)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2,  2, 2, 1, 1, 1, 1, 0,  0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, 2, 2, 1, -1, -2, 2, -2,  2, -2, 1, -1, 2,  1,  0, -1,  2]


def bfs(u, S, M, H, W):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx = u[0] + mX[i]
            ny = u[1] + mY[i]
            if nx < 0 or H <= nx:
                continue
            if ny < 0 or W <= ny:
                continue
            if S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] >= M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for i in range(20):
            wx = u[0] + zX[i]
            wy = u[1] + zY[i]
            if wx < 0 or H <= wx:
                continue
            if wy < 0 or W <= wy:
                continue
            if S[wx][wy] == "#":
                continue
            if M[wx][wy] == -1:  # state を確認
                M[wx][wy] = M[u[0]][u[1]] + 1
                q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

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

    if S[Ch - 1][Cw - 1] == "#":
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

    print(M[Dh - 1][Dw - 1])


main()

Submission status: Wrong Answer

Solution code:
h, w = list(map(int, input().split()))
cy, cx = list(map(int, input().split()))
dy, dx = list(map(int, input().split()))

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

areas = []
connections = []
visited = {}

for y in range(h):
    for x in range(w):
        if grid[y][x] == "#":
            continue

        if str((x, y)) not in visited:
            area = []
            neighbours = [(x, y)]

            while len(neighbours) > 0:
                nei = neighbours.pop()
                if str(nei) in visited:
                    continue
                if grid[nei[1]][nei[0]] == "#":
                    continue

                visited[str(nei)] = len(areas)

                area.append(nei)
                if nei[0] < w-1:
                    neighbours.append((nei[0]+1, nei[1]))
                if nei[0] > 0:
                    neighbours.append((nei[0]-1, nei[1]))
                if nei[1] < h-1:
                    neighbours.append((nei[0], nei[1]+1))
                if nei[1] > 0:
                    neighbours.append((nei[0], nei[1]-1))

            areas.append(area)
            connections.append(set())

        #check neighbours
        neighbours = []
        for o1 in [-2, 2]:
            for o2 in [-1, 0, 1]:
                neighbours.append((x+o1, y+o2))
                neighbours.append((x+o2, y+o1))

            for o3 in [-2, 2]:
                neighbours.append((x+o1, y+o3))

        for nei in neighbours:
            if nei[0] < 0 or nei[0] >= w or nei[1] < 0 or nei[1] >= h:
                continue

            if str(nei) in visited:
                this = visited[str((x, y))]
                tel = visited[str(nei)]

                if this != tel:
                    connections[this].add(tel)
                    connections[tel].add(this)

start = visited[str((cx-1, cy-1))]
target = visited[str((dx-1, dy-1))]
visited = {start: True}
found = False
dist = 0

neighbours = [(start, 0)]
while len(neighbours) > 0:
    nei = neighbours.pop(0)
    if nei[0] == target:
        dist = nei[1]
        found = True
        break

    for n2 in connections[nei[0]]:
        if n2 not in visited:
            neighbours.append((n2, nei[1]+1))

        visited[n2] = True

print(dist if found else -1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def dfs2(y, x, c):
    dy = [1, 0, 0, -1]
    dx = [0, -1, 1, 0]
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if ny < 0 or H <= ny or nx < 0 or W <= nx:
            continue
        if field[ny][nx] == '#':
            pass
        elif field[ny][nx] == '.':
            field[ny][nx] = c
        else:
            field[ny][nx] = min(c, field[ny][nx])
    return


def dfs1(y, x, c):
    dy = [2, 2, 2, 2, 2, 1, 1, 0, 0, -1, -1, -2, -2, -2, -2, -2, 1, 1, -1, -1]
    dx = [-2, -1, 0, 1, 2, -2, 2, -2, 2, -2, 2, -2, -1, 0, 1, 2, -1, 1, -1, 1]
    for k in range(20):
        ny = y + dy[k]
        nx = x + dx[k]
        if ny < 0 or H <= ny or nx < 0 or W <= nx:
            continue
        if field[ny][nx] == '#':
            pass
        elif field[ny][nx] == '.':
            field[ny][nx] = c+1
        else:
            field[ny][nx] = min(c+1, field[ny][nx])
    return


H, W = map(int, readline().split())
cy, cx = map(int, readline().split())
ey, ex = map(int, readline().split())
cy -= 1
cx -= 1
ey -= 1
ex -= 1

field = [list(readline().decode().rstrip()) for _ in range(H)]


field[cy][cx] = 0
for y in range(cy, H):
    for x in range(cx, W):
        if field[y][x] != '#' and field[y][x] != '.':
            dfs1(y, x, field[y][x])
            dfs2(y, x, field[y][x])

for y in range(cy):
    for x in range(cx):
        if field[y][x] != '#' and field[y][x] != '.':
            dfs1(y, x, field[y][x])
            dfs2(y, x, field[y][x])

print('-1' if field[ey][ex] == '.' else field[ey][ex])

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
def abc176d_wizard_in_maze():
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start[0] -= 1
    start[1] -= 1
    goal[0] -= 1
    goal[1] -= 1
    maze = []
    for i in range(h):
        maze.append(input())
    dp = [[float('inf')] * w for _ in range(h)]

    dp[start[0]][start[1]] = 0
    q = [start]

    while len(q) != 0:
        v = q.pop()
        x, y = v[0], v[1]
        check = False
        for dx, dy in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
            if 0 <= x + dx < h and 0 <= y + dy < w and maze[x + dx][y + dy] != '#' and dp[x][y] < dp[x + dx][y + dy]:
                dp[x + dx][y + dy] = dp[x][y]
                q.append([x + dx, y + dy])
                check = True
        if check: continue

        for dx in [-2, 1, 0, 1, 2]:
            if not 0 <= x + dx < h:
                continue
            for dy in [-2, 1, 0, 1, 2]:
                if 0 <= y + dy < w and maze[x + dx][y + dy] != '#' and dp[x][y] + 1 < dp[x + dx][y + dy]:
                    dp[x + dx][y + dy] = dp[x][y] + 1
                    q.append([x + dx, y + dy])

    if dp[goal[0]][goal[1]] == float('inf'):
        print('-1')
    else:
        print(dp[goal[0]][goal[1]])


abc176d_wizard_in_maze()

Submission status: Wrong Answer

Solution code:
from collections import deque
R,C = map(int, input().split())
sy,sx = map(int, input().split())
gy,gx = map(int, input().split())
sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
c = [input() for i in range(R)]
visited = [[-1]*C for _ in range(R)]
warp = [[0]*C for _ in range(R)]
visited[sy][sx] = 0
Q = deque([[sy,sx]])
while Q:
  y,x = Q.popleft()
  if [y,x] == [gy,gx]:
    print(warp[y][x])
    exit()
  for i,j in [(0,1),(1,0),(-1,0),(0,-1)]:
    if y+i >= R or y+i < 0 or x+j >= C or x+j < 0:
      continue
    if c[y+i][x+j] == '.' and visited[y+i][x+j] == -1:
      visited[y+i][x+j] = visited[y][x]+1
      warp[y+i][x+j] = warp[y][x]
      Q.append([y+i,x+j])
    elif c[y+i][x+j] == '#':
      for k,l in [(0,1),(1,0),(-1,0),(0,-1),(-1,-1),(1,1),(1,-1),(-1,1)]:

        if 0 <= y+i+k < R and 0 <=  x+j+l < C:
          if c[y+i+k][x+j+l] == '.' and visited[y+i+k][x+j+l] == -1 and warp[y+i+k][x+j+l] == 0:
            warp[y+i+k][x+j+l] = warp[y][x]+1
            visited[y+i+k][x+j+l] = 0
            if [y+i+k,x+j+l] == [gy,gx]:
              print(warp[gy][gx])
              exit()
            Q.append([y+i+k,x+j+l])
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())
    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,Flag):
        que = deque()
        que.append((x,y,Flag))

        while que:
            x,y,Flag = que.popleft()
            for dx in range(-2,3):
                for dy in range(-2,3):
                    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] == '.':
                        if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                            que.append((sx,sy,True))
                            S[sy][sx] = S[y][x]
                        else:
                            que.append((sx,sy,False))
                            S[sy][sx] = S[y][x] + 1
                    elif Flag:
                        continue
                    elif (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                        if S[sy][sx] > S[y][x]:
                            S[sy][sx] = S[y][x]
                            que.append((sx,sy,True))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy,False))
    bfs(Cw-1,Ch-1,True)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
  d = [[-1]*w for i in range(h)]
  
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]
  
  que = deque([])
  que.append((ch, cw))
  d[ch][cw] = 0
  
  while que:
    p = que.popleft()
    if p[0]==dh and p[1]==dw:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==-1:
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]]
      elif 0<=nx<h and 0<=ny<w and maze[nx][ny]=='#':
        for j in range(-2, 3):
          for k in range(-2, 3):
            nx = p[0] + j
            ny = p[1] + k
            if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==-1:
              que.append((nx, ny)) 
              d[nx][ny] = d[p[0]][p[1]]+1
              
              
  return d[dh][dw]
        
  
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
maze = [list(input()) for i in range(h)]

print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import stdin
input=stdin.readline
n,m=map(int,input().split())
a,b=map(int,input().split())
x,y=map(int,input().split())
x=x-1
y=y-1
arr=[]
from math import inf
for i in range(n):
    arr.append(list(input().strip()))
def isvalid(x,y):
    if x<0 or y<0 or x>=n or y>=m or arr[x][y]=="#" or vis[x][y]==1:
        return False
    return True
vis=[[0]*m for i in range(n)]
stack=deque([[a-1,b-1,0]])
vis[a-1][b-1]=1
mi=inf
while(stack):
    xx,yy,cost=stack.popleft()


    if xx==x and yy==y:
        mi=min(mi,cost)

    for i in range(-2,3,1):
        for j in range(-2, 3, 1):
            if isvalid(xx+i,yy+j):
                if -1<=i<=1 and -1<=j<=1 and i!=j:
                    vis[xx][yy] = 1
                    stack.append([xx+i,yy+j,cost])
                else:
                    vis[xx][yy] = 1
                    stack.append([xx + i, yy + j, cost+1])
if mi==inf:
    print(-1)
else:
    print(mi)

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

# S = [["." if j % 2 == 0 else "#" for j in range(W)] for i in range(H)]
# S[0][0] = "."
# S[DH-1][DW-1] = "."

# for i in range(H):
#     print(S[i])

from collections import deque

q = deque([(CH-1, CW-1)])

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
# 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)]

M = []
for i in range(H):
    M.append([10**9] * W)
M[CH-1][CW-1] = 0

# for i in range(H):
#     visited.append([False] * W)
# visited[CH-1][CW-1] = True

visited = deque([(CH-1, CW-1)])
while True:
    while q:
        h, w = q.popleft()
        for dh, dw in directions:
            if 0 <= h+dh < H and 0 <= w+dw < W and S[h+dh][w+dw] == ".":
                if M[h+dh][w+dw] > M[h][w]:
                    M[h+dh][w+dw] = M[h][w]
                    q.append((h+dh, w+dw))
                    visited.append((h+dh, w+dw))

    while visited:
        vh, vw = visited.popleft()
        for wh, ww in warp:
            if 0 <= vh+wh < H and 0 <= vw+ww < W and S[vh+wh][vw+ww] == ".":
                if M[vh+wh][vw+ww] > M[vh][vw] + 1:
                    M[vh+wh][vw+ww] = M[vh][vw] + 1
                    q.append((vh+wh, vw+ww))
    
    if len(q) == 0:
        break

# for i in range(H):
#     print(M[i])

if M[DH-1][DW-1] == 10**9:
    print(-1)
else:
    print(M[DH-1][DW-1])

Submission status: Wrong Answer

Solution code:
import collections, sys
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 = []
for i in range(h):
    s.append(list(input()))
s = np.array(s)
num = np.array([[float("inf") for i in range(w)] for i in range(h)])
flag = np.array([[False for i in range(w)] for i in range(h)])
num[ch - 1][cw - 1] = 0
queue = collections.deque([[ch, cw]])
d1 = np.array([[-1, 0], [1, 0], [0, -1], [0, 1]])
d2 = np.array([[-1, -1], [-1, 1], [1, -1], [1, 1], [-2, 0], [2, 0], [0, -2], [0, 2]])
d3 = np.array([[-2, -1], [-1, -2], [2, -1], [1, -2], [-2, 1], [-1, 2], [2, 1], [1, 2]])
d4 = np.array([[-2, -2], [-2, 2], [2, -2], [2, 2]])
while queue:
    test = queue.popleft()
    x = test[0]
    y = test[1]
    if flag[y - 1][x - 1] == True:
        continue
    flag[y - 1][x - 1] = True
    temp = num[y - 1][x - 1]
    for i in d1:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = temp
            queue.append([x2, y2])
    for i in d2:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([x2, y2])
    for i in d3:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([x2, y2])
    for i in d4:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == "." and flag[y2 - 1][x2 - 1] == False:
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([x2, y2])
if num[dh - 1][dw - 1] == float("inf"):
    print(-1)
else:
    print(int(num[dh - 1][dw - 1]))