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())
s = [[-1]*(w+4)]
s.append([-1]*(w+4))
for i in range(h):
  s.append(list(input()))
  s[i+2].insert(0,-1)
  s[i+2].insert(0,-1)
  s[i+2].append(-1)
  s[i+2].append(-1)
s.append([-1]*(w+4))
s.append([-1]*(w+4))
for i in range(2,h+2):
  for j in range(2,w+2):
    if s[i][j] == '#':
      s[i][j] = -1
    else:
      s[i][j] = 10**6
s[ch+1][cw+1] = 0

stack = []
stack.append([ch+1,cw+1])
while True:
  if len(stack)==0:
    break
  st = stack.pop()
  sh = st[0]
  sw = st[1]
  if s[sh-1][sw]>s[sh][sw]:
    s[sh-1][sw] = s[sh][sw]
    stack.append([sh-1,sw])
    if sh-1==dh and sw==dw:
      break
  if s[sh][sw-1]>s[sh][sw]:
    s[sh][sw-1] = s[sh][sw]
    stack.append([sh,sw-1])
    if sh==dh and sw-1==dw:
      break
  if s[sh+1][sw]>s[sh][sw]:
    s[sh+1][sw] = s[sh][sw]
    stack.append([sh+1,sw])
    if sh+1==dh and sw==dw:
      break
  if s[sh][sw+1]>s[sh][sw]:
    s[sh][sw+1] = s[sh][sw]
    stack.append([sh,sw+1])
    if sh==dh and sw+1==dw:
      break
  shh = st[0]-2
  sww = st[1]-2
  for i in range(5):
    for j in range(5):
      if s[shh+i][sww+j] > s[sh][sw]+1:
        s[shh+i][sww+j] = s[sh][sw]+1
        stack.insert(0,[shh+i,sww+j])
      
if s[dh+1][dw+1]==10**6:
  print(-1)
else:
  print(s[dh+1][dw+1])

Submission status: Wrong Answer

Solution code:
h = 0
w = 0
reached = []
maze = []
dh = 0
dw = 0


def main():
    global h
    global w
    global dh
    global dw
    h, w = map(int, input().split())    # 迷路
    ch, cw = map(int, input().split())  # 魔法使い位置
    dh, dw = map(int, input().split())  # ゴール
    for i in range(h):
        maze.append(list(input()))
    # for (i, row) in enumerate(maze, 1):
    #     print('{}: {}'.format(i, row))
    warp_count = 0
    while True:
        if walk_to(ch, cw):
            # 到達
            # print('Goal!')
            print(warp_count)
            break
        else:
            # 行ったことのある場所からワープ
            mch, mcw = most_close()
            # print('一番近かったのは {},{}'.format(mch, mcw))
            warped_hw = warp_from(mch, mcw)
            if warped_hw is not None:
                warp_count += 1
                ch, cw = warped_hw
            else:
                # 到達不能
                # print('到達不能')
                print(-1)
                break


def warp_from(mch, mcw):
    start_h = max(mch - 2, 1)
    end_h = min(mch + 2, h)
    start_w = max(mcw - 2, 1)
    end_w = min(mcw + 2, w)

    min_distance = None
    min_hw = None
    for i in range(start_h, end_h + 1):
        for j in range(start_w, end_w + 1):
            # print(i, j)
            if get_block(i, j) == '.' and yet(i, j):
                # print('{},{}にはワープできるね'.format(i, j))
                distance = abs(dh - i) + abs(dw - j)
                if min_distance is None or distance < min_distance:
                    min_distance = distance
                    min_hw = [i, j]
    return min_hw


def most_close():
    min_hw = []
    min_distance = None
    for r in reached:
        distance = max(abs(dh - r[0]), abs(dw - r[1]))
        if min_distance is None or distance < min_distance:
            min_distance = distance
            min_hw = [r[0], r[1]]
    return min_hw


def walk_to(current_h, current_w):
    reached.append([current_h, current_w])    # 到達済み
    if current_h == dh and current_w == dw:
        return True
    # ↑
    if current_h > 1 and get_block(current_h - 1, current_w) == '.' and yet(current_h - 1, current_w):
        # print('現在{},{}: 上に行けるよ'.format(current_h, current_w))
        return walk_to(current_h - 1, current_w)
    # →
    if current_w < w and get_block(current_h, current_w + 1) == '.' and yet(current_h, current_w + 1):
        # print('現在{},{}: 右に行けるよ'.format(current_h, current_w))
        return walk_to(current_h, current_w + 1)
    # ↓
    if current_h < h and get_block(current_h + 1, current_w) == '.' and yet(current_h + 1, current_w):
        # print('現在{},{}: 下に行けるよ'.format(current_h, current_w))
        return walk_to(current_h + 1, current_w)
    # ←
    if current_w > 1 and get_block(current_h, current_w - 1) == '.' and yet(current_h, current_w - 1):
        # print('現在{},{}: 左に行けるよ'.format(current_h, current_w))
        return walk_to(current_h, current_w - 1)

    # print('現在{},{}: どこにも行けない'.format(current_h, current_w))
    return False


def get_block(target_h, target_w):
    return maze[target_h - 1][target_w - 1]


def yet(check_h, check_w):
    for r in reached:
        if check_h == r[0] and check_w == r[1]:
            return False
    return True


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def C_BFS2(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs2(maze, row, column, sy, sx, gy, gx):
        tmp = [[2,2],[2,1],[2,0],[2,-1],[2,-2],\
       [1,2],[1,-2],[0,2],[0,-2],\
       [-1,2],[-1,-2],\
       [-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                 # ゴール座標と一致するなら
                break
            for i in range(16):
                nx = x + tmp[i][0]
                ny = y + tmp[i][1]
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x] + 1
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    if dist[ny][nx] > dist[y][x]:
                        dist[ny][nx] = min(dist[y][x],dist[ny][nx])
        return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs2(maze, R, C, sy, sx, gy, gx)
    return ans

def C_BFS(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs(maze, row, column, sy, sx, gy, gx):
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x]
                    # （追記）距離の最大値を更新する
                    if dist_max < dist[ny][nx]:
                        dist_max = dist[ny][nx]
        return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs(maze, R, C, sy, sx, gy, gx)
    return ans

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]
import sys
# スタート地点は全て試す
dist_ans = 0
dist_tmp = C_BFS(H, W, Ch, Cw, Dh, Dw, S) # 今回、 gy, gx は不要
INF = float('inf')
if dist_tmp == 0:
    print(0)
    sys.exit()
else:
    dist_ans = 0
    dist_tmp = C_BFS2(H, W, Ch, Cw, Dh, Dw, S) # 今回、 gy, gx は不要
    INF = float('inf')
    if dist_tmp == INF:
        print(-1)
    else:
        print(dist_tmp)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
c = [int(i) + 1 for i in input().split()]
d = [int(i) + 1 for i in input().split()]

s = []
s.append('#'*(W+4))
s.append('#'*(W+4))
for i in range(H):
    a = input()
    s.append('##' + a + '##')
s.append('#'*(W+4))
s.append('#'*(W+4))

q = deque([]) # 探索開始点
qq = deque([])
q.append((c[0], c[1], 0))
visited = [[False for __ in range(W+4)] for _ in range(H+4)]

while q:
    xx, yy, kaisuu = q.pop()
    qq.append((xx, yy, kaisuu))
    visited[xx][yy] = True
    ls = []
    while qq:
        x, y, kaisuu = qq.pop()
        visited[x][y] = True
        ls.append((x, y, kaisuu))
        if x == d[0] and y == d[1]:
            print(kaisuu)
            sys.exit()
        if s[x+1][y] == '.' and visited[x+1][y] == False:
            qq.append((x+1, y, kaisuu))
            visited[x+1][y] = True
        if s[x-1][y] == '.' and visited[x-1][y] == False:
            qq.append((x-1, y, kaisuu))
            visited[x-1][y] = True
        if s[x][y+1] == '.' and visited[x][y+1] == False:
            qq.append((x, y+1, kaisuu))
            visited[x][y+1] = True
        if s[x][y-1] == '.' and visited[x][y-1] == False:
            qq.append((x, y-1, kaisuu))
            visited[x][y-1] = True
    for u in ls:
        a, b, c = u
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if abs(i) == 1 and abs(j) == 1:
                    continue
                if s[a+i][b+j] == '.' and visited[a+i][b+j] == False:
                    q.append((a+i, b+j, c+1))
print(-1)

Submission status: Wrong Answer

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

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "#":
				continue
			for i in range(-2, 2+1):
				for j in range(-2, 2+1):
					if (i, j) == (0, 0):
						continue
					if getMaze(x + i, y + j) == ".":
						if (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
							graph[y][x].append((x + i, y + j, 0))
						else:
							graph[y][x].append((x + i, y + j, 1))


	log.print(graph)
	stack = deque([(cw-1, ch-1)])
	dist = [[-1]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		if dist[y][x] == -1:
			dist[y][x] = 0
		d = dist[y][x]
		nexts = graph[y][x]
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] != -1:
				dist[ny][nx] = min(d + cost, dist[ny][nx])
				continue
			dist[ny][nx] = d + cost
			if cost == 1:
				stack.append((nx, ny))
			else:
				stack.appendleft((nx, ny))
	log.print(dist)
	print(dist[dh-1][dw-1])
	
	


main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = deque([(Dh, Dw)])
    bq = deque()
    while True:
        while q:
            h, w = q.pop()
            # print('({}, {}) = {}'.format(h, w, ans))
            if h == Ch and w == Cw:
                print(ans)
                return True
            M[h][w] = 'x'
            for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= h+dh < H and 0 <= w+dw < W:
                    if M[h+dh][w+dw] == '.':
                        q.append((h+dh, w+dw))
                    elif M[h+dh][w+dw] == '#':
                        bq.append((h+dh, w+dw))
            for dh, dw in [(1, 1), (-1, 1), (-1, -1), (1, -1)]:
                if 0 <= h+dh < H and 0 <= w+dw < W:
                    if M[h+dh][w+dw] == '#':
                        bq.append((h+dh, w+dw))

        while bq:
            h, w = bq.pop()
            for dh in range(-1, 2):
                for dw in range(-1, 2):
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q.append((h+dh, w+dw))
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

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

                if 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

                if 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

H,W = map(int,input().split())
curX,curY = map(int,input().split())
goalX,goalY =  map(int,input().split())
goalX -= 1
goalY -= 1

graph = []
for _ in range(H):
  r = list(input())
  graph.append(r)

ans = float('inf')
q = deque([(curX-1,curY-1,0)])
visited = [ [False]*W for _ in range(H) ]
while q:
  new_q = deque()

  for _ in range(len(q)):
    r,c,hop = q.popleft()
    if r==goalX and c==goalY:
      ans = min(ans, hop)
      continue
    visited[r][c] = True

    # # if be able to move 1 step
    # for x,y in [(-1,0),(0,-1),(1,0),(0,1)]:
    #   nr,nc = r+x,c+y
    #   if nr<0 or nc<0 or nr>=H or nc>=W: continue
    #   if graph[nr][nc] == "#": continue
    #   if visited[nr][nc]: continue
    #   new_q.append((nr,nc,hop))

    for i in range(-2, 3):
      for j in range(-2, 3):
        nr,nc = r+i,c+j
        if nr<0 or nc<0 or nr>=H or nc>=W: continue
        if graph[nr][nc] == "#": continue
        if visited[nr][nc]: continue
        if (i,j) in [(-1,0),(0,-1),(1,0),(0,1)]:
          new_q.append((nr,nc,hop))
        else:
          new_q.append((nr,nc,hop+1))

  q = new_q

if ans == float('inf'):
  print(-1)
else:
  print(ans)

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

# 島がいくつあるか検索
# nは何個目の島か
next_list = [[ch-1,cw-1]]
n = 1

def dfs(h_i, w_i, n):
  S[h_i][w_i] = n
  
  if not next_list:
    for i in range(max(h_i-2,0), min(h_i+3,h))[::-1]:
      for j in range(max(w_i-2,0), min(w_i+3,w))[::-1]:
        if S[i][j]=='.':
          next_list.append([i,j])
          break
    
  for dh, dw in [[1,0], [0,-1], [-1,0], [0,1]]:
    if 0<=h_i+dh<=h-1 and 0<=w_i+dw<=w-1:
      if S[h_i+dh][w_i+dw]=='.':
        dfs(h_i+dh, w_i+dw, n)

while next_list:
  h_i, w_i = next_list.pop(0)
  if S[h_i][w_i]=='.':
    dfs(h_i, w_i, n)
    n += 1

print(-1 if S[dh-1][dw-1]=='.' else S[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    h,w= map(int, input().split())
    cx,cy = map(int, input().split())
    dx,dy = map(int, input().split())
    s=[]
    s.append(list("#"*(w+4)))
    s.append(list("#"*(w+4)))
    for i in range(h):
        temp=input()
        temp="##"+temp+"##"
        s.append(list(temp))
    s.append(list("#"*(w+4)))
    s.append(list("#"*(w+4)))
#    for i in range(h+4):
#        print(s[i])

    visited = [[0 for i in range(w+4)] for _ in range(h+4)]
    warpvisited = [[0 for i in range(w + 4)] for _ in range(h + 4)]
    warp = [[INFI for i in range(w+4)] for _ in range(h+4)]
    visited[cx+1][cy+1]=1
    warp[cx+1][cy+1]=0

    walkqueue = deque([])
    warpqueue = deque([])
    warpdire=[[-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],
              [0,-1],[-1,0],[1,0],[0,1]]
    walkdire=[[0,-1],[-1,0],[1,0],[0,1]]


    def warploop():
        warpvisited = [[0 for i in range(w + 4)] for _ in range(h + 4)]
        nowx = cx + 1
        nowy = cy + 1
        for i in warpdire:
            if s[nowx + i[0]][nowy + i[1]] == "." and warpvisited[nowx + i[0]][nowy + i[1]] == 0:
                warpqueue.append([nowx + i[0], nowy + i[1]])
                warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy] + 1, warp[nowx + i[0]][nowy + i[1]])
                visited[nowx + i[0]][nowy + i[1]] = 1
                warpvisited[nowx + i[0]][nowy + i[1]] = 1

        while warpqueue:
            if len(warpqueue) <= 0:
                break
            now = warpqueue.popleft()
            nowx = now[0]
            nowy = now[1]

            for i in warpdire:
                if s[nowx + i[0]][nowy + i[1]] == "." and warpvisited[nowx + i[0]][nowy + i[1]] == 0:
                    warpqueue.append([nowx + i[0], nowy + i[1]])
                    warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy] + 1, warp[nowx + i[0]][nowy + i[1]])
                    visited[nowx + i[0]][nowy + i[1]] = 1
                    warpvisited[nowx + i[0]][nowy + i[1]] = 1
        return
    warploop()

    def walkloop(aaa, bbb):
        nowx = aaa
        nowy = bbb
        walkvisited = []
        walkmin = warp[nowx][nowy]
        for i in walkdire:
            if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] <= 1:
                walkqueue.append([nowx + i[0], nowy + i[1]])
                warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy], warp[nowx + i[0]][nowy + i[1]])

                visited[nowx + i[0]][nowy + i[1]] = 2

        while walkqueue:
            if len(walkqueue) <= 0:
                break
            now = walkqueue.popleft()
            nowx = now[0]
            nowy = now[1]
            walkmin = min(warp[nowx][nowy], walkmin)
            walkvisited.append([nowx, nowy])
            for i in walkdire:
                if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] <= 1:
                    walkqueue.append([nowx + i[0], nowy + i[1]])
                    warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy], warp[nowx + i[0]][nowy + i[1]])
                    visited[nowx + i[0]][nowy + i[1]] = 2
        for i in walkvisited:
            warp[i[0]][i[1]] = walkmin

    if visited[dx + 1][dy + 1] != 0:
        while visited[dx + 1][dy + 1] <= 1:
            walkloop(cx + 1, cy + 1)
            for ii in range(h+4):
                for j in range(w+4):
                    if visited[ii][j]>=2 or s[ii][j]=="#":
                        continue
                    for i in warpdire:
                        warp[ii][j] = min(warp[ii][j], warp[ii - i[0]][j - i[1]]+1)
                    walkloop(ii,j)
                    visited[ii][j]=2




    if visited[dx+1][dy+1]==0:
        print("-1")
    else:
        print(warp[dx+1][dy+1])

 #   for i in range(h+4):
 #       print(visited[i])
 #   for i in range(h+4):
   #     print(warp[i])




if __name__ == "__main__":

    main()

Submission status: Wrong Answer

Solution code:
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
dp = [[1e10+1 for __ in range(w)] for _ in range(h)]
isFirst = True
S = [[] for _ in range(h)]
for i in range(h):
    S[i] = list(input())
    for j in range(w):
        if S[i][j] == '#':
            dp[i][j] = -1
            continue
        if isFirst:
            dp[i][j] = 0
            isFirst = False
        
        t = max(0, i-2)
        b = min(h-1, i+2)
        l = max(0, j-2)
        r = min(w-1, j+2)
        magic = dp[i][j]+1
        for wi in range(t, b+1):
            for wj in range(l, r+1):
                dp[wi][wj] = min(dp[wi][wj], magic)

        if i-1 >= 0:
            dp[i-1][j] = min(dp[i-1][j], dp[i][j])
        if i+1 < h:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j-1 >= 0:
            dp[i][j-1] = min(dp[i][j-1], dp[i][j])
        if j+1 < w:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])

# print(dp)
if dp[ch-1][cw-1] == 1e10+1 or dp[dh-1][dw-1] == 1e10+1:
    print(-1)
else:
    print(abs(dp[ch-1][cw-1] - dp[dh-1][dw-1]))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = ['#' * (H + 4)]
S.append('#' * (H + 4))
for _ in range(H):
    S.append('##' + input() + '##')
S.append('#' * (H + 4))
S.append('#' * (H + 4))

mapping = [[-1] * (W + 4) for _ in range(H + 4)]
count = 0

Ch = Ch + 1
Cw = Cw + 1
Dh = Dh + 1
Dw = Dw + 1


def dfs(i, j):
    if S[i][j] == '#' or mapping[i][j] != -1:
        return
    mapping[i][j] = count
    dfs(i - 1, j)
    dfs(i + 1, j)
    dfs(i, j - 1)
    dfs(i, j + 1)


dfs(Ch, Cw)

warp = [[-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]]
flag = [0]

while mapping[Dh][Dw] == -1 and flag[0] == 0:
    flag[0] = 1
    count += 1
    for i in range(2, H + 2):
        for j in range(2, W + 2):
            if S[i][j] == '.' and mapping[i][j] == -1:
                for n in range(20):
                    if mapping[i + warp[n][0]][j + warp[n][1]] == count - 1:
                        mapping[i][j] = count
                        flag[0] = 0
                        break
            if mapping[i][j] == count:
                dfs(i, j)

print(mapping[Dh][Dw])

Submission status: Wrong Answer

Solution code:
def get_position(node):
    h = node//W + 1
    w = node%W
    if w == 0:
        w = W
    return (h,w)

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

N=H*W

#壁のノード
wall=[]
for h in range(H):
    for w_idx,w in enumerate(list(input())):
        if w == '#':
            wall.append(W*h+w_idx+1)
#道のノード        
path=[_ for _ in range(1,N+1) if _ not in wall]

#隣接リスト
ad = {}
for n in range(N):
    ad[n+1]=[]
    
for n in range(N):
    n=n+1
    if n not in wall:
        up = n-W
        if up > 0 and up not in wall:
            ad[n].append(up)
            
        down = n+W
        if down <= N and down not in wall:
            ad[n].append(down)
            
        left = n-1
        if n % W != 1 and left not in wall and left > 0:
            ad[n].append(left)
        
        right = n+1
        if n % W != 0 and right not in wall:
            ad[n].append(right)     

from collections import deque
    
color = {}
for n in range(N):
    color[n+1] = -1

depth = {}
for n in range(N):
    depth[n+1] = -1
    
group = {}
# for n in range(N):
#     group[n+1] = -1
    
group_= 0
for p in path:
    if color[p] != -1: 
        continue
    elif color[p] == -1: 
        start = p
        color[start] = 0
        que = deque([start])
        visit = deque([])
        group_+=1
        group[group_] = [start]

    depth[start] = 0
    while len(que) > 0:
        start = que[0]
#         print(start,que)
        for v in ad[start]:
#             print(v,color[v])
            if color[v] == -1:
                que.append(v)
                color[v] = 0
                depth[v] = depth[start]+1
                group[group_].append(v)
                
        color[start] = 1
        visit.append(que.popleft())

group_conect={}
for g in group.keys():
    group_conect[g] = set([])
    
break_flag = False
for g_1 in range(1,group_+1):
    for g_2 in range(g_1+1,group_+1):
        for g1 in group[g_1]:
            for g2 in group[g_2]:
                y,x = get_position(g1)
                y_min = max(0,y-2)
                y_max = min(W,y+2)
                x_min = max(0,x-2)
                x_max = min(H,x+2)
                Y,X = get_position(g2)

                if y_min <= Y and Y <= y_max and x_min <= X and X <= x_max:
                    group_conect[g_1].add(g_2)
                    group_conect[g_2].add(g_1)
                    break
print(group_conect)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
i0, j0 = map(lambda x: int(x) - 1, input().split())
i1, j1 = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
D = [[10**5] * w for i in range(h)]
V = [[False] * w for i in range(h)]
Q = deque([(i0, j0)])
D[i0][j0] = 0
V[i0][j0] = True
while Q:
    i2, j2 = Q.popleft()
    if (i2, j2) == (i1, j1):
        print(D[i2][j2])
        exit()
    for i3 in range(i2 - 2, i2 + 3):
        for j3 in range(j2 - 2, j2 + 3):
            if 0 <= i3 < h and 0 <= j3 < w and S[i3][j3] == "." and not V[i3][j3]:
                Q.append((i3, j3))
                D[i3][j3] = min(D[i3][j3], D[i2][j2] + 1)
                if (i3, j3) in ((i2 - 1, j2), (i2 + 1, j2),
                                (i2, j2 - 1), (i2, j2 + 1)):
                    D[i3][j3] = D[i2][j2]
if D[i1][j1] == 10**5:
    print(-1)
else:
    print(D[i1][j1])