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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h, w = LI()
    ch, cw = LI()
    dh, dw = LI_()
    # from time import time
    # st = time()
    s = SR(h)
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch-1, cw-1))
    c[(ch - 1, cw - 1)] = 0
    nq = deque()
    mv = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    while 1:
        while q:
            nh, nw = q.popleft()
            now = c[(nh, nw)]
            for i in range(4):
                mh, mw = mv[i]
                mh += nh
                mw += nw
                if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now:
                    if s[mh][mw] == ".":
                        c[(mh, mw)] = now
                        q.appendleft((mh, mw))
                    if s[mh][mw] == "#":
                        c[(mh,mw)] = now
                        nq.append((mh, mw, i))
        while nq:
            nh, nw, x = nq.popleft()
            now = c[(nh, nw)]
            if x == 0:
                for i in range(-2, 3):
                    i += nh
                    if 0 <= i < h:
                        si = s[i]
                        for j in range(1, 2):
                            j += nw
                            if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and si[j] == ".":
                                c[(i, j)] = now + 1
                                q.append((i, j))
            elif x == 1:
                for i in range(1, 2):
                    i += nh
                    if 0 <= i < h:
                        si = s[i]
                        for j in range(-2, 3):
                            j += nw
                            if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and si[j] == ".":
                                c[(i, j)] = now + 1
                                q.append((i, j))
            elif x == 2:
                for i in range(-2, -1):
                    i += nh
                    if 0 <= i < h:
                        si = s[i]
                        for j in range(-2, 3):
                            j += nw
                            if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and si[j] == ".":
                                c[(i, j)] = now + 1
                                q.append((i, j))
            else:
                for i in range(-2, 3):
                    i += nh
                    if 0 <= i < h:
                        si = s[i]
                        for j in range(-2, -1):
                            j += nw
                            if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and si[j] == ".":
                                c[(i, j)] = now + 1
                                q.append((i, j))
        # print(q)
        if len(q) == 0:
            break
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh, dw = map(int, input().split())
dh -= 1
dw -= 1
s = [input() for _ in range(H)]

def walk(h, w):
    q = deque([[h, w]])
    coord = []
    while q:
        y, x = q.popleft()
        for i, j in [(0,1), (0,-1), (1,0),(-1,0)]:
            if (y+i<0 or y+i>H-1) or (x+j<0 or x+j>W-1):
                continue
            if s[y+i][x+j] == '#':
                continue
            if m[y+i][x+j] != -1:
                continue
            q.append([y+i, x+j])
            m[y+i][x+j] = m[h][w]
            coord.append([y+i, x+j])
    return coord


def warp(h, w):
    coord = []
    v = m[h][w]
    h_s = max(0, h-2)
    h_e = min(H-1, h+2)
    w_s = max(0, w-2)
    w_e = min(W-1, w+2)
    for h1 in range(h_s, h_e+1):
        for w1 in range(w_s, w_e+1):
            if h==h1 and w==w1:
                continue
            if m[h1][w1] == -1 and s[h1][w1] != '#':
                m[h1][w1] = v + 1
                coord.append([h1, w1])
    return coord

    
m = [[-1] * W for _ in range(H)]
m[ch][cw] = 0
queue = [[ch, cw]]
while True:
    coord = []
    co = []
    for y, x in queue:
        coord += walk(y, x)
    coord += queue
    
    for h, w in coord:
        co = warp(h, w)
    if len(co) == 0:
        break
    queue = co.copy()

print(m[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs():
    H, W = map(int, input().split())
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = [list(input()) for _ in range(H)]

    tests = ((0, 1), (1, 0), (-1, 0), (0, -1))
    warps = (
        (1, 1),
        (-1, 1),
        (-1, -1),
        (1, -1),
        (2, 0),
        (2, -1),
        (2, -2),
        (1, -2),
        (0, -2),
        (-1, -2),
        (-2, -2),
        (-2, -1),
        (-2, 0),
        (-2, 1),
        (-2, 2),
        (-1, 2),
        (0, 2),
        (1, 2),
        (2, 2),
        (1, 2),
    )

    start = (C[0] - 1, C[1] - 1, 0)
    goal = (D[0] - 1, D[1] - 1, 0)

    queue = deque()
    # (x, y, ワープ回数)
    queue.append(start)
    # warp_N = [[0 for _ in range(W)] for _ in range(H)]

    while queue:
        next_queue = deque()

        for _ in range(len(queue)):
            x, y, w_n = queue.pop()

            # 通常移動
            for dx, dy in tests:
                nx = x + dx
                ny = y + dy

                if nx < 0 or nx >= H or ny < 0 or ny >= W:
                    break

                if S[nx][ny] != "#":
                    if S[nx][ny] != "." and w_n >= S[nx][ny]:
                        continue
                    else:
                        S[nx][ny] = w_n
                        next_queue.append((nx, ny, w_n))

            # warp
            w_n += 1
            for dx, dy in warps:
                nx = x + dx
                ny = y + dy

                if nx < 0 or nx >= H or ny < 0 or ny >= W:
                    continue

                if S[nx][ny] != "#":
                    if S[nx][ny] != "." and w_n >= S[nx][ny]:
                        continue
                    else:
                        S[nx][ny] = w_n
                        next_queue.append((nx, ny, w_n))

        queue = next_queue

    if S[goal[0]][goal[1]] == ".":
        print(-1)
    else:
        print(S[goal[0]][goal[1]])


bfs()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
h,w = list(map(int,input().split()))
ch,cw = list(map(int,input().split()))
dh,dw = list(map(int,input().split()))
d = [["#","#"] + list(input())  + ["#","#"] for i in range(h)]
d = [["#"] * (w+4)] * 2 + d + [["#"] * (w+4)] * 2

import sys
sys.setrecursionlimit(4100000)

def bfs(h,w,cnt=0):
    if d[h][w]==".":
        d[h][w]=cnt
        bfs(h+1,w,cnt)
        bfs(h-1,w,cnt)
        bfs(h,w+1,cnt)
        bfs(h,w-1,cnt)

cnt = 0
for i in range(h+4):
    for j in range(w+4):
        if d[i][j]==".":
            bfs(i,j,cnt)
            cnt+=1

can_move_area = [set() for _ in range(cnt)]

for i in range(h+2):
    for j in range(w+2):
        a = d[i][j]
        if a != "#":
            b = d[i-2][j+1]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i-2][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i-1][j+1]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i-1][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+1][j+1]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+1][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+2][j]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+2][j+1]
            if b != "#" and b!=a:
                can_move_area[a].add(b)
            b = d[i+2][j+2]
            if b != "#" and b!=a:
                can_move_area[a].add(b)

from copy import copy
can_move = copy(can_move_area)
for i,v in enumerate(can_move_area):
    for j in v:
        can_move[j].add(i)

start_area = d[ch+1][cw+1]
goal_area = d[dh+1][dw+1]

cost_from_start_area = [-1] * cnt
cost_from_start_area[start_area] = 0
def area_bfs(area_id,cost):
    global cost_from_start_area
    next_areas = can_move[area_id]
    next_b = []
    for ai in next_areas:
        if cost_from_start_area[ai]==-1:
            cost_from_start_area[ai] = cost+1
            next_b.append(ai)
    for ai in next_b:
        area_bfs(ai,cost+1)

area_bfs(start_area,0)

print(cost_from_start_area[goal_area])

Submission status: Wrong Answer

Solution code:
from heapq import *
from sys import stdin
input=stdin.readline
n,m=map(int,input().split())
a,b=map(int,input().split())
x,y=map(int,input().split())
x=x-1
y=y-1
arr=[]
from math import inf
for i in range(n):
    arr.append(list(input().strip()))
def isvalid(x,y):
    if x<0 or y<0 or x>=n or y>=m or arr[x][y]=="#" or vis[x][y]==1:
        return False
    return True
vis=[[0]*m for i in range(n)]
stack=[[0,a-1,b-1]]
heapify(stack)
if x==a-1 and y==b-1 and arr[x][y]=="#":
    print(-1)
    quit()
vis[a-1][b-1]=1
mi=inf
while(stack):
    cost,xx,yy=heappop(stack)
    if xx==x and yy==y:
        mi=min(mi,cost)
    for i in range(-2,3,1):
        for j in range(-2, 3, 1):
            if isvalid(xx+i,yy+j):
                if -1<=i<=1 and -1<=j<=1 and i!=j:
                    vis[xx+i][yy+j] = 1
                    heappush(stack,[cost,xx+i,yy+j])
                else:
                    vis[xx+i][yy+j] = 1
                    heappush(stack, [cost+1, xx + i, yy + j])
if mi==inf:
    print(-1)
else:
    print(mi)

Submission status: Wrong Answer

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

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s)
        print(s[a,b])
        exit(0) 

    if s[a+1,b]=='.': 
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a,b+1]=='.':
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a-1,b]=='.':
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a,b-1]=='.':
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.pop(0)
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

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

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

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

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

bfs(ch,cw)

Submission status: Wrong Answer

Solution code:
import queue

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
#c->d

s=[input() for i in range(h)]

seen=[[0 for _ in range(w)] for _ in range(h)]
distance=[[10**7 for _ in range(w)] for _ in range(h)]

q=queue.Queue()

distance[ch][cw]=0
seen[ch][cw]=1
q.put([ch,cw])


while not q.empty():
  sth,stw=q.get()
  qi=queue.Queue()
  qi.put([sth,stw])
  ph=0
  pw=0
  wlis=[]
  while not qi.empty():
    ph,pw=qi.get()
    cntp=0
    for nearh,nearw in [[ph-1,pw],[ph+1,pw],[ph,pw-1],[ph,pw+1]]:
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="." and seen[nearh][nearw]==0:
        qi.put([nearh,nearw])
        seen[nearh][nearw]=1
        distance[nearh][nearw]=distance[ph][pw]
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="#":
        cntp+=1
    if cntp!=0:
      wlis.append([ph,pw])
  for i,j in wlis:
    for warph,warpw in [[i-2,j-2],[i-2,j-1],[i-2,j],[i-2,j+1],[i-2,j+2],
                        [i-1,j-2],[i-1,j-1],[i-1,j],[i-1,j+1],[i-1,j+2],
                        [i,j-2],[i,j-1],[i,j],[i,j+1],[i,j+2],
                        [i+1,j-2],[i+1,j-1],[i+1,j],[i+1,j+1],[i+1,j+2],
                        [i+2,j-2],[i+2,j-1],[i+2,j],[i+2,j+1],[i+2,j+2]]:
      if 0<=warph<=h-1 and 0<=warpw<=w-1 and s[warph][warpw]=="." and seen[warph][warpw]==0:
        q.put([warph,warpw])
        seen[warph][warpw]=1
        distance[warph][warpw]=distance[i][j]+1

if distance[dh][dw]==10**7:
  print(-1)
else:
  print(distance[dh][dw])

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 = []
for i in range(H):
	S.append(input())
que = deque([])
que.append([C[0]-1, C[1]-1, 0])
visited = [[1000 for i in range(W)] for j in range(H)]
visited[C[0]-1][C[1]-1] = 0
while que:
	cur = que.popleft()
	for i in range(-2,3):
		for j in range(-2,3):
			if (i != 0 or j != 0) and cur[0] + i < H and cur[0] + i >= 0 and cur[1] + j < W and cur[1] + j >= 0:
				if S[cur[0] + i][cur[1] + j] == '.':
					if (i == 0 and j == 1) or (i == 0 and j == -1) or (i == 1 and j == 0) or (i == -1 and j == 0):
						if visited[cur[0] + i][cur[1] + j] > cur[2]:
							que.append([cur[0]+i, cur[1]+j, cur[2]])
							visited[cur[0]+i][cur[1]+j] = cur[2]
					else:
						if visited[cur[0] + i][cur[1] + j] > cur[2]+1:
							que.append([cur[0]+i, cur[1]+j, cur[2]+1])
							visited[cur[0]+i][cur[1]+j] = cur[2]+1
if visited[D[0]-1][D[1]-1] != 1000:
	print(visited[D[0]-1][D[1]-1])
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
import pprint
import sys
sys.setrecursionlimit(10**8)
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

city = []
for i in range(H):
    city.append(input())

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

def dfs(x, y, count):

    if (not (0 <= x < W)) or (not (0 <= y < H)):
        return

    if visited[y][x] > -1:
        return

    if x == Dw and y == Ch:
        visited[y][x] = count
        print(count)
        exit()

    if city[y][x] == "#":
        return

    if visited[y][x] == -1:
        visited[y][x] = count

    dfs(x+1, y, count)
    dfs(x, y+1, count)
    dfs(x-1, y, count)
    dfs(x, y-1, count)

    for i in range(-2, 3):
        for j in range(-2, 3):
            if (not (0 <= x+j < W)) or (not (0 <= y+i < H)):
                continue
            if visited[y+i][x+j] > -1:
                continue
            if city[y+i][x+j] == "#":
                continue

            dfs(x+j, y+i, count+1)



dfs(Cw, Ch, 0)

print(visited[Dh][Dw])

Submission status: Wrong Answer

Solution code:
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    q2 = collections.deque()
    q2.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-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)]
    while len(q) != 0 and len(q2) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    elif d > dist[h2][w2]:
                        dist[h][w] = dist[h2][w2]
        h, w = q2.popleft()
        d = dist[h][w]
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
                    q2.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))

Submission status: Wrong Answer

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

H,W=map(int,readline().split())

sy,sx = map(int,readline().split())
gy,gx = map(int,readline().split())

sy -= 1
sx -= 1
gy -= 1
gx -= 1

G = [None] * H
for i in range(H):
  G[i] = readline().rstrip()

# 幅優先探索
INF = 10 ** 10
costs = [[INF] * W for i in range(H)]

from collections import deque
q = deque([])
# y,x,魔法の回数,親y,親x
q.append((sy,sx,0,-1,-1))

cases = ((0,1),(0,-1),(1,0),(-1,0))
warp = ((-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-2,-1),(2,-1),(-2,0),(2,0),(-2,1),(2,1),(-2,-2),(-2,-1),(-2,0),(-2,0),(-2,0))
while q:
  y,x,co,py,px = q.popleft()
  if costs[y][x] <= co:
    continue
  if G[y][x] == "#":
    continue
  costs[y][x] = co
  nex = 0
  for c in cases:
    if y + c[0] == py and x + c[1] == px:
      continue
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      if G[y + c[0]][x + c[1]] == "#":
        continue
      if costs[y + c[0]][x + c[1]] <= co:
        continue
      q.append((y + c[0], x + c[1], co, y, x))
      nex += 1
  # 行先がないのでワープ検討
  for w in warp:
    if 0 <= y + w[0] < H and 0 <= x + w[1] < W:
      if G[y + w[0]][x + w[1]] == "#":
        continue
      if costs[y + w[0]][x + w[1]] <= co + 1:
        continue
      q.append((y + w[0], x + w[1], co + 1, y, x))

if costs[gy][gx] == INF:
  print(-1)
else:
  print(costs[gy][gx])

Submission status: Wrong Answer

Solution code:
h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]

for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="#":map[gyou][retu]=-2

genzai=[[c_h-1,c_w-1]]
tugi=[]

map[c_h-1][c_w-1]=0

def idou(gyou,retu,kaisuu):
    for i in (-1,1):
        if 0<gyou+i and gyou+i<h:
            if map[gyou+i][retu]>kaisuu or map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append([gyou+i,retu])
    for i in (-1,1):
        if 0<retu+i and retu+i<w:
            if map[gyou][retu+i]>kaisuu or map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append([gyou,retu+i])
    
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<gyou+i and gyou+i<h and 0<retu+j and retu+j<w:
                if map[gyou+i][retu+j]>kaisuu+1 or map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    tugi.append([gyou+i,retu+j])

wapu=0

import copy

while True:

    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu)
        genzai.pop(0)
    
    if len(genzai)==0:
        if len(tugi)!=0:
            genzai=copy.deepcopy(tugi)
            tugi=[]
            wapu+=1
        else:
            print(map[d_h-1][d_w-1])
            exit()

Submission status: Wrong Answer

Solution code:
import heapq
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 = input()
    S.append(s)

que = []
heapq.heappush(que, (0, Ch-1, Cw-1))
d = {}
d[(Ch-1, Cw-1)] = 0

def check(newh, neww, dis, c):
    if newh < 0 or newh >= H or neww < 0 or neww >= W:
        return
    if S[newh][neww] == "#":
        return
    if dis == 1:
        if (newh,neww) in d:
            d[(newh, neww)] = min(d[(newh,neww)], c)
        else:
            d[(newh, neww)] = c
            heapq.heappush(que, (c, newh, neww))
    else:
        if (newh,neww) in d:
            d[(newh, neww)] = min(d[(newh,neww)], c+1)
        else:
            d[(newh, neww)] = c+1
            heapq.heappush(que, (c+1, newh, neww))
    

while que:
    _, h, w = heapq.heappop(que)
    nowc = d[(h,w)]
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            check(h+i, w+j, abs(i)+abs(j), nowc)

if (Dh-1, Dw-1) in d:
    print(d[(Dh-1, Dw-1)])
else:
    print(-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 = [[-1]*w for i in range(h)]
#dist[sx][sy] = 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]==-1:
                    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]==-1:
                        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:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

import numpy as np
from itertools import permutations


class Lab:
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.map = np.zeros(shape=(h, w), dtype=np.int8)
        self.max_c = 1
        self.tree = dict()

    def set_wall(self, ih, walls):
        self.map[ih] = walls

    def bfs(self, y, x, c):
        self.map[y][x] = c

        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ny, nx = y+dy, x+dx
            if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                continue
            if self.map[ny][nx] != 0:
                continue
            self.bfs(ny, nx, c)

    def coloring(self):
        for y in range(self.h):
            for x in range(self.w):
                if self.map[y][x] == 0:
                    self.max_c += 1
                    self.bfs(y, x, self.max_c)

    def room(self):
        if self.max_c == 1:
            return

        for c in range(2, self.max_c+1):
            self.tree[c] = set()

        for y in range(self.h):
            for x in range(self.w):
                c = self.map[y][x]
                # if c == 1:
                #     continue
                # for dy in range(-2, 3):
                #     for dx in range(-2, 3):
                #         ny, nx = y + dy, x + dx
                #         if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                #             continue
                #         tc = self.map[ny][nx]
                #         if tc not in (1, c):
                #             self.tree[c].add(tc)


def solve():
    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

    lab = Lab(h, w)
    for i in range(h):
        walls = np.array(list(map(lambda x: int(x == "#"), input())))
        lab.set_wall(i, walls)
    # 
    # lab.coloring()
    # # print(lab.map)
    # dc = lab.map[dh][dw]
    # if dc == 1:
    #     return "-1"
    # 
    # cc = lab.map[ch][cw]
    # if dc == cc:
    #     return 0
    # 
    # lab.room()
    # # print(lab.tree)
    # ct = lab.tree[cc]
    # if dc in ct:
    #     return 1
    # 
    # lab.tree.pop(cc)
    # pre_set = ct
    # min_dist = 10 ** 9
    # for roots in permutations(lab.tree):
    #     # print(roots)
    #     dist = 0
    #     ok = False
    #     for nc in roots:
    #         if nc not in pre_set:
    #             break
    #         dist += 1
    #         if dc in pre_set:
    #             ok = True
    #             break
    #         pre_set = lab.tree[nc]
    #     if ok:
    #         min_dist = min(min_dist, dist)
    # 
    # if min_dist == 10 ** 9:
    #     return "-1"

    # return min_dist
    return 0

def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def f(i, j, wc):
    warp[i][j] = wc
    if i-1 >= 0 and s[i-1][j] == '.' and wc < warp[i-1][j]:
        f(i-1, j, wc)
    if j-1 >= 0 and s[i][j-1] == '.' and wc < warp[i][j-1]:
        f(i, j-1, wc)
    if i+1 < h and s[i+1][j] == '.' and wc < warp[i+1][j]:
        f(i+1, j, wc)
    if j+1 < w and s[i][j+1] == '.' and wc < warp[i][j+1]:
        f(i, j+1, wc)

    for di in range(max(i-2, 0), min(i+2, h-1)+1):
        for dj in range(max(j-2, 0), min(j+2, w-1)+1):
            if s[di][dj] == '.' and wc + 1 < warp[di][dj]:
                f(di, dj, wc+1)


h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
s = []
warp = [[10000] * w for i in range(h)]
for i in range(h):
    s.append(input())

# f(ch-1, cw-1, 0)

q = [(ch - 1, cw - 1, 0)]
while len(q) > 0:
    i = q[0][0]
    j = q[0][1]
    wc = q[0][2]
    if wc < warp[i][j]:
        warp[i][j] = wc
    if i-1 >= 0 and s[i-1][j] == '.' and wc < warp[i-1][j]:
        q.append((i - 1, j, wc))
    if j-1 >= 0 and s[i][j-1] == '.' and wc < warp[i][j-1]:
        q.append((i, j - 1, wc))
    if i+1 < h and s[i+1][j] == '.' and wc < warp[i+1][j]:
        q.append((i + 1, j, wc))
    if j+1 < w and s[i][j+1] == '.' and wc < warp[i][j+1]:
        q.append((i, j + 1, wc))

    for di in range(max(i-2, 0), min(i+2, h-1)+1):
        for dj in range(max(j-2, 0), min(j+2, w-1)+1):
            if s[di][dj] == '.' and wc + 1 < warp[di][dj]:
                q.append((di, dj, wc + 1))
    del q[0]

if warp[dh-1][dw-1] == 10000:
    print(-1)
else:
    print(warp[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
S = []
C_h -= 1
C_w -= 1
D_h -= 1
D_w -= 1
for h in range(H):
    tmp = [x for x in input()]
    S.append(tmp)

ans = 0
while D_h != C_h or D_w != C_w:
    if D_h - C_h > 0:
        dir_h = 1
    else:
        dir_h = -1

    if D_w - C_w > 0:
        dir_w = 1
    else:
        dir_w = -1

    while True:
        if D_h == C_h:
            break
        if S[C_h + dir_h][C_w] == '#':
            break
        C_h += dir_h
    
    if C_h + dir_h == H or C_h + dir_h < 0:
        dir_h = 0

    while True:
        if D_w == C_w:
            break
        if S[C_h][C_w + dir_w] == '#':
            break
        C_w += dir_w
    
    if C_w + dir_w == W or C_w + dir_w < 0:
        dir_w = 0

    if D_h == C_h and D_w == C_w:
        break
    
    flag = 0
    for h in reversed(range(1,3)):
        if flag == 0:
            for w in reversed(range(1,3)):
                if 0 < C_h + h * dir_h < H and 0 < C_w + w * dir_w < W:
                    if S[C_h + h * dir_h][C_w + w * dir_w] == '.':
                        ans += 1
                        C_h += h * dir_h
                        C_w += w * dir_w
                        flag = 1
                        break
        else:
            break
    
    if flag == 0:
        ans = -1
        break

print(ans)