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, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

H, W = nn()
Ch, Cw = nn()
Dh, Dw = nn()
S = sm(H)

T = [u"#"*(W+4)] * 2
for s in S:
    T.append("##" + s[0] + "##")
T += [u"#"*(W+4)] * 2

H += 4
W += 4
Ch += 2 - 1
Cw += 2 - 1
Dh += 2 - 1
Dw += 2 - 1

deq1 = deque()
deq1.append((Ch, Cw))
deq2 = deque()

cnt = 0

memo = array2(H, W, 9)
memo[Ch][Cw] = 0

for i in range(10**6):
    #pprint(T)
    #pprint(memo)
    #print("-"*30 + "\n")

    if len(deq1) == 0:
        print(-1)
        exit(0)

    while len(deq1) > 0:
        h, w = deq1.pop()

        if h == Dh and w == Dw:
            print(i)
            exit(0)

        def sch(x, y, i):
            #print(x, y, T[x][y])
            if T[x][y] == "." and i < memo[x][y]:
                memo[x][y] = i
                deq1.append((x, y))

        sch(h+1, w, i)
        sch(h-1, w, i)
        sch(h, w+1, i)
        sch(h, w-1, i)

    for j in range(H):
        for k in range(W):
            if memo[j][k] == i:
                for l in range(-2, 3):
                    for m in range(-2, 3):
                        if T[j+l][k+m] == "." and i + 1 < memo[j+l][k+m]:
                            memo[j+l][k+m] = i + 1
                            deq2.append((j+l, k+m))

    deq1 = deq2
    deq2 = deque()

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

H, W = map(int, input().split())
ori = list(map(int, input().split()))
dis = list(map(int, input().split()))
S = [0] * H
for i in range(H):
    S[i] = input()

D = 10 ** 7

def co_num(h, w):
    return h * W + w

row = []
col = []
dist = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '#': continue
        for hh in range(3):
            if not 0 <= h + hh < H: continue
            for ww in range(-2, 3):
                if not (0 <= h + hh < H and 0 <= w + ww < W): continue
                if hh == ww == 0: continue
                if S[h+hh][w+ww] == '#': continue
                if abs(hh) + abs(ww) == 1:
                    d = 1
                else:
                    d = D
                row.append(co_num(h, w))
                col.append(co_num(h+hh, w+ww))
                dist.append(d)
                
d = dijkstra(csr_matrix((dist, (row, col)), shape=[H*W, H*W]), directed=True, indices=co_num(ori[0]-1, ori[1]-1))

if d[co_num(dis[0]-1, dis[1]-1)] == np.inf:
    print(-1)
else:
    print(int(d[co_num(dis[0]-1, dis[1]-1)] // D))

# d.reshape([H, W])

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int,input().split())
sx,sy = map(int,input().split())
sx -= 1
sy -= 1
gx,gy = map(int,input().split())
gx -= 1
gy -= 1

field = []
d = [[float("inf")]*w for i in range(h)]
for i in range(h):
    c = list(input())
    field.append(c)
 

que = deque([])
que.append((sx,sy))
d[sx][sy] = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
 
while len(que) > 0:
    p = que.popleft()
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == float("inf"):
            if field[nx][ny] == "#":
                for x in range(-2,3):
                    for y in range(-2,3):
                        try:
                            d[nx+x][ny+y] = d[p[0]][p[1]] + 1
                            que.append((nx,ny))
                        except IndexError:
                            continue
            else:
                d[nx][ny] = d[p[0]][p[1]]
                que.appendleft((nx,ny))
if d[gx][gy] == float("inf"):
    print(-1)
else:
    print(d[gx][gy])

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())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
q=deque()
q.append(s)
d={s:0}
while q:
    y,x=q.popleft()
    flg=False
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
            elif d[(ny,nx)]>d[(y,x)]:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
        else:
            flg=True
    if flg:
        for dy,dx in [(-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)]:
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if m[ny][nx]=='.':
                if (ny,nx) not in d and (ny-1,nx) not in d and (ny,nx-1) not in d and (ny+1,nx) not in d and (ny+1,nx) not in d:
                    q.append((ny,nx))
                    d[(ny,nx)]=d[(y,x)]+1
                    break
                elif (ny,nx) in d and d[(ny,nx)]>d[(y,x)]+1:
                    q.append((ny,nx))
                    d[(ny,nx)]=d[(y,x)]+1
if g in d:
    print(d[g])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
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
    m = [[0]*(w+4)]
    m.append([0]*(w+4))
    for i in range(h):
        s = input()
        temp = [0,0]
        for j in s:
            if j == ".":
                temp.append(1)
            else:
                temp.append(0)
        temp.append(0)
        temp.append(0)
        m.append(temp)
    m.append([0]*(w+4))
    m.append([0]*(w+4))

    t = [[1000000]*(w+4) for _ in range(h+4)]


    queue = deque([(ch,cw,0)])
    t[ch][cw] = 0
    
    while(len(queue) > 0):
        q = queue.popleft()
        nh = q[0]
        nw = q[1]
        dir = [(1,0),(-1,0),(0,1),(0,-1)]
        
        for d in dir:
            if m[nh + d[0]][nw + d[1]] == 1 and t[nh + d[0]][nw + d[1]] > q[2]:
                queue.appendleft((nh + d[0] , nw + d[1], q[2]))
                t[nh + d[0]][nw + d[1]] = q[2]

        dir = [(1,1),(-1,1),(-1,-1),(1,-1),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-2,1),(2,1),(-2,0),(2,0),(-2,-1),(2,-1),(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2)]

        for d in dir:
            if m[nh + d[0]][nw + d[1]] == 1 and t[nh + d[0]][nw + d[1]] > q[2]+1:
                queue.append((nh + d[0] , nw + d[1], q[2] + 1))
                t[nh + d[0]][nw + d[1]] = q[2]+1
        

    print(t[dh][dw] if t[dh][dw] != 10000 else -1)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [list(input().rstrip()) for _ in range(H)]

dir_h = [0, 0, 1, -1]
dir_w = [1, -1, 0, 0]

seen = [[-1 for _ in range(W)] for _ in range(H)]
edge = []
nex = [[ch - 1, cw - 1]]
num = 0


def bfs():
    q = deque([])

    for h, w in nex:
        q.append([h, w])
        seen[h][w] = num
        while q:
            h, w = q.popleft()

            for dh, dw in zip(dir_h, dir_w):
                nh, nw = h + dh, w + dw

                if nh < 0 or nh >= H or nw < 0 or nw >= W:
                    continue
                elif S[nh][nw] == "#":
                    edge.append([h, w])
                    continue
                elif seen[nh][nw] != -1:
                    continue
                else:
                    seen[nh][nw] = num
                    q.append([nh, nw])


def dfs():
    d = deque([])
    for h, w in edge:
        d.append([h, w])

        while d:
            h, w = d.pop()
            num = seen[h][w]
            for dh in range(1, 3):
                for dw in range(1, 3):
                    nh, nw = h + dh, w + dw

                    if nh < 0 or nh >= H or nw < 0 or nw >= W:
                        continue
                    elif S[nh][nw] == "#":
                        continue
                    elif seen[nh][nw] != -1:
                        continue
                    else:
                        seen[nh][nw] = min(num, seen[nh][nw])
                        nex.append([nh, nw])


while True:
    bfs()
    nex = []
    num += 1
    dfs()
    if not edge:
        break
    edge = []

# for s in seen:
#     print(s)

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

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
smat=[]
smat.append([False]*(W+4))
smat.append([False]*(W+4))
for _ in range(H):
  line=[False,False]+[x=="." for x in input()]+[False,False]
  smat.append(line)
smat.append([False]*(W+4))
smat.append([False]*(W+4))
#print(smat)

from collections import defaultdict
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist,prev={},{}
  used=set()
  for v in vlist:
    dist[v]=float("inf")
    prev[v]=-1
  dist[s]=0
  used.add(s)

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if min_v in used:
      continue

    dist[min_v]=min_w
    prev[min_v]=u
    used.add(min_v)
    for v,w in graph[min_v]:
      if not v in used:
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

vlist=[]
#ここで点の集合をvlistに入れておく
for i in range(2,H+2):
  for j in range(2,W+2):
    if smat[i][j]:
      vlist.append((i,j))

graph=defaultdict(list)
#graph[i]: iから出る道の[重み,行先]の辞書
for i in range(2,H+2):
  for j in range(2,W+2):
    if not smat[i][j]:
      continue
    
    if smat[i-1][j]:
      graph[(i,j)].append([(i-1,j),0])
    else:
      graph[(i,j)].append([(i-2,j),1])
    if smat[i+1][j]:
      graph[(i,j)].append([(i+1,j),0])
    else:
      graph[(i,j)].append([(i+2,j),1])
    if smat[i][j-1]:
      graph[(i,j)].append([(i,j-1),0])
    else:
      graph[(i,j)].append([(i,j+2),1])
    if smat[i][j+1]:
      graph[(i,j)].append([(i,j+1),0])
    else:
      graph[(i,j)].append([(i,j+2),1])
    
    if not smat[i-1][j] and not smat[i][j-1] and smat[i-1][j-1]:
      graph[(i,j)].append([(i-1,j-1),1])
    if not smat[i-1][j] and not smat[i][j+1] and smat[i-1][j+1]:
      graph[(i,j)].append([(i-1,j+1),1])
    if not smat[i+1][j] and not smat[i][j-1] and smat[i+1][j-1]:
      graph[(i,j)].append([(i+1,j-1),1])
    if not smat[i+1][j] and not smat[i][j+1] and smat[i+1][j+1]:
      graph[(i,j)].append([(i+1,j+1),1])

    for k in range(-2,3):
      if k==0:
        continue
      if smat[i-2][j+k]:
        graph[(i,j)].append([(i-2,j+k),1])
      if smat[i+2][j+k]:
        graph[(i,j)].append([(i+2,j+k),1])
        
    for k in range(-1,2,2):
      if smat[i+k][j-2]:
        graph[(i,j)].append([(i+k,j-2),1])
      if smat[i+k][j+2]:
        graph[(i,j)].append([(i+k,j+2),1])

dist,prev=dijkstra_heap((Ch+1,Cw+1))
#print(dist)
#print(prev)

if dist[(Dh+1,Dw+1)]==float("inf"):
  print(-1)
else:
  print(dist[(Dh+1,Dw+1)])

Submission status: Wrong Answer

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

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

while not next.empty():
    i, j, now = next.get()
    now = dp[i][j]
    visited[i][j] = 1

    for k, l in [[i-1, j], [i, j-1], [i+1, j], [i, j+1]]:
        if 0 <= k < h and 0 <= l < w and visited[k][l] == 0:
            if s[k][l] == ".":
                dp[k][l] = min(dp[k][l], now)
            next.put([k, l, now])
            visited[k][l] = 1

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

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

Submission status: Wrong Answer

Solution code:
def main():
	inf=10**9
	h,w=map(int,input().split())
	a,b=map(int,input().split())
	c,d=map(int,input().split())
	s=[input() for _ in range(h)]
	cnt=[[inf]*w for _ in range(h)]
	LIS=((-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[a-1][b-1]=0
	new_stack=[(a-1,b-1)]
	for i in range(h+w):
		if len(new_stack)==0:
			break
		lis=[]
		stack=new_stack.copy()
		new_stack=[]
		while stack:
			r=stack.pop()
			lis.append(r)
			x,y=r[0],r[1]
			for dx,dy in ((-1,0),(0,1),(1,0),(0,-1)):
				if 0<=x+dx<h and 0<=y+dy<w:
					if s[x+dx][y+dy]=="." and cnt[x+dx][y+dy]==inf:
						cnt[x+dx][y+dy]=i
						stack.append((x+dx,y+dy))
		for x,y in lis:
			for dx,dy in LIS:
				if 0<=x+dx<h and 0<=y+dy<w:
					if s[x+dx][y+dy]=="." and cnt[x+dx][y+dy]==inf:
						cnt[x+dx][y+dy]=i+1
						new_stack.append((x+dx,y+dy))		
	print(cnt[c-1][d-1] if cnt[c-1][d-1]!=inf else -1)
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq as hq
import functools, collections
import math, random
from collections import Counter, defaultdict
import threading

threading.stack_size(2**27)
sys.setrecursionlimit(10**6 + 5)

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def dijkstra(G, s):
    n = len(G)
    visited = [False]*n
    weights = [math.inf]*n
    path = [None]*n
    queue = []
    weights[s] = 0
    hq.heappush(queue, (0, s))
    while len(queue) > 0:
        g, u = hq.heappop(queue)
        visited[u] = True
        for v, w in G[u]:
            if not visited[v]:
                f = g + w
                if f < weights[v]:
                    weights[v] = f
                    path[v] = u
                    hq.heappush(queue, (f, v))
    return path, weights


def solve(grid, sx, sy, ex, ey):  # fix inputs here
    console("----- solving ------")

    grid = [[0 if cell == "#" else 1 for cell in row] for row in grid]
    grid = [[0] * len(grid[0])]*2 + grid + [[0] * len(grid[0])]*2
    grid = [[0,0] + row + [0,0] for row in grid]
    sx, sy, ex, ey = sx+1, sy+1, ex+1, ey+1

    labels = [[False for _ in row] for row in grid]
    diffs = [(-1,0), (1,0), (0,-1), (0,1)]

    g = defaultdict(set)

    @functools.lru_cache(maxsize=None)
    def dfs(x,y,cur_label):
        for dx,dy in diffs:
            xx, yy = x+dx, y+dy
            if labels[xx][yy]:
                continue
            if grid[xx][yy] == 0:
                continue
            labels[xx][yy] = cur_label
            dfs(xx,yy,cur_label)

    cur_label = 0
    for i,row in enumerate(grid):
        for j,cell in enumerate(row):
            if labels[i][j]:
                continue
            if cell == 0:
                continue
            cur_label += 1
            labels[i][j] = cur_label
            dfs(i,j,cur_label)
            
    console("label")
    console(labels)


    start = labels[sx][sy]
    end = labels[ex][ey]
    console("start and end", start, end)
    if start == end:
        return 0

    connections = defaultdict(set)

    for i,row in enumerate(grid):
        for j,cell in enumerate(row):
            if cell == 0:
                continue
            for dx in [-2,-1,0,1,2]:
                for dy in [-2,-1,0,1,2]:
                    if labels[i][j] != False and labels[i+dx][j+dy] != False:
                        if labels[i][j] != labels[i+dx][j+dy]:
                            connections[labels[i][j]].add(labels[i+dx][j+dy])
                            connections[labels[i+dx][j+dy]].add(labels[i][j])

    console("connections", connections)

    G = [[] for _ in range(cur_label+1)]

    for k,lst in connections.items():
        G[k].extend([(x,1) for x in lst])

    console("G", G)

    _, result = dijkstra(G, start)
    
    console("result", result)

    if result[end] > 10**4:
        return -1
    return result[end]



def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

def main():
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    nrows, w = list(map(int,input().split()))
    sx, sy = list(map(int,input().split()))
    ex, ey = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for _ in range(nrows):
        grid.append(list(input()))

    res = solve(grid, sx, sy, ex, ey)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

t = threading.Thread(target=main)
t.start()
t.join()

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w = m()

c = l()

d = l()

s = [list(input()[:-1]) for i in range(h)]

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

po = [cl.deque([]) for i in range(h+w+1)]

now = 0
po[0] = cl.deque([[c[0]-1,c[1]-1]])
d[0] -= 1
d[1] -= 1
dire = [[1,0],[0,1],[-1,0],[0,-1]]

#data[c[0]-1][c[1]-1] = 0
while True:
    if now >= h+w+1:
        break
    if len(po[now]) == 0:
        now += 1
        continue
    else:
        popo = po[now].popleft()
        if data[popo[0]][popo[1]] != -1 and data[popo[0]][popo[1]] < now:
            continue
        else:
            data[popo[0]][popo[1]] = now
            for kkk in dire:
                if (popo[0] + kkk[0] >= 0 and popo[0] + kkk[0] < h) and (popo[1] + kkk[1] >= 0 and popo[1] + kkk[1] < w):
                    if s[popo[0] + kkk[0]][popo[1] + kkk[1]] == "#":
                        continue
                    if data[popo[0] + kkk[0]][popo[1] + kkk[1]] == -1 or data[popo[0] + kkk[0]][popo[1] + kkk[1]] > now:
                        data[popo[0] + kkk[0]][popo[1] + kkk[1]] = now
                        po[now].append([popo[0]+ kkk[0],popo[1] + kkk[1]])

            for i in range(5):
                i -= 2
                if i + popo[0] < 0 or i + popo[0] >= h:
                    continue
                for j in range(5):
                    j -= 2
                    if j + popo[1] < 0 or j + popo[1] >= w:
                        continue
                    elif s[popo[0]+ i][popo[1] + j] == ".":
                        if data[popo[0]+ i][popo[1] + j] > now+1 or data[popo[0]+ i][popo[1] + j] == -1:
                            if now + 1 <= h+w:
                                data[popo[0]+ i][popo[1] + j] = now+1
                                po[now+1].append([popo[0]+ i,popo[1] + j])


print(data[d[0]][d[1]])

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
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 TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	Q=deque()
	Q.append([ch,cw,0])

	while Q:
		x,y,d=Q.popleft()
		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				Q.append([x+xx,y+yy,d])
			elif S[x+xx][y+yy]=="#":
				for t in [-2,-1,0,1,2]:
					if xx==0:
						if S[x+t][y+2*yy]==".":
							S[x+t][y+2*yy]=d+1
							Q.append([x+t,y+2*yy,d+1])
						elif S[x+t][y+2*yy]=="#":
							continue
						elif S[x+t][y+2*yy]>d+1:
							S[x+t][y+2*yy]=d+1
							Q.append([x+t,y+2*yy,d+1])
					else:
						if S[x+2*xx][y+t]==".":
							S[x+2*xx][y+t]=d+1
							Q.append([x+2*xx,y+t,d+1])
						elif S[x+2*xx][y+t]=="#":
							continue
						elif S[x+2*xx][y+t]>d+1:
							S[x+2*xx][y+t]=d+1
							Q.append([x+2*xx,y+t,d+1])
			elif S[x+xx][y+yy]==d:
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				Q.append([x+xx,y+yy,d])
			else:
				S[x][y]=S[x+xx][y+yy]
				Q.append([x,y,S[x+xx][y+yy]])

	print(-1 if S[dh][dw]=="." else S[dh][dw])


























if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

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


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)

Submission status: 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
S=[['X']*(W+4) for _ in range(2)]+['XX'+input()+'XX' for _ in range(H)]+[['X']*(W+4) for _ in range(2)]
T=[[-2]*(W+4) for _ in range(H+4)]

from collections import deque
q0=deque()
q0.append([Ch, Cw])
T[Ch][Cw]=0
q1=deque()
q1.append([Ch, Cw])

while T[Dh][Dw]==-2 and len(q0)>0:  
  while q0:
    a, b=q0.popleft()
    if T[a-1][b]==-2 and S[a-1][b]=='.':
      q0.append([a-1, b])
      q1.append([a-1, b])
      T[a-1][b]=T[a][b]+0
    if T[a+1][b]==-2 and S[a+1][b]=='.':
      q0.append([a+1, b])
      q1.append([a+1, b])
      T[a+1][b]=T[a][b]+0
    if T[a][b-1]==-2 and S[a][b-1]=='.':
      q0.append([a, b-1])
      q1.append([a, b-1])
      T[a][b-1]=T[a][b]+0
    if T[a][b+1]==-2 and S[a][b+1]=='.':
      q0.append([a, b+1])
      q1.append([a, b+1])
      T[a][b+1]=T[a][b]+0
  while q1:
    a, b=q1.popleft()
    if T[a-2][b-2]==-2 and S[a-2][b-2]=='.':
      q0.append([a-2, b-2])
      T[a-2][b-2]=T[a][b]+1
    if T[a-2][b-1]==-2 and S[a-2][b-1]=='.':
      q0.append([a-2, b-1])
      T[a-2][b-1]=T[a][b]+1
    if T[a-2][b]==-2 and S[a-2][b]=='.':
      q0.append([a-2, b])
      T[a-2][b]=T[a][b]+1
    if T[a-2][b+1]==-2 and S[a-2][b+1]=='.':
      q0.append([a-2, b+1])
      T[a-2][b+1]=T[a][b]+1
    if T[a-2][b+2]==-2 and S[a-2][b+2]=='.':
      q0.append([a-2, b+2])
      T[a-2][b+2]=T[a][b]+1
    if T[a-1][b-2]==-2 and S[a-1][b-2]=='.':
      q0.append([a-1, b-2])
      T[a-1][b-2]=T[a][b]+1
    if T[a-1][b-1]==-2 and S[a-1][b-1]=='.':
      q0.append([a-1, b-1])
      T[a-1][b-1]=T[a][b]+1
    if T[a-1][b+1]==-2 and S[a-1][b+1]=='.':
      q0.append([a-1, b+1])
      T[a-1][b+1]=T[a][b]+1
    if T[a-1][b+2]==-2 and S[a-1][b+2]=='.':
      q0.append([a-1, b+2])
      T[a-1][b+2]=T[a][b]+1
    if T[a][b-2]==-2 and S[a][b-2]=='.':
      q0.append([a, b-2])
      T[a][b-2]=T[a][b]+1
    if T[a][b+2]==-2 and S[a][b+2]=='.':
      q0.append([a, b+2])
      T[a][b+2]=T[a][b]+1
    if T[a+1][b-2]==-2 and S[a+1][b-2]=='.':
      q0.append([a+1, b-2])
      T[a+1][b-2]=T[a][b]+1
    if T[a+1][b-1]==-2 and S[a+1][b-1]=='.':
      q0.append([a+1, b-1])
      T[a+1][b-1]=T[a][b]+1
    if T[a+1][b+1]==-2 and S[a+1][b+1]=='.':
      q0.append([a+1, b+1])
      T[a+1][b+1]=T[a][b]+1
    if T[a+1][b+2]==-2 and S[a+1][b+2]=='.':
      q0.append([a+1, b+2])
      T[a+1][b+2]=T[a][b]+1
    if T[a+2][b-2]==-2 and S[a+2][b-2]=='.':
      q0.append([a+2, b-2])
      T[a+2][b-2]=T[a][b]+1
    if T[a+2][b-1]==-2 and S[a+2][b-1]=='.':
      q0.append([a+2, b-1])
      T[a+2][b-1]=T[a][b]+1
    if T[a+2][b]==-2 and S[a+2][b]=='.':
      q0.append([a+2, b])
      T[a+2][b]=T[a][b]+1
    if T[a+2][b+1]==-2 and S[a+2][b+1]=='.':
      q0.append([a+2, b+1])
      T[a+2][b+1]=T[a][b]+1
    if T[a+2][b+2]==-2 and S[a+2][b+2]=='.':
      q0.append([a+2, b+2])
      T[a+2][b+2]=T[a][b]+1
      
    
if T[Dh][Dw]>-1:
  print(T[Dh][Dw])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  H,W=LI()
  Ch,Cw=LI()
  Dh,Dw=LI()
  Ch-=1
  Cw-=1
  Dh-=1
  Dw-=1
  field=[S() for _ in range(H)]

  q=collections.deque()
  q.append((Ch,Cw,0))
  ans=[[inf]*W for _ in range(H)]
  while q:
    # for x in ans:
    #   print(x)
    # print()
    y,x,cnt=q.popleft()
    if ans[y][x]<=cnt:
      continue
    ans[y][x]=cnt
    if y==Dh and x==Dw:
      continue

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny<H and 0<=nx<W:
        if field[ny][nx]=='.':
          q.append((ny,nx,cnt))
        else:
          if dy==1 and dx==0:
            for i in range(1,2):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q.append((nny,nnx,cnt+1))
          elif dy==0 and dx==1:
            for i in range(-2,3):
              for j in range(1,2):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q.append((nny,nnx,cnt+1))
          elif dy==-1 and dx==0:
            for i in range(-1,0):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q.append((nny,nnx,cnt+1))
          elif dy==0 and dx==-1:
            for i in range(-2,3):
              for j in range(-1,0):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q.append((nny,nnx,cnt+1))

  x=ans[Dh][Dw]
  if x==inf:
    return -1
  return x

# main()
print(main())