Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Wrong Answer

Solution code:
import queue

#入力
H,W = list(map(int,input().split()))
X_S, Y_S = list(map(int,input().split()))
X_G, Y_G = list(map(int,input().split()))

#壁と道を数字に
field = []
for _ in range(H):
    temp1 = input()
    temp2 = []
    for j in range(len(temp1)):
        if temp1[j] == ".":
            temp2.append(10000000000)
        elif temp1[j] == "#":
            temp2.append(-1)
    field.append(temp2)

#スタートとゴールを設定
field[X_S - 1][Y_S - 1] = 0
field[X_G - 1][Y_G - 1] = "G"

next_to_check = queue.Queue()    
next_to_check.put([X_S - 1, Y_S - 1])
changed = queue.Queue()
changed.put([X_S - 1, Y_S - 1])

#ウォークとワープ
def walk(z):
    x,y = z
    count = field[x][y]
    for i,j in [[0,1],[0,-1],[1,0],[-1,0]]:
        if x + i >= 0 and y + j >= 0 and x + i < H and y + j < W:
            try:
                if field[x + i][y + j] > count:
                    field[x + i][y + j] = count
                    next_to_check.put([x + i, y + j])
                    changed.put([x + i,y + j])
            except:
                print(count)
                exit()
            
def warp(z):
    x,y = z
    count = field[x][y] + 1
    for i,j 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 x + i >= 0 and y + j >= 0 and x + i < H and y + j < W:
            try:
                if field[x + i][y + j] > count:
                    field[x + i][y + j] = count
                    next_to_check.put([x + i, y + j])
            except:
                print(count)
                exit()
                
#実行部分

while not (next_to_check.empty() and changed.empty()):
    
    #walk
    while not next_to_check.empty():
        walk(next_to_check.get())
    #warp
    while not changed.empty():
        warp(changed.get())
        
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import queue

#入力
H,W = list(map(int,input().split()))
X_S, Y_S = list(map(int,input().split()))
X_G, Y_G = list(map(int,input().split()))

#壁と道を数字に
field = []
for _ in range(H):
    temp1 = input()
    temp2 = []
    for j in range(len(temp1)):
        if temp1[j] == ".":
            temp2.append(8)
        elif temp1[j] == "#":
            temp2.append(-1)
    field.append(temp2)

#スタートとゴールを設定
field[X_S - 1][Y_S - 1] = 0
field[X_G - 1][Y_G - 1] = "G"

next_to_check = queue.Queue()    
next_to_check.put([X_S - 1, Y_S - 1])
changed = queue.Queue()
changed.put([X_S - 1, Y_S - 1])

#ウォークとワープ
def walk(z):
    x,y = z
    count = field[x][y]
    for i,j in [[0,1],[0,-1],[1,0],[-1,0]]:
        if x + i >= 0 and y + j >= 0 and x + i < H and y + j < W:
            try:
                if field[x + i][y + j] > count:
                    field[x + i][y + j] = count
                    next_to_check.put([x + i, y + j])
                    changed.put([x + i,y + j])
            except:
                print(count)
                exit()
            
def warp(z):
    x,y = z
    count = field[x][y] + 1
    for i,j 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 x + i >= 0 and y + j >= 0 and x + i < H and y + j < W:
            try:
                if field[x + i][y + j] > count:
                    field[x + i][y + j] = count
                    next_to_check.put([x + i, y + j])
            except:
                print(count)
                exit()
                
#実行部分

while not (next_to_check.empty() and changed.empty()):
    
    #walk
    while not next_to_check.empty():
        walk(next_to_check.get())
    #warp
    while not changed.empty():
        warp(changed.get())
        
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

def select_shotest_coordinate(dh,dw,check):
  coordinate = check[0]
  min_dist = math.sqrt((dh-check[0][0])**2+(dw-check[0][1])**2)
  
  for ch in check:
    dist = math.sqrt((dh-ch[0])**2+(dw-ch[1])**2)
    if dist < min_dist:
      mindist = dist
      coordinate = ch
  
  return coordinate

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
stage = []
check = []
count = 0
for i in range(h):
  stage.append(input())
  
queue = deque([(ch,cw)])
check.append((ch,cw))

while True:
  while len(queue):
    v = queue.popleft()
  
    if v == (dh,dw):
      print(count)
      exit()

    if v[0] != 1 and stage[v[0]-2][v[1]-1] == '.' and (v[0]-1,v[1]) not in check:
      check.append((v[0]-1,v[1]))
      queue.append((v[0]-1,v[1]))
    if v[1] != 1 and stage[v[0]-1][v[1]-2] == '.' and (v[0],v[1]-1) not in check:
      check.append((v[0],v[1]-1))
      queue.append((v[0],v[1]-1))
    if v[0] != h and stage[v[0]][v[1]-1] == '.' and (v[0]+1,v[1]) not in check:
      check.append((v[0]+1,v[1]))
      queue.append((v[0]+1,v[1]))
    if v[1] != w and stage[v[0]-1][v[1]] == '.' and (v[0],v[1]+1) not in check:
      check.append((v[0],v[1]+1))
      queue.append((v[0],v[1]+1))
      
  canloop = True  
  coordinate = select_shotest_coordinate(dh,dw,check)
      
  for i in range(-2,3):
    for j in range(-2,3):
      y = coordinate[0] + i -1
      x = coordinate[1] + j -1
      if canloop and 0 <= y and y < h and 0 <= x and x < w and stage[y][x] == '.' and (y+1,x+1) not in check:
          check.append((y+1,x+1))
          queue.append((y+1,x+1))
          count += 1
          canloop = False
          break
      else:
        continue
      break
  
  if len(queue) == 0:
    print(-1)
    break

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())
stage = []
check = []
count = 0
for i in range(h):
  stage.append(input())
  
queue = deque([(ch,cw)])
check.append((ch,cw))

while True:
  while len(queue):
    v = queue.popleft()
  
    if v == (dh,dw):
      print(count)
      exit()

    if v[0] != 1 and stage[v[0]-2][v[1]-1] == '.' and (v[0]-1,v[1]) not in check:
      check.append((v[0]-1,v[1]))
      queue.append((v[0]-1,v[1]))
    if v[1] != 1 and stage[v[0]-1][v[1]-2] == '.' and (v[0],v[1]-1) not in check:
      check.append((v[0],v[1]-1))
      queue.append((v[0],v[1]-1))
    if v[0] != h and stage[v[0]][v[1]-1] == '.' and (v[0]+1,v[1]) not in check:
      check.append((v[0]+1,v[1]))
      queue.append((v[0]+1,v[1]))
    if v[1] != w and stage[v[0]-1][v[1]] == '.' and (v[0],v[1]+1) not in check:
      check.append((v[0],v[1]+1))
      queue.append((v[0],v[1]+1))
      
  canloop = True    
      
  for i in range(-2,3):
    for j in range(-2,3):
      y = v[0] + i -1
      x = v[1] + j -1
      if canloop and 0 <= y and y < h and 0 <= x and x < w and stage[y][x] == '.' and (y+1,x+1) not in check:
          check.append((y+1,x+1))
          queue.append((y+1,x+1))
          count += 1
          canloop = False
          break
      else:
        continue
      break
  
  if len(queue) == 0:
    print(-1)
    break

Submission status: Wrong Answer

Solution code:
import numpy as np
from queue 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

def warpable(maze, score, h, w):
    neighbors = [-2, -1, 0, 1, -2]
    for dh in neighbors:
        for dw in neighbors:
            y = h + dh
            x = w + dw
            if y < 0 or H <= y:
                continue
            if w < 0 or W <= x:
                continue
            if maze[y, x] == '.' and score[y, x] < -1:
                return True
    return False



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

score = np.zeros((H, W), dtype=int)
score[:, :] = -1

score[Ch, Cw] = 0

visited = np.zeros((H, W), dtype=bool)

candidates = Queue()
candidates.put((Ch, Cw))

while not candidates.empty():
    moved = False
    h, w = candidates.get()
    # move
    dh = [-1, +1, 0, 0]
    dw = [0, 0, +1, -1]
    for i in range(4):
        y = h + dh[i]
        x = w + dw[i]
        if y < 0 or H <= y:
            continue
        if x < 0 or W <= x:
            continue        
        if maze[y][x] == '.' and score[y, x] < 0:
            score[y, x] = score[h, w]
            candidates.put((y, x))
            moved = True        
    # warp
    if not moved: 
        neighbors = [-2, -1, 0, 1, -2]
        for dh in neighbors:
            for dw in neighbors:
                y = h + dh
                x = w + dw
                if y < 0 or H <= y:
                    continue
                if x < 0 or W <= x:
                    continue
                if maze[y][x] == '.' and score[y, x] < 0:
                    score[y, x] = score[h, w] + 1
                    candidates.put((y, x))

print (score[Dh, Dw])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
ans = 0
seen = [[-1]*W for _ in range(H)]
vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]
v2 = [[1, 1], [-1, 1], [-1, -1], [1, -1], [2, 1], [1, 2], [-1, 2], [2, -1], [-2, 1], [1, -2], [-1, -2], [-2, -1], [2, 0], [0, 2], [-2, 0], [0, -2], [2, 2], [2, -2], [-2, -2], [-2, 2]]
queue = deque()
q = deque()
queue.append([Ch-1, Cw-1])
q.append([Ch-1, Cw-1])
seen[Ch-1][Cw-1]=0

while queue:
    while queue:
        l = queue.popleft()
        h, w = l[0], l[1]
        for ll in vec:
            #コースアウト
            if h+ll[0]>=H or h+ll[0]<0 or w+ll[1]>=W or w+ll[1]<0:
                continue
            #障害物
            if S[h+ll[0]][w+ll[1]]=="#":
                continue
            #既視
            if seen[h+ll[0]][w+ll[1]]!=-1:
                continue
            queue.append([h+ll[0], w+ll[1]])
            q.append([h+ll[0], w+ll[1]])
            seen[h+ll[0]][w+ll[1]]=ans
    if seen[Dh-1][Dw-1]!=-1:
        print(seen[Dh-1][Dw-1])
        sys.exit()
    ans+=1
    while q:
        l = q.popleft()
        h, w = l[0], l[1]
        for z in v2:
            #コースアウト
            if h+z[0]>=H or h+z[0]<0 or w+z[1]>=W or w+z[1]<0:
                continue
            #障害物
            if S[h+z[0]][w+z[1]]=="#":
                continue
            #既視
            if seen[h+z[0]][w+z[1]]!=-1:
                continue
            queue.append([h+z[0], w+z[1]])
            seen[h+z[0]][w+z[1]]=ans
    if seen[Dh-1][Dw-1]!=-1:
        print(seen[Dh-1][Dw-1])
        sys.exit()
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
ans = 0
seen = [[-1]*W for _ in range(H)]
vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]
v2 = [[1, 1], [-1, 1], [-1, -1], [1, -1], [2, 1], [1, 2], [-1, 2], [2, -1], [-2, 1], [1, -2], [-1, -2], [-2, -1], [2, 0], [0, 2], [-2, 0], [0, -2], [2, 2], [2, -2], [-2, -2], [-2, 2]]
queue = deque()
q = deque()
queue.append([Ch-1, Cw-1])
q.append([Ch-1, Cw-1])
seen[Ch-1][Cw-1]=0

while queue:
    while queue:
        l = queue.popleft()
        h, w = l[0], l[1]
        for ll in vec:
            if h+ll[0]==Dh-1 and w+ll[1]==Dw-1:
                print(ans)
                sys.exit()
            #コースアウト
            if h+ll[0]>=H or h+ll[0]<0 or w+ll[1]>=W or w+ll[1]<0:
                continue
            #障害物
            if S[h+ll[0]][w+ll[1]]=="#":
                continue
            #既視
            if seen[h+ll[0]][w+ll[1]]!=-1:
                continue
            queue.append([h+ll[0], w+ll[1]])
            q.append([h+ll[0], w+ll[1]])
            seen[h+ll[0]][w+ll[1]]=ans
    ans+=1
    while q:
        l = q.popleft()
        h, w = l[0], l[1]
        for z in v2:  
            if h+z[0]==Dh-1 and w+z[1]==Dw-1:
                print(ans)
                sys.exit()
            #コースアウト
            if h+z[0]>=H or h+z[0]<0 or w+z[1]>=W or w+z[1]<0:
                continue
            #障害物
            if S[h+z[0]][w+z[1]]=="#":
                continue
            #既視
            if seen[h+z[0]][w+z[1]]!=-1:
                continue
            queue.append([h+z[0], w+z[1]])
            seen[h+z[0]][w+z[1]]=ans
print(-1)

Submission status: Wrong Answer

Solution code:
import copy


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()))
visited = []
visited.append([ch-1, cw-1])
new_visit = [[ch-1, cw-1]]


def check_pos(s, x, y, dx, dy, visited):
    if x+dx < 0 or x+dx >= w:
        return
    if y+dy < 0 or y+dy >= h:
        return

    if s[y+dy][x+dx] == ".":
        if [y+dy, x+dx] not in visited:
            visited.append([y+dy, x+dx])
            new_visit.append([y+dy, x+dx])
            check_around(s, x+dx, y+dy, visited)


def check_around(s, x, y, visited):
    check_pos(s, x, y, 1, 0, visited)
    check_pos(s, x, y, 0, 1, visited)
    check_pos(s, x, y, 0, -1, visited)
    check_pos(s, x, y, -1, 0, visited)

def warp(x, y, visited, s):
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if dx == 0 and dy == 0:
                continue
            if x+dx < 0 or x+dx >= w:
                continue
            if y+dy < 0 or y+dy >= h:
                continue

            if s[y+dy][x+dx] == ".":
                if [y+dy, x+dx] not in visited:
                    new_visit.append([y+dy, x+dx])
                    visited.append([y+dy, x+dx])

def second_move(visited, s):
    prev_visited = copy.deepcopy(visited)
    for visited_pos in prev_visited:
        warp(visited_pos[1], visited_pos[0], visited, s)

count = 0
is_finish = False
while not is_finish and visited:
    prev_new_visit = copy.deepcopy(new_visit)
    for visited_pos in prev_new_visit:
        check_around(s, visited_pos[0], visited_pos[1], visited)
    for visited_pos in new_visit:
        if visited_pos[0]+1 == dh and visited_pos[1]+1 == dw:
            print(count)
            is_finish = True
            break
    new_visit = []
    second_move(visited, s)
    count += 1
    if not new_visit and not is_finish:
        print("-1")
        is_finish = True

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
si,sj=map(int,input().split())
di,dj=map(int,input().split())

D =[f'{input()}' for _ in range(H)]


# デキューを用意する
from collections import deque
d = deque()

si-=1
sj-=1
di-=1
dj-=1
fx = [1,0,-1,0]
fy = [0,1,0,-1]

ans = [[float('inf')] * (W) for _ in range(H)]
p = 0
Done = []
d.append((si,sj,p))


while len(d) !=0:
    i,j,pp = d.popleft()
    if (i,j) in Done:continue
    Done.append((i,j))
    ans[i][j] = pp
    if (i,j) == (di,dj):
      print(ans[di][dj])
    
    for x,y in zip(fx,fy):

        if i+x < 0 or i+x > H-1 or j+y <0 or j+y >W-1: continue
        if D[i+x][j+y] == "#":continue
        if ans[i+x][j+y] <= ans[i][j] :continue
        if (i+x,j+y) in Done :continue
        d.appendleft((i+x,j+y,ans[i][j] ))

    for mx in range(-2,3):
        for my in range(-2,3):
            if i+mx < 0 or i+mx > H-1 or j+my <0 or j+my >W-1: continue
            if D[i+mx][j+my] == "#":continue
            if ans[i+mx][j+my] <= ans[i][j] + 1 :continue
            if (i+mx,j+my) in Done :continue
            d.append((i+mx,j+my,ans[i][j]+1))
            
if ans[di][dj] == float('inf') :
  print(-1)
else:
  print(ans[di][dj])

Submission status: Wrong Answer

Solution code:
from collections import deque
 
def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    grid = []
    for i in range(H):
        grid.append(list(input()))
 
    INF = 10**15
    d = [[INF for _ in range(W)] for _ in range(H)]    
    d[Ch-1][Cw-1] = 0
 
    direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]
 
    def dfs(ch, cw):   
        stack = deque()
        stack.append((ch, cw))
    
        while stack:
            x, y = stack.popleft()
        
            if(x == Dh-1 and y == Dw-1):
                return d[x][y]
    
            for dx, dy in direction:
                nx = x + dx
                ny = y + dy
        
                if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                    continue
                if(grid[nx][ny] == "#"):
                    continue
                if(d[nx][ny] != INF):
                    continue
                d[nx][ny] = d[x][y]
                stack.append((nx, ny))
        
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if(x+i < 0 or x+i >= H or y+j < 0 or y+j >= W):
                        continue
                    if(grid[x+i][y+j] == "#"):
                        continue
                    if(d[x][y] + 1 >= d[x+i][y+j]):
                        continue
                    d[x+i][y+j] = d[x][y] + 1
                    stack.append((x+i, y+j))
        return -1
    
    print(dfs(Ch-1, Cw-1))
        
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
 
def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    grid = []
    for i in range(H):
        grid.append(list(input()))
 
    INF = 10**15
    d = [[INF for _ in range(W)] for _ in range(H)]    
    d[Ch-1][Cw-1] = 0
 
    direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]
 
    def dfs(ch, cw):   
        stack = deque()
        stack.append((ch, cw))
    
        while stack:
            x, y = stack.popleft()
        
            if(x == Dh-1 and y == Dw-1):
                return d[x][y]
    
            for dx, dy in direction:
                nx = x + dx
                ny = y + dy
        
                if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                    continue
                if(grid[nx][ny] == "#"):
                    continue
                if(d[nx][ny] == INF):
                    continue
                d[nx][ny] = d[x][y]
                stack.append((nx, ny))
        
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if(x+i < 0 or x+i >= H or y+j < 0 or y+j >= W):
                        continue
                    if(grid[x+i][y+j] == "#"):
                        continue
                    if(d[x][y] + 1 >= d[x+i][y+j]):
                        continue
                    d[x+i][y+j] = d[x][y] + 1
                    stack.append((x+i, y+j))
        return -1
    
    print(dfs(Ch-1, Cw-1))
        
main()

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

inf=1<<20
def dijkstra(edge,st):
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    q=[(0,st)]
    heapify(q)
    v=[False]*n
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                heappush(q,(alt,dst))
    return d

# Under construction
# To be verified by https://atcoder.jp/contests/abc176/tasks/abc176_d

class GridGraph:
    def __init__(self,h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
        self.h=h+2
        self.w=w+2
        self.n=self.h*self.w
        self.edge=[[]for i in range(self.n)]
        self.nb=[-1,1,-self.w,self.w]
        #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
        self.mp=[boundary]*self.w
        self.found={}
        for i in range(self.h-2):
            s=input()
            self.mp+=[boundary]
            for i in range(self.w-2):
                char=s[i]
                if search and char in search:
                    self.found[char]=((i+1)*self.w+i+1)
                    mp_def[char]=mp_def[replacement_of_found]
                self.mp+=[mp_def[char]]
            self.mp+=[boundary]
        self.mp+=[boundary]*self.w
        self.h,self.w,self.mp,self.found
        return

    def create_edge(self,cost_func=lambda x,y:1):
        w=self.w
        nbw=[2,2*w+1,2*w+2,w+1,w+2,+2*w,2*w-1,2*w-2,w-1,w-2]
        for i in range(self.n):
            if self.mp[i]==1:
                continue
            for di in self.nb:
                nx=i+di
                if self.mp[nx]!=1:
                    #self.edge[i].append((nx,cost_func(self.mp[i],self.mp[nx])))
                    self.edge[i].append((nx,0))
            
            for di in nbw:
                nx=i+di
                if 0<=nx<self.n and self.mp[nx]!=1:
                    self.edge[i].append((nx,1))
                    self.edge[nx].append((i,1))
            
        return self.edge


    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v

    def __str__(self):
        for i in range(self.h):
            print(self.mp[i*self.w:(i+1)*self.w])
        return ''
 
    def show_map(self,length=2):
        for i in range(self.h):
            print(*[' '*(length-(len(str(j))))+str(j) for j in self.mp[i*self.w:(i+1)*self.w]])

    def show_node_num(self,length=2):
        for i in range(self.h):
            print(*[' '*(length-(len(str(j))))+str(j) for j in range(i*self.w,(i+1)*self.w)])

    def show_map_w_node_num(self,length=2):
        for i in range(self.h):
            print(*[[' '*(length-(len(str(j))))+str(j),self.mp[j]] for j in range(i*self.w,(i+1)*self.w)])
    
    def show_edge(self,length=2):
        for i in range(self.h):
            print(*[[' '*(length-(len(str(j))))+str(j),self.edge[j]] for j in range(i*self.w,(i+1)*self.w)])


    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

show_flg=False
show_flg=True

ans=0

h,w=LI()
sh,sw=LI()
gh,gw=LI()

gg=GridGraph(h,w)
gg.create_edge()
d=dijkstra(gg.edge,sh*gg.w+sw)
print(d[gh*gg.w+gw])

Submission status: Wrong Answer

Solution code:
# 01-bfs
from collections import deque
import math
t1 = ((1,0),(-1,0),(0,1),(0,-1))
t2 = (((2,2),(2,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)))
h,w = map(int,input().split())
ch,cw = map(lambda x:int(x)-1,input().split())
dh,dw = map(lambda x:int(x)-1,input().split())
s = [input() for _ in range(h)]
d = deque([[ch,cw,0]]) #[x,y,cost]
visited = [[math.inf]*w for _ in range(h)]
visited[ch][cw] = 0

while d:
    x,y,cost = d.popleft()
    if y==dh and x==dw:
        break
    for dx,dy in t1:
        if 0<=y+dy<=h-1 and 0<=x+dx<=w-1:
            if visited[y+dy][x+dx]>cost and s[y+dy][x+dx]=='.':
                visited[y+dy][x+dx]=cost
                d.appendleft([y+dy,x+dx,cost])
    for dx,dy in t2:
        if 0<=y+dy<=h-1 and 0<=x+dx<=w-1:
            if visited[y+dy][x+dx]>cost+1 and s[y+dy][x+dx]=='.':
                visited[y+dy][x+dx]=cost+1
                d.append([y+dy,x+dx,cost+1])
            
if visited[dh][dw]==math.inf:
    print(-1)
else:
    print(cost)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
 
import sys
from collections import deque 
INF = float('INF') #INFの宣言
#入力部
H, W = map(int, input().split())
Ch, Cw = map(lambda c: int(c) +1 , input().split())
Dh, Dw = map(lambda d: int(d) +1, input().split())
mymap = []
mymap += [['#' for w in range(W+4)]]
mymap += [['#' for w in range(W+4)]]
for h in range(H):
    mymap += [ ['#', '#'] + list(input()) +['#', '#']]
mymap += [['#' for w in range(W+4)]]
mymap += [['#' for w in range(W+4)]]
#for m in mymap:
#    print(m)
#各地点までの最短距離の配列,INFで初期化
d = [ [INF for w in range(W+4)] for h in range(H+4) ]
#obstacleの処理
for h in range(H+4):
    for w in range(W+4):
        if mymap[h][w] == '#':
            d[h][w] = -1
#for dd in d:
#    print(dd)
#移動4方向のベクトル
dx, dy  = [1, 0, -1, 0], [0, 1, 0, -1]  
 
def bfs(h, w):
    warp_cnt = 0
    mydeque = deque()
    mydeque.append([h, w]) #スタート地点をdequeに入れる
    d[h][w] = warp_cnt     #スタート地点のwarp回数をresにする
    #warp先の座標を格納するリスト
    warp_deque = deque()
    # dequeが空になるまでループ
    while mydeque:
        while mydeque:
            #dequeの先頭を取り出す
            y, x = mydeque.popleft()
            warp_deque.append((y,x))
            for i in range(4):
                #移動後の点を(nx, ny) とする
                nx, ny = x + dx[i], y + dy[i]
                if  d[ny][nx] >  warp_cnt:
                    d[ny][nx] =  warp_cnt
                    #print(ny, nx, d[ny][nx], mymap[ny][nx])
                    #if  mymap[ny][nx] != '#' : 
                    #移動できるならdequeに入れ、その点の距離をwarp_cntで確定する
                    mydeque.append([ny, nx])
                    #if d[ny][nx] > warp_cnt:
                    #    d[ny][nx] = warp_cnt
                #if d[ny][nx] != -1:
                #warp_deque.append((ny, nx))
        #for dd in d:
        #    print(dd)
        #xprint('---- w')
        #Goalが探索済みであれば，探索をやめる
        if d[Dh][Dw] != INF:
            break
        #warpの処理
        print(warp_deque)
        warp_cnt += 1
        while warp_deque:
            a, b = warp_deque.popleft()
            for ii in range(-2, 3):
                for jj in range(-2, 3):
                    nny, nnx = a + ii, b + jj
                    if d[nny][nnx] > warp_cnt:
                        d[nny][nnx] = warp_cnt
                        mydeque.append([nny,nnx])
        #for dd in d:
        #    print(dd)
        #print('----')
    return
 
 
bfs(Ch,Cw)
#for dd in d:
#    print(dd)

if d[Dh][Dw] == INF:
    print(-1)
else:
    print(d[Dh][Dw])