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:
#dp[][]は何回のジャンプが必要かを示す

from collections import deque
h,w = list(map(int,input().split()))
sy,sx = list(map(int,input().split()))
gy,gx = list(map(int,input().split()))


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


grid = [input() for _ in range(h)]
dp = [[-1 for _ in range(w)] for _ in range(h)]

dp[sy][sx] = 0

#print(dp)
pos_que = deque()
pos_que.append((sx,sy))
#print(pos_que)

def area_move(pos_que):
    while pos_que:
        px,py = pos_que.popleft()
        d = dp[py][px]
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            px_new = px + dx
            py_new = py + dy
            if py_new < 0 or h <= py_new or px_new < 0 or w <= px_new or dp[py_new][px_new] != -1:
                continue
            if grid[py_new][px_new] == '.':
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
    return False




def magic_jump(n):
    for i in range(w):
        for j in range(h):
            if dp[j][i] == n:
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '.' and dp[new_h][new_w] == -1:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '.'and dp[new_h][new_w] == -1:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                
def main(dp_old):
    for i in range(100):
        area_move(pos_que)
        if dp[gy][gx] != -1:
            return dp[gy][gx]
        #print(i)
        magic_jump(i)
        #print(i)
        if not pos_que:
            return -1
    return -1

print(main([]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
h,w = map(int,input().split())
sx,sy = map(int,input().split())
sx -= 1
sy -= 1
gx,gy = map(int,input().split())
gx -= 1
gy -= 1
route = []
for i in range(h):
  lst = list(input())
  route.append(lst)
  
brock = [['#']*w for i in range(h)]
s = 0
que = deque([])
dx = [-1,0,1,0]
dy = [0,-1,0,1]

brock[sx][sy] = 0
que.append((sx,sy))
lst = [(sx,sy)]


while que:
  (p,q) = que.popleft()
  if (p,q) == (gx,gy):
    print(brock[gx][gy])
    sys.exit()
  for i in range(4):
    p2,q2 = p+dx[i],q+dy[i]
    if 0 <= p2 < h and 0<= q2 < w and route[p2][q2] == '.' and brock[p2][q2] == '#':
      brock[p2][q2] = brock[p][q]
      que.append((p2,q2))
      lst.append((p2,q2))
      
    if len(que) == 0:
      s += 1
      for (x,y) in lst:
        
        for j in range(-2,3):
          for k in range(-2,3):
            x2 = x+j
            y2 = y+k
            if 0 <= x2 < h and 0<= y2 < w and route[x2][y2] == '.' and brock[x2][y2] == '#':
              brock[x2][y2] = s
              que.append((x2,y2))
              
print(-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c = list(map(int,input().split()))
c[0] -= 1
c[1] -= 1
d = list(map(int,input().split()))
d[0] -= 1
d[1] -= 1
p = []
q = [[None for i in range(w)]for i in range(h)]
r = [[] for i in range(10**6)]
for i in range(h):
    s = input()
    s = list(s)
    p.append(s)
from collections import deque
de = deque()
de.append([c[0],c[1]])
q[c[0]][c[1]] = 0
g = 0
while q[d[0]][d[1]] == None and g < 10**6-3:
    while de:
        v = de.popleft()
        r[g].append([v[0],v[1]])
        for i in (-1,1):
            j = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
        for j in (-1,1):
            i = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
    g += 1
    while r[g-1]:
        v = r[g-1].pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if -1 <= i <= 1 and -1 <= j <= 1:
                    continue
                else:
                    if 0 <= v[0]-i <= h-1:
                        if 0 <= v[1]-j <= w-1:
                            if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                                q[v[0]-i][v[1]-j] = g
                                de.append([v[0]-i,v[1]-j])
if q[d[0]][d[1]] == None:
    print(-1)
else:
    print(q[d[0]][d[1]])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c = list(map(int,input().split()))
c[0] -= 1
c[1] -= 1
d = list(map(int,input().split()))
d[0] -= 1
d[1] -= 1
p = []
q = [[None for i in range(w)]for i in range(h)]
r = [[] for i in range(10**6)]
for i in range(h):
    s = input()
    s = list(s)
    p.append(s)
from collections import deque
de = deque()
de.append([c[0],c[1]])
q[c[0]][c[1]] = 0
g = 0
while q[d[0]-1][d[1]-1] == None and g < 10**6-3:
    while de:
        v = de.popleft()
        r[g].append([v[0],v[1]])
        for i in (-1,1):
            j = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
        for j in (-1,1):
            i = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
    g += 1
    while r[g-1]:
        v = r[g-1].pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if -1 <= i <= 1 and -1 <= j <= 1:
                    continue
                else:
                    if 0 <= v[0]-i <= h-1:
                        if 0 <= v[1]-j <= w-1:
                            if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                                q[v[0]-i][v[1]-j] = g
                                de.append([v[0]-i,v[1]-j])
if q[d[0]][d[1]] == None:
    print(-1)
else:
    print(q[d[0]][d[1]])

Submission status: Wrong Answer

Solution code:
from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int, input().split())
si,sj = map(int, input().split())
ti,tj = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -=1
s = list()
for i in range(H):
  s.append(input())

inf = 10**9
dist = [[inf] * W for i in range(H)]
q = deque()
q.appendleft([si,sj])
dist[si][sj] = 0
while(len(q) > 0):
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == "#":
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
  for ei in range(-2, 3, 1):
    for ej in range(-2, 3, 1):
      ni = i + ei
      nj = j + ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if dist[ni][nj] <= d+1:
        continue
      if s[ni][nj] == "#":
        continue
      dist[ni][nj] = d+1
      q.append([ni,nj])

ans = dist[ti][tj]
if ans == inf:
  ans -= 1
print(ans)

Submission status: Wrong Answer

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

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

chizu[ch-1][cw-1]=0

def bfs(x,y,num):
    global chizu
    for i in [-2,-1,0,1,2]:#x座標
        for j in [-2,-1,0,1,2]:#y座標
            if i!=0 or j!=0:#周囲の24つ調べる
                if 1<=x+i<=h and 1<=y+j<=w:#枠内ならば
                    if [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:#上下左右
                        if chizu[x+i-1][y+j-1]!="#":#道があれば
                            if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                                chizu[x+i-1][y+j-1]=num
                                bfs(x+i,y+j,num)
                            else:#到達済みなら
                                if num<chizu[x+i-1][y+j-1]:#より早ければ
                                    chizu[x+i-1][y+j-1]=num
                                    bfs(x+i,y+j,num)
                    else:#ワープ
                        if chizu[x+i-1][y+j-1]!="#":#道があれば
                            if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                                chizu[x+i-1][y+j-1]=num+1
                                bfs(x+i,y+j,num+1)
                            """
                            else:#到達済みなら
                                if num+1<chizu[x+i-1][y+j-1]:#より早ければ
                                    chizu[x+i-1][y+j-1]=num+1
                                    bfs(x+i,y+j,num+1)
"""

bfs(ch,cw,0)
ans=chizu[dh-1][dw-1]
if chizu[dh-1][dw-1]=="#" or chizu[dh-1][dw-1]==".":
    ans=-1
print(ans)

Submission status: Wrong Answer

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

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

def bfs(x,y,num):
    global chizu
    for i in [-2,-1,0,1,2]:#x座標
        for j in [-2,-1,0,1,2]:#y座標
            if i!=0 or j!=0:#周囲の24つ調べる
                if 1<=x+i<=h and 1<=y+j<=w:#枠内ならば
                    if [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:#上下左右
                        if chizu[x+i-1][y+j-1]!="#":#道があれば
                            if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                                chizu[x+i-1][y+j-1]=num
                                bfs(x+i,y+j,num)
                            else:#到達済みなら
                                if num<chizu[x+i-1][y+j-1]:#より早ければ
                                    chizu[x+i-1][y+j-1]=num
                                    bfs(x+i,y+j,num)
                    else:#ワープ
                        if chizu[x+i-1][y+j-1]!="#":#道があれば
                            if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                                chizu[x+i-1][y+j-1]=num+1
                                bfs(x+i,y+j,num+1)
                            else:#到達済みなら
                                if num+1<chizu[x+i-1][y+j-1]:#より早ければ
                                    chizu[x+i-1][y+j-1]=num+1
                                    bfs(x+i,y+j,num+1)


bfs(ch,cw,0)

print(chizu[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()))

Ss = [str(input()) for _ in range(H)]
group = [[-1 for _ in range(W)] for _ in range(H)]

moves = [[-1,0], [1,0], [0,-1], [0,1]]

from collections import deque
todo = deque()
now_group = -1
for i in range(H):
    for j in range(W):
        if group[i][j] == -1 and Ss[i][j]==".":
            todo.append([i,j])
            now_group += 1
            group[i][j] = now_group
        while len(todo) > 0:
            checking = todo.pop()
            for move in moves:
                now = [checking[0]+move[0],checking[1]+move[1]]
                if not (0 <= now[0] <H and 0 <= now[1] <W):
                    continue
                if group[now[0]][now[1]] == -1 and Ss[now[0]][now[1]]==".":
                    todo.append(now)
                    group[now[0]][now[1]] = now_group

can_waap = [set() for _ in range(now_group+1)]

for i in range(H):
    for j in range(W):
        if group[i][j] ==-1:
            continue
        for yoko in range(-2,3):
            for tate in range(-2,3):
                now = [tate+i, yoko+j]
                if not (0<=now[0]<H and 0<=now[1]<W):
                    continue
                if group[now[0]][now[1]] == -1:
                    continue
                
                if group[i][j] != group[now[0]][now[1]]:
                    can_waap[group[i][j]].add(group[now[0]][now[1]])
                    can_waap[group[now[0]][now[1]]].add(group[i][j])

start = group[C[0]][C[1]]
goal = group[D[0]][D[1]]
import sys
import copy
seen = set([start])
nows = [start]

if start==goal:
    print(0)
    sys.exit()
print(can_waap)
for step in range(now_group+1):
    pre_nows = copy.deepcopy(nows)
    nows = []
    for pre_now in pre_nows:
        for j in can_waap[pre_now]:
            if j not in seen:
                seen.add(j)
                nows.append(j)
                if j == goal:
                    print(step+1)
                    sys.exit()

print(-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()))

Ss = [str(input()) for _ in range(H)]
group = [[-1 for _ in range(W)] for _ in range(H)]

moves = [[-1,0], [1,0], [0,-1], [0,1]]

from collections import deque
todo = deque()
now_group = -1
for i in range(H):
    for j in range(W):
        if group[i][j] == -1 and Ss[i][j]==".":
            todo.append([i,j])
            now_group += 1
            group[i][j] = now_group
        while len(todo) > 0:
            checking = todo.pop()
            for move in moves:
                now = [checking[0]+move[0],checking[1]+move[1]]
                if not (0 <= now[0] <H and 0 <= now[1] <W):
                    continue
                if group[now[0]][now[1]] == -1 and Ss[now[0]][now[1]]==".":
                    todo.append(now)
                    group[now[0]][now[1]] = now_group

can_waap = [set() for _ in range(now_group+1)]

for i in range(H):
    for j in range(W):
        if group[i][j] ==-1:
            continue
        for yoko in range(-2,3):
            for tate in range(-2,3):
                now = [tate+i, yoko+j]
                if not (0<=now[0]<H and 0<=now[1]<W):
                    continue
                if group[now[0]][now[1]] == -1:
                    continue
                
                if group[i][j] != group[now[0]][now[1]]:
                    can_waap[group[i][j]].add(group[now[0]][now[1]])
                    can_waap[group[now[0]][now[1]]].add(group[i][j])
start = group[C[0]][C[1]]
goal = group[D[0]][D[1]]
import sys
import copy
seen = set([start])
nows = [start]

if start==goal:
    print(0)
    sys.exit()

for step in range(now_group+1):
    pre_nows = copy.deepcopy(nows)
    nows = []
    for pre_now in range(len(pre_nows)):
        for j in can_waap[pre_now]:
            if j not in seen:
                seen.add(j)
                nows.append(j)
                if j == goal:
                    print(step+1)
                    sys.exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = 10 ** 12

class BFS:
    def __init__(self, H, W, S, C, D):
        self.H = H
        self.W = W
        self.S = S
        # 魔法使いの場所
        self.C = C
        # 目的地
        self.D = D

        # 盤面上のセルの状態
        # -1: 未到達
        # 0 : 魔法0回で到達
        # 1 : 魔法1回で到達
        # 2 : 魔法2回で到達, and so on...
        self.board_states = [[INF] * W for i in range(H)]
        self.board_states[C[0]][C[1]] = 0
        self.queue = deque([C])

    def is_legal_move(self, move):
        h = move[0]
        w = move[1]

        if h < 0 or h >= self.H or w < 0 or w >= self.W:
            return False
        return self.S[h][w] == "."

    def walk(self):
        while len(self.queue) > 0:
            move = self.queue.popleft()
            step_count = self.get_boart_states(move)

            if move == self.D:
                return

            up = (move[0]-1, move[1])
            down = (move[0]+1, move[1])
            left = (move[0], move[1]-1)
            right = (move[0], move[1]+1)

            next_moves = list(filter(self.is_legal_move, [up, down, left, right]))

            for next_move in next_moves:
                if self.get_boart_states(next_move) > step_count:
                    self.queue.append(next_move)
                    self.set_boart_states(next_move, step_count)

            for i in range(-2, 3):
                for j in range(-2, 3):
                    next_move = (move[0]+i, move[1]+j)
                    if not self.is_legal_move(next_move):
                        continue

                    if self.get_boart_states(next_move) > step_count + 1:
                        self.queue.append(next_move)
                        self.set_boart_states(next_move, step_count + 1)

    def set_boart_states(self, move, value):
        self.board_states[move[0]][move[1]] = value

    def get_boart_states(self, move):
        return self.board_states[move[0]][move[1]]

    def print_board_states(self):
        for l in self.board_states:
            print(l)

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1

S = [ [None] * W for i in range(H) ]
for i in range(H):
    l = input()
    for j, s in enumerate(l):
        S[i][j] = s

bfs = BFS(H, W, S, (C_h, C_w), (D_h, D_w))
bfs.walk()
goal_state = bfs.get_boart_states((D_h, D_w))
print(goal_state if goal_state != INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = 10 ** 12

class BFS:
    def __init__(self, H, W, S, C, D):
        self.H = H
        self.W = W
        self.S = S
        # 魔法使いの場所
        self.C = C
        # 目的地
        self.D = D

        # 盤面上のセルの状態
        # -1: 未到達
        # 0 : 魔法0回で到達
        # 1 : 魔法1回で到達
        # 2 : 魔法2回で到達, and so on...
        self.board_states = [[INF] * W for i in range(H)]
        self.board_states[C[0]][C[1]] = 0
        self.queue = deque([C])

    def is_legal_move(self, move):
        h = move[0]
        w = move[1]

        if h < 0 or h >= self.H or w < 0 or w >= self.W:
            return False
        return self.S[h][w] == "."

    def walk(self):
        while len(self.queue) > 0:
            move = self.queue.popleft()
            step_count = self.get_boart_states(move)

            if move == self.D:
                return

            up = (move[0]-1, move[1])
            down = (move[0]+1, move[1])
            left = (move[0], move[1]-1)
            right = (move[0], move[1]+1)

            next_moves = list(filter(self.is_legal_move, [up, down, left, right]))

            for next_move in next_moves:
                if self.get_boart_states(next_move) == step_count:
                    continue
                self.queue.append(next_move)
                self.set_boart_states(next_move, step_count)

            for i in range(-2, 3):
                for j in range(-2, 3):
                    next_move = (move[0]+i, move[1]+j)
                    if not self.is_legal_move(next_move):
                        continue

                    if self.get_boart_states(next_move) > step_count + 1:
                        self.queue.append(next_move)
                        self.set_boart_states(next_move, step_count + 1)

    def set_boart_states(self, move, value):
        self.board_states[move[0]][move[1]] = value

    def get_boart_states(self, move):
        return self.board_states[move[0]][move[1]]

    def print_board_states(self):
        for l in self.board_states:
            print(l)

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1

S = [ [None] * W for i in range(H) ]
for i in range(H):
    l = input()
    for j, s in enumerate(l):
        S[i][j] = s

bfs = BFS(H, W, S, (C_h, C_w), (D_h, D_w))
bfs.walk()
goal_state = bfs.get_boart_states((D_h, D_w))
print(goal_state if goal_state != INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

## INF = 10 ** 12
INF = 10

class BFS:
    def __init__(self, H, W, S, C, D):
        self.H = H
        self.W = W
        self.S = S
        # 魔法使いの場所
        self.C = C
        # 目的地
        self.D = D

        # 盤面上のセルの状態
        # -1: 未到達
        # 0 : 魔法0回で到達
        # 1 : 魔法1回で到達
        # 2 : 魔法2回で到達, and so on...
        self.board_states = [[INF] * W for i in range(H)]
        self.board_states[C[0]][C[1]] = 0
        self.queue = deque([C])

    def is_legal_move(self, move):
        h = move[0]
        w = move[1]

        if h < 0 or h >= self.H or w < 0 or w >= self.W:
            return False
        return self.S[h][w] == "."

    def walk(self):
        while len(self.queue) > 0:
            move = self.queue.popleft()
            step_count = self.get_boart_states(move)

            if move == self.D:
                return

            up = (move[0]-1, move[1])
            down = (move[0]+1, move[1])
            left = (move[0], move[1]-1)
            right = (move[0], move[1]+1)

            next_moves = list(filter(self.is_legal_move, [up, down, left, right]))

            for next_move in next_moves:
                self.queue.append(next_move)
                self.set_boart_states(next_move, step_count)

            for i in range(-2, 3):
                for j in range(-2, 3):
                    next_move = (move[0]+i, move[1]+j)
                    if not self.is_legal_move(next_move):
                        continue

                    if self.get_boart_states(next_move) > step_count + 1:
                        self.queue.append(next_move)
                        self.set_boart_states(next_move, step_count + 1)

    def set_boart_states(self, move, value):
        self.board_states[move[0]][move[1]] = value

    def get_boart_states(self, move):
        return self.board_states[move[0]][move[1]]

    def print_board_states(self):
        for l in self.board_states:
            print(l)

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1

S = [ [None] * W for i in range(H) ]
for i in range(H):
    l = input()
    for j, s in enumerate(l):
        S[i][j] = s

bfs = BFS(H, W, S, (C_h, C_w), (D_h, D_w))
bfs.walk()
goal_state = bfs.get_boart_states((D_h, D_w))
print(goal_state if goal_state != INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x:int(x)-1, input().split())    #0indexにして受け取る
dh, dw = map(lambda x:int(x)-1, input().split())
s = [input() for _ in range(h)]
#距離(スタートからijまでの総コスト)
MAX_DIST = 10**9
dist = [[MAX_DIST]*w for _ in range(h)]
dist[ch][cw] = 0
#両端キュー
dq = deque()
dq.append((ch, cw))

#01^BFS
while len(dq):
    i, j = dq.popleft()
    for i2 in range(i-2,i+3):
        if not 0 <= i2 < h:
            continue
        for j2 in range(j-2,j+3):
            if not 0 <= j2 < w:
                continue
            #自身へのループなら無視
            if (i2,j2) == (i,j):
                continue
            #壁へは進めない
            if s[i2][j2] == '#':
                continue

            #間に壁があるか
            mi, mj = int(i+(i2-i)/2), int(j+(j2-j)/2)
            wall = False
            for x,y in ((i2,mj), (mi,j2), (i, mj), (mi,j)):
                if s[x][y] == '#':
                    wall = True
                    break
            #i2,j2までの距離
            d = dist[i][j] + wall

            #距離が短ければ更新
            if d < dist[i2][j2]:
                dist[i2][j2] = d
                #コスト1の移動はキューの末尾，コスト0は先頭
                if wall:
                    dq.append((i2,j2))
                else:
                    dq.appendleft((i2,j2))

if MAX_DIST == dist[dh][dw] :
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque

class BFS:
    def __init__(self, H, W, S, C, D):
        self.H = H
        self.W = W
        self.S = S
        # 魔法使いの場所
        self.C = C
        # 目的地
        self.D = D

        # 盤面上のセルの状態
        # -1: 未到達
        # 0 : 魔法0回で到達
        # 1 : 魔法1回で到達
        # 2 : 魔法2回で到達, and so on...
        self.board_states = [[-1] * W for i in range(H)]
        self.board_states[C[0]][C[1]] = 0
        self.queue = deque([C])
        self.walked_cells = [C]

    def is_legal_move(self, move):
        h = move[0]
        w = move[1]

        if h < 0 or h >= self.H or w < 0 or w >= self.W:
            return False
        return self.S[h][w] == "."

    def is_not_visited(self, move):
        h = move[0]
        w = move[1]
        return self.board_states[h][w] == -1

    def search(self):
        while len(self.queue) > 0:
            self.walk()
            self.queue = self.get_can_warp_moves()

    
    def get_can_warp_moves(self):
        next_moves = deque([])
        while len(self.walked_cells) > 0:
            move = self.walked_cells.pop()
            step_count = self.get_boart_states(move)
            for i in range(-2, 3):
                for j in range(-2, 3):
                    next_move = (move[0]+i, move[1]+j)
                    if not self.is_legal_move(next_move):
                        continue

                    if self.is_not_visited(next_move):
                        next_moves.append(next_move)
                        self.set_boart_states(next_move, step_count + 1)

        return next_moves

    def walk(self):
        while len(self.queue) > 0:
            move = self.queue.popleft()

            up = (move[0]-1, move[1])
            down = (move[0]+1, move[1])
            left = (move[0], move[1]-1)
            right = (move[0], move[1]+1)

            next_moves = list(filter(self.is_legal_move, [up, down, left, right]))

            for next_move in next_moves:
                if self.is_not_visited(next_move):
                    self.queue.append(next_move)
                    self.walked_cells.append(next_move)
                    self.set_boart_states(next_move, self.get_boart_states(move))

    def set_boart_states(self, move, value):
        self.board_states[move[0]][move[1]] = value

    def get_boart_states(self, move):
        return self.board_states[move[0]][move[1]]

    def print_board_states(self):
        for l in self.board_states:
            print(l)

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1

S = [ [None] * W for i in range(H) ]
for i in range(H):
    l = input()
    for j, s in enumerate(l):
        S[i][j] = s

bfs = BFS(H, W, S, (C_h, C_w), (D_h, D_w))
bfs.search()
print(bfs.get_boart_states((D_h, D_w)))

Submission status: Wrong Answer

Solution code:
from collections import deque
import itertools

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[-1 for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] == -1:
        return True
    elif dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    if cost >= dist[h][w] and dist[h][w] != -1:
        continue
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh, dw in itertools.product(range(-2, 3), range(-2, 3)):
        if check_appnendable(h+dh, w+dw, cost+1):
            d.appendleft([h+dh, w+dw, cost+1])
            dist[h+dh][w+dw] =cost+1

print(dist[D_h-1][D_w-1])