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:
from collections import deque

import time


def bfs():
    t1 = time.time()


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

                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

        t2 = time.time()
        if t2 - t1 > 1.85:
            break

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



bfs()

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
masu = [list(input()) for _ in range(H)]

import copy

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

from collections import deque
seen = [[0]*W for _ in range(H)]

def bfs(sx,sy,k):
    que = deque([])
    que.append((sx,sy))
    seen[sy][sx] = k
    li = []
    newy,newx = float('inf'),float('inf')
    while que:
        a,b = que.popleft()
        if a==gx and b == gy:
            print(k-1)
            exit()
        for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
            nx = a+x
            ny = b+y
            if 0<=nx<W and 0<=ny<H and not seen[ny][nx]:
                if masu[ny][nx] != '#':
                    seen[ny][nx] = k
                    que.append((nx,ny))
                    if (ny,nx) in li:
                        li.remove((ny,nx))
                else:
                    for p in range(-2,3):
                        for q in range(-2,3):
                            if 0<=a+p<W and 0<=b+q<H and not seen[b+q][a+p] and masu[b+q][a+p] == '.':
                                li.append((b+q,a+p))
    return seen,li

k = 1
while 1:
    seen,li = bfs(sx,sy,k)
    #for l in seen:print(*l)
    #rint(f'{k}:x={sx},y={sy}')
    #print(li)
    if not li:
        print('-1')
        exit()
    for l in li:
        #print(l)
        if not seen[l[0]][l[1]]:
            sx,sy = l[1],l[0]
            break
    k+=1

Submission status: Wrong Answer

Solution code:
import queue
h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
ans = []
q = queue.Queue()
route = [['#']*(w+2)]
for i in range(h):
    route += [list('#'+input()+'#')]
route += [['#']*(w+2)]
a = 0
q.put([c[0], c[1], 0])
while not q.empty():
    now = q.get()
    if now[0] == d[0] and now[1] == d[1]:
        ans.append(now[2]-1+a)

    if route[now[0]+1][now[1]] != '#':
        q.put([now[0]+1, now[1], now[2]+1])
    if route[now[0]-1][now[1]] != '#':
        q.put([now[0]-1, now[1], now[2]+1])
    if route[now[0]][now[1]+1] != '#':
        q.put([now[0], now[1]+1, now[2]+1])
    if route[now[0]][now[1]-1] != '#':
        q.put([now[0], now[1]-1, now[2]+1])
    for i in range(max(0, now[0]-2), min(h+2, now[0]+3)):
        for j in range(max(0, now[1]-2), min(w+2, now[1]+3)):
            if route[i][j] != '#':
                q.put([i, j, now[2]+1])
                route[i][j] = '#'
                a = 1
    route[now[0]][now[1]] = '#'                
if len(ans) == 0:
    print(-1)
else:
    print(min(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 = []
for _ in range(H):
    S.append(list(input()))

# from collections import defaultdict
from queue import Queue

path = dict()
cache = set()

Cur = (Cw-1, Ch-1)
Q = Queue()
Q.put(Cur)
cache.add(Cur)

path[Cur] = 0
G = (Dw - 1, Dh - 1)

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

wdx = []
wdy = []

while not Q.empty():
    node = Q.get()
    cx, cy = node

    # move
    for di in range(4):
        nx = cx + dx[di]
        ny = cy + dy[di]

        if W > nx >= 0 and H > ny >= 0:
            nt = (nx, ny)
            if S[ny][nx] == '.':
                if nt not in cache:
                    # 移動可能
                    Q.put(nt)
                    cache.add(nt)
                    path[nt] = path[node]

                elif nt in path.keys() and path[node] < path[nt]:
                    path[nt] = path[node]
    
    # warp
    for wdx in range(-2, 3, 1):
        for wdy in range(-2, 3, 1):
            if wdx == wdy == 0:
                continue

            nx = cx + wdx
            ny = cy + wdy
            nt = (nx, ny)

            if W > nx >= 0 and H > ny >= 0 and S[ny][nx] == '.':
                if nt not in cache:
                    Q.put(nt)
                    cache.add(nt)
                    path[nt] = path[node] + 1
                elif nt in path.keys() and path[node] + 1 < path[nt]:
                    path[nt] = path[node] + 1

print(path[G] if G in path.keys() else -1)

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	Q=[[0,ch,cw]]
	heapq.heapify(Q)

	#print(Q)

	while Q:
		d,x,y=heapq.heappop(Q)
		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				for t in [-2,-1,0,1,2]:
					if xx==0:
						if S[x+t][y+2*yy]==".":
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
						elif S[x+t][y+2*yy]=="#":
							continue
						elif S[x+t][y+2*yy]>d+1:
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
					else:
						if S[x+2*xx][y+t]==".":
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
						elif S[x+2*xx][y+t]=="#":
							continue
						elif S[x+2*xx][y+t]>d+1:
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
			elif S[x+xx][y+yy]==d:
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])

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


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
Done = [[False]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([])
Q.append([C,0])
while Q:
  z, score = Q.popleft()
  x = z[0];y=z[1]

  if Done[x][y]:
    #print(z,reach[x][y],"DONE")
    continue
  Done[x][y] = True
  #print(z,reach[x][y],Done[x][y])
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      #if Done[nx][ny]: #すでに訪問済みならやらない
      #  continue
      Q.append([u,score])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      #if Done[mx][my]:
      #  continue
      Q.append([p,score+1])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[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())
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:
      if flag:
        break
      for i in range(-2, 3):
        if flag:
          break
        for j in range(-2, 3):
          if (_h + i, _w + j) in field:
            ans += 1
            ch, cw = _h + i + 1, _w + j + 1
            flag = True
            break
    if not flag:
      break

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

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


h, w = inpl()
sy, sx = inpl()
gy, gx = inpl()
sy, sx, gy, gx = sy - 1, sx - 1, gy - 1, gx - 1
maze = [str_inp() for _ in range(h)]
queue = collections.deque()

dp = [[INF] * w for i in range(h)]
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]


def bfs():
    queue.append([sx, sy])
    dp[sy][sx] = 0
    while len(queue):
        x, y = queue.pop()
        if x == gx and y == gy:
            break
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if x + j >= 0 and x + j < w and y + i >= 0 and y + i < h and maze[y + i][x + j] != "#" and dp[y + i][x + j] > dp[y][x]:
                    dp[y + i][x + j] = dp[y][x] + 1
                    queue.append([x + j, y + i])

        for i in range(4):
            next_x = x + dx[i]
            next_y = y + dy[i]

            if next_x >= 0 and next_x < w and next_y >= 0 and next_y < h and maze[
                    next_y][next_x] != "#" and dp[next_y][next_x] > dp[y][x]:
                queue.append([next_x, next_y])
                dp[next_y][next_x] = dp[y][x]
    return dp[gy][gx]


ans = bfs()
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import collections
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 = [input() for _ in range(h)]
table = [[float('inf') for _ in range(w)] for _ in range(h)]
table[Ch][Cw] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
used = [[0 for _ in range(w)] for _ in range(h)]
used[Ch][Cw] = 1
que = collections.deque()
que.append([Ch, Cw])

def bfs(Q):
    while Q:
        # print(Q)
        v = Q.popleft()
        i = v[0]
        j = v[1]
        for k in range(4):
            if 0 <= i+dy[k] < h and 0 <= j+dx[k] < w:
                if s[i+dy[k]][j+dx[k]] == '.':
                    if used[i+dy[k]][j+dx[k]] == 0:
                        table[i+dy[k]][j+dx[k]] = table[i][j]
                        used[i+dy[k]][j+dx[k]] = 1
                        Q.append([i+dy[k], j+dx[k]])
                        # magic
        for a in range(-2, 3):
            for b in range(-2, 3):
                if 0 <= i+a < h and 0 <= j+b < w:
                    if s[i+a][j+b] == '.':
                        table[i+a][j+b] = min(table[i][j]+1, table[i+a][j+b])
        # print(*table, sep='\n')
        # print(*used, sep='\n')
        # print(*s, sep='\n')

bfs(que)
while True:
    for i in range(h):
        for j in range(w):
            if used[i][j] == 0 and table[i][j] != float('inf'):
                que = collections.deque()
                que.append([i, j])
                bfs(que)
                continue
    break

if table[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(table[Dh][Dw])

Submission status: Wrong Answer

Solution code:
# 2020/08/22
# AtCoder Beginner Contest 176 - D

# Input
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
sl = list()
sl.append(['#'] * (w+2))
for i in range(h):
    s = list('#' + input())
    s.append('#')
    sl.append(s)
sl.append(['#'] * (w+2))

wcnt = 0
findflg = False
posq = list()
tl = [[0] * (w+2) for i in range(h+2)]
tl[ch][cw] = 1
posq.append([ch, cw])
passq = list()

loopmax = h  * w

for i in range(loopmax):
    while(len(posq) > 0):
        th, tw = posq.pop()
        if th == dh and tw == dw:
            findflg = True
            break
            
        passq.append([th, tw])
    
        if sl[th-1][tw] == '.' and tl[th-1][tw] == 0:
            posq.append([th-1, tw])
            tl[th-1][tw] = 1
        elif sl[th][tw-1] == '.' and tl[th][tw-1] == 0:
            posq.append([th, tw-1])
            tl[th][tw-1] = 1
        elif sl[th+1][tw] == '.' and tl[th+1][tw] == 0:
            posq.append([th+1, tw])
            tl[th+1][tw] = 1
        elif sl[th][tw+1] == '.' and tl[th][tw+1] == 0:
            posq.append([th, tw+1])
            tl[th][tw+1] = 1

    if findflg == True:
        break

    while(len(passq) > 0):
        ph, pw = passq.pop()
        
        for i in range(ph-2, ph+3):
            for j in range(pw-2, pw+3):
                if i > 0 and i <= h and j > 0 and j <= w:
                    if sl[i][j] == '.' and tl[i][j] == 0:
                        posq.append([i, j])
                        tl[i][j] = 1
    wcnt = wcnt + 1
    if len(posq) == 0:
        break

# Output
if findflg == True:
    ans = wcnt
else:
    ans = -1
    
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

class UnionFind(object):
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    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
    S = [list(input()) for _ in range(H)]

    ncon_num = 0
    nodes = []
    idx = {}
    groups = {}
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                idx[(h, w)] = len(nodes)
                groups[h, w] = None
                nodes.append((h, w))
    N = len(nodes)
    uf = UnionFind(N)

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#': continue
            I = idx[h, w]
            for i in range(4):
                nnh, nnw = h + dh[i], w + dw[i]
                if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                    J = idx[nnh, nnw]
                    uf.unite(I, J)

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#': continue
            I = idx[h, w]
            # print(I, uf.members(I))
            if groups[nodes[I]] is None:
                groups[nodes[I]] = ncon_num
                for k in uf.members(I):
                    groups[nodes[k]] = ncon_num
                ncon_num += 1

    if ncon_num == 1:
        print(0)
        exit()

    ncon = len(set(groups.values()))
    start_con, goal_con = groups[Ch, Cw], groups[Dh, Dw]
    # print(ncon, start_con, goal_con)
    # print(groups)
    
    edges = [[] for _ in range(ncon)]
    dist_mat = [[float("inf")] * ncon for _ in range(ncon)]
    for k in range(ncon):
        dist_mat[k][k] = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#': continue
            I = idx[h, w]
            di = groups[nodes[I]]
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nnh, nnw = h + ddh, w + ddw
                    if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                        J = idx[nnh, nnw]
                        dj = groups[nodes[J]]
                        if I == J:
                            continue
                        elif di == dj:
                            continue
                        else:
                            dist_mat[di][dj] = 1

    for n in range(ncon):
        for m in range(n + 1, ncon):
            if dist_mat[n][m] != float("inf"):
                edges[n].append((m, 1))
                edges[m].append((n, 1))

    # 作成したグラフでDijkstra
    d = [float("inf")] * ncon
    used = [True] * ncon
    d[start_con] = 0
    used[start_con] = False
    edgelist = []
    for e in edges[start_con]:
        heappush(edgelist, e)
    
    while len(edgelist):
        minedge = heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edges[v]:
            if used[e[1]]:
                heappush(edgelist,[e[0]+d[v],e[1]])

    if d[goal_con] == float("inf"):
        print(-1)
    else:
        print(d[goal_con])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

H, W = map(int,input().split())
Ch1, Cw1 = map(int,input().split())
Dh1, Dw1 = map(int,input().split())

Ch = Ch1 -1
Cw = Cw1 -1

Dh = Dh1 - 1
Dw = Dw1 - 1


def finding(a,b): #(a,b)から5マス以内に数字マスがあるか索敵
    if type(T[a][b]) == int:
        return T[a][b]
    else:
        V = []
        for i in range(-5,6):
            for j in range(-(5 - abs(i)), 6 - abs(i)):
                if type(T[min(max(0,a-i), H-1)][min(max(0,b-j),W-1)]) == int:
                    V += [T[min(max(0,a-i), H-1)][min(max(0,b-j),W-1)]]
        if V != []:
            return min(n + 1 for n in V)
        else:
            return T[a][b]
            


i = 0
S = []
while i < H:
    s= map(list,input().split())
    li = list(s)
    S += li
    i += 1

T = deepcopy(S)
T[Ch][Cw] = 0
U = []
while T!= U:
    while T != U:
        U = deepcopy(T)
        for i in range(H):
            for j in range(W):
                if T[i][j] != '#':
                    if type(T[max(i-1,0)][j]) == int:
                        T[i][j] = T[max(i-1,0)][j]
                    if type(T[i][min(j+1,W-1)]) == int:
                        T[i][j] = T[i][min(j+1,W-1)]
                    if type(T[min(i+1,H-1)][j]) == int:
                        T[i][j] = T[min(i+1,H-1)][j]
                    if type(T[i][max(j-1,0)]) == int:
                        T[i][j] = T[i][max(j-1,0)]
    for a in range(H):
        for b in range(W):
            if T[a][b] != '#':
                T[a][b] = finding(a,b)


if T[Dh][Dw] == '.':
    print(-1)
else:
    print(T[Dh][Dw])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


# MAGIC = ((-2, -2), (-1, -2), (1, -2), (2, -2),
#          (-2, -1), (-1, -1),  (1, -1), (2, -1),
#          (-2, 1), (-1, 1), (1, 1), (2, 1),
#          (-2, -2), (-1, 2), (1, 2), (2, 2))

MAGIC = ((-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))
H, W = zz()

c_h, c_w = zz()
d_h, d_w = zz()
board = []
c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
for i in range(H):
    tmp = S()
    # N += tmp.count('.')
    board.append(tmp)

# print(board)
que = deque([[c_h, c_w, 0]])
visited = []
magic_visited = []
dist = {}
# bfs()
while que:
    h, w, magic = que.popleft()
    visited.append((h, w))
    if (magic > 0):
        magic_visited.append((h, w))
    try:
        dist[(h, w)] = min(dist[(h, w)], magic)
    except:
        dist[(h, w)] = magic
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        # セルが白('.')であるのと同義
        if board[new_h][new_w] == '.' and ((new_h, new_w) not in visited):
            que.append((new_h, new_w, magic))

    for dy, dx in MAGIC:
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if board[new_h][new_w] == '.' and ((new_h, new_w) not in magic_visited):
            # print(new_h, new_w, magic)
            que.append((new_h, new_w, magic+1))
"""
que = deque(visited)
count = 0
while que:
    tmp = que.popleft()
    if (len(tmp) == 3):
        h, w, magic = tmp
    else:
        h, w = tmp
        magic = 0
    visited.append((h, w))
    dist[(h, w)] = magic
    for dy, dx in MAGIC:
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if board[new_h][new_w] == '.' and ((new_h, new_w) not in visited):
            print(new_h, new_w)
            que.append((new_h, new_w, magic+1))
"""
try:
    print(dist[(d_h, d_w)])
except:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

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

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])

while route:
    while route:
        y, x = route.popleft()
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    wroute = deque([])
    for i in range(w):
        for j in range(h):
            if visit[j][i] == cnt:
                wroute.append([j, i])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

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())
sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
S = [list(input()) for _ in range(H)]

stamp = [[-1 for _ in range(W)] for _ in range(H)]
dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
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]]
cnt = 0

def search(x,y):
  if x == gx-1 and y == gy-1:
    print(cnt)
    sys.exit()
  if x < 0 or H-1 < x or y < 0 or W-1 < y or stamp[x][y] != -1:
    return
  elif S[x][y] == "#":
    stamp[x][y] = 0
    return
  stamp[x][y] = 0
  for dx, dy in dxdy:
    search(x+dx,y+dy)
  return

x, y = sx-1, sy-1
search(x,y)

check = True
while check:
  cnt += 1
  for dx, dy in warp:
    if x+dx < 0 or H-1 < x+dx or y+dy < 0 or W-1 < y+dy:
      continue
    elif stamp[x+dx][y+dy] == -1:
      x = x+dx
      y = y+dy
      search(x,y)
  check = False
  for i in stamp:
    for j in i:
      if j == -1:
        check = True

print(-1)