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 queue import deque
import heapq

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
inf = 10**10

ch -= 1
cw -= 1
dh -= 1
dw -= 1

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = input()
    for j in range(w):
        li[i][j] = s[j]

dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
bomb_count = 0

mx = []
my = []

for i in range(-2,3):
    for j in range(-2,3):
        if i == 0 and j == 0:
            continue
        mx.append(i)
        my.append(j)

lin = [[inf for i in range(w)]for j in range(h)]
lin[ch][cw] = 0#ここをスタートの座標に変えること
que.append((ch,cw))#ここもスタートの座標に変えること
visited = [[False for i in range(w)]for j in range(h)]

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]

    se = set()

    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#" :
            continue
        elif visited[nx][ny] == True:
            continue
        else:
            if lin[nx][ny] > lin[x][y]:
                visited[nx][ny] = True
                se.add((nx,ny))
                lin[nx][ny] = lin[x][y]# 直接行ける
        
    # 魔法の力をもってすれば行ける
    for i,j in zip(mx,my):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#" :
            continue
        else:
            if lin[nx][ny] > lin[x][y]+1:
                se.add((nx,ny))
                lin[nx][ny] = lin[x][y]+1

    que += se

if lin[dh][dw] == inf:
    print(-1)
else:
    print(lin[dh][dw])

Submission status: Wrong Answer

Solution code:
#D
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
A= [list(input()) for _ in range(H)]
d= [ [ -1 for _ in range(W) ] for _ in range(H)]
f= [ [ False for _ in range(W) ] for _ in range(H)]
ans=0

v = deque([ [ch,cw] ])
d[ch][cw]=0
f[ch][cw]=True
move = [(1,0),(-1,0),(0,1),(0,-1)]  #y,xの順

while v:
    while v:
        a = v.pop()
        for mv in move:
            y = a[0]+mv[0]
            x = a[1]+mv[1]
            if 0<=y<=H-1 and 0<=x<=W-1:
                if d[y][x]== -1:
                    if A[y][x]==".":
                        d[y][x] = d[a[0]][a[1]]
                        v.append([y,x])
                        if y==dh and x==dw:
                            print(d[y][x])
                            exit()
    else:
        for i in range(0,W):
            for j in range(0,H):
                if d[j][i]==-1:
                    if A[j][i]==".":
                        d[j][i]=10**9
                        k = max(j-2,0)
                        l = min(j+2,H-1)
                        m = max(i-2,0)
                        n = min(i+2,W-1)
                        for s in range(m,n+1):
                            for t in range(k,l+1):
                                if d[t][s]>=0:
                                    d[j][i] = min(d[j][i],d[t][s]+1)
                        if d[j][i]==10**9:
                            d[j][i]=-1
                        else:
                            v.append([j,i])
                            if j==dh and i==dw:
                                print(d[j][i])
                                exit()
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
xy=[(1,0),(-1,0),(0,1),(0,-1)]
wp=[(-1,-1),(-1,1),(1,1),(1,-1),(2,0),(-2,0),(0,2),(0,-2),(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]

h,w=map(int,input().split())
c1,c2=map(int,input().split())
d1,d2=map(int,input().split())
d=[list(input()) for i in range(h)]
d[c1-1][c2-1]=0
p=set([(c1-1,c2-1)])
while len(p):
    a,b=p.pop()
    for x,y in xy:
        x+=a
        y+=b
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>d[a][b]:
                d[x][y]=d[a][b]
                p.add((x,y))
    #for x,y in wp:
    #    x+=a
    #    y+=b
    #    if 0<=x<h and 0<=y<w and d[x][y]!="#":
    #        if d[x][y]=="." or d[x][y]>d[a][b]+1:
    #            d[x][y]=d[a][b]+1
    #            p.add((x,y))
#    print(p)
#    print(d)

print(-1 if (d[d1-1][d2-1]=="#" or d[d1-1][d2-1]==".") else d[d1-1][d2-1])

Submission status: Wrong Answer

Solution code:
import heapq
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)
queue = []
heapq.heappush(queue,[0,ch-1,cw-1])
used_map = [[-1]*w for _ in range(h)]

layer_set = set()
layer_set.add((ch-1,cw-1))
loop = 0
while layer_set != set():
    layer_set = set()
    #move walk
    while queue != []:
        dot = heapq.heappop(queue)
        if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
            continue
        if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
            continue
        if road_map[dot[1]][dot[2]] == "#":
            continue
        used_map[dot[1]][dot[2]] = dot[0]
        layer_set.add((dot[1],dot[2]))
        if used_map[dh-1][dw-1] > -1 and dot[0] >= used_map[dh-1][dw-1]:
            break

        if not (dot[2] - 1 < 0):
            heapq.heappush(queue,[dot[0],dot[1],dot[2]-1])
        if not (dot[2] + 1 >= w):
            heapq.heappush(queue,[dot[0],dot[1],dot[2]+1])
        if not (dot[1]+1 >= h):
            heapq.heappush(queue,[dot[0],dot[1]+1,dot[2]])
        if not (dot[1]-1 < 0):
            heapq.heappush(queue,[dot[0],dot[1]-1,dot[2]])

    temp = []
    for s in layer_set:
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(s[0]+ x < 0 or s[1]+y < 0 or s[0]+x >= h or s[1]+y >= w):
                    if used_map[s[0]+x][s[1]+y] == -1 and road_map[s[0]+x][s[1]+y] == ".":
                        temp = [s[0]+x,s[1]+y]
                if temp != []:
                    break
            if temp != []:
                break
        if temp != []:
            break 
    if temp != []:
        heapq.heappush(queue,[loop+1,temp[0],temp[1]])
    loop+=1
    
print(used_map[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
import sys, math

# input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[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.parents) if x < 0]

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


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


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]


groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue
        g = set()
        for s in S[max(0, i-2):i+3]:
            g |= set(s[max(0, j-2):j+3])
        if -1 in g:
            g.remove(-1)
        for k in g:
            can_reach[S[i][j]][k] = True
            can_reach[k][S[i][j]] = True

can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()
"""
reached = [s]
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    new_reached = []
    ans += 1
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[k]:
                new_reached.append(k)
    reached = list(set(new_reached))
print(-1)
"""

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

    warp = ((-2, -2), (-2, -2), (-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))

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc + 1:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1
                        break

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

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

cost = [[0] * W for _ in range(H)]


dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(ch-1, cw-1, 0)])
used = {(ch-1, cw-1)}
warp = [(ch-1, cw-1)]
ddd = []
for i in range(-2,3):
    for j in range(-2,3):
        if i == j == 0:
            continue
        ddd.append((i,j))    

idx = 0
while que:
    while que:
        s, t, cost = que.popleft()
        if s == dh-1 and t == dw-1: 
            print(cost)
            sys.exit()
            break
        for di, dj in dd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost))
            warp.append((xi,yj)) 
            
    while idx <= len(warp) - 1:
        s, t = warp[idx]
        if s == dh-1 and t == dw-1: 
            print(cost)
            sys.exit()
        for di, dj in ddd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost+1))
        idx += 1
    

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import stdin
h,w =map(int, stdin.readline().split())
ch,cw = map(int, stdin.readline().split())
dh,dw =map(int, stdin.readline().split())

g = []
for i in range(h):
  s = list(input())
  g.append(s)
inf = float("inf")
dist = [[inf]*w for i in range(h)]
seen = [[False]*w for i in range(h)]
queue = deque()
start = [ch-1,cw-1,0]
queue.append(start)
def dfs(y,x,wapu):
  if seen:
    return
  dist[y][x] == wapu
  for new_y, new_x in ([y+1, x], [y-1, x], [y, x+1], [y, x-1]):
        if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue           
            elif wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = wapu
                queue.append([new_y, new_x,wapu])
  
while queue:
    y, x,wapu = queue.popleft()
    if dist[y][x]<wapu:
      continue
    dist[y][x] = wapu
    for new_y, new_x in ([y+1, x], [y-1, x], [y, x+1], [y, x-1]):
        if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#' or seen[new_y][new_x]:
                continue           
            elif wapu < dist[new_y][new_x]:
                dfs(new_y,new_x,wapu)
                
    for new_y, new_x in ([y+1, x+1], [y+1, x-1], [y-1, x+1], [y-1, x-1], [y+2, x-1], [y-2, x-1], [y-2, x], [y+2, x], [y+2, x+1], [y-2, x+1], [y-1, x+2], [y, x+2], [y+1, x+2], [y+2, x+2], [y-2, x-2], [y-2, x+2], [y+2, x-2], [y-1, x-2], [y, x-2], [y+1, x-2]):
      if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#' or seen[new_y][new_x]:
                continue       
            else:
                 new_wapu= wapu +1
            if new_wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = new_wapu
                queue.append([new_y, new_x,new_wapu])

ans = dist[dh-1][dw-1]
if ans == inf:
  print(-1)
else:
  print(dist[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
lh, lw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
lh -= 1
lw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]

queue.append([ch, cw])
d = 0

while queue:
    queue2 = queue.copy()
    queue = deque()
    while queue2:
        pos = queue2.popleft()
        flg = [False, False, False, False]
        for dh, dw in walk:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                if dh == 1:
                    flg[0] = True
                elif dh == -1:
                    flg[1] = True
                elif dw == 1:
                    flg[2] = True
                else:
                    flg[3] = True
                continue
            if check[n_h][n_w] <= d:
                continue
            check[n_h][n_w] = d
            queue2.append([n_h, n_w])
            
        magic = []
        if flg[0]:
            magic.append([2, 0])
            if flg[2]:
                magic.append([2, 1])
                magic.append([2, 2])
                magic.append([1, 2])
            if flg[3]:
                magic.append([2, -1])
                magic.append([2, -2])
                magic.append([1, -2])
        if flg[1]:
            magic.append([-2, 0])
            if flg[2]:
                magic.append([-2, 1])
                magic.append([-2, 2])
                magic.append([-1, 2])
            if flg[3]:
                magic.append([-2, -1])
                magic.append([-2, -2])
                magic.append([-1, -2])
        if flg[2]:
            magic.append([0, 2])
        if flg[3]:
            magic.append([0, -2])
            
        for dh, dw in magic:
            n_h = pos[0] + dh
            n_w = pos[1] + dw
            if n_h == -1 or n_w == -1 or n_h == h or n_w == w:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            if check[n_h][n_w] <= d + 1:
                continue
            check[n_h][n_w] = d + 1
            queue.append([n_h, n_w])
    d += 1

if check[lh][lw] == inf:
    print(-1)
else:
    print(check[lh][lw])

Submission status: Wrong Answer

Solution code:
import sys, math

# input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[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.parents) if x < 0]

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


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


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]

"""
groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue
        g = set()
        for s in S[max(0, i-2):i+3]:
            g |= set(s[max(0, j-2):j+3])
        if -1 in g:
            g.remove(-1)
        for k in g:
            can_reach[S[i][j]][k] = True
            can_reach[k][S[i][j]] = True

can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()

reached = [s]
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    new_reached = []
    ans += 1
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[k]:
                new_reached.append(k)
    reached = list(set(new_reached))
print(-1)
"""

Submission status: Wrong Answer

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for X in range(max(0,x-3),min(h,x+3)):
            for Y in range(max(0,y-3),min(w,y+3)):
                if color[X][Y]!="black":
                    D[X][Y]=min(D[X][Y],D[x][y])
                    if color[X][Y]=="white":
                        queue.append([X,Y])
                    color[X][Y]="gray"
        color[x][y]="black"

    return D


def Check():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if D[i][j]==inf:
                color[i][j]="black"

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if D[i][j]==0 and color[i][j]=="white":
                queue.append([i,j])
                while len(queue)>0:
                    x,y=queue.popleft()
                    for a,b in [[1,0],[0,1],[0,-1],[-1,0]]:
                        X,Y=x+a,y+b
                        if 0<=X<h and 0<=Y<w:
                            if color[X][Y]=="white":
                                color[X][Y]="gray"
                                queue.append([X,Y])
                    color[x][y]="black"
                point +=1

    return point


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
ans=True if D[G[0]-1][G[1]-1]!=inf else False
if ans==False:print(-1);exit()
print(Check()-1)

Submission status: Wrong Answer

Solution code:
import queue
import sys
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
readline = sys.stdin.readline
S = [''.join([i for i in readline().split()]) for _ in range(h)]

sx, sy = ch-1, cw-1  # スタートの座標
gx, gy = dh-1, dw-1  # ゴールの座標

INF = 10**5
d = [[0]*w for i in range(h)]  # 各点までの最短距離の配列
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]  # 移動4方向のベクトル

# ワープ5*5の範囲のベクトル
dx_w = []
dy_w = []
for i in range(-2, 3):
    for j in range(-2, 3):
        dx_w.append(i)
        dy_w.append(j)
d_w = [[0]*w for i in range(h)]  # 各点までの最小ワープ回数

# (sx, sy)から(gx, gy)への最短距離を求める
# たどり着けないとINF


def bfs():
    que = queue.Queue()
    # 全ての点をINFで初期化
    for i in range(h):
        for j in range(w):
            d[i][j] = INF
    # スタート地点をキューに入れ、その点の距離を0にする
    que.put([sx, sy])
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que.qsize():
        # キューの先頭を取り出す
        p = que.get()
        # 取り出してきた状態がゴールなら探索を辞める
        if p[0] == gx and p[1] == gy:
            break

        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を(nx, ny)とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定と既に訪れたことがあるかの判定(d[nx][ny] != INF なら訪れたことあり)
            if 0 <= nx and nx < h and 0 <= ny and ny < w and S[nx][ny] != '#' and d[nx][ny] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.put([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


def bfs_w():
    que = queue.Queue()
    # 全ての点をINFで初期化
    for i in range(h):
        for j in range(w):
            d_w[i][j] = INF
    # スタート地点をキューに入れ、その点の距離を0にする
    que.put([sx, sy])
    d_w[sx][sy] = 0

    # キューが空になるまでループ
    while que.qsize():
        # キューの先頭を取り出す
        p = que.get()
        # 取り出してきた状態がゴールなら探索を辞める
        if p[0] == gx and p[1] == gy:
            break

        for i in range(25):
            nx = p[0] + dx_w[i]
            ny = p[1] + dy_w[i]

            if 0 <= nx and nx < h and 0 <= ny and ny < w and S[nx][ny] != '#' and d_w[nx][ny] == INF:
                que.put([nx, ny])
                if d[nx][ny] == INF:
                    d_w[nx][ny] = d_w[p[0]][p[1]] + 1
                else:
                    d_w[nx][ny] = 0

    return d_w[gx][gy]


res = bfs()
if res != INF:
    print(0)
else:
    res = bfs_w()
    if res != INF:
        print(res)
    else:
        print(-1)

# print(d)
# print(d_w)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
sy,sx = map(int,input().split())
sy -= 1
sx -= 1
gy,gx = map(int,input().split())
grid = [0]*H
for i in range(H):
    grid[i] = input()
cost = [[float('inf')]*W for _ in range(H)]
cost[sy][sx] = 0
done = [[0]*W for _ in range(H)]
done[sy][sx] = 1
walk_q = deque()
walk_q.append([sy,sx])
magic_q = deque()
magic_q.append([sy,sx])
def walk(y,x):
    for new_y, new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0 <= new_y < H and 0 <= new_x < W and grid[new_y][new_x] == '.':
            cost[new_y][new_x] = min(cost[new_y][new_x],cost[y][x])
            if not done[new_y][new_x]:
                walk_q.append([new_y,new_x])
                magic_q.append([new_y,new_x])
                done[new_y][new_x] = 1
def magic(y,x):
    for y_add in [i for i in range(-2,3)]:
        for x_add in [i for i in range(-2,3)]:
            if 0 <= y+y_add < H and 0 <= x+x_add < W and grid[y+y_add][x+x_add] == '.':
                cost[y+y_add][x+x_add] = min(cost[y+y_add][x+x_add],cost[y][x]+1)
                if not done[y+y_add][x+x_add]:
                    walk_q.append([y+y_add,x+x_add])
                    done[y+y_add][x+x_add] = 1

while walk_q or magic_q:
    while walk_q:
        y,x = walk_q.popleft()
        walk(y,x)
    while magic_q:
        y,x = magic_q.popleft()
        magic(y,x)
if not done[gy-1][gx-1]:
    print(-1)
else:
    print(cost[gy-1][gx-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
graph = []
visited = []
for _ in range(H):
    graph.append(list(input()))
    visited.append([float('inf')] * W)
visited[sH][sW] = 0
q = deque()
m2_q = deque()
q.append([sW, sH])
m2_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while q or m2_q:
    while q:
        x, y = q.pop()
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny:
                continue
            if visited[ny][nx] > (visited[y][x] + 1) and graph[ny][nx] == '.':
                visited[ny][nx] = visited[y][x]
                q.appendleft([nx, ny])
                m2_q.append([nx, ny])

    while m2_q:
        x, y = m2_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny:
                    continue

                if visited[ny][nx] > visited[y][x] and graph[ny][nx] == '.':
                    q.append([nx, ny])
                    visited[ny][nx] = visited[y][x] + 1

# print(*visited,sep='\n')
if visited[gH][gW] == float('inf'):
    print(-1)
else:
    print(visited[gH][gW])

Submission status: Wrong Answer

Solution code:
import collections
import sys
H, W = map(int, input().split())
C = tuple(int(x) - 1 for x in input().split())
D = tuple(int(x) - 1 for x in input().split())
S = [sys.stdin.readline() + "###" for _ in range(H)]
S.append("#" * (W + 3))
S.append("#" * (W + 3))

ans = 0
todo = collections.deque()
todo.append(C)
done = set()
while todo:
    done.clear()
    while todo:
        p = todo.popleft()
        done.add(p)
        h, w = p
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nh, nw = (h + dh, w + dw)
            if S[nh][nw] == "#":
                continue
            np = (nh, nw)
            if np == D:
                print(ans)
                sys.exit()
            if np in done:
                continue
            todo.append(np)

    ans += 1
    for h, w in done:
        for nh in range(h - 2, h + 2 + 1):
            for nw in range(w - 2, w + 2 + 1):
                if S[nh][nw] == "#":
                    continue
                np = (nh, nw)
                if np in done:
                    continue
                todo.append(np)
print(-1)

Submission status: Wrong Answer

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

S=[["#"]*(W+4),["#"]*(W+4)]
for h in range(H):
	temp=list(input())
	S.append(["#","#"] +temp+["#","#"])
S.append(["#"]*(W+4))
S.append(["#"]*(W+4))

que=[[Ch+1,Cw+1,0]]
que_=[[Ch+1,Cw+1,0]]
while len(que)>0:
	temp=que.pop(0)
	h,w,cnt=temp[0],temp[1],temp[2]
	if S[h+1][w]==".":
		S[h+1][w]=str(cnt)
		que.append([h+1,w,cnt])
		que_.append([h+1,w,cnt])
	if S[h-1][w]==".":
		S[h-1][w]=str(cnt)
		que.append([h-1,w,cnt])
		que_.append([h-1,w,cnt])
	if S[h][w+1]==".":
		S[h][w+1]=str(cnt)
		que.append([h,w+1,cnt])
		que_.append([h,w+1,cnt])
	if S[h][w-1]==".":
		S[h][w-1]=str(cnt)
		que.append([h,w-1,cnt])
		que_.append([h,w-1,cnt])

while len(que_)>0:
	temp=que_.pop(0)
	h,w,cnt=temp[0],temp[1],temp[2]+1
	for h_ in range(-2,3):
		for w_ in range(-2,3):
			if S[h+h_][w+w_]==".":
				S[h+h_][w+w_]=str(cnt)
				que_.append([h+h_,w+w_,cnt])
			if S[h+h_][w+w_].isdecimal():
				if int(S[h+h_][w+w_])>int(cnt):
					S[h+h_][w+w_]=str(cnt)
					que_.append([h+h_,w+w_,cnt])

print("-1" if S[Dh+1][Dw+1]=="." else S[Dh+1][Dw+1])