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
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):
    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()
    if h == Dh and w == Dw:
        print(n)
        exit()
    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 abs(nh-h) > 2 or abs(nw-w) > 2:
            continue
        if dist[nh][nw] == -1:
            bfs(nh,nw,n+1)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

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

map_ = []
for hi in range(h):
    s = input()
    line = [None if s[wi] == "." else "#" for wi in range(w)]
    map_.append(line)        

#print(map_)

def umeru(x, y, cur_cost, cur_kabe):
    map_[y][x] = cur_cost
    global cur_kabes
    tonaris = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]

    for nx, ny in tonaris:
        if 0 <=nx<w and 0<=ny<h:
            if map_[ny][nx] is None:
                map_[ny][nx] = cur_cost
                umeru(nx, ny, cur_cost, cur_kabe)
            elif map_[ny][nx] == cur_kabe:
                #print((x, y), (nx, ny))
                #map_[ny][nx] -= 1
                map_[ny][nx] = "$"
                cur_kabes.append([nx, ny])

    tonaris = [[x-1, y-1], [x-1, y+1], [x+1, y-1], [x+1, y+1]]
    for nx, ny in tonaris:
        if 0 <=nx<w and 0<=ny<h:
            if map_[ny][nx] == cur_kabe:
                map_[ny][nx] = "$"
                cur_kabes.append([nx, ny])

def find_ins(x, y):
    tonaris = [[nx, ny] for nx in [x-1, x, x+1] for ny in [y-1, y, y+1]]
    ins = []
    
    for nx, ny in tonaris:
        if 0 <=nx<w and 0<=ny<h:
            if map_[ny][nx] is None:
                ins.append([nx, ny])
    return ins


                
                
ins = [[cw, ch]]
cur_cost = 0
cur_kabe = "#"
while True:
    cur_kabes = []
    for inw, inh in ins:
        umeru(inw, inh, cur_cost, cur_kabe)

    ins = []
    for x, y in cur_kabes:
        ins += find_ins(x, y)

    if len(ins) == 0:
        break
        
    cur_cost += 1
    #cur_kabe -= 1

if False:
    for m in map_:
        line = []
        for c in m:
            if c is None:
                c = "."
            elif isinstance(c, int):
                c = str(c)
            line.append(c)
        print("".join(line))

out = map_[dh][dw]
if out is None:
    out = -1
assert out >= -1
print(out)

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.pop()
    qq.append((xx, yy, kaisuu))
    visited[xx][yy] = True
    ls = []
    while qq:
        x, y, kaisuu = qq.pop()
        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))
            visited[x+1][y] = True
        if s[x-1][y] == '.' and visited[x-1][y] == False:
            qq.append((x-1, y, kaisuu))
            visited[x-1][y] = True
        if s[x][y+1] == '.' and visited[x][y+1] == False:
            qq.append((x, y+1, kaisuu))
            visited[x][y+1] = True
        if s[x][y-1] == '.' and visited[x][y-1] == False:
            qq.append((x, y-1, kaisuu))
            visited[x][y-1] = True
    for u in ls:
        a, b, c = u
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if i == 1 and j == 1:
                    continue
                if i == 1 and j == -1:
                    continue
                if i == -1 and j == 1:
                    continue
                if i == -1 and j == -1:
                    continue
                if s[a+i][b+j] == '.' and visited[a+i][b+j] == False:
                    q.append((a+i, b+j, c+1))
print(-1)

Submission status: Wrong Answer

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


def valid(a, b):
    return 0 <= a < n and 0 <= b < m


n, m = sp()
sx, sy = sp()
ex, ey = sp()
sx -= 1
sy -= 1
ex -= 1
ey -= 1
mat = [data() for i in range(n)]
answer = 10 ** 10
q = deque()
q.append([sx, sy])
x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
vis = [[0] * m for _ in range(n)]
vis[sx][sy] = 1
jump = [[answer] * m for _ in range(n)]
jump[sx][sy] = 0
while q:
    sx, sy = q.popleft()
    cnt = 0
    for i in range(4):
        tx, ty = sx + x[i], sy + y[i]
        if valid(tx, ty) and mat[tx][ty] == ".":
            if not vis[tx][ty]:
                q.append([tx, ty])
                vis[tx][ty] = 1
                cnt += 1
            jump[tx][ty] = min(jump[tx][ty], jump[sx][sy])
    if cnt == 0:
        for i in range(-2, 3):
            for j in range(-2, 3):
                tx, ty = sx + i, sy + j
                if valid(tx, ty) and mat[tx][ty] == ".":
                    if not vis[tx][ty]:
                        q.append([tx, ty])
                        vis[tx][ty] = 1
                    jump[tx][ty] = min(jump[tx][ty], jump[sx][sy]+1)
if jump[ex][ey] == 10 ** 10:
    print(-1)
    exit()
print(jump[ex][ey])

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

import queue
A = queue.Queue()
A.put((Ch-1, Cw-1))
q = queue.Queue()
c = queue.Queue()

for count in range(1000000):
  if A.qsize() == 0:
    break

  while A.qsize() > 0:
    q.put(A.get())

    while q.qsize() > 0:
      i, j = q.get()
      if S[i][j] == '.':
        S[i][j] = count
      else:
        continue

      if i >= 1:
        ni, nj = i-1, j
        if S[ni][nj] == '.':
          q.put((ni, nj))
        elif S[ni][nj] == '#':
          c.put((i, j))
      if j >= 1:
        ni, nj = i, j-1
        if S[ni][nj] == '.':
          q.put((ni, nj))
        elif S[ni][nj] == '#':
          c.put((i, j))
      if i <= H-2:
        ni, nj = i+1, j
        if S[ni][nj] == '.':
          q.put((ni, nj))
        elif S[ni][nj] == '#':
          c.put((i, j))
      if j <= W-2:
        ni, nj = i, j+1
        if S[ni][nj] == '.':
          q.put((ni, nj))
        elif S[ni][nj] == '#':
          c.put((i, j))
  # for l in S:
  #   print(l)
  # print()

  while c.qsize() > 0:
    i, j = c.get()
    for ni in range(i-2, i+3):
      for nj in range(j-2, j+3):
        if ni >= 0 and ni < H and nj >= 0 and nj < W and S[ni][nj] == '.':
          A.put((ni, nj))

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
S = [list(input()) for _ in range(H)]

stamp = [[-1 for _ in range(W)] for _ in range(H)]
dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
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]]
cnt = 0

def search(x,y):
  if x == gx-1 and y == gy-1:
    print(cnt)
    sys.exit()
  if x < 0 or H-1 < x or y < 0 or W-1 < y or stamp[x][y] != -1:
    return
  elif S[x][y] == "#":
    stamp[x][y] = 0
    return
  stamp[x][y] = 0
  for dx, dy in dxdy:
    search(x+dx,y+dy)
  return

x, y = sx-1, sy-1
search(x,y)

check = True
for _ in range(10**3):
  cnt += 1
  for dx, dy in warp:
    if x+dx < 0 or H-1 < x+dx or y+dy < 0 or W-1 < y+dy:
      continue
    elif stamp[x+dx][y+dy] == -1:
      x = x+dx
      y = y+dy
      search(x,y)

print(-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:
            continue
        flag = 0
        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 += 1
                else:
                    flag += 1
        if flag>=2:
            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] > dist[h][w] + 1:
                        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:
from collections import deque
import sys
sys.setrecursionlimit(10**8)

def main():
    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 = [list(input()) for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    visited[Ch][Cw] = True
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.pop()
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if visited[nh][nw] == False:
                    cnt[nh][nw] = cnt[h][w]
                    visited[nh][nw] = True
                    Q.append([nh,nw])
                else:
                    if cnt[nh][nw] > cnt[h][w]:
                        cnt[nh][nw] = cnt[h][w]
                        Q.append([nh,nw])
        for j in range(-2,3):
            for k in range(-2,3):
                nh = h + j
                nw = w + k
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if cnt[nh][nw] > cnt[h][w]:
                        cnt[nh][nw] = cnt[h][w] + 1
                        visited[nh][nw] = True
                        Q.append([nh,nw])

    if cnt[Dh][Dw] == float('inf'):
        print(-1)
    else:
        print(cnt[Dh][Dw])




if __name__ == "__main__":
    main()

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

for i in range(h):
    s.append(list(str(input())))



currentH = ch - 1
currentW = cw - 1
warpCount = 0
errorH = False
errorW = False
while dh - 1 != currentH and dw - 1 != currentW and (errorH == False or errorW == False):
    #縦
    hSize = dh - ch
    if hSize < 0:
        moveH = -1
    else:
        moveH = 1
    while dh - 1 != currentH:
        if s[currentH + moveH][currentW] == "#":
            if 2 <= abs(dh - 1 - currentH):
                if s[currentH + moveH * 2][currentW] == ".":
                    currentH += moveH * 2
                    warpCount += 1
                else:
                    errorH = True
                    break
            else:
                errorH = True
                break
        else:
            currentH += moveH
        #print(currentH, currentW)
        errorW = False

    #横
    wSize = dw - cw
    if wSize < 0:
        moveW = -1
    else:
        moveW = 1
    while dw - 1 != currentW:
        if s[currentH][currentW + moveW] == "#":
            if 2 <= abs(dw - 1 - currentW):
                if s[currentH][currentW + moveW * 2] == ".":
                    currentW += moveW * 2
                    warpCount += 1
                else:
                    errorW = True
                    break
            else:
                errorW = True
                break
        else:
            currentW += moveW
        #print(currentH, currentW)
        errorH == False

if errorH == True and errorW == True:
    warpCount = -1

print(warpCount)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
        
    s[y][x]='#'
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i:
                continue
            if x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]!='#':
                nxt.append([y+i,x+j,now+1])
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        rcl(y+yy,x+xx,now)

for _ in range(250):
    for i in nxt:
        if i[0]==dh and i[1]==dw:
            print(i[2])
            exit()
        rcl(i[0],i[1],i[2])

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
inf = float('inf')
graph = []
for _ in range(H):
    g = input()
    graph.append(g)
    
def get_near(vh, vw):
    next_list = []
    for h, w in [[vh, vw + 1], [vh, vw - 1], [vh - 1, vw], [vh + 1, vw]]:
        if (0 <= h < H) & (0 <= w < W):
                    next_list.append([h, w])
    return next_list

def get_far(vh, vw):
    next_list = []
    for h in range(vh - 2, vh + 3):
        for w in range(vw - 2, vw + 3):
            if 0 <= h < H:
                if 0 <= w < W:
                    next_list.append([h, w])
    return next_list


from collections import deque
path = [[-1 for _ in range(W)] for _ in range(H)]
checked = [[False for _ in range(W)] for _ in range(H)]
d = deque([[ch, cw]])
path[ch][cw] = 0
checked[ch][cw] = True
while d:
    vh, vw = d.popleft()
    checked[vh][vw] = True
    for h, w in get_near(vh, vw):
        if not checked[h][w]:
            checked[h][w] =True
            if (graph[h][w] != '#') & (path[h][w] == -1):
                path[h][w] = path[vh][vw]
                d.append([h, w])
    if not d:
        for vh in range(H):
            for vw in range(W):
                if not checked[vh][vw]:
                    for h, w in get_far(vh, vw):
                        if (path[h][w] != -1) & (graph[h][w] != '#') & (graph[vh][vw] != '#'):
                            d.append([vh, vw])
                            path[vh][vw] = path[h][w] + 1                            
                            break
                    if graph[vh][vw] == '#':
                        checked[vh][vw] = True
ans = path[dh][dw]
if ans == inf:
    print(-1)
else:
    print(ans)

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=[list('#' for i in range(W+2)) for j in range(H+2)]
for i in range(1, H+1):
    for j in range(1, W+1):
        S[i][j]=s[i-1][j-1]
counter=0
h,w=Ch,Cw       
while h!=Dh or w!=Dw:
    flag1=False
    flag2=False
    #check to walk closer to C from current position
    if Dh<h and S[h-1][w]=='.':
        h-=1
        flag1=True
    elif Dh>h and S[h+1][w]=='.':
        h+=1
        flag1=True
    elif Dw<w and S[h][w-1]=='.':
        w-=1
        flag1=True
    elif Dw>w and S[h][w+1]=='.':
        w+=1
        flag1=True
    else:
        #use 2nd magic
        for i in range(h-2, h+3):
            for j in range(w-2, w+3):
                if i==Dh and j==Dw:
                    h=Dh
                    w=Dw
                    flag2=True
                    counter+=1
                    break
                elif i!=h and j!=w and abs(i-h)+abs(j-w)>=abs(i-Dh)+abs(j-Dw) and S[i][j]=='.':
                    #move to (i,j) with the magic
                    h=i
                    w=j
                    flag2=True
                    counter+=1
                    break
            if flag2:
                break
    if flag1 == False and flag2 == False:
        counter=-1
        break
print(counter)

Submission status: Wrong Answer

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


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = [[None]*W for _ in range(H)]
  now = set()
  d[sh][sw]=0
  
  while queue:
    h,w = queue.popleft()
    now.add((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
      queue.append((nh,nw))
      now.add((nh,nw))
      d[nh][nw]=d[h][w]

    if queue: continue
    for h,w in now:
      for i,j in [(h-2,w-2),(h-2,w-1),(h-2,w),(h-2,w+1),(h-2,w+2),(h-1,w-2),(h-1,w-1),(h-1,w+1),(h-1,w+2),(h,w-2),(h,w+2),(h+1,w-2),(h+1,w-1),(h+1,w+1),(h+1,w+2),(h+2,w-2),(h+2,w-1),(h+2,w),(h+2,w+1),(h+2,w+2)]:
        if i==0 and abs(j)<=1: continue
        if j == 0 and abs(i)<=1: continue
        nh,nw = h-i,w-j
        if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
        d[nh][nw] = d[h][w]+1
        queue.append((nh,nw))
    now = set()
    #print(queue)
  return d

d = bfs(Ch,Cw)
if d[Dh][Dw] == None: 
  print(-1)
  exit()
print(d[Dh][Dw])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[deepcopy(num) for i in range(W)] for j in range(H)]
    
move1 = [[1,0],[0,1],[-1,0],[0,-1]]
move2 = [[i,j] for i in range(-2, 3) for j in range(-2, 3) if i != 0 and j != 0]

def main():
    shift = 10000
    H, W = MI()
    sx, sy = MI()
    gx, gy = MI()
    sx -= 1
    sy -= 1
    gx -= 1
    gy -= 1
    D = Init(H, W, -1)
    D2 = defaultdict(lambda: [])
    mylist = [input().rstrip() for i in range(H)]
    index = 0
    start_index = -1
    g_index = -1

    for i in range(H):
        for j in range(W):
            if mylist[i][j] == "." and D[i][j] == -1:
                dq = deque()
                dq.append([i,j])
                D[i][j] = 1
                while dq:
                    x, y = dq.popleft()
                    if x == sx and y == sy:
                        start_index = index
                    elif x == gx and y == gy:
                        g_index = index
                    for x2, y2 in move1:
                        x2 += x
                        y2 += y
                        if x2 >= 0 and y2 >= 0 and x2 < H and y2 < W and mylist[x2][y2] == "." and D[x2][y2] == -1:
                            dq.append([x2, y2])
                            D[x2][y2] = 1
                            D2[index].append(x2*shift + y2)
                index+=1
    if start_index == g_index:
        print(0)
        sys.exit()

    dq = deque()
    dq.append(start_index)
    D3 = defaultdict(lambda: float('inf'))
    D3[start_index] = 0
    
    while dq:
        temp_index = dq.popleft()
        if temp_index == g_index:
            print(D3[g_index])
            sys.exit()
        for i in D2[temp_index]:
            x = i // shift
            y = i % shift
            for j in D2.keys():
                if D3[j] != float('inf'):
                    continue
                for x2, y2 in move2:
                    x2 += x
                    y2 += y
                    temp3 = x2*shift+y2
                    if temp3 in D2[j]:
                        D3[j] = D3[temp_index]+1
                        dq.append(j)
                        break
    res = D3[g_index]
    if res == float('inf'):
        print(-1)
    else:
        print(res)


        

        
        


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

move = [[0,1], [0,-1], [1,0], [-1,0]]

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

s =[[-1 for j in range(w+4)] for i in range(h+4)]
for i in range(h):
  a = input()
  for j in range(2, w+2):
    s[i+2][j] = w*h+1 if a[j-2]=='.' else -1

    
#for i in s:
#  print(i)
q1 = deque([[ch,cw]])
s[ch][cw] = 0
while(s[dh][dw] == w*h+1 and q1):
  q2 = q1.copy()
  while q1:
    now = q1.popleft()
    nows = s[now[0]][now[1]]
    for m in move:
      nh, nw = now[0]+m[0], now[1]+m[1]
      if(s[nh][nw] == -1):
        continue
      elif(s[nh][nw] > nows):
        s[nh][nw] = nows
        q1.append([nh, nw])
        q2.append([nh, nw])
 
  if(s[dh][dw] != w*h+1):
    break
    
  while q2:
    now = q2.popleft()
    nows = s[now[0]][now[1]]
    f = False
    for m in move:
      nh, nw = now[0]+m[0], now[1]+m[1]
      if(s[nh][nw] == -1):
        f = True
        break
    if(not f):
      break
    
    
    for i in range(-2,3):
      for j in range(-2,3):
        nh, nw = now[0]+i, now[1]+j
        if(s[nh][nw] == -1):
          continue
        elif(s[nh][nw] > nows+1):
          s[nh][nw] = nows+1
          q1.append([nh, nw])

if(s[dh][dw] == w*h+1):
  print(-1)
else:
  print(s[dh][dw])

Submission status: Wrong Answer

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