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:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]
    V = [[-1]*W for i in range(H)]  # 頂点i

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy][sx] = v
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h][next_w] != -1:
                    continue
                if A[next_h][next_w] == '#':
                    continue
                V[next_h][next_w] = v
                que.append((next_h, next_w))

    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" or V[h][w] != -1:
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))

    # for h in range(H):
    #     print(V[h])

    # for i in range(vertex):
    #     print(G[i])

    def bfs(s, g, N):
        que = deque([0])
        par = [-1 for _ in range(N)]
        dist = [-1]*N
        dist[s] = 0
        while que:
            v = que.popleft()
            for i in G[v]:
                if par[v] == i:
                    continue
                que.append(i)
                dist[i] = dist[v] + 1
                par[i] = v
        return dist[g]

    s = V[Ch][Cw]
    g = V[Dh][Dw]
    ans = bfs(s, g, vertex)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = [[s for s in input()]for _ in range(h)]
que = deque([[C[0]-1,C[1]-1]])
que2 = deque([])
dd = [-1,1]
reach = [[False for _ in range(w)]for _ in range(h)]
reach[C[0]-1][C[1]-1]=True
ans = 0
while que:
    u = que.popleft()
    x,y = u
    if y < 0 or x < 0 or y >= w or x >= h:
        continue
    if S[x][y] == '#':
        continue
    else:
        reach[x][y] = True
    for d in dd:
        xx = x+d
        yy = y+d
        if 0 <= xx < h:
            if S[xx][y] == '.':
                if not reach[xx][y]:
                    que.append([xx,y])
                    reach[xx][y] = True
            else:
                for k in dd:
                    que2.append([xx+k,y])
                    que2.append([xx,y+k])
                    que2.append([xx+k,y+k])
                    que2.append([xx+k,y-k])
            
        if 0 <= yy < w:
            if S[x][yy] =='.':
                if not reach[x][yy]:
                    que.append([x,yy])
                    reach[x][yy] = True
            else:
                for k in dd:
                    que2.append([x+k,yy])
                    que2.append([x,yy+k])
                    que2.append([x+k,yy+k])
                    que2.append([x+k,yy-k])
    if reach[D[0]-1][D[1]-1]:
        print(ans)
        exit()    
    if not que:
        que = que2
        que2 = deque([])
        ans += 1
print(-1)

Submission status: Wrong Answer

Solution code:
import collections, itertools
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) + 1 for _ in [H, W, ch, cw, dh, dw]]
H += 3
W += 3
S = ['#' * W] + ['#' * W] + ['##' + s + '##'
                             for s in S] + ['#' * W] + ['#' * W]
Dist = [[None] * W for _ in range(H)]
Q = collections.deque([(0, ch, cw)])
while Q:
    d, ox, oy = Q.popleft()
    stack = [[ox, oy]]
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        Dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx, dy in itertools.product(range(-2, 3), repeat=2):
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None and S[nx][ny] == '.':
                Q += [(d + 1, nx, ny)]
                Dist[nx][ny] = d + 1
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(sl, visited, sy, sx, gy, gx, h, w):
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    qn = deque([[sy,sx]])

    while q:
        # print('---q')
        while q:
            y, x = q.popleft()
            if [y, x] == [gy, gx]:
                return visited[gy][gx]
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y+j, x+k
                if ny >= h or nx >= w or ny < 0 or nx < 0:
                    continue
                if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x]
                    q.append([ny,nx])
                    qn.append([ny,nx])
            # print(q)
            # print(qn)
            # print()
            
        # print('---------qn')
        next_qnl = []
        while qn:
            y, x = qn.popleft()
            q.append([y,x])
            for j in range(-2,3):
                for k in range(-2,3):
                    ny, nx = y+j, x+k
                    if ny >= h or nx >= w or ny < 0 or nx < 0: continue
                    if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                        visited[ny][nx] = visited[y][x] + 1
                        # qn.append([ny,nx])
                        q.append([ny,nx])
            # print(q)
            # print(qn)
            # print()

    return -1


h, w = map(int, input().split()) 
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
sl = [list(input()) for _ in range(h)]
visited = [ [-1]*w for i in range(h)]
ans = bfs(sl,visited,ch-1,cw-1,dh-1,dw-1,h,w)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from itertools import permutations


H, W = map(int, input().split())
start = tuple(map(lambda x: int(x) - 1, input().split()))
goal = tuple(map(lambda x: int(x) - 1, input().split()))

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

visited = set()

Q = [(0, start)]
while Q:
    c, pos = heappop(Q)
    visited.add(pos)
    if pos == goal:
        print(c)
        exit()
    # A
    for move in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        nx = pos[0] + move[0]
        ny = pos[1] + move[1]
        if 0 <= nx < H and 0 <= ny < W:
            if maze[nx][ny] == '.':
                if (nx, ny) not in visited:
                    heappush(Q, (c, (nx, ny)))
    # B
    for move in permutations(range(-2, 3), 2):
        nx = pos[0] + move[0]
        ny = pos[1] + move[1]
        if 0 <= nx < H and 0 <= ny < W:
            if maze[nx][ny] == '.':
                if (nx, ny) not in visited:
                    heappush(Q, (c + 1, (nx, ny)))
print(-1)

Submission status: Wrong Answer

Solution code:
H,W=[int(i) for i in input().split(" ")]
Ch, Cw=[int(i)+1 for i in input().split(" ")]
Dh,Dw=[int(i)+1 for i in input().split(" ")]
S=[[False for i in range(W+4)],[False for i in range(W+4)]]
for i in range(H):
    S.append([False,False]+[j=='.' for j in input()]+[False,False])
S+=[[False for i in range(W+4)],[False for i in range(W+4)]]

def check(h,w,island_num):
    block[h][w]=island_num
    if S[h-1][w] and block[h-1][w]==-1:
        check(h-1,w,island_num)
    if S[h+1][w] and block[h+1][w]==-1:
        check(h+1,w,island_num)
    if S[h][w-1] and block[h][w-1]==-1:
        check(h,w-1,island_num)
    if S[h][w+1] and block[h][w+1]==-1:
        check(h,w+1,island_num)

block=[]
for i in range(H+4):
    block.append([-1 for j in range(W+4)])

island_num=0

for h in range(H+4):
    for w in range(W+4):
        if S[h][w] and block[h][w]==-1:
            check(h,w,island_num)
            island_num+=1


neighbor={}
for island in range(island_num):
    neighbor[island]=set()


for h in range(H+4):
    for w in range(W+4):
        if block[h][w]!=-1:
            for y in range(h-2,h+3):
                for x in range(w-2, w+3):
                    if block[y][x]!=-1 and block[h][w]!=block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start=block[Ch][Cw]
goal=block[Dh][Dw]
assert start!=-1
assert goal!=-1



dist=[10**10 for i in range(island_num)]
dist[start]=0

nexts=[start]
while len(nexts)!=0:
    for n in nexts:
        _nexts=[]
        for neigh in neighbor[n]:
            if dist[neigh]>dist[n]+1:
                _nexts.append(neigh)
                dist[neigh]=dist[n]+1
        nexts=set(_nexts)

if dist[goal]==10**10:
    print(-1)
else:
    print(dist[goal])

Submission status: Wrong Answer

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    H, W = read_ints()
    Ch, Cw = read_ints()
    Ch -= 1
    Cw -= 1
    Dh, Dw = read_ints()
    Dh -= 1
    Dw -= 1
    table = []
    for _ in range(H):
        table.append(list(input()))
    costs = [
        [math.inf for _ in range(W)] for _ in range(H)
    ]

    def dfs(points, cost):
        Q = list(points)
        discovered = list(points)
        while Q:
            i, j = Q.pop()
            costs[i][j] = cost
            for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= x < H and 0 <= y < W and table[x][y] == '.' and costs[x][y] == math.inf:
                    costs[x][y] = cost
                    Q.append((x, y))
                    discovered.append((x, y))
        reachables = []
        for x, y in discovered:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    new_x, new_y = x+dx, y+dy
                    if 0 <= new_x < H and 0 <= new_y < W and table[new_x][new_y] == '.' and costs[new_x][new_y] == math.inf:
                        reachables.append((new_x, new_y))
        return reachables

    cost = 0
    Q = [(0, 0)]
    while Q:
        Q = dfs(Q, cost)
        cost += 1
    if costs[Dh][Dw] == math.inf:
        return -1
    return costs[Dh][Dw]


if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = list(map(int,input().split()))
g = list(map(int,input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
  tmp = input()
  raw.append(tmp)
  t = []
  for j in range(w):
    if tmp[j] == '.':
      t.append(0)
    else:
      t.append(1)
  seen.append(t)
#print(seen)
now = [s]
ans = 0
def check(ii,jj):
  if 0 <= ii < h and 0 <= jj < w:
    if seen[ii][jj] == 0:
      seen[ii][jj] = 1
      now.append([ii,jj])
seen[s[0]][s[1]] = 1
from collections import deque
now = deque([s])
while now:
  for i in range(10**6):
    try:
      a,b = now[i]
      check(a-1,b)
      check(a+1,b)
      check(a,b-1)
      check(a,b+1)
    except:
      break
  if seen[g[0]][g[1]] == 1:
    print(ans)
    break
  #print(now)
  ans += 1
  last = now
  now = deque()
  for x in last:
    a,b = x
    for di in range(-2,3):
      for dj in range(-2,3):
        check(a+di,a+dj)
  #print(now)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
H,W=[int(i) for i in input().split(" ")]
Ch, Cw=[int(i)+1 for i in input().split(" ")]
Dh,Dw=[int(i)+1 for i in input().split(" ")]
S=[[False for i in range(W+4)],[False for i in range(W+4)]]
for i in range(H):
    S.append([False,False]+[j=='.' for j in input()]+[False,False])
S+=[[False for i in range(W+4)],[False for i in range(W+4)]]

def check(h,w,island_num):
    block[h][w]=island_num
    if S[h-1][w] and block[h-1][w]==-1:
        check(h-1,w,island_num)
    if S[h+1][w] and block[h+1][w]==-1:
        check(h+1,w,island_num)
    if S[h][w-1] and block[h][w-1]==-1:
        check(h,w-1,island_num)
    if S[h][w+1] and block[h][w+1]==-1:
        check(h,w+1,island_num)

block=[]
for i in range(H+4):
    block.append([-1 for j in range(W+4)])

island_num=0

for h in range(H+4):
    for w in range(W+4):
        if S[h][w] and block[h][w]==-1:
            check(h,w,island_num)
            island_num+=1


neighbor={}
for island in range(island_num):
    neighbor[island]=set()


for h in range(H+4):
    for w in range(W+4):
        if block[h][w]!=-1:
            for y in range(h-2,h+3):
                for x in range(w-2, w+3):
                    if block[y][x]!=-1 and block[h][w]!=block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start=block[Ch][Cw]
goal=block[Dh][Dw]
assert start!=-1
assert goal!=-1



dist=[10**10 for i in range(island_num)]
dist[start]=0

nexts=[start]
while len(nexts)!=0:
    for n in nexts:
        _nexts=[]
        for neigh in neighbor[n]:
            if dist[neigh]>dist[n]+1:
                _nexts.append(neigh)
                dist[neigh]=dist[n]+1
        nexts=set(_nexts)

print(dist[goal])

Submission status: Wrong Answer

Solution code:
import queue
h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
s=[input() for _ in range(h)]
q=queue.deque([[sy-1,sx-1]])
q2=[[sy-1,sx-1]]
inf=10**7
dist=[[inf for _ in range(w)] for _ in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
dist[sy-1][sx-1]=0

while q:
    y,x=q.pop()
    for dy,dx in d:
        ny,nx=y+dy,x+dx
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==inf:
            dist[ny][nx]=min(dist[y][x],dist[ny][nx])
            q.append([ny,nx])
            q2.append([ny,nx])
    if not q:
        for y,x in q2:
            for dy in range(-2,3):
                for dx in range(-2,3):
                    ny,nx=y+dy,x+dx
                    if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==inf:
                        dist[ny][nx]=min(dist[y][x]+1,dist[ny][nx])
                        q.append([ny,nx])
        q2=[]
print(dist[gy-1][gx-1] if dist[gy-1][gx-1]!=inf else -1)

Submission status: Wrong Answer

Solution code:

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
X = [input() for _ in range(H)]

inf = 10 ** 9
dist = [[inf] * W for _ in range(H)]
dist[C_h - 1][C_w - 1] = 0
q1 = deque()
q1.append((C_h - 1, C_w - 1))
q2 = deque()
q2.append((C_h - 1, C_w - 1))


def bfs_1():
    while q1:
        u, v = q1.popleft()
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if (0 <= u + i < H and 0 <= v + j < W
                    and X[u + i][v + j] == "."
                    and dist[u + i][v + j] > dist[u][v]):
                dist[u + i][v + j] = dist[u][v]
                q1.append((u + i, v + j))
                q2.append((u + i, v + j))


def bfs_2():
    while q2:
        u, v = q2.popleft()
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (0 <= u + i < H and 0 <= v + j < W
                        and X[u + i][v + j] == "."
                        and dist[u + i][v + j] > dist[u][v] + 1):
                    dist[u + i][v + j] = dist[u][v] + 1
                    q1.append((u + i, v + j))


while q1 or q2:
    bfs_1()
    bfs_2()

if dist[D_h - 1][D_w - 1] < inf:
    print(dist[D_h - 1][D_w - 1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int,input().split())
c=tuple(map(int,input().split()))
c=(c[0]-1,c[1]-1)
d=tuple(map(int,input().split()))
d=(d[0]-1,d[1]-1)
S=[]
for i in range(H):
  S.append(input())
  
INF=10**8

###ここから###

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  total = [[INF for i in range(W)] for j in range(H)]
  todo = deque([])
  now = s
  seen[now[0]][now[1]],total[now[0]][now[1]] = 1,0
  todo.append(now)
  while 1:
    if len(todo)==0:break
    now = todo.popleft()
    wall = [0,0]
    for d in [(1,0),(-1,0),(0,1),(0,-1)]:
      new = (now[0]+d[0], now[1]+d[1])
      if new[0]<0 or new[0]>=H:continue
      if new[1]<0 or new[1]>=W:continue
      if seen[new[0]][new[1]]==1:continue
      if S[new[0]][new[1]]=='#':
        wall[0] += abs(new[0])
        wall[1] += abs(new[1])
        continue
      seen[new[0]][new[1]] = 1
      todo.append(new)
      total[new[0]][new[1]] = total[now[0]][now[1]]
    if sum(wall)==0:continue
    for dx in range(-2,3):
      if wall[0]==0:continue
      for dy in range(-2,3):
        if wall[1]==0:continue
        new = (now[0]+dx,now[1]+dy)
        if new[0]<0 or new[0]>=H:continue
        if new[1]<0 or new[1]>=W:continue
        if seen[new[0]][new[1]]==1:continue
        if S[new[0]][new[1]]=='#':continue
        seen[new[0]][new[1]] = 1
        todo.append(new)
        total[new[0]][new[1]] = total[now[0]][now[1]]+1
        
  return total

total = bfs(c)
ans = total[d[0]][d[1]]
if ans == 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=[""]
for i in range(h):
    S.append("#"+input())
        
V=[[999999 for i in range(w+1)] for q in range(h+1)]

V[ch][cw]=0
que=[(ch,cw)]
head=0

    
def ex(nx,ny):
    return [(nx+1,ny),(nx-1,ny),(nx,ny+1),(nx,ny-1)]

def ex3(nx,ny):
    return [(nx+1,ny+1),(nx-1,ny-1),(nx-1,ny+1),(nx+1,ny-1)]

def ex2(nx,ny):
    return [(nx+1,ny),(nx-1,ny),(nx,ny+1),(nx,ny-1),(nx+1,ny+1),(nx-1,ny-1),(nx-1,ny+1),(nx+1,ny-1)]

def calc(nx,ny):
    if S[nx][ny]==".":
        return 0
    else:
        return 1

while len(que)>head:
    now=que[head]
    head+=1
    if S[now[0]][now[1]]==".":
        for nex in ex(now[0],now[1]):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)
                if V[now[0]][now[1]]+flg<V[nx][ny]:
                    V[nx][ny]= V[now[0]][now[1]]+flg
                    que.append((nx,ny))
        for nex in ex3(now[0],now[1]):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)
                if flg==0:
                    continue
                if V[now[0]][now[1]]+flg<V[nx][ny]:
                    V[nx][ny]= V[now[0]][now[1]]+flg
                    que.append((nx,ny))
    else:
        for nex in ex2(now[0],now[1]):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)*1000000
                if V[now[0]][now[1]]+flg<V[nx][ny]:
                    V[nx][ny]= V[now[0]][now[1]]+flg
                    que.append((nx,ny))

if V[dh][dw]==999999:
    print(-1)
else:
    print(V[dh][dw])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = list(map(int,input().split()))
g = list(map(int,input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
  tmp = input()
  raw.append(tmp)
  t = []
  for j in range(w):
    if tmp[j] == '.':
      t.append(0)
    else:
      t.append(1)
  seen.append(t)
#print(seen)
now = [s]
ans = 0
def check(ii,jj):
  if 0 <= ii < h and 0 <= jj < w:
    if seen[ii][jj] == 0:
      seen[ii][jj] = 1
      now.append([ii,jj])
seen[s[0]][s[1]] = 1
while now:
  for x in now:
    a,b = x
    check(a-1,b)
    check(a+1,b)
    check(a,b-1)
    check(a,b+1)
  if seen[g[0]][g[1]] == 1:
    print(ans)
    break
  #print(now)
  ans += 1
  last = now
  now = []
  for x in last:
    a,b = x
    for di in range(-2,3):
      for dj in range(-2,3):
        check(a+di,a+dj)
  #print(now)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
def dfs(x,y,visited,grid,dp,r,c,n):
    stack = [(x,y)]
    k = 0
    while k < len(stack):
        x,y = stack[k]
        if (x,y) not in visited:
            dp[x][y] = n
            visited.add((x,y))
            if x+1 < r and grid[x+1][y] == '.':
                stack.append((x+1,y))

            if y+1 < c and grid[x][y+1] == '.':
                stack.append((x,y+1))

            if x-1 >= 0 and grid[x-1][y] == '.':
                stack.append((x-1,y))

            if y-1 >= 0 and grid[x][y-1] == '.':
                stack.append((x,y-1))

        k += 1

def shortestPath(x,y,edges):
    stack = [(x,0)]
    visited = set()
    k = 0
    while k < len(stack):
        x,d = stack[k]
        if x not in visited:
            visited.add(x)
            if x == y:
                print(d)
                return
            
            for kid in edges[x]:
                stack.append((kid,d+1))

        k += 1

    print(-1)

def main():
    r,c = map(int,input().split())
    x1,y1 = map(int,input().split())
    x2,y2 = map(int,input().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    dp = [[0 for j in range(c)] for i in range(r)]
    grid = []
    for i in range(r):
        grid.append(input())

    visited = set()
    n = 1
    for i in range(r):
        for j in range(c):
            if (i,j) not in visited and grid[i][j] == '.':
                dfs(i,j,visited,grid,dp,r,c,n)
                n += 1

    edges = {}
    for i in range(1,n):
        edges[i] = set()

    for i in range(r):
        for j in range(c):
            if grid[i][j] == '.':
                x = dp[i][j]
                for k in range(max(0,i-2),min(r,i+3)):
                    for l in range(max(0,j-2),min(j,j+3)):
                        y = dp[k][l]
                        if x != y and y != 0:
                            edges[x].add(y)
                            edges[y].add(x)

    x = dp[x1][y1]
    y = dp[x2][y2]
    shortestPath(x,y,edges)

main()

Submission status: Wrong Answer

Solution code:
import queue
h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
s=[input() for _ in range(h)]
q=queue.deque([[sy-1,sx-1]])
q2=[[sy-1,sx-1]]
dist=[[-1 for _ in range(w)] for _ in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
dist[sy-1][sx-1]=0
while q:
    y,x=q.pop()
    for dy,dx in d:
        ny,nx=y+dy,x+dx
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]
            q.append([ny,nx])
            q2.append([ny,nx])
    if not q:
        for y,x in q2:
            for dy in range(-2,3):
                for dx in range(-2,3):
                    ny,nx=y+dy,x+dx
                    if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==-1:
                        dist[ny][nx]=dist[y][x]+1
                        q.append([ny,nx])
        q2=[]
print(dist[gy-1][gx-1])

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
sy,sx=map(int,input().split())
sy-=1
sx-=1
gy,gx=map(int,input().split())
gy-=1
gx-=1

maze=[list(input()) for _ in range(h)]

from collections import deque
stack = deque([(sy,sx)])
maze[sy][sx]=0

while len(stack)>0:
    (y,x)=stack.pop()
    if (y,x)==(gy,gx):
        print(maze[y][x])
        exit()
    for (my,mx) in ((1,0),(0,1),(-1,0),(0,-1)):
        ny=my+y
        nx=mx+x
        if 0<=ny<h and 0<=nx<w:
            if maze[ny][nx]=="." or (maze[ny][nx]!="#" and maze[ny][nx]>maze[y][x]):
                stack.appendleft((ny,nx))
                maze[ny][nx]=maze[y][x]
            #ワープ
            elif maze[ny][nx]=="#":
                ny+=my
                nx+=mx
                if 0<=ny<h and 0<=nx<w:
                    if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+1):
                        stack.append((ny,nx))
                        maze[ny][nx]=maze[y][x]+1
    #斜めのワープを入れる
    for (my,mx) in ((1,1),(-1,-1),(-1,1),(1,-1)):
        for k in (1,2):
            ny=my*k+y
            nx=mx*k+x
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+k):
                    stack.append((ny,nx))
                    maze[ny][nx]=maze[y][x]+1




print(-1)

Submission status: Wrong Answer

Solution code:

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
X = [input() for _ in range(H)]

inf = 10 ** 9
dist = [[inf] * W for _ in range(H)]
dist[C_h - 1][C_w - 1] = 0
q = deque()
q.append((C_h - 1, C_w - 1))


def bfs_1():
    while q:
        u, v = q.popleft()
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if (0 <= u + i < H and 0 <= v + j < W
                    and X[u + i][v + j] == "."
                    and dist[u + i][v + j] > dist[u][v]):
                dist[u + i][v + j] = dist[u][v]
                q.append((u + i, v + j))


def bfs_2():
    for u in range(H):
        for v in range(W):
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if (0 <= u + i < H and 0 <= v + j < W
                            and X[u + i][v + j] == "."
                            and dist[u + i][v + j] > dist[u][v] + 1):
                        dist[u + i][v + j] = dist[u][v] + 1
                        q.append((u + i, v + j))


while q:
    bfs_2()
    bfs_1()

if dist[D_h - 1][D_w - 1] < inf:
    print(dist[D_h - 1][D_w - 1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
s = [input() for i in range(h)]

reach = [[False]*w for i in range(h)]
reach[ch][cw] = True
from collections import deque
q = deque([[ch,cw,0]])

ans = -1
while q:
    cx,cy,cnt = q.popleft()

    if cx==dh and cy==dw:
        ans = cnt
        break

    f = False
    for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
        if not(0<=cx+dx<h and 0<=cy+dy<w):continue
        if s[cx+dx][cy+dy]=='.':
            if not reach[cx+dx][cy+dy]:
                reach[cx+dx][cy+dy] = True
                q.append([cx+dx,cy+dy,cnt])
                f = True
    if f:continue
    for dx in range(-2,3):
        for dy in range(-2,3):
            if not(0<=cx+dx<h and 0<=cy+dy<w):continue
            if not reach[cx+dx][cy+dy] and s[cx+dx][cy+dy]=='.':
                reach[cx+dx][cy+dy] = True
                q.append([cx+dx,cy+dy,cnt+1])
                f = True

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from heapq import heappop,heappush

h,w = map(int,readline().split())
ch,cw = map(int,readline().split())
dh,dw = map(int,readline().split())
s = read().split()

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

wall = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] == '#'):
            wall[i][j] = 1

cost = [[-1] * w for _ in range(h)]
hq = [(ch,cw,0)]

while(hq):
    xi,yi,ci = heappop(hq)
    if(cost[xi][yi] != -1):
        continue
    cost[xi][yi] = ci

    for dx in range(-2,3):
        for dy in range(-2,3):
            xj,yj = xi+dx,yi+dy
            # print(xi,yi,xj,yj)
            if(xj<0)|(xj>=h)|(yj<0)|(yj>=w):
                continue
            if(cost[xj][yj]!=-1):
                continue
            if(xi==xj)&(yi==yj):
                continue
            if(wall[xj][yj]==1):
                continue
            if(abs(xi-xj)+abs(yi-yj)==1):
                heappush(hq,(xj,yj,ci))
            else:
                heappush(hq,(xj,yj,ci+1))

print(cost[dh][dw])

Submission status: Wrong Answer

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

H, W = map(int, input().split())
Cy, Cx = map(int, input().split())
Dy, Dx = map(int, input().split())
Board = [input().rstrip() for _ in range(H)]







Cy -= 1
Cx -= 1
Dy -= 1
Dx -= 1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
vst = [[-1] * W for _ in range(H)]

def BFS(y, x, C):
    vst[y][x] = C
    q = [(x, y)]
    for x1, y1 in q:
        for i in range(4):
            x2 = x1 + dx[i]
            y2 = y1 + dy[i]
            if 0 <= x2 < W and 0 <= y2 < H and vst[y2][x2] < 0 and Board[y2][x2] == '.':
                vst[y2][x2] = C
                q.append((x2, y2))

count = 0
for i in range(H):
    for j in range(W):
        if vst[i][j] < 0 and Board[i][j] == '.':
            BFS(i, j, count)
            count += 1






vst2 = [[-1] * W for _ in range(H)]
q = [(Cx, Cy, 0)]
vst2[Cy][Cx] = 0

for x1, y1, cnt in q:

    for i in range(4):
        x2 = x1 + dx[i]
        y2 = y1 + dy[i]
        if 0 <= x2 < W and 0 <= y2 < H and vst2[y2][x2] < 0 and Board[y2][x2] == '.':
            vst2[y2][x2] = cnt
            q.append((x2, y2, cnt))
    for i in [-2, -1, 0, 1, 2]:
        for j in [-2, -1, 0, 1, 2]:
            x2 = x1 + i
            y2 = y1 + j
            if 0 <= x2 < W and 0 <= y2 < H and vst2[y2][x2] < 0 and Board[y2][x2] == '.':
                if vst[y2][x2] != vst[y1][x1]:
                    vst2[y2][x2] = cnt + 1
                    q.append((x2, y2, cnt + 1))


print(vst2[Dy][Dx])