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:
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

start = (Ch, Cw)

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

counter = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      counter[k][j] = 10**7

counter[Ch][Cw] = 0

#print(counter)
#print(S)

now = [start]
for item in now:
  x = item[0]
  y = item[1]
  if counter[x+1][y] == 10**7:
    counter[x+1][y] = 0
    now.append((x+1, y))
  if counter[x][y+1] == 10**7:
    counter[x][y+1] = 0
    now.append((x, y+1))
  if counter[x-1][y] == 10**7:
    counter[x-1][y] = 0
    now.append((x-1, y))
  if counter[x][y-1] == 10**7:
    counter[x][y-1] = 0
    now.append((x, y-1))

#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 10**7:
  if len(now) == 0:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    x = item[0]
    y = item[1]
    if counter[x+2][y+2] > ans:
      counter[x+2][y+2] = ans
      nextlist.append((x+2, y+2))
    if counter[x+2][y+1] > ans:
      counter[x+2][y+1] = ans
      nextlist.append((x+2, y+1))
    if counter[x+2][y] > ans:
      counter[x+2][y] = ans
      nextlist.append((x+2, y))
    if counter[x+2][y-1] > ans:
      counter[x+2][y-1] = ans
      nextlist.append((x+2, y-1))
    if counter[x+2][y-2] > ans:
      counter[x+2][y-2] = ans
      nextlist.append((x+2, y-2))
    if counter[x+1][y+2] > ans:
      counter[x+1][y+2] = ans
      nextlist.append((x+1, y+2))
    if counter[x+1][y-2] > ans:
      counter[x+1][y-2] = ans
      nextlist.append((x+1, y-2))
    if counter[x][y+2] > ans:
      counter[x][y+2] = ans
      nextlist.append((x, y+2))
    if counter[x][y-2] > ans:
      counter[x][y-2] = ans
      nextlist.append((x, y-2))
    if counter[x-2][y+2] > ans:
      counter[x-2][y+2] = ans
      nextlist.append((x-2, y+2))
    if counter[x-2][y+1] > ans:
      counter[x-2][y+1] = ans
      nextlist.append((x-2, y+1))
    if counter[x-2][y] > ans:
      counter[x-2][y] = ans
      nextlist.append((x-2, y))
    if counter[x-2][y-1] > ans:
      counter[x-2][y-1] = ans
      nextlist.append((x-2, y-1))
    if counter[x-2][y-2] > ans:
      counter[x-2][y-2] = ans
      nextlist.append((x-2, y-2))
    if counter[x-1][y+2] > ans:
      counter[x-1][y+2] = ans
      nextlist.append((x-1, y+2))
    if counter[x-1][y-2] > ans:
      counter[x-1][y-2] = ans
      nextlist.append((x-1, y-2))
  
  
  for item in nextlist:
    x = item[0]
    y = item[1]
    if counter[x+1][y] > ans:
      counter[x+1][y] = ans
      nextlist.append((x+1, y))
    if counter[x][y+1] > ans:
      counter[x][y+1] = ans
      nextlist.append((x, y+1))
    if counter[x-1][y] > ans:
      counter[x-1][y] = ans
      nextlist.append((x-1, y))
    if counter[x][y-1] > ans:
      counter[x][y-1] = ans
      nextlist.append((x, y-1))
  now = nextlist
  if ans > 10**7:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

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

maze = [ None for _ in range(h) ]
reachable = [ [ None for _ in range(w) ] for _ in range(h) ]

for hi in range(h):
    maze[hi] = input()

def warpable(y, x):
    next_travels = []

    for j in range(-2, 3):
        for i in range(-2, 3):
            wy = y + j if 0 <= (y + j) < h else y
            wx = x + i if 0 <= (x + i) < w else x

            if reachable[wy][wx] is None and maze[wy][wx] == '.':
                next_travels.append((wy, wx))

    return next_travels

def traveling(y, x, warp_count):
    if reachable[y][x] is None:
        reachable[y][x] = warp_count

    else:
        reachable[y][x] = warp_count if warp_count < reachable[y][x] else reachable[y][x]

    u = y - 1 if (y - 1) >= 0 else y
    d = y + 1 if (y + 1) <  h else y
    l = x - 1 if (x - 1) >= 0 else x
    r = x + 1 if (x + 1) <  w else x

    next_travels = []

    if reachable[u][x] is None and maze[u][x] == '.':
        next_travels.append((u, x))

    if reachable[d][x] is None and maze[d][x] == '.':
        next_travels.append((d, x))

    if reachable[y][l] is None and maze[y][l] == '.':
        next_travels.append((y, l))

    if reachable[y][r] is None and maze[y][r] == '.':
        next_travels.append((y, r))

    if len(next_travels) == 0:
        warp_count += 1
        next_travels = warpable(y, x)

    for travel in next_travels:
        traveling(*travel, warp_count)


traveling(ch, cw, 0)

print(reachable[dh][dw] if reachable[dh][dw] is not None else -1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def main():

    input = sys.stdin.readline

    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())

    S=[list(map(str,list(input()[:-1]))) for i in range(H)]
    F=[ [-1] * W for i in range(H)]
    dist=[ [10000000] * W for i in range(H)]

    dh = (1, 0, -1, 0)
    dw = (0, 1, 0, -1)
    warph = (2, 2, 2, 2 ,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2)
    warpw = (-2, -1, 0, 1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2)

    d = deque()

    d.append((Ch-1,Cw-1))

    F[Ch-1][Cw-1] = 0
    dist[Ch-1][Cw-1] = 0

    while len(d) > 0:
        Ph,Pw = d.popleft()

        # if (Ph == Dh-1) & (Pw == Dw-1):
        #     goal = True
        #     break

        for i in range(4):
            nh = Ph + dh[i]
            nw = Pw + dw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.append((nh,nw))
                F[nh][nw] = 0

            dist[nh][nw] = min(dist[nh][nw],dist[Ph][Pw])

        for i in range(20):
            nh = Ph + warph[i]
            nw = Pw + warpw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.append((nh,nw))
                F[nh][nw] = 0
            dist[nh][nw] = min(dist[nh][nw],dist[Ph][Pw]+1)

    if dist[Dh-1][Dw-1] >= 10000000:
        print("-1")
    else:
        print(dist[Dh-1][Dw-1])
         

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(maze, visited,Ch,Cw,Dh,Dw):
  queue = deque([[Ch,Cw]])
  visited[Ch][Cw] = 0
  while queue:
    y,x = queue.popleft()
    if [y,x] == [Dh,Dw]:
      return visited[y][x]
    for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
      new_y,new_x = y+j,x+k
      if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == ".":
        if visited[new_y][new_x] == "x" or  visited[new_y][new_x] > visited[y][x]:
          visited[new_y][new_x] = visited[y][x]
          queue.append([new_y,new_x])
      elif 0 <= new_y+j < H and 0 <= new_x+k < W and maze[new_y][new_x] == "#"and maze[new_y+j][new_x+k] == ".":
        if visited[new_y+j][new_x+k] == "x" or  visited[new_y+j][new_x+k] > visited[y][x]+1:
          visited[new_y+j][new_x+k] = visited[y][x] +1
          queue.append([new_y+j,new_x+k])
    for l,m in ([1,1],[1,-1],[-1,-1],[-1,1],[1,2],[2,1],[2,2],[1,-2],[2,-1],[2,-2],[-1,-1],[-2,-1],[-2,-2],[-1,-2],[-1,2],[-2,1],[-2,2]):
      ex_y,ex_x = y + l, x + m
      if 0 <= ex_y < H and 0 <= ex_x < W and maze[ex_y][ex_x] == ".":
        if visited[ex_y][ex_x] == "x" or  visited[ex_y][ex_x] > visited[y][x]+1:
          visited[ex_y][ex_x] = visited[y][x] +1
          queue.append([ex_y,ex_x])

  if visited[Dh][Dw] == "x":
    return -1
  else:
    return visited[Dh][Dw]
        
        
                                      
      
  
H, W = map(int,input().split())
Ch,Cw =  map(int,input().split())
Dh,Dw = map(int,input().split())
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1

maze = [input() for i in range(H)]
visited = [["x"]*W for j in range(H)]

print(bfs(maze, visited,Ch,Cw,Dh,Dw))

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0, 1, -1, -1, 1], [0, 1, 0, -1, 1, 1, -1, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if i <= 3 and s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft((nx, ny))
            elif s[ny][nx] == '#' and s[y][x] == '.' and d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append((nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
import heapq
class solve:
    def __init__(self):
        self.H, self.W = map(int, input().split())
        self.Ch, self.Cw = map(int, input().split())
        self.Dh, self.Dw = map(int, input().split())
        maze = []
        for i in range(self.H):
            maze.append(list(input()))
        ad = [[[] for j in range(self.W)] for i in range(self.H)]
        for i in range(0, self.H):
            for j in range(0, self.W):
                if maze[i][j] == ".":
                    for s in range(i-2, i+2):
                        for t in range(j-2, j+2):
                            if 0 <= s < self.H and 0 <= t < self.W:
                                if maze[s][t] != "#":
                                    if not (s == i and t == j):
                                        if (abs(s-i) <= 1 and abs(j-t) <= 1) and(abs(s-i) !=1 or abs(t-j) != 1):
                                            ad[i][j] = ad[i][j] + [[(s,t), 0]]
                                        else:
                                            ad[i][j] = ad[i][j] + [[(s,t), 1]]
        self.list = [[] for i in range(self.H*self.W+1)]
        for i in range(self.H):
            for j in range(self.W):
                for k in range(len(ad[i][j])):
                    s, t = ad[i][j][k][0]
                    self.list[self.W*i+j].append([self.W*s+t, ad[i][j][k][1]])
    def sol(self):
        frm = self.W * (self.Ch-1) + (self.Cw-1)
        d = [float('inf') for i in range(len(self.list))]
        d[frm] = 0
        prev = [None for i in range(len(self.list))]
        pq = []
        heapq.heappush(pq, [0, frm])
        while len(pq) > 0:
            weight, u = heapq.heappop(pq)
            for v, weight in self.list[u]:
                if d[v] > d[u] + weight:
                    d[v] = d[u] + weight
                    heapq.heappush(pq, [d[v], v])
                    prev[v] = u
        return d[self.W * (self.Dh-1) + (self.Dw-1)]
a = solve()
d = a.sol()
print(d)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = ch*w+cw
goal = dh*w+dw
seen = [None]*n
seen[start] = 0
from queue import deque 
q = deque([(0, start)]) # ワープ回数, 現在位置, 最後の道の位置
# dx = [0,1,0,-1]
# dy = [1,0,-1,0]
dx = []
dy = []
vvs = []
for i in range(-2,3):
    for j in range(-2,3):
        if not (i==j==0):
            dx.append(i)
            dy.append(j)
            if abs(i)+abs(j)>1:
                vvs.append(1)
            else:
                vvs.append(0)
while q:
    pnum,pu = q.popleft()
    ux,uy = divmod(pu,w)
    # print(pnum,divmod(pu,w))
    if pu==goal:
        break
    for xx,yy,vv in zip(dx,dy,vvs):
#         x = ux+xx
#         y = uy+yy
        x,y = ux+xx, uy+yy
        u = x*w + y
        num = pnum+vv
        if x<0 or y<0 or x>=h or y>=w or ss[x][y]=="#":
            continue
#         print(x,y)
        if seen[u] is None or seen[u]>num:
            seen[u] = num
            if num==0:
                q.appendleft((num, u))
            else:
                q.append((num,u))
val = seen[goal]
if val is None:
    print(-1)
else:
    print(val)

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())
field = set()

cnt = 0
for i in range(h):
  s = input()
  for j in range(w):
    if s[j] == ".":
      field.add((i, j))
      cnt += 1

ans = 0
dq = deque()

while (dh - 1, dw - 1) in field:
  field2 = set()
  dq.append((ch - 1, cw - 1))
  field2.add((ch - 1, cw - 1))
  while len(dq) > 0:
    now_h, now_w = dq.popleft()
    if (now_h, now_w) in field:
      field.remove((now_h, now_w))
      cnt -= 1
    if (now_h - 1, now_w) in field:
      dq.append((now_h - 1, now_w))
      field2.add((now_h - 1, now_w))
    if (now_h + 1, now_w) in field:
      dq.append((now_h + 1, now_w))
      field2.add((now_h + 1, now_w))
    if (now_h, now_w - 1) in field:
      dq.append((now_h, now_w - 1))
      field2.add((now_h + 1, now_w))
    if (now_h, now_w + 1) in field:
      dq.append((now_h, now_w + 1))
      field2.add((now_h, now_w + 1))
  
  if (dh - 1, dw - 1) in field:
    flag = False
    for _h, _w in field2:
      for i in range(-2, 3):
        for j in range(-2, 3):
          if (_h + i, _w + j) in field:
            ans += 1
            dq.append((_h + i + 1, _w + j + 1))
            flag = True
    if not flag:
      break

print(ans if cnt == 0 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [list(input()) for _ in range(h)]



def clear_maze(h, w, ch, cw, dh, dw, S):
    visited = [[-1] * w for _ in range(h)]
    visited[ch - 1][cw - 1] = 0
    queue = deque([[ch - 1 , cw - 1]])
    m_queue = deque([])
    while queue or m_queue:
        if queue:
            y, x = queue.popleft()
        else:
            n_y, n_x, y, x = m_queue.popleft()
            visited[n_y][n_x] = visited[y][x] + 1
            y, x = n_y, n_x
        if [y, x] == [dh - 1, dw - 1]:
            return visited[y][x]
        num = 0
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y = y + i
            n_x = x + j
            if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.':
                if visited[n_y][n_x] == -1:
                    visited[n_y][n_x] = visited[y][x]
                    queue.append([n_y, n_x])
                else:
                    if visited[y][x] < visited[n_y][n_x]:
                        queue.append([n_y, n_x])
                    visited[n_y][n_x] = min(visited[n_y][n_x], visited[y][x])
        for i in range(-2, 2 + 1):
            for j in range(-2, 2 + 1):
                if not [i, j] in ([1, 0], [-1, 0], [0, 0], [0, 1], [0, -1]):
                    n_y = y + i
                    n_x = x + j
                    if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.':
                        if visited[n_y][n_x] == -1:
                            # visited[n_y][n_x] = visited[y][x] + 1
                            m_queue.append([n_y, n_x, y, x])
                        # else:
                            # if visited[y][x] + 1 < visited[n_y][n_x]:
                            #     queue.append([n_y, n_x])
                            # visited[n_y][n_x] = min(visited[n_y][n_x], visited[y][x] + 1)
    return -1

print(clear_maze(h, w, ch, cw, dh, dw, S))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)

from collections import deque

MOVE_DIRECTIONS = ((0, 1), (1, 0), (-1, 0), (0, -1))
WARP_DIRECTIONS = ((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))

def bfs(a,b,dh,dw):
    q = deque([(a,b,0)])
    
    while q:
        p = q.popleft()
        cx,cy,move_count = p[0],p[1],p[2]
        blocked = 0
        for mx, my in MOVE_DIRECTIONS:
            nx = cx + mx
            ny = cy + my
            if nx >= 0 and nx <= H - 1 and ny >= 0 and ny <= W - 1:
                if searched[nx][ny] > move_count:
                    if nx == dh and ny == dw:
                        return move_count
                    elif S[nx][ny] == '.':
                        q.append((nx,ny,move_count))
                        searched[nx][ny] = move_count
                    else:
                        blocked += 1
        if blocked > 0:
            for mx, my in WARP_DIRECTIONS:
                nx = cx + mx
                ny = cy + my
                if nx >= 0 and nx <= H - 1 and ny >= 0 and ny <= W - 1:
                    if searched[nx][ny] > move_count + 1:
                        if nx == dh and ny == dw:
                            return move_count + 1
                        elif S[nx][ny] == '.':
                            q.appendleft((nx,ny,move_count+1))
                            searched[nx][ny] = move_count + 1
    else:
        return -1

H,W,Ch,Cw,Dh,Dw,*S = open(0).read().split()
H = int(H)
W = int(W)
Ch = int(Ch)
Cw = int(Cw)
Dh = int(Dh)
Dw = int(Dw)
searched = [[float('inf')] * W for _ in range(H)]
print(bfs(Ch-1,Cw-1,Dh-1,Dw-1))

Submission status: Wrong Answer

Solution code:
import heapq
class solve:
    def __init__(self):
        self.H, self.W = map(int, input().split())
        self.Ch, self.Cw = map(int, input().split())
        self.Dh, self.Dw = map(int, input().split())
        maze = []
        for i in range(self.H):
            maze.append(list(input()))
        ad = [[[] for j in range(self.W)] for i in range(self.H)]
        for i in range(0, self.H):
            for j in range(0, self.W):
                if maze[i][j] == ".":
                    for s in range(i-2, i+2):
                        for t in range(j-2, j+2):
                            if 0 <= s < self.H and 0 <= t < self.W:
                                if maze[s][t] != "#":
                                    if not (s == i and t == j):
                                        if (abs(s-i) <= 1 and abs(j-t) <= 1) and(abs(s-i) !=1 or abs(t-j) != 1):
                                            ad[i][j] = ad[i][j] + [[(s,t), 0]]
                                        else:
                                            ad[i][j] = ad[i][j] + [[(s,t), 1]]
        self.list = [[] for i in range(self.H*self.W+1)]
        for i in range(self.H):
            for j in range(self.W):
                for k in range(len(ad[i][j])):
                    s, t = ad[i][j][k][0]
                    self.list[self.W*i+j].append([self.W*s+t, ad[i][j][k][1]])
    def sol(self):
        frm = self.W * (self.Ch-1) + (self.Cw-1)
        d = [float('inf') for i in range(len(self.list))]
        d[frm] = 0
        prev = [None for i in range(len(self.list))]
        pq = []
        heapq.heappush(pq, [0, frm])
        while len(pq) > 0:
            weight, u = heapq.heappop(pq)
            for v, weight in self.list[u]:
                if d[v] > d[u] + weight:
                    d[v] = d[u] + weight
                    heapq.heappush(pq, [d[v], v])
                    prev[v] = u
        return d[self.W * (self.Dh-1) + (self.Dw-1)]

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
S=[list(input()) for _ in range(H)]

import sys

stack = [[Ch-1,Cw-1,0]] #現在地を指定
visited_stack = [[Ch-1,Cw-1,0]]
visited = [[0 for w in range(W)] for h in range(H)]
visited[Ch-1][Cw-1]=1
S[Dh-1][Dw-1]='G'

dh_dw=[[1,0],[0,1],[-1,0],[0,-1]]
warph_warpw=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 and j!=0:
            warph_warpw.append([i,j])

warp_cnt=0
while stack:
    h,w,wc = stack.pop() #現在地
    for i in range(4):
        nh,nw=h+dh_dw[i][0],w+dh_dw[i][1] #移動後の現在地
        #print(nh,nw,visited[nh][nw],S[nh][nw])
        if 0<=nh<H and 0<=nw<W and visited[nh][nw] == 0 and S[nh][nw] != '#':
            #print(nh,nw)
            visited[nh][nw] = 1
            stack.append([nh,nw,wc])
            visited_stack.append([nh,nw,wc])
    
    #stackがなくなったら
    if len(stack)==0:
        while visited_stack:
            h,w,wc=visited_stack.pop()
            for i in range(len(warph_warpw)):
                nh,nw = h+warph_warpw[i][0],w+warph_warpw[i][1]
                if 0<=nh<H and 0<=nw<W and visited[nh][nw] == 0 and S[nh][nw] != '#':
                    visited[nh][nw] = 1
                    stack.append([nh,nw,wc+1])
                    if S[nh][nw] == 'G':
                        print(wc+1)
                        sys.exit()
                    #visited_stack.append([nh,nw])
    
print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
si, sj = map(lambda x: int(x) - 1, input().split())
gi, gj = map(lambda x: int(x) - 1, input().split())

maze = [input() for i in range(H)]
reached = [[-1] * W for i in range(H)]

direction = [(-1, 0), (0, -1), (0, 1), (1, 0)]
reached_que = deque([[si, sj]])


def bfs(si, sj):
    que = deque([[si, sj]])
    reached[si][sj] += 1
    while que:
        h, w = que.popleft()
        for a, b in direction:
            next_h = h + a
            next_w = w + b
            if next_h > H - 1 or next_w > W - 1 or next_h < 0 or next_w < 0:
                continue
            if maze[next_h][next_w] == '#':
                continue
            if reached[next_h][next_w] != -1:
                continue
            que.append([next_h, next_w])
            reached[next_h][next_w] = reached[h][w] + 1
            reached_que.append([next_h, next_w])


hankei_5 = [
    [-2, -2],
    [-2, -1],
    [-2, 0],
    [-2, 1],
    [-2, 2],
    [-1, -2],
    [-1, -1],
    [-1, 0],
    [-1, 1],
    [-1, 2],
    [0, -2],
    [0, -1],
    [0, 1],
    [0, 2],
    [1, -2],
    [1, -1],
    [1, 0],
    [1, 1],
    [1, 2],
    [2, -2],
    [2, -1],
    [2, 0],
    [2, 1],
    [2, 2]
]

ans = -1


def bfs2(si, sj, ans):
    for i, j in hankei_5:
        next_h = si + i
        next_w = sj + j
        if next_h > H - 1 or next_w > W - 1 or next_h < 0 or next_w < 0:
            continue
        if maze[next_h][next_w] == '.' and reached[next_h][next_w] == -1:
            ans += 1
            check(next_h, next_w,ans)


def check(si, sj, ans):
    bfs(si, sj)
    if reached[gi][gj] == -1:
        for r in reached_que:
            bfs2(r[0], r[1], ans)
        print(-1)
        exit(0)
    else:
        print(ans)
        exit(0)


check(si, sj, 0)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import deque

readline = sys.stdin.readline
read = sys.stdin.read

h, w = map(int, readline().split())
ch, cw = map(int, readline().split())
dh, dw = map(int, readline().split())
a = np.array(list(read())).reshape(h,-1)
a = np.where(a=='.', 0, -1)[:,:-1]
b = np.ones((h+4,w+4), dtype=np.bool)
b[2:h+2,2:w+2] = a.astype(np.bool)
to = deque([(0,ch,cw)])

while to:
    x, xh, xw = to.popleft()
    b[xh-1,xw-1] = True
    if xh == dh and xw == dw:
        print(x)
        sys.exit()
    if b[xh-1,xw-1]:
        continue
    else:
        if not b[xh,xw-1]:
            to.appendleft((x,xh,xw-1))
        if not b[xh-1,xw]:
            to.appendleft((x,xh-1,xw))
        if not b[xh-2,xw-1]:
            to.appendleft((x,xh-2,xw-1))
        if not b[xh-1,xw-2]:
            to.appendleft((x,xh-1,xw-2))
        bh,bw = np.where(b[xh-3:xh+2,xw-3:xw+2]==False)
        for hh, ww in zip(bh,bw):
            to.append((x+1,hh,ww))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
ch-=1
cw-=1
dh-=1
dw-=1

a=[[-1]*(w+4) for ii in range(h+4)]
s=[[""]*w for ii in range(h)]
for ii in range(h):
  sii=list(input())
  for jj in range(len(sii)):
    if sii[jj]==".":
      a[ii+2][jj+2]=0

import sys
sys.setrecursionlimit(10**9)

def func(hh,ww,dh,dw,rr,flg):
  if (not flg) and hh==dh and ww==dw:
    print(rr-1)
    exit()
  if (not flg) and a[hh+2][ww+2]==1:
    print(rr-1)
    exit()
  if a[hh+2][ww+2]!=0:
    #print(hh,ww)
    return
  a[hh+2][ww+2]=rr+1
  func(hh+1,ww,dh,dw,rr,flg)
  func(hh-1,ww,dh,dw,rr,flg)
  func(hh,ww+1,dh,dw,rr,flg)
  func(hh,ww-1,dh,dw,rr,flg)
  return

rr=0
func(dh,dw,dh,dw,rr,True)
rr+=1
func(ch,cw,dh,dw,rr,False)

for ii in range(h):
  for jj in range(w):
    if a[ii+2][jj+2]==0:
      rr+=1
      func(ii,jj,dh,dw,rr,False)

for ii in range(h+4):
  print(a[ii])

# todo 
# implement warp

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

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

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

    queue = deque()
    # (x, y, ワープ回数)
    queue.append(start)

    while queue:
        next_queue = deque()

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

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

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

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

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

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

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

        queue = next_queue

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


bfs()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(maze, visited,Ch,Cw,Dh,Dw):
  queue = deque([[Ch,Cw]])
  visited[Ch][Cw] = 0
  while queue:
    y,x = queue.popleft()

    for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
      new_y,new_x = y+j,x+k
      if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == ".":
        if visited[new_y][new_x] == "x" or  visited[new_y][new_x] > visited[y][x]:
          visited[new_y][new_x] = visited[y][x]
          queue.append([new_y,new_x])
      elif 0 <= new_y+j < H and 0 <= new_x+k < W and maze[new_y][new_x] == "#"and maze[new_y+j][new_x+k] == ".":
        if visited[new_y+j][new_x+k] == "x" or  visited[new_y+j][new_x+k] > visited[y][x]+1:
          visited[new_y+j][new_x+k] = visited[y][x] +1
          queue.append([new_y+j,new_x+k])
    for l,m in ([1,1],[1,-1],[-1,-1],[-1,1],[1,2],[2,1],[2,2],[1,-2],[2,-1],[2,-2],[-1,-1],[-2,-1],[-2,-2],[-1,-2],[-1,2],[-2,1],[-2,2]):
      ex_y,ex_x = y + l, x + m
      if 0 <= ex_y < H and 0 <= ex_x < W and maze[ex_y][ex_x] == ".":
        if visited[ex_y][ex_x] == "x" or  visited[ex_y][ex_x] > visited[y][x]+1:
          visited[ex_y][ex_x] = visited[y][x] +1
          queue.append([ex_y,ex_x])

  if visited[Dh][Dw] == "x":
    return -1
  else:
    return visited[Dh][Dw]
        
        
                                      
      
  
H, W = map(int,input().split())
Ch,Cw =  map(int,input().split())
Dh,Dw = map(int,input().split())
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1

maze = [input() for i in range(H)]
visited = [["x"]*W for j in range(H)]

print(bfs(maze, visited,Ch,Cw,Dh,Dw))
print(visited)