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 copy
H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
maze = []
vis=[]
can = []
stack = [[Ch-1,Cw-1]]
flag = True
for h in range(H):
  maze.append(list(input()))
  vis.append([-1]*W)
vis[Ch-1][Cw-1] = 0

while flag:
  canN=[]
  previs = copy.deepcopy(vis)
  while stack: #0cost
    p = stack.pop()
    canN.append(p)
    
    for i in [-1,0,1]:
      for j in [-1,0,1]:
        if 0<= p[0]+i <H and 0<= p[1]+j <W and i*i+j*j==1:
          if maze[p[0]+i][p[1]+j]=="." and not[p[0]+i,p[1]+j] in stack:
            if vis[p[0]+i][p[1]+j]==-1 or vis[p[0]+i][p[1]+j]>vis[p[0]][p[1]]:
              vis[p[0]+i][p[1]+j] = vis[p[0]][p[1]]
              stack.append([p[0]+i,p[1]+j])
  can.append(canN)
  print(vis)
  
  while canN:
    p = canN.pop()
    for i in range(-2,3):
      for j in range(-2,3):
        if 0<= p[0]+i <H and 0<= p[1]+j <W and i*i+j*j>1:
          if maze[p[0]+i][p[1]+j]=="." and not[p[0]+i,p[1]+j] in stack:
            if vis[p[0]+i][p[1]+j]==-1 or vis[p[0]+i][p[1]+j]>vis[p[0]][p[1]]:
              vis[p[0]+i][p[1]+j] = vis[p[0]][p[1]]+1
              stack.append([p[0]+i,p[1]+j])
  print(vis)
  if previs==vis:
    print(vis[Dh-1][Dw-1])
    flag=False

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

s = []
for i in range(h):
  t = input()
  s.append(t)

dx = [1,0,-1,0]
dy = [0,1,0,-1]

queue = deque([[ch,cw]])
visited = [[10000 for i in range(w)] for j in range(h)]
visited[ch][cw] = 0
while queue:
  l,m = queue.popleft()
  d = visited[l][m]
  for k in range(4):
    x = l + dx[k]
    y = m + dy[k]
    if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] <= d or s[x][y] == "#":
      continue
    visited[x][y] = d
    queue.appendleft([x,y])
  for i in range(-2,3):
    for j in range(-2,3):
      if (i== 1 and j == 0)or(i==-1 and j == 0)or(i==0 and j == 1)or(i==0 and j==-1)or(i==0 and j==0):
        continue
      x = l + i
      y = m + j
      if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] <= d+1 or s[x][y] == "#":
        continue
      visited[x][y] = d + 1
      queue.append([x,y])
  #print (queue)
if visited[dh][dw] == 10000:
  print (-1)
else:
  print (visited[dh][dw])

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

s = []
for i in range(h):
  t = input()
  s.append(t)

dx = [1,0,-1,0]
dy = [0,1,0,-1]

queue = deque([[ch,cw]])
visited = [[10000 for i in range(w)] for j in range(h)]
visited[ch][cw] = 0
while queue:
  l,m = queue.popleft()
  d = visited[l][m]
  for k in range(4):
    x = l + dx[k]
    y = m + dy[k]
    if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] <= d or s[x][y] == "#":
      continue
    visited[x][y] = d
    queue.appendleft([x,y])
  for i in range(-2,3):
    for j in range(-2,3):
      if (i== 1 and j == 0)or(i==-1 and j == 0)or(i==0 and j == 1)or(i==0 and j==-1)or(i==0 and j==0):
        continue
      x = l + i
      y = m + j
      if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] <= d or s[x][y] == "#":
        continue
      visited[x][y] = d + 1
      queue.append([x,y])
  #print (queue)
if visited[dh][dw] == 10000:
  print (-1)
else:
  print (visited[dh][dw])

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

s = []
for i in range(h):
  t = input()
  s.append(t)

dx = [1,0,-1,0]
dy = [0,1,0,-1]

queue = deque([[ch,cw]])
visited = [[10000 for i in range(w)] for j in range(h)]
visited[ch][cw] = 0
while queue:
  l,m = queue.popleft()
  d = visited[l][m]
  for k in range(4):
    x = l + dx[k]
    y = m + dy[k]
    if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] <= d or s[x][y] == "#":
      continue
    visited[x][y] = visited[l][m]
    queue.appendleft([x,y])
  for i in range(-2,3):
    for j in range(-2,3):
      if (i== 1 and j == 0)or(i==-1 and j == 0)or(i==0 and j == 1)or(i==0 and j==-1)or(i==0 and j==0):
        continue
      x = l + i
      y = m + j
      if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] <= d or s[x][y] == "#":
        continue
      visited[x][y] = visited[l][m] + 1
      queue.append([x,y])
if visited[dh][dw] == 10000:
  print (-1)
else:
  print (visited[dh][dw])

Submission status: Wrong Answer

Solution code:
from sys import stdin
from math import ceil
inp = lambda : stdin.readline().strip()

X = [0,1,0,-1]
Y = [-1,0,1,0]
def isValid(x,y):
    if x >= 0 and y >= 0 and x < h  and y < w:
        return True
    return False


def dfs_iter(x,y):
    stack = [(x,y)]
    while stack:
        x,y = stack.pop()
        if isValid(x,y) and visited[x][y] == -1 and  maze[x][y] != '#':
            visited[x][y] = curr
            for i,j in zip(X,Y):
                if isValid(x+i,y+j) and visited[x+i][y+j] == -1  and maze[x+i][y+j] != '#':
                    stack.append((x+i,y+j))
def dfs(n):
    stack = [n]
    depths = [0]
    ans = 10**9 + 7
    while stack:
        node = stack.pop()
        depth = depths.pop()
        visited2[node] = True
        if node == visited[dh-1][dw-1]:
            ans = min(ans,depth)
        for child in adj[node]:
            if not visited2[child]:
                stack.append(child)
                depths.append(depth+1)
    if ans == 10**9 + 7:
        return -1
    return ans


h, w = [int(x) for x in inp().split()]
ch,cw = [int(x) for x in inp().split()]
dh, dw = [int(x) for x in inp().split()]
visited  = [[-1]*w for x in range(h)]

maze = []
adj = [set() for i in range(ceil(h*w/2))]
visited2 = [False]*(ceil(h*w/2))
for i in range(h):
    maze.append(list(inp()))

curr = 0
ans = []
for i in range(h):
    for j in range(w):
        if visited[i][j] == -1 and maze[i][j] != '#':
            dfs_iter(i,j)
            curr += 1
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            for k in range(-2,3):
                for l in range(-2,3):
                    if not (k==l and l == 0):
                        if isValid(i+k,j + l) and visited[i][j] != visited[i+k][j+l] and maze[i+k][j+l] != '#':
                            adj[visited[i][j]].add(visited[i+k][j+l])

print(dfs(visited[ch-1][cw-1]))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from math import ceil
inp = lambda : stdin.readline().strip()

X = [0,1,0,-1]
Y = [-1,0,1,0]
def isValid(x,y):
    if x >= 0 and y >= 0 and x < h  and y < w:
        return True
    return False


def dfs_iter(x,y):
    stack = [(x,y)]
    while stack:
        x,y = stack.pop()
        if isValid(x,y) and visited[x][y] == -1 and  maze[x][y] != '#':
            visited[x][y] = curr
            for i,j in zip(X,Y):
                if isValid(x+i,y+j) and visited[x+i][y+j] == -1  and maze[x+i][y+j] != '#':
                    stack.append((x+i,y+j))
def dfs(n):
    stack = [n]
    depths = [0]
    ans = 10**9
    while stack:
        node = stack.pop()
        depth = depths.pop()
        if not visited2[node]:
            visited2[node] = True
            if node == visited[dh-1][dw-1]:
                ans = min(ans,depth)
            for child in adj[node]:
                if not visited2[child]:
                    stack.append(child)
                    depths.append(depth+1)
    if ans == 10**9:
        return -1
    return ans


h, w = [int(x) for x in inp().split()]
ch,cw = [int(x) for x in inp().split()]
dh, dw = [int(x) for x in inp().split()]
visited  = [[-1]*w for x in range(h)]

maze = []
adj = [set() for i in range(ceil(h*w/2))]
visited2 = [False]*(ceil(h*w/2))
for i in range(h):
    maze.append(list(inp()))

curr = 0
ans = []
for i in range(h):
    for j in range(w):
        if visited[i][j] == -1 and maze[i][j] != '#':
            dfs_iter(i,j)
            curr += 1
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            for k in range(-2,3):
                for l in range(-2,3):
                    if not (k==l and l == 0):
                        if isValid(i+k,j + l) and visited[i][j] != visited[i+k][j+l] and maze[i+k][j+l] != '#':
                            adj[visited[i][j]].add(visited[i+k][j+l])

print(dfs(visited[ch-1][cw-1]))

Submission status: Wrong Answer

Solution code:
from sys import stdin
from math import ceil
inp = lambda : stdin.readline().strip()

X = [0,1,0,-1]
Y = [-1,0,1,0]
def isValid(x,y):
    if x >= 0 and y >= 0 and x < h  and y < w:
        return True
    return False


def dfs_iter(x,y):
    stack = [(x,y)]
    while stack:
        x,y = stack.pop()
        if isValid(x,y) and visited[x][y] == -1 and  maze[x][y] != '#':
            visited[x][y] = curr
            for i,j in zip(X,Y):
                if isValid(x+i,y+j) and visited[x+i][y+j] == -1  and maze[x+i][y+j] != '#':
                    stack.append((x+i,y+j))
def dfs(n):
    stack = [n]
    depths = [0]
    while stack:
        node = stack.pop()
        depth = depths.pop()
        if not visited2[node]:
            visited2[node] = True
            if node == visited[dh-1][dw-1]:
                return depth
            for child in adj[node]:
                if not visited2[child]:
                    stack.append(child)
                    depths.append(depth+1)
    return -1


h, w = [int(x) for x in inp().split()]
ch,cw = [int(x) for x in inp().split()]
dh, dw = [int(x) for x in inp().split()]
visited  = [[-1]*w for x in range(h)]

maze = []
adj = [set() for i in range(ceil(h*w/2))]
visited2 = [False]*(ceil(h*w/2))
for i in range(h):
    maze.append(list(inp()))

curr = 0
for i in range(h):
    for j in range(w):
        if visited[i][j] == -1 and maze[i][j] != '#':
            dfs_iter(i,j)
            curr += 1
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            for k in range(-2,3):
                for l in range(-2,3):
                    if not (k==l and l == 0):
                        if isValid(i+k,j + l) and visited[i][j] != visited[i+k][j+l] and maze[i+k][j+l] != '#':
                            adj[visited[i][j]].add(visited[i+k][j+l])

print(dfs(visited[ch-1][cw-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque



R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
maze = [list(input()) for i in range(R)]
d = deque()
ds = deque()
maze[sy][sx] = 0
d.append([sy, sx])
ds.append([sy, sx])
while(d or ds):
  while(d):
    [y, x] = d.popleft()
    if (y, x) == (gy, gx):
      print(maze[gy][gx])
      exit()
    for [dy, dx] in [[1,0], [-1,0], [0,1], [0,-1]]:
      ny = y + dy
      nx = x + dx
      if  R > ny and ny >= 0 and C > nx and nx >= 0 and maze[ny][nx] == ".":
        maze[ny][nx] = maze[y][x]
        d.append([ny, nx])
        ds.append([ny, nx])

  while(ds):   
    [y, x] = ds.popleft()
    for [dy, dx] 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]]:
      ny = y + dy
      nx = x + dx
      if  R > ny and ny >= 0 and C > nx and nx >= 0 and maze[ny][nx] == ".":
        maze[ny][nx] = maze[y][x]+1
        d.append([ny,nx])
        
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

def check_checked(y, x):
  if 0>y or 0>x or C<=x or R<=y or check_list[y][x] != 1:
    return False 
  check_list[y][x] = 2
  return True

def check_walkable(y, x):
  if 0>y or 0>x or C<=x or R<=y or check_list[y][x]!=".":
    return False 
  check_list[y][x] = 1  
  return True


R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
maze = [list(input()) for i in range(R)]
check_list = copy.deepcopy(maze)

d = deque()
maze[sy][sx] = 0
check_list[sy][sx] = 1
while(1):
  old_sy, old_sx = sy, sx
  d.append([sy, sx])
  while(d):
    [y, x] = d.popleft()
    if (y, x) == (gy, gx):
      print(maze[gy][gx])
      exit()
    for np in [[y+1, x], [y-1, x], [y, x+1], [y, x-1]]:
      if check_walkable(np[0], np[1]):
        maze[np[0]][np[1]] = maze[y][x]
        d.append([np[0], np[1]])
  d.append([sy, sx])
  while(d):
    [y, x] = d.popleft()
    for np in [[y+1, x], [y-1, x], [y, x], [y, x+1], [y, x-1]]:
      if check_checked(np[0], np[1]):
        d.append([np[0], np[1]])
        for (dy, dx) 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 dy == 0 and dx == 0:
            check_list[np[0]+dy][np[1]+dx] = 2
            continue

          if check_walkable(np[0]+dy, np[1]+dx):
            maze[np[0]+dy][np[1]+dx] = maze[np[0]][np[1]]+1
            sy, sx = np[0]+dy, np[1]+dx
  if (old_sy, old_sx) == (sy, sx):
    print(-1)
    exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

def check_checked(y, x):
  if 0>y or 0>x or C<=x or R<=y or check_list[y][x] != 1:
    return False 
  check_list[y][x] = 2
  return True

def check_walkable(y, x):
  if 0>y or 0>x or C<=x or R<=y or check_list[y][x]!=".":
    return False 
  check_list[y][x] = 1
  return True


R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
maze = [list(input()) for i in range(R)]
check_list = copy.deepcopy(maze)

d = deque()
maze[sy][sx] = 0
check_list[sy][sx] = 1
while(1):
  old_sy, old_sx = sy, sx
  d.append([sy, sx])
  while(d):
    [y, x] = d.popleft()
    if (y, x) == (gy, gx):
      print(maze[gy][gx])
      exit()
    for np in [[y+1, x], [y-1, x], [y, x+1], [y, x-1]]:
      if check_walkable(np[0], np[1]):
        maze[np[0]][np[1]] = maze[y][x]
        d.append([np[0], np[1]])
  d.append([sy, sx])
  while(d):
    [y, x] = d.popleft()
    for np in [[y+1, x], [y-1, x], [y, x], [y, x+1], [y, x-1]]:
      if check_checked(np[0], np[1]):
        d.append([np[0], np[1]])
        for dy in range(-2, 3):
          for dx in range(-2, 3):
            if dy == 0 and dx == 0:
              check_list[np[0]+dy][np[1]+dx] = 2
              continue
              
            if check_walkable(np[0]+dy, np[1]+dx):
              maze[np[0]+dy][np[1]+dx] = maze[np[0]][np[1]]+1
              sy, sx = np[0]+dy, np[1]+dx
  if (old_sy, old_sx) == (sy, sx):
    print(-1)
    exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

def check_checked(y, x):
  if 0>y or 0>x or C<=x or R<=y or check_list[y][x] != 1:
    return False 
  check_list[y][x] = 2
  return True

def check_walkable(y, x):
  if 0>y or 0>x or C<=x or R<=y or check_list[y][x]!=".":
    return False 
  check_list[y][x] = 1
  return True


R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
maze = [list(input()) for i in range(R)]
check_list = copy.deepcopy(maze)

d = deque()
maze[sy][sx] = 0
while(1):
  old_sy, old_sx = sy, sx
  d.append([sy, sx])
  while(d):
    [y, x] = d.popleft()
    if (y, x) == (gy, gx):
      print(maze[gy][gx])
      exit()
    for np in [[y+1, x], [y-1, x], [y, x], [y, x+1], [y, x-1]]:
      if check_walkable(np[0], np[1]):
        maze[np[0]][np[1]] = maze[y][x]
        d.append([np[0], np[1]])
  d.append([sy, sx])
  while(d):
    [y, x] = d.popleft()
    for np in [[y+1, x], [y-1, x], [y, x], [y, x+1], [y, x-1]]:
      if check_checked(np[0], np[1]):
        d.append([np[0], np[1]])
        for dy in range(-2, 3):
          for dx in range(-2, 3):
            if dy == 0 and dx == 0:
              check_list[np[0]+dy][np[1]+dx] = 2
              continue
              
            if check_walkable(np[0]+dy, np[1]+dx):
              maze[np[0]+dy][np[1]+dx] = maze[np[0]][np[1]]+1
              sy, sx = np[0]+dy, np[1]+dx
  if (old_sy, old_sx) == (sy, sx):
    print(-1)
    exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

def check_checked(y, x):
  if 0>y or 0>x or C<=x or R<=y or check_list[y][x] != 1:
    return False 
  check_list[y][x] = 2
  return True

def check_walkable(y, x):
  if 0>y or 0>x or C<=x or R<=y or check_list[y][x]!=".":
    return False 
  check_list[y][x] = 1
  return True


R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
maze = [list(input()) for i in range(R)]
check_list = copy.deepcopy(maze)

d = deque()
maze[sy][sx] = 0
while(1):
  old_sy, old_sx = sy, sx
  d.append([sy, sx])
  while(d):
    [y, x] = d.popleft()
    if (y, x) == (gy, gx):
      print(maze[gy][gx])
      exit()
    for np in [[y+1, x], [y-1, x], [y, x], [y, x+1], [y, x-1]]:
      if check_walkable(np[0], np[1]):
        maze[np[0]][np[1]] = maze[y][x]
        d.append([np[0], np[1]])
  d.append([sy, sx])
  while(d):
    [y, x] = d.popleft()
    for np in [[y+1, x], [y-1, x], [y, x], [y, x+1], [y, x-1]]:
      if check_checked(np[0], np[1]):
        d.append([np[0], np[1]])
        for dy in range(-2, 3):
          for dx in range(-2, 3):
            if check_walkable(np[0]+dy, np[1]+dx):
              maze[np[0]+dy][np[1]+dx] = maze[np[0]][np[1]]+1
              sy, sx = np[0]+dy, np[1]+dx
  if (old_sy, old_sx) == (sy, sx):
    print(-1)
    exit()

Submission status: Wrong Answer

Solution code:
# https://yamakasa.net/atcoder-abc-176-d/

from collections import deque
import sys

# 入力
H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))

# IDをまとめる表、-1で初期化
ID = [[-1] * W for i in range(H)]

# 移動Aで動ける範囲のマスは同一のIDを持つとして、IDを割り振る
id = 0
for x in range(H):
    for y in range(W):
        if maze[x][y]  == "." and ID[x][y] == -1:  # 到達可能でまだIDが割り振られていない点
            #ID[x][y] = id
            # BFSで同一のIDを持つ領域をくまなく探索
            que = deque([])
            que.append((x, y))
            while que:
                temp_x, temp_y = que.popleft()
                ID[temp_x][temp_y] = id
                for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nx = temp_x + dx
                    ny = temp_y + dy
                    if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == "." and ID[nx][ny] == -1:
                        que.append((nx, ny))

            id += 1

# ワープ可能なID同士の繋がりを記録
ID_graph = [[0] * id for i in range(id)]  # IDmとIDnの間がワープ可能ならID[m][n] = 1、そうでなければID[m][n] = 0
for x in range(H):
    for y in range(W):
        if maze[x][y] != "#" and ID[x][y] != -1:  # IDが割り振られている点
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    if abs(dx) + abs(dy) >= 2:  # 移動Aでは移動不可で移動Bでは移動可能なマス
                        nx = x + dx
                        ny = x + dy
                        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and ID[x][y] != ID[nx][ny]:
                            ID_graph[ID[x][y]][ID[nx][ny]] = 1
                            ID_graph[ID[nx][ny]][ID[x][y]] = 1

# ID間の関係から最短距離を求める
ID_score = [float("inf")] * id  # 各IDまで何回のワープでたどり着けるか、INFで初期化
init_ID = ID[C_h-1][C_w-1]  # 初期位置
ID_score[init_ID] = 0

que = deque([])
que.append(init_ID)
while que:
    temp_id = que.popleft()
    if temp_id == ID[D_h-1][D_w-1]:  # ゴールのIDに到達
        break
    for k in range(id):
        if ID_graph[temp_id][k] == 1 and ID_score[k] == float("inf"):  # 今着目しているIDからワープできてまだ見ていないID
            que.append(k)
            ID_score[k] = ID_score[temp_id] + 1

if ID_score[ID[D_h-1][D_w-1]] != float("inf"):
    print(ID_score[ID[D_h-1][D_w-1]])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(lambda x: x - 1, map(int, input().split()))
Dh, Dw = map(lambda x: x - 1, map(int, input().split()))
S = []
already = []
for i in range(H):
    S.append(input())
    already.append([False] * W)
queue = deque()
queue.append((Ch, Cw, 0))
already[Ch][Cw] = True
answer = -1
while len(queue) > 0:
    x, y, cost = queue.popleft()
    if x == Dh and y == Dw:
        answer = cost
        break
    for i in range(-2, 3):
        for j in range(-2, 3):
            new_x, new_y = (x + i, y + j)
            # 場外
            if new_x < 0 or new_y < 0 or H <= new_x or W <= new_y:
                continue
            # 動かない
            if new_x == x and new_y == y:
                continue
            # 壁
            if S[new_x][new_y] == '#':
                continue
            # 探索済み
            if already[new_x][new_y]:
                continue
            if - 1 <= i and i <= 1 and - 1 <= j and j <= 1:
                queue.appendleft((new_x, new_y, cost))
            else:
                queue.append((new_x, new_y, cost+1))
            already[new_x][new_y] = True
print(answer)

Submission status: Wrong Answer

Solution code:

import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

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

MAX = 1000001
cost_list = [[MAX] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()

walk_directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
warp_directions = ((-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))


def walk(z):
    h, w = z
    cost = cost_list[h][w]
    wall = 0
    for [p, q] in walk_directions:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == ".":
                if cost_list[h + p][w + q] > cost:
                    cost_list[h + p][w + q] = cost
                    to_walk.put([h + p, w + q])
            else:
                wall += 1

    if wall > 1:
        to_warp.put([h, w])


def warp(z):
    h, w = z
    cost = cost_list[h][w] + 1
    for [p, q] in warp_directions:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." and cost_list[h + p][w + q] > cost:
                cost_list[h + p][w + q] = cost
                to_walk.put([h + p, w + q])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == MAX:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])

Submission status: Wrong Answer

Solution code:

import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

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

MAX = 1000001
cost_list = [[MAX] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()


def walk(z):
    h, w = z
    cost = cost_list[h][w]
    wall = 0
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == ".":
                if cost_list[h + p][w + q] > cost:
                    cost_list[h + p][w + q] = cost
                    to_walk.put([h + p, w + q])
            else:
                wall += 1
                
    if wall > 1:
        to_warp.put([h, w])


def warp(z):
    h, w = z
    cost = cost_list[h][w] + 1
    for [p, q] 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 (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." and cost_list[h + p][w + q] > cost:
                cost_list[h + p][w + q] = cost
                to_walk.put([h + p, w + q])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == MAX:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])

Submission status: Wrong Answer

Solution code:

import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

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

INF = 10000000
cost_list = [[INF] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()


def walk(z):
    x, y = z
    cost = cost_list[y][x]
    to_warp.put([x, y])
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (0 <= x + p < W) and (0 <= y + q < H):
            if maze[y + q][x + p] == "." and cost_list[y + q][x + p] > cost:
                cost_list[y + q][x + p] = cost
                to_walk.put([x + p, y + q])
                to_warp.put([x + p, y + q])


def warp(z):
    x, y = z
    cost = cost_list[y][x] + 1
    for [p, q] 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 (0 <= x + p < W) and (0 <= y + q < H):
            if maze[y + q][x + p] == "." and cost_list[y + q][x + p] > cost:
                cost_list[y + q][x + p] = cost
                to_walk.put([x + p, y + q])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == INF:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])

Submission status: Wrong Answer

Solution code:

import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

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

INF = 1000000
cost_list = [[INF] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()


def walk(z):
    x, y = z
    cost = cost_list[y][x]
    to_warp.put([x, y])
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (0 <= x + p < W) and (0 <= y + q < H):
            if maze[y + q][x + p] == "." and cost_list[y + q][x + p] > cost:
                cost_list[y + q][x + p] = cost
                to_walk.put([x + p, y + q])
                to_warp.put([x + p, y + q])


def warp(z):
    x, y = z
    cost = cost_list[y][x] + 1
    for [p, q] 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 (0 <= x + p < W) and (0 <= y + q < H):
            if maze[y + q][x + p] == "." and cost_list[y + q][x + p] > cost:
                cost_list[y + q][x + p] = cost
                to_walk.put([x + p, y + q])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == INF:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])

Submission status: Wrong Answer

Solution code:
import queue

W, H = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = S[0] - 1, S[1] - 1
G = G[0] - 1, G[1] - 1

field = []
for i in range(W):
    temp_i = input()
    temp_o = []
    for j in range(H):
        if temp_i[j] == ".":
            temp_o.append(9999)
        if temp_i[j] == "#":
            temp_o.append(-999)
    field.append(temp_o)
field[S[0]][S[1]] = 0
field[G[0]][G[1]] = "G"


def walk(z):
    x, y = z
    cost = field[x][y]
    # print("walk from ", x, y)
    warp_check.put([x, y])
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (0 <= x + p < W) and (0 <= y + q < H):
            try:
                if field[x + p][y + q] > cost:
                    field[x + p][y + q] = cost
                    walk_check.put([x + p, y + q])
                    warp_check.put([x + p, y + q])
            except:
                print(cost)
                exit()


def warp(z):
    x, y = z
    cost = field[x][y] + 1
    # print("warp from", x, y)
    for [p, q] in [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 1], [-1, 2], [0, -2], [0, 0],
                   [0, 2], [1, -2], [1, -1], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]:
        if (0 <= x + p < W) and (0 <= y + q < H):
            try:
                if field[x + p][y + q] > cost:
                    field[x + p][y + q] = cost
                    walk_check.put([x + p, y + q])
            except:
                print(cost)
                exit()


walk_check = queue.Queue()
walk_check.put(S)
warp_check = queue.Queue()

while True:
    while not walk_check.empty():
        walk(walk_check.get())

    while not warp_check.empty():
        warp(warp_check.get())

    if walk_check.empty() and warp_check.empty():
        print(-1)
        break


# for i in range(W):
#     print(field[i])