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 sys, math, heapq

def calcweight_dijkstra(N_vertices, start, edges, inf = 10**7):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    queues = [ [distances[start], start] ] # 1

    while( len(queues)>0 ):
        queue = heapq.heappop(queues)
        if( is_confirmed[ queue[1] ]==False ):
            is_confirmed[ queue[1] ] = True
            for i in range( len(edges[ queue[1] ] ) ):
                destination = edges[ queue[1] ][i]
                distance = queue[0] + 1
                if(is_confirmed[destination]==False and distances[destination] > distance):
                    distances[destination] = distance
                    heapq.heappush(queues, [ distances[destination], destination ] )
    return distances

def search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y, parent):

    if(flag_searched[pos_y][pos_x]==True or Mazes[pos_y][pos_x] == "#"):
        return


    parents[pos_y][pos_x] = parent
    flag_searched[pos_y][pos_x] = True
    x = len(Mazes[0])
    y = len(Mazes)

    if(pos_y+1 < y and flag_searched[pos_y+1][pos_x]==False and Mazes[pos_y+1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y+1, parent)
    if(pos_y > 0 and flag_searched[pos_y-1][pos_x]==False and Mazes[pos_y-1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y-1, parent)
    if(pos_x+1 < x and flag_searched[pos_y][pos_x+1]==False and Mazes[pos_y][pos_x+1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x+1, pos_y, parent)
    if(pos_x > 0 and flag_searched[pos_y][pos_x-1]==False and Mazes[pos_y][pos_x-1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x-1, pos_y, parent)



def check(Mazes, flag_searched, parents, pos_x, pos_y, Edges, road_types):
    x = len(Mazes[0])
    y = len(Mazes)
    parentsnum= [-1] * 9

    index = 0
    for i in range( max(pos_y-1, 0), min(pos_y+2, y) ):
        for j in range( max(pos_x-1, 0), min(pos_x+2, x) ):
            if(Mazes[i][j] == "."):
                flag_searched[i][j] = True
                parentsnum[index] = parents[i][j]
            index += 1
    for k in range(8):
        for m in range(k+1, 9):
            if(parentsnum[k] != -1 and parentsnum[m] != -1 and parentsnum[k] != parentsnum[m]):
                point1 = road_types.index( parentsnum[k] )
                point2 = road_types.index( parentsnum[m] )
                Edges[point1].append(point2)
                Edges[point2].append(point1)



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    deque = []
    parents = [ [ i*H+j for j in range(W)] for i in range(H) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]
    dists = [ [inf for _ in range(W) ] for _ in range(H)]

    road_types = []
    heapq.heappush(deque, [0, start])
    while( len(deque)>0 ):
        dist_pos = heapq.heappop(deque)
        for dx, dy in ( (-1, 0), (1, 0), (0, -1), (0, 1) ):
            if( dist_pos[1][0]+ dx < 0 or dist_pos[1][0]+ dx > W-1 or dist_pos[1][1]+ dy < 0 or dist_pos[1][1]+ dy > H-1 ):
                continue
            pos = [dist_pos[1][0], dist_pos[1][1]]
            next = [dist_pos[1][0]+ dx, dist_pos[1][1]+ dy]
            if(dists[next[1] ][next[0] ] > dists[pos[1] ][pos[0] ]):
                dists[next[1] ][next[0] ] = dists[pos[1] ][pos[0] ]
                heapq.heappush(deque, [dist_pos[0], dists[next[1] ][next[0] ] ])

    for i in range(H):
        for j in range(W):
            parent = i*H+j
            if(parents[i][j] == parent and flag_searched[i][j] == False and Maps[i][j] == "."):
                search_with_DFS_using_recursion(Maps, flag_searched, parents, j, i, parent)

                road_types.append(parent)
    # print(parents)

    """
    昇順のはず
    road_types[i]がその頂点に対応
    """
    start_index = road_types.index( parents[start[0]][start[1]] )
    # print(parents[ goal[0]][ goal[1]])
    goal_index = road_types.index( parents[ goal[0]][ goal[1]] )
    N_vertices = len(road_types)
    Edges = [ [] for _ in range(N_vertices) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    #print(road_types)
    for i in range(H):
        for j in range(W):
            """
            if(Maps[i][j] == "#" and flag_searched[i][j] == False):
                flag_searched[i][j] = True
                check(Maps, flag_searched, parents, j, i, Edges, road_types)
            """

            if(Maps[i][j] == "." and flag_searched[i][j] == False):
                flag_searched[i][j] = True
                #print("i, j ", i, j, min(H-i, 3)-1, "X", max(-j, -2) , min(W-j, 3)-1 )
                for dy in range( min(H-i, 3) ):
                    for dx in range( max(-j, -2), min(W-j, 3) ):
                        if( flag_searched[i+dy][j+dx]==False):
                            flag_searched[i+dy][j+dx] = True

                            if( Maps[i+dy][j+dx] == "." and parents[i+dy][j+dx] != parents[i][j]):
                                point1 = road_types.index( parents[i+dy][j+dx] )
                                point2 = road_types.index( parents[i][j] )
                                Edges[point1].append(point2)
                                Edges[point2].append(point1)

    if(parents[start[0]][start[1]]== parents[goal[0]][goal[1]]):
        print(0)
    else:
        inf = 10**7
        dist= calcweight_dijkstra(N_vertices, start_index, Edges, inf)
        if(dist[goal_index] == inf):
            print(-1)
        else:
            print(dist[goal_index])

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

readline = stdin.readline

H, W = map(int, readline().rstrip().split())
CH, CW = map(lambda x: int(x) - 1, readline().split())
DH, DW = map(lambda x: int(x) - 1, readline().split())
S = [readline().rstrip() for _ in range(H)]
v = [[False] * W for _ in range(H)]
dq = deque([(0, CH, CW)])
while dq:
    d, h, w = dq.popleft()
    if (h, w) == (DH, DW):
        print(d)
        exit()
    if v[h][w]:
        continue
    v[h][w] = True
    for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nh = mh + h
        nw = mw + w
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
            dq.appendleft([d, nh, nw])
    for mh in range(-2, 3):
        for mw in range(-2, 3):
            if h == w == 0:
                continue
            nh = mh + h
            nw = mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[nh][nw]:
                dq.append([d + 1, nh, nw])
print(-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

readline = stdin.readline

def main():
    H, W = map(int, readline().rstrip().split())
    CH, CW = map(lambda x: int(x) - 1, readline().split())
    DH, DW = map(lambda x: int(x) - 1, readline().split())
    S = [readline().rstrip() for _ in range(H)]
    v = [[False] * W for _ in range(H)]
    dq = deque([(0, CH, CW)])
    while dq:
        d, h, w = dq.popleft()
        if (h, w) == (DH, DW):
            print(d)
            exit()
        if v[h][w]:
            continue
        v[h][w] = True
        for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = mh + h
            nw = mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                dq.appendleft([d, nh, nw])
        for mh in range(-2, 3):
            for mw in range(-2, 3):
                if h == w == 0:
                    continue
                nh = mh + h
                nw = mw + w
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[nh][nw]:
                    dq.append([d + 1, nh, nw])
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

readline = stdin.readline

def main():
    H, W = map(int, readline().rstrip().split())
    CH, CW = map(lambda x: int(x) - 1, readline().split())
    DH, DW = map(lambda x: int(x) - 1, readline().split())
    S = [readline().rstrip() for _ in range(H)]
    v = [[False] * W for _ in range(H)]
    dq = deque([(0, CH, CW)])
    while dq:
        d, h, w = dq.popleft()
        if (h, w) == (DH, DW):
            print(d)
            exit()
        if v[h][w]:
            continue
        v[h][w] = True
        for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = mh + h
            nw = mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[nh][nw]:
                dq.appendleft([d, nh, nw])
        for mh in range(-2, 3):
            for mw in range(-2, 3):
                if h == w == 0:
                    continue
                nh = mh + h
                nw = mw + w
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[nh][nw]:
                    dq.append([d + 1, nh, nw])
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0
s = set()

while True:
  # 行けるところすべて追加
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          if not(i == 0 and j == 0):
            flag = True
  # クリアしてるか確認
  temps = set(d)
  if (Dh,Dw) in temps:
    print(ans)
    exit()
  else:
    s |= temps
    d = deque()
    for Th,Tw in temps:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque, defaultdict

readline = stdin.readline

def main():
    H, W = map(int, readline().rstrip().split())
    CH, CW = map(lambda x: int(x) - 1, readline().rstrip().split())
    DH, DW = map(lambda x: int(x) - 1, readline().rstrip().split())
    S = [readline().rstrip() for _ in range(H)]
    # v = defaultdict(lambda : False)
    v = [[False] * W for _ in range(H)]
    dq = deque([(0, CH, CW)])
    while dq:
        d, h, w = dq.popleft()
        if (h, w) == (DH, DW):
            print(d)
            exit()
        if v[h][w]:
            continue
        v[h][w] = True
        for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = mh + h
            nw = mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[nh][nw]:
                dq.appendleft([d, nh, nw])
        for mh in range(-2, 3):
            for mw in range(-2, 3):
                if h == w == 0:
                    continue
                nh = mh + h
                nw = mw + w
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[nh][nw]:
                    dq.append([d + 1, nh, nw])
    print(-1)

if __name__ == "__main__":
    main()

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())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
q=deque()
q.append(s)
q2=deque()
q2.append(s)
c=0
d={s:0}
while q:
    while q:
        y,x=q.popleft()
        for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if m[ny][nx]=='.' and (ny,nx) not in d:
                q.append((ny,nx))
                q2.append((ny,nx))
                d[(ny,nx)]=c
    c+=1
    while q2:
        y,x=q2.popleft()
        for dy,dx in [(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(-2,-1),(-1,-1),(1,-1),(2,-1),(-2,0),(2,0),(-2,1),(-1,1),(1,1),(2,1),(-2,2),(-1,2),(0,2),(1,2),(2,2)]:
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if m[ny][nx]=='.' and (ny,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=c
if g in d:
    print(d[g])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import exit

h,w=map(int,input().split())
sh,sw=map(lambda s: int(s)-1,input().split())
gh,gw=map(lambda s: int(s)-1,input().split())
s = [input() for _ in range(h)]
d = [[h*w] * w for _ in range(h)]
q = deque()
d[sh][sw] = 0
q.append((sw, sh))
while len(q):
  p = q.popleft()
  print(p)
  if p[0] == gw and p[1] == gh:
    print(d[gh][gw])
    exit(0)
  for dx in range(-2, 3):
    for dy in range(-2, 3):
      nx, ny = p[0] + dx, p[1] + dy
      c = 0 if abs(dx) + abs(dy) == 1 else 1
      if dx == dy == 0 or nx < 0 or ny < 0 or w <= nx or h <= ny or s[ny][nx] == '#' or d[ny][nx] <= d[p[1]][p[0]] + c:
        continue
      d[ny][nx] = d[p[1]][p[0]] + c
      np = (nx, ny)
      if c:
        q.append(np)
      else:
        q.appendleft(np)
print(-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque, defaultdict

readline = stdin.readline

def main():
    H, W = map(int, readline().rstrip().split())
    CH, CW = map(lambda x: int(x) - 1, readline().rstrip().split())
    DH, DW = map(lambda x: int(x) - 1, readline().rstrip().split())
    S = [readline().rstrip() for _ in range(H)]
    v = defaultdict(lambda : False)
    dq = deque([(0, CH, CW)])
    while dq:
        d, h, w = dq.popleft()
        # print(f'{c} : {h} : {w} : {S[h][w]}')
        if (h, w) == (DH, DW):
            print(d)
            exit()
        if v[(h, w)]:
            continue
        v[(h, w)] = True
        for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = mh + h
            nw = mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                dq.appendleft([d, nh, nw])
        for mh in range(-2, 3):
            for mw in range(-2, 3):
                if h == w == 0:
                    continue
                nh = mh + h
                nw = mw + w
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                    dq.append([d + 1, nh, nw])
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0
s = set()

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  temps = set(d)
  if (Dh,Dw) in temps:
    print(ans)
    exit()
  else:
    s |= temps
    d = deque()
    for Th,Tw in temps:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w:
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0
s = set()

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  temps = set(d)
  if (Dh,Dw) in temps:
    print(ans)
    exit()
  else:
    s |= temps
    d = deque()
    for Th,Tw in temps:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and not(i == 0 and j == 0) and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

Submission status: Wrong Answer

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

H, W = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for h in range(H):
   s.append(input().rstrip('\n'))

A = []
B = []
C = []

for h in range(H):
    for w in range(W):
        for dh in (-2, -1, 1, 2):
            for dw in (-2, -1, 1, 2):
                nh = h + dh
                nw = h + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] != '.':
                    continue
                if (nh, nw) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
                    A.append(h*W+w)
                    B.append(nh*W+nw)
                    C.append(0)
                else:
                    A.append(h*W+w)
                    B.append(nh*W+nw)
                    C.append(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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0
s = set()

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  temps = set(d)
  if (Dh,Dw) in temps:
    print(ans)
    exit()
  else:
    s |= temps
    d = deque()
    for Th,Tw in temps:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and (i == 0 and j == 0) and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 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())
dh, dw = map(lambda x: int(x) - 1, input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch, cw)])
S = [[float("inf")]*w for _ in range(h)]
S[ch][cw] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = ((1,0),(0,1),(-1,0),(0,-1))
    ans = S[y][x]

    if (y, x) == (dh, dw):
            S[y][x] = ans
            break

    for j, i in dx_dy:
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = ans
                queue.appendleft((y+j, x+i))

    ans += 1
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > ans and G[y+j][x+i] == ".":
                        S[y+j][x+i] = ans
                        queue.append((y+j, x+i))


if S[dh][dw] == float("inf"):
    print(-1)
else:
    print(S[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

def BFS1(task, ct):
  D = [(1,0), (0,1), (-1,0), (0,-1)]
  adj_list = deque([])
  while task:
    s = task.popleft()
    #print(s, ct, 1)
    if s == (hg, wg):
      print(ct)
      sys.exit()
    x = s[0]
    y = s[1]
    for d in D:
      s_n = (x+d[0], y+d[1])
      if 0 <= s_n[0] <= H-1 and 0 <= s_n[1] <= W-1 and (s_n not in visited) and S[s_n[0]][s_n[1]] == ".":
        task.append(s_n)
        visited.add(s_n)
    make_adj_list(s, adj_list)
  return (ct+1, adj_list)

def make_adj_list(s, adj_list):
  D = [(1,0), (0,1), (-1,0), (-1,-1), (1,1), (-1,-1), (-1, 1), (1,-1)]
  flag = False
  for d in D:
    s_n = (s[0]+d[0], s[1]+d[1])
    if 1 <= s_n[0] <= H-2 and 1 <= s_n[1] <= W-2 and S[s_n[0]][s_n[1]] == "#":
      flag = True
      break
  if flag:
    adj_list.append((s,0))  

"""
def BFS2(task):
  D = [(1,0), (0,1), (-1,0), (-1,-1), (1,1), (-1,-1), (-1, 1), (1,-1)]
  task_n = deque([])
  while task:
    s, c = task.popleft()
    print(s, c, task, task_n)
    x = s[0]
    y = s[1]
    for d in D:
      s_n = (x+d[0], y+d[1])
      if 0 <= s_n[0] <= H-1 and 0 <= s_n[1] <= W-1 and s_n not in visited and c <= 1:
        if S[s_n[0]][s_n[1]] == "#":
          task.append((s_n, c+1))
          visited.add(s_n)
        else:
          task_n.append(s_n)
          visited.add(s_n)
  return task_n
"""

def warp(task):
  #print(task)
  semi_visited = set()
  task_n = deque([])
  while task:
    s, c = task.popleft()
    x = s[0]
    y = s[1]
    for dh in range(-2,3):
      for dw in range(-2,3):
        s_n = (x+dh, y+dw)
        if 0 <= s_n[0] <= H-1 and 0 <= s_n[1] <= W-1:
          #print(s_n, s)
          #if S[s_n[0]][s_n[1]] == "#" and s_n not in semi_visited:
            #task.append((s_n, c+1))
            #semi_visited.add(s_n)
          if S[s_n[0]][s_n[1]] == "." and s_n not in visited:
            task_n.append(s_n)
            visited.add(s_n)
  return task_n
  
H, W = map(int, input().split())
hs, ws = map(int, input().split())
hs -= 1
ws -= 1
hg, wg = map(int, input().split())
hg -= 1
wg -= 1

S = [input() for _ in range(H)]

task = deque([(hs, ws)])
visited = {(hs, ws)}
ct = 0

while task:
  #print(ct)
  ct, adj_list = BFS1(task, ct)
  #print(ct)
  #task = BFS2(adj_list)
  task = warp(adj_list)
  del adj_list
  
print(-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque, defaultdict

readline = stdin.readline

def main():
    H, W = map(int, readline().rstrip().split())
    CH, CW = map(lambda x: int(x) - 1, readline().rstrip().split())
    DH, DW = map(lambda x: int(x) - 1, readline().rstrip().split())
    S = [readline().rstrip() for _ in range(H)]
    v = defaultdict(lambda : False)
    dq = deque([(0, CH, CW)])
    while dq:
        d, h, w = dq.popleft()
        # print(f'{c} : {h} : {w} : {S[h][w]}')
        if (h, w) == (DH, DW):
            print(d)
            exit()
        if v[(h, w)]:
            continue
        v[(h, w)] = True
        for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = mh + h
            nw = mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                dq.appendleft([d, nh, nw])
        for mh in range(-2, 3):
            for mw in range(-2, 3):
                if h == w == 0:
                    continue
                nh = mh + h
                nw = mw + w
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                    dq.append([d + 1, nh, nw])
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0
s = set()

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  temps = set(d)
  if (Dh,Dw) in temps:
    print(ans)
    exit()
  else:
    s |= temps
    d = deque()
    for Th,Tw in temps:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in s) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    warp_up = [
        (-2, -2),
        (-1, -2),
        (0, -2),
        (1, -2),
        (2, -2),
        (-2, -1),
        (-1, -1),
        (1, -1),
        (2, -1),
    ]
    warp_do = [
        (2, 2),
        (1, 2),
        (0, 2),
        (-1, 2),
        (-2, 2),
        (2, 1),
        (1, 1),
        (-1, 1),
        (-2, 1),
    ]
    warp_ri = [
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
    ]
    warp_le = [
        (-2, 2),
        (-2, 1),
        (-2, 0),
        (-2, -1),
        (-2, -2),
        (-1, 2),
        (-1, 1),
        (-1, -1),
        (-1, -2),
    ]

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(30000):
        for _ in range(50000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            next = [next_x, next_y]
                            if next == [1, 0]:
                                warp = warp_ri.copy()
                            elif next == [0, 1]:
                                warp = warp_do.copy()
                            elif next == [-1, 0]:
                                warp = warp_le.copy()
                            elif next == [0, -1]:
                                warp = warp_up.copy()
                            for next_x, next_y in warp:
                                x, y = now_x + next_x, now_y + next_y
                                if 0 <= x < w and 0 <= y < h:
                                    if c[y][x] not in "#=!":
                                        c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                        d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()