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:
h,w = map(int, input().split())
ch,hw = map(int, input().split())
dh,dw = map(int, input().split())

sx,sy=ch-1,hw-1
gx,gy=dw-1,dh-1

l = [None]*h
for i in range(h):
    l[i] = list(input())

dist = [[10**9]*w for i in range(h)]
dist[sy][sx] = 0

from collections import deque
def walk(warped,cnt):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque(warped)
    walked=warped
    changed=False
    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==10**9:
                    changed=True
                    Q.append([nx, ny])
                    walked.append([nx,ny])
                    dist[ny][nx] = cnt
                    if nx==gx and ny==gy:
                        print(cnt)
                        exit()
    return walked,changed
def warp(walked,cnt):
    warped=[]
    changed=False

    for x,y in walked:
        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                if dx==0 and dy==0:
                    continue
                if abs(dx)+abs(dy)<=1:
                    continue

                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]=="." and dist[ny][nx]==10**9:
                        changed=True
                        warped.append([nx,ny])
                        dist[ny][nx] = cnt
                        if nx==gx and ny==gy:
                            print(cnt)
                            exit()
    return warped,changed

cnt=0

warped=[[sx,sy]]

while True:
    walked,walkchange= walk(warped,cnt)
    cnt+=1
    warped,warpchange=warp(walked,cnt)
    if not walkchange and not warpchange:
        print(-1)
        exit()

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 = [[[inf, inf] for _ in range(W)] for _ in range(H)]
d = deque([[ch, cw]])
path[ch][cw] = [0, 0]
while d:
    vh, vw = d.popleft()
    warp = False
    for h, w in get_near(vh, vw):        
        if graph[h][w] != '#':
            if (path[h][w][1] > path[vh][vw][1]):
                d.append([h, w])
                path[h][w] = [path[vh][vw][0] + 1, path[vh][vw][1]]
            elif (path[h][w][0] > path[vh][vw][0] + 1):
                d.append([h, w])
                path[h][w] = [path[vh][vw][0] + 1, path[vh][vw][1]]
        else:
            warp = True
    if warp:
        for h, w in get_far(vh, vw):
            if graph[h][w] != '#':
                if path[h][w][1] == inf:
                    if (path[h][w][1] > path[vh][vw][1] + 1):
                        d.append([h, w])
                        path[h][w] = [path[vh][vw][0], path[vh][vw][1] + 1]
ans = path[dh][dw][1]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

h,w = map(int, sys.stdin.readline().rstrip("\n").split())
sh,sw = map(int, sys.stdin.readline().rstrip("\n").split())
sh,sw = sh-1,sw-1
gh,gw = map(int, sys.stdin.readline().rstrip("\n").split())
gh,gw = gh-1,gw-1
labyrinth = [ line.rstrip("\n") for line in sys.stdin ]
done = [[False]*w for _ in range(h)]
move = [(1,0),(-1,0),(0,1),(0,-1)]
warp = [(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(2,1),(2,2),(1,2),(0,2),(-2,2),(-1,2),(-2,1),(-2,0),(-2,-1),(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(2,-1)]

d = deque()
d.append((sh,sw,0))
done[sh][sw] = True
warpmin = -1
while d:
    ph,pw,pwarp = d.popleft()
    if ph == gh and pw == gw:
        warpmin = pwarp
        break
    cm = 0
    for m in move:
        nh,nw = ph+m[0],pw+m[1]
        if 0<=nh<h and 0<=nw<w and labyrinth[nh][nw] == '.' and done[nh][nw] == False:
            done[nh][nw] = True
            d.appendleft((nh,nw,pwarp))
            cm = 1
    if cm == 0:
        for m in warp:
            nh,nw = ph+m[0],pw+m[1]
            if 0<=nh<h and 0<=nw<w and labyrinth[nh][nw] == '.' and done[nh][nw] == False:
                d.append((nh,nw,pwarp+1))

print(warpmin)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))

S = [[True if c == "." else False for c in input()] for _ in range(H)]

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

gen = 0

q = deque([[C[0] - 1, C[1] - 1, 0]])


def check(r, c, count, que, ret_list):
    if S[r][c] and ans[r][c] == -1:
        ans[r][c] = count
        que.append([r, c])
        ret_list.append([r, c])


def paint(r, c, count):
    if ans[r][c] != -1:
        return []

    q_paint = deque([[r, c]])
    ans[r][c] = count

    painted_list = [[r, c]]

    while len(q_paint) > 0:
        p_paint = q_paint.pop()
        if p_paint[0] > 0:
            check(p_paint[0] - 1, p_paint[1], count, q_paint, painted_list)
        if p_paint[0] < H - 1:
            check(p_paint[0] + 1, p_paint[1], count, q_paint, painted_list)
        if p_paint[1] > 0:
            check(r, p_paint[1] - 1, count, q_paint, painted_list)
        if p_paint[1] < W - 1:
            check(r, p_paint[1] + 1, count, q_paint, painted_list)
    return painted_list


def jump(r, c):
    jump_possible_list = []
    for i in range(r - 2, r + 3):
        for j in range(c - 2, c + 3):
            if 0 <= i < H and 0 <= j < W and S[i][j] and ans[i][j] == -1:
                jump_possible_list.append([i, j])
    return jump_possible_list


while len(q) > 0:
    check_point = q.popleft()
    if ans[check_point[0]][check_point[1]] == -1:
        painted = paint(check_point[0], check_point[1], check_point[2])
        next_gen = []
        for point in painted:
            jump_list = jump(point[0], point[1])
            for next_point in jump_list:
                q.append([next_point[0], next_point[1], check_point[2] + 1])

print(ans[D[0] - 1][D[1] - 1])

Submission status: Wrong Answer

Solution code:
from collections import *
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S = 2*[(W+4)*["#"]]+[2*["#"]+list(input())+2*["#"] for h in range(H)]+2*[(W+4)*["#"]]
S[CH+1][CW+1] = 0
P = []
Q = deque([[CH+1,CW+1]])
ans = 0

for n in range(700):
  while Q:
    y,x = Q.popleft()
    P+=[[y,x]]
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      if S[y+dy][x+dx]==".":
        S[y+dy][x+dx] = S[y][x]
        Q+=[[y+dy,x+dx]]

  if S[DH+1][DW+1]==".":
    for y,x in P:
      for dy,dx in [[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]]:
        if S[y+dy][x+dx]==".":
          S[y+dy][x+dx] = ans+1
          Q+=[[y+dy,x+dx]]
    P = []
    ans+=1

if S[DH+1][DW+1]==".":
  print(-1)
else:
  print(S[DH+1][DW+1])

Submission status: Wrong Answer

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

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for i in range(h)]

m = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j:j+1] == "#":
            m[i][j] = -1

def mapping(l,m,k,total_l):
    next_l = []
    for n in range(len(l)):
        x = l[n][0]
        y = l[n][1]
        m[x][y] = k
        total_l.append([x,y])
        if x+1 >= 0 and x+1 < h:
            if m[x+1][y] == 0:
                m[x+1][y] = k
                next_l.append([x+1,y])
                total_l.append([x+1,y])
        if y+1 >= 0 and y+1 < w:
            if m[x][y+1] == 0:
                m[x][y+1] = k
                next_l.append([x,y+1])
                total_l.append([x,y+1])
        if x-1 >= 0 and x-1 < h:
            if m[x-1][y] == 0:
                m[x-1][y] = k
                next_l.append([x-1,y])
                total_l.append([x-1,y])
        if y-1 >= 0 and y-1 < w:
            if m[x][y-1] == 0:
                m[x][y-1] = k
                next_l.append([x,y-1])
                total_l.append([x,y-1])
    if next_l != []:
        total_l = mapping(next_l,m,k,total_l)
    return(total_l)

def warp(m,l,k):
    next_l = []
    for i in range(len(l)):
        for x in range(5):
            for y in range(5):
                if (l[i][0]-2+x >= 0 and l[i][0]-2+x < h) and(l[i][1]-2+y >= 0 and l[i][1]-2+y < w):
                    if m[l[i][0]-2+x][l[i][1]-2+y] == 0:
                        m[l[i][0]-2+x][l[i][1]-2+y] = k
                        next_l.append([l[i][0]-2+x,l[i][1]-2+y])
    return(next_l)

next_l = [[ch-1,cw-1]]
count = 1
while 1:
    total_l = mapping(next_l,m,count,[])
    count += 1
    next_l = warp(m,total_l,count)
    if next_l == [] or count >= 10**4:
        break
#for i in m:
#    print(i)

if m[dh-1][dw-1] != 0:
    print(m[dh-1][dw-1]-1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
H, W = map(int, input().split())
C = tuple(int(x) - 1 for x in input().split())
D = tuple(int(x) - 1 for x in input().split())
S = [sys.stdin.readline() + "###" for _ in range(H)]
S.append("#" * (W + 3))
S.append("#" * (W + 3))

todo = []
heapq.heappush(todo, (0, 0, C))
done = set()
while todo:
    wcount, count, p = heapq.heappop(todo)
    if p == D:
        print(wcount)
        break
    done.add(p)
    h, w = p
    pdone = {p}
    for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nh, nw = (h + dh, w + dw)
        if S[nh][nw] == "#":
            continue
        np = (nh, nw)
        pdone.add(np)
        if np in done:
            continue
        heapq.heappush(todo, (wcount, count + 1, np))
    for nh in range(h - 2, h + 2 + 1):
        for nw in range(w - 2, w + 2 + 1):
            if S[nh][nw] == "#":
                continue
            np = (nh, nw)
            if np in done or np in pdone:
                continue
            heapq.heappush(todo, (wcount + 1, count + 1, np))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def f1(x,y,xa,ya):
    if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y]:
         if c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y]
            r.append([xa,ya])
            q.append([xa,ya])

def f2(x,y,xa,ya):
    if 0 <= xa <= h+1 and 0 <= ya <= w+1:
    
        if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y] + 1:
            if c[xa][ya] == ".":
                reach[xa][ya] = reach[x][y] + 1
                q.append([xa,ya])

h,w = map(int,input().split())
cx, cy = map(int,input().split())
dx, dy = map(int,input().split())

c = [0]*(h+2)
for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[-1 for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0
sw = 0

while q:
    if sw == 1:
        break
    
    
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        if sw == 1:
            break
        for j in range(-2,3):
            f2(x,y,x+i,y+j)
            
            if x == dx and y == dy:
                sw = 1
                break

print(reach[dx][dy])

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
ch,cw = lr()
ch-=1
cw-=1
dh, dw = lr()
dh-=1
dw-=1
s = [input() for i in range(h)]
visited = [[inf for j in range(w)] for i in range(h)]
revisited = [[False for j in range(w)] for i in range(h)]
visited[ch][cw] = 0
q = deque([[ch, cw]])
dir = [[0,1], [0,-1], [-1,0], [1,0]]
while q:
    y,x = q.popleft()
    c = visited[y][x]
    for dy,dx in dir:
        ny,nx = y+dy,x+dx
        if 0<=ny<h and 0<=nx<w:
            if s[ny][nx] == '.':
                if visited[ny][nx] > c:
                    visited[ny][nx] = c
                    q.append([ny,nx])
    if len(q) == 0:
        dq = deque([[y, x]])
        revisited[y][x] = True
        while dq:
            y,x = dq.popleft()
            # ワープ処理
            ty, tx = y-2, x-2
            for i in range(5):
                for j in range(5):
                    ny, nx = ty + i, tx + j
                    if 0<=ny<h and 0<=nx<w:
                        if s[ny][nx]=='.':
                            if visited[ny][nx] > c+1:
                                visited[ny][nx] = c+1
                                q.append([ny,nx])
                            elif visited[ny][nx] == c and revisited[ny][nx] == False:
                                revisited[ny][nx] = True
                                dq.append([ny,nx])
if visited[dh][dw] != inf:
    print(visited[dh][dw])
else:
    print(-1)

Submission status: Wrong Answer

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

Ch +=1
Cw += 1
Dh += 1
Dw += 1

start = (Ch, Cw)

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

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

counter[Ch][Cw] = 0

#print(counter)
#print(S)

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

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

Submission status: Wrong Answer

Solution code:

# lrud = [[0, -1], [0, 1], [-1, 0], [1, 0], \
#     [1, -1], [1, 1], [-1, -1], [-1, 1]]
lrud = [[0, -1], [0, 1], [-1, 0], [1, 0]]
lrud2 = [[-1, -1], [1, 1], [-1, 1], [1, -1]]
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch, Cw = Ch-1, Cw-1
Dh, Dw = map(int, input().split())
Dh, Dw = Dh-1, Dw-1
S = [list(input()) for i in range(H)]

is_visited = [[float('inf') for j in range(W)]for i in range(H)]
is_visited[Ch][Cw] = 0
for i in range(2):
    for x in range(H):
        for y in range(W):
            cost = int(S[x][y] == '#')
            for dx, dy in lrud:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and not (cost and S[nx][ny]=='#'):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
            if cost == 1:
                for dx, dy in lrud2:
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < H and 0 <= ny < W and not (cost and S[nx][ny]=='#'):
                        is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
    for x in range(H-1, -1, -1):
        for y in range(W-1, -1, -1):
            cost = int(S[x][y] == '#')
            for dx, dy in lrud:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and not (cost and S[nx][ny]=='#'):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
            if cost == 1:
                for dx, dy in lrud2:
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < H and 0 <= ny < W and not (cost and S[nx][ny]=='#'):
                        is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
if is_visited[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(is_visited[Dh][Dw])

Submission status: Wrong Answer

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

input=sys.stdin.readline

H,W=list(map(int,input().split()))

sh,sw = list(map(int,input().split()))
gh,gw = list(map(int,input().split()))

sh-=1
sw-=1
gh-=1
gw-=1

c=[]
seen=[]
for i in range(H):
    c+=[input()]
    seen+=[[False]*W]

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

hop=0
ans=10000000

def dfs(c,h,w,hop):
    global seen,dx,dy,H,W,ans
    seen[h][w]=True
    #print(h,w,hop)

    for i in range(4):
        nh=h+dy[i]
        nw=w+dx[i]

        if nh<0 or nh>=H or nw<0 or nw>=W:
            continue
        if c[nh][nw] == "#":
            for j in range(-2,3):
                for k in range(-2,3):
                    if 0<=h+j and h+j<H and 0<=w+k and w+k<W:
                        if c[h+j][w+k]=="." and seen[h+j][w+k]==False:
                            nh=h+j
                            nw=w+k
                            hop+=1
                            if nh==gh and nw==gw:
                                seen[nh][nw]=True
                                if ans>hop:
                                    ans=hop
                                return True
                            else:
                                dfs(c,nh,nw,hop)    
            continue
        if seen[nh][nw]:
            continue
        if nh==gh and nw==gw:
            seen[nh][nw]=True
            if ans>hop:
                ans=hop
            return True
        if dfs(c,nh,nw,hop):
            return True

dfs(c,sh,sw,hop)
if seen[gh][gw]:
    print(ans)
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


def f(hi, wi):
    return hi * w + wi


h, w = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())
s = [input() for _ in range(h)]
N = h * w

row = []
col = []
cost = []

d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
coef = 2
for hi in range(h):
    for wi in range(w):
        if s[hi][wi] == "#":
            continue
        for dh, dw in d:
            nh = hi + dh
            nw = wi + dw
            if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                row.append(f(hi, wi))
                col.append(f(nh, nw))
                cost.append(0)

            nh = hi + coef * dh
            nw = wi + coef * dw
            if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                row.append(f(hi, wi))
                col.append(f(nh, nw))
                cost.append(1)

g = csr_matrix((cost, (row, col)), shape=(N, N))
dist = dijkstra(g, indices=f(sh-1, sw-1)).astype(int)
ans = dist[f(gh-1, gw-1)]
ans = max(ans, -1)
print(ans)

Submission status: Wrong Answer

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

h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))

s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1

Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1

for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)

count = 0
best = 0

while True:
  while Q:
    new_Q = []
    for node in Q:
      i,j = node[0], node[1]
      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))

      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))

      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))

      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))

    Q = new_Q

  if V[f1][f2]==1:
    print(count)
    break
  else:
    temp = sum(sum(kk) for kk in V) 
    count += 1
    part= []
    
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>-1 and y>-1 and x<h and y<w:
            if G[x][y] == '.':
              part.append((x,y))
       
    ALL = list(set(part))
    Q = list(ALL)
    
    #print(temp,best)
    if (f1,f2) in ALL:
      print(count)
      break

    if temp==best:
      print(-1)
      break
    else:
      best = temp

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

WALL = -100
INI = -1
PASSED = 0

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

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

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

is_goal = False
while len(d):
    y, x = d.popleft()
    flag = False
    for dy, dx in direction:
        next_y = y + dy
        next_x = x + dx
        if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
            continue
        if S[next_y][next_x] == INI:
            d.append((next_y, next_x))
            S[next_y][next_x] = S[y][x]
            flag = True
        if next_y == Dh and next_x == Dw:
            is_goal = True

    if not flag:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                next_y = y + dy
                next_x = x + dx
                if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
                    continue
                if S[next_y][next_x] == INI:
                    d.append((next_y, next_x))
                    S[next_y][next_x] = S[y][x] + 1
                if next_y == Dh and next_x == Dw:                    
                    is_goal = True
    if is_goal:
        break

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

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
cx+=1
cy+=1
dx,dy=map(int,input().split())
dx+=1
dy+=1
l=[]
l.append("#"*(w+4))
l.append("#"*(w+4))
for i in range(h):
    l.append("##"+input()+"##")
l.append("#"*(w+4))
l.append("#"*(w+4))
#input

"""
for i in l:
    print(*i)
"""

q=deque([[cx,cy]])
qq=deque([[cx,cy]])
s=[[-1 for i in j]for j in l]
s[cx][cy]=0

while len(qq)>0:
    while len(q)>0:
        x,y=q.popleft()
        for px,py in ((0,1),(0,-1),(1,0),(-1,0)):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]
                q.appendleft([x+px,y+py])
                qq.appendleft([x+px,y+py])
    x,y=qq.popleft()
    for px in range(-2,3):
        for py in range(-2,3):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]+1
                q.append([x+px,y+py])
                qq.append([x+px,y+py])
"""
for i in s:
    print(*i)
"""

print(s[dx][dy])