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

h,w = map(int,input().split())
sy,sx= map(int,input().split())
gy,gx= map(int,input().split())
S=[]



for i in range(h):
    S.append(input())
    
move = [[x,y] for x in range(-2,3) for y in range(-2,3)] 
walk = [[1,0],[-1,0],[0,1],[0,-1]]
dist = [[99999]*w for i in range(h)]
#visited = [[0]*w for i in range(h)]

q=deque()
q.append((sx-1,sy-1,0))
dist[sy-1][sx-1]=0
goaled = 0
endwarp=0
#while goaled==0:
while len(q):
    endwarp=0
    
    x,y,d = q.popleft()
    
    if x==gx-1 and y==gy-1:
        goaled=1
#        print(d)
#        break
    
#    print(x,y,d)
    for i in move:
        if 0<=x+i[0]<w and 0<=y+i[1]<h:
            if S[y+i[1]][x+i[0]]!="#" :
            
#                if visited[x+i[0]][y+i[1]] == 0:
                if dist[y+i[1]][x+i[0]] > d:
                
                    

                    if abs(i[0])+abs(i[1])==1:
                        dist[y+i[1]][x+i[0]] = d
                        q.append((x+i[0],y+i[1],d+0))
                    else:  
                        dist[y+i[1]][x+i[0]] = d+1
                        q.appendleft((x+i[0],y+i[1],d+1))
                        
                         
    
    

if goaled==0:
    print(-1)
    
else:
    print(dist[gy-1][gx-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
CH = CH -1
CW = CW -1
DH = DH -1
DW = DW -1
S = np.array([list(input()) for i in range(H)])
countWarp = np.ones((H,W))*H*W
nowH = CH
nowW = CW
countWarp[CH,CW] = 0
q = deque([])
q.append([nowH,nowW])
for n in range(0,H*W):
  tmp = q.popleft()
  nowH = tmp[0]
  nowW = tmp[1]
  for i in range(-2,2+1):
    for j in range(-2,2+1):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if abs(i) + abs(j) == 1:
          if S[nowH+i,nowW+j] == '.':
            if countWarp[nowH+i,nowW+j] == H*W:
              q.append([nowH+i,nowW+j])
            countWarp[nowH+i,nowW+j] = min(countWarp[nowH,nowW],countWarp[nowH+i,nowW+j])
        if abs(i) + abs(j) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if countWarp[nowH+i,nowW+j] == H*W:
              q.append([nowH+i,nowW+j])
            countWarp[nowH+i,nowW+j] = min(countWarp[nowH,nowW]+1,countWarp[nowH+i,nowW+j])
  if len(q) == 0:
    break
if countWarp[DH,DW] == H*W:
  print(-1)
else:
  print(int(countWarp[DH,DW]))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[20000]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

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()) and distance[dh][dw]==10**7:
  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:
    dij=distance[i][j]
    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+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]=dij+1

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

Submission status: Wrong Answer

Solution code:
import copy

from collections import deque
 
H, W = [int(x) for x in 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

cell = [list(input()) for i in range(H)]

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

copy_stack = []
copy_stack.append([Ch,Cw])

nstack = []

dp[Ch][Cw] = 0

def search(stack):
    while len(stack) > 0:
        h,w = stack.pop()
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dy
            nw = w + dx
            if 0 <= nh < H and 0 <= nw < W and (dp[nh][nw] == -1 or dp[nh][nw] > dp[h][w]):
                if cell[nh][nw] == '.':
                    dp[nh][nw] = dp[h][w]
                    stack.append([nh,nw])
                   
while True:
    if len(copy_stack):
        nstack = copy.copy(copy_stack)
    else:
        copy_stack = copy.copy(nstack)
    search(nstack)
    #print(dp)
    if dp[Dh][Dw] == -1:
        while len(copy_stack)>0:
            h,w = copy_stack.pop()
            for ddy in range(-2,3):
                for ddx in range(-2,3):
                    if ddy==ddx==0:
                        continue
                    nnh = h + ddy
                    nnw = w + ddx
                    if 0 <= nnh < H and 0 <= nnw < W:
                        if cell[nnh][nnw] == '.' and dp[nnh][nnw] == -1:
                            dp[nnh][nnw] = dp[h][w] + 1
                            nstack.append([nnh,nnw])
        if len(nstack) == 0:
            break
    else:
        break
                        
if dp[Dh][Dw] != -1:
    print(dp[Dh][Dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import collections

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))
num = [[float("inf") for i in range(w)] for i in range(h)]
flag = [[False for i in range(w)] for i in range(h)]
num[ch - 1][cw - 1] = 0
queue = collections.deque([[ch, cw]])
d1 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
d2 = [[-1, -1], [-1, 1], [1, -1], [1, 1], [-2, 0], [2, 0], [0, -2], [0, 2]]
d3 = [[-2, -1], [-1, -2], [2, -1], [1, -2], [-2, 1], [-1, 2], [2, 1], [1, 2]]
d4 = [[-2, -2], [-2, 2], [2, -2], [2, 2]]
while queue:
    test = queue.popleft()
    x = test[1]
    y = test[0]
    if flag[y - 1][x - 1] == True:
        continue
    #print(num)
    #print(test)
    flag[y - 1][x - 1] = True
    temp = num[y - 1][x - 1]
    for i in d1:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(num[y2 - 1][x2 - 1], temp)
            queue.append([y2, x2])
    for i in d2:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([y2, x2])
    for i in d3:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([y2, x2])
    for i in d4:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([y2, x2])
if num[dh - 1][dw - 1] == float("inf"):
    print(-1)
else:
    print(num[dh - 1][dw - 1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "#":
				continue
			for i in range(-2, 2+1):
				for j in range(-2, 2+1):
					if (i, j) == (0, 0):
						continue
					if getMaze(x + i, y + j) == ".":
						if (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
							graph[y][x].append((x + i, y + j, 0))
						else:
							graph[y][x].append((x + i, y + j, 1))


	# log.print(graph)
	stack = deque([(cw-1, ch-1)])
	dist = [[[-1, 1]]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		log.print(x, y, dist[y][x])
		if dist[y][x] == [-1, 1]:
			dist[y][x] = [0, 0]
		d, _ = dist[y][x]
		nexts = graph[y][x]
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] != [-1, 1]:
				if dist[ny][nx][1] == 1:
					dist[ny][nx][0] = min(dist[ny][nx][0], d + cost)
				continue
			dist[ny][nx] = [d + cost, cost]
			if cost == 1:
				stack.append((nx, ny))
			else:
				stack.appendleft((nx, ny))
	log.print(dist)
	print(dist[dh-1][dw-1][0])
	
	


main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
toGo = [[-1 if i != C[0] or j != C[1] else 0 for j in range(W)] for i in range(H)]
queue = [C]
ans = 0

while True:
    tmp = queue.pop()
    dfs = [tmp]

    while len(dfs):
        a = dfs.pop()
        for move in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            hh, ww = a[0] + move[0], a[1] + move[1]
            if hh >= H or hh < 0 or ww >= W or ww < 0:
                continue

            if toGo[hh][ww] == -1 and S[hh][ww] == '.':
                toGo[hh][ww] = ans
                dfs.append([hh, ww])

    if toGo[D[0]][D[1]] != -1:
        break

    flag = True
    if not len(queue):
        ans += 1
        for i in range(H):
            for j in range(W):
                if toGo[i][j] == ans - 1:
                    t = False
                    for ii in range(-2, 3):
                        for jj in range(-2, 3):
                            hh, ww = i + ii, j + jj
                            if hh >= H or hh < 0 or ww >= W or ww < 0:
                                continue

                            if toGo[hh][ww] == -1 and S[hh][ww] == '.':
                                toGo[hh][ww] = ans
                                flag = False
                                queue.append([hh, ww])
                                break
        if flag:
            print(-1)
            exit()

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1<<50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
from collections import deque
q = deque([])
q.append((ch-1,cw-1))
while len(q)>0:
    h,w = q.popleft()
    cnt = dps[h][w]
    # 先に魔法を使っておく
    for dh in range(-2,3):
        for dw in range(-2,3):
            hn = h + dh
            wn = w + dw
            if (dh,dw) in mvs:
                if 0<=hn<H and 0<=wn<W:
                    if dps[hn][wn] <= cnt:continue
                    if fs[hn][wn] == ".":
                        q.appendleft((hn, wn))
                        dps[hn][wn] = min(dps[h][w], cnt)
            else:
                if 0<=hn<H and 0<wn<W:
                    if dps[hn][wn] <= cnt+1:continue
                    if fs[hn][wn] == ".":
                        q.append((hn,wn))
                        dps[hn][wn] = min(dps[hn][wn], cnt + 1)

# for r in dps:
#     print(*r)
ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
def input():return sys.stdin.readline().strip()
def main():
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1; sw -= 1
    start = (sh+2)*(W+4) + 2 + sw
    dh, dw = map(int, input().split())
    dh -= 1; dw -= 1
    goal = (dh+2)*(W+4) + 2 + dw

    field = "#"*(W+4)*2
    field += "##" + "####".join([ input() for _ in range(H)]) + "##"
    field += "#"*(W+4)*2

    move = [-1, 1, -(W+4), W+4]
    ex_left = [-2*(W+4)-2, -(W+4)-2, -2, (W+4)-2, 2*(W+4)-2]
    ex_right = [-2*(W+4)+2, -(W+4)+2, +2, (W+4)+2, 2*(W+4)+2]
    ex_up = [-2*(W+4)-2, -2*(W+4)-1, -2*(W+4), -2*(W+4)+1, -2*(W+4)+2]
    ex_down = [2*(W+4)-2, 2*(W+4)-1, 2*(W+4), 2*(W+4)+1, 2*(W+4)+2]

    INF = 10 ** 18
    num = [INF] * (H+4) * (W+4)
    warped = [False] * (H+4) * (W+4)

    def bfs(s):
        q = deque()
        num[s] = 0
        q.append((s, 0))
    
        while q:
            now, cost = q.popleft()
            if cost > num[now]:
                continue
            else:
                num[now] = cost

            if now == goal:
                return

            for i, dx in enumerate(move):
                nx = now + dx
                if field[nx] == "." and num[nx] == INF:
                    q.appendleft((nx, cost))
                    num[nx] = cost

                elif field[nx] == "#":
                    if i == 0:
                        ex = ex_left
                    elif i == 1:
                        ex = ex_right
                    elif i == 2:
                        ex = ex_up
                    else:
                        ex = ex_down

                    for dx2 in ex:
                        nx2 = now + dx2
                        if field[nx2] == "." and num[nx2] == INF and not warped[nx2]:
                            q.append((nx2, cost+1))
                            warped[nx2] = True
    
    bfs(start)

    if num[goal] == INF:
        print(-1)
    else:
        print(num[goal])

    
    # for i in range(0, (H+4)*(W+4), W+4):
    #     print(field[i:i+W+4])
    
    # print(start)
    # print(start//(W+4), start%(W+4))
    # print(goal)
    # print(goal//(W+4), goal%(W+4))
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


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


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


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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**5]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

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

def BFS(maze,s,g):
  q1,q2 = deque([s]),deque()
  checked = []
  while len(q1)>0 or len(q2)>0:
    if len(q1)>0: h,w,n = q1.popleft()
    elif len(q2)>0: h,w,n = q2.popleft()
    if (h,w)==g: return n
    dp = [(i-2,j-2) for i in range(5) for j in range(5) if (i-2,j-2)!=(0,0)]
    for i in dp:
      if (h+i[0],w+i[1]) in checked: continue
      else: checked.append((h+i[0],w+i[1]))

      if (0<h+i[0]<len(maze)) and (0<w+i[1]<len(maze[0])) and maze[h+i[0]][w+i[1]]==".":
        if i[0]%2==0 or i[1]%2==0: q2.append((h+i[0],w+i[1],n+1))
        else: q1.append((h+i[0],w+i[1],n))
  return -1

print(BFS(maze,(CH-1,CW-1,0),(DH-1,DW-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()

import heapq

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=[[0,ch,cw]]
	heapq.heapify(Q)
	S[ch][cw]=0

	#print(Q)

	while Q:
		#print(Q)
		d,x,y=heapq.heappop(Q)

		if S[x][y]<d:
			continue

		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			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
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
						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
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
					else:
						if S[x+2*xx][y+t]==".":
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
						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
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]<d:
				S[x][y]=S[x+xx][y+yy]
				heapq.heappush(Q,[S[x+xx][y+yy],x,y])


	#print(S[2:-2])

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


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[1000]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(visited[gh][gw] if visited[gh][gw] != 1000 else -1)

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())
slist = [input() for i in range(h)]

if ch == dh and dw == cw:
    print(0)
    exit()

que = deque()
memo_que = deque()
que.append([ch - 1, cw - 1, 0])
memo_que.append([ch - 1, cw - 1, 0])
memo = {}
memo[(ch - 1, cw - 1)] = 0
ans = float("inf")
while len(que) != 0:
    while len(que) != 0:
        sh, sw, count = que.popleft()
        print(sh, sw, count)
        for ph, pw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if 0 <= sh + ph < h and 0 <= sw + pw < w:
                if sh + ph == dh - 1 and sw + pw == dw - 1:
                    print(count)
                    exit()
                if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count:
                    continue
                if slist[sh + ph][sw + pw] == ".":
                    que.append([sh + ph, sw + pw, count])
                    memo[(sh + ph, sw + pw)] = count
                    memo_que.append([sh + ph, sw + pw, count])
    templist = []
    for sh, sw, count in list(memo_que):
        print(sh, sw, count)
        for ph in range(-2, 3):
            for pw in range(-2, 3):
                if [ph, pw] not in [[-1, 0], [1, 0], [0, 1], [0, -1], [0, 0]]:
                    if 0 <= sh + ph < h and 0 <= sw + pw < w:
                        if sh + ph == dh - 1 and sw + pw == dw - 1:
                            print(count + 1)
                            exit()
                        if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count + 1:
                            continue
                        if slist[sh + ph][sw + pw] == ".":
                            que.append([sh + ph, sw + pw, count + 1])
                            memo[(sh + ph, sw + pw)] = count + 1
                            templist.append([sh + ph, sw + pw, count + 1])
    memo_que = deque(templist)

print(-1)

Submission status: Wrong Answer

Solution code:
import collections

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

res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
x,y = Ch,Cw
count = 0

que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0

while (que or que_warp):
    while (que):
        for i in range(4):
            nx = int(que[0][1]+dx[i])
            ny = int(que[0][0]+dy[i])
            if (1<=nx<=W) and (1<=ny<=H):
                if res_S[ny-1][nx-1]<0 and S[ny-1][nx-1]=='.':
                    res_S[ny-1][nx-1]=count
                    que.append((ny,nx))
                    que_warp.append((ny,nx))
        que.pop(0)

    count += 1

    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][1] + ddx[i])
            ny = int(que_warp[0][0] + ddy[i])
            if (1 <= nx <= W) and (1 <= ny <= H):
                if res_S[ny-1][nx-1]<0 and S[ny-1][nx-1]=='.':
                    res_S[ny-1][nx-1] = count
                    que.append((ny, nx))
        que_warp.pop(0)

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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
toGo = [[-1 if i != C[0] or j != C[1] else 0 for j in range(W)] for i in range(H)]
queue = [C]
ans = 0

while True:
    tmp = queue.pop()
    dfs = [tmp]

    while len(dfs):
        a = dfs.pop()
        for move in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            hh, ww = a[0] + move[0], a[1] + move[1]
            if hh >= H or hh < 0 or ww >= W or ww < 0:
                continue

            if toGo[hh][ww] == -1 and S[hh][ww] == '.':
                toGo[hh][ww] = ans
                dfs.append([hh, ww])

    if toGo[D[0]][D[1]] != -1:
        break

    flag = True
    if not len(queue):
        ans += 1
        for i in range(H):
            for j in range(W):
                if toGo[i][j] == ans - 1:
                    t = False
                    for ii in range(-2, 3):
                        for jj in range(-2, 3):
                            hh, ww = i + ii, j + jj
                            if hh >= H or hh < 0 or ww >= W or ww < 0:
                                continue

                            if toGo[hh][ww] == -1 and S[hh][ww] == '.':
                                toGo[hh][ww] = ans
                                flag, t = False, True
                                queue.append([hh, ww])
                                break
                        if t:
                            break
        if flag:
            print(-1)
            exit()

print(ans)