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
  import sys
  input = sys.stdin.buffer.readline

  h, w = map(int, input().split())
  ch, cw = map(int, input().split())
  dh, dw = 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
  dh -= 1
  dw -= 1
  check[ch][cw] = 0
  walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
  magic = [[1, 1], [-1, 1], [1, -1], [-1, -1], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
      ,[1, -2], [1, 2], [0, -2], [0, 2], [-1, -2], [-1, 2], [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2]]

  queue.append([ch, cw])
  queue.append(0)
  while queue:
      pos = queue.popleft()
      dd = queue.popleft()
      for dy, dx in walk:
          n_h = pos[0] + dy
          n_w = pos[1] + dx
          if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
              continue
          if check[n_h][n_w] <= dd:
              continue
          if tizu[n_h][n_w] == "#":
              continue
          check[n_h][n_w] = dd
          queue.append([n_h, n_w])
          queue.append(dd)

      for dy, dx in magic:
          n_h = pos[0] + dy
          n_w = pos[1] + dx
          if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
              continue
          if check[n_h][n_w] <= dd:
              continue
          if tizu[n_h][n_w] == "#":
              continue
          check[n_h][n_w] = dd + 1
          queue.append([n_h, n_w])
          queue.append(dd + 1)

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

Submission status: Wrong Answer

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


h,w=mdata()
ch,cw=mdata()
dh,dw=mdata()
ch-=1
dh-=1
cw-=1
dw-=1
S=[data() for i in range(h)]
if S[ch][cw]=='#' or S[dh][dw]=='#':
    out(-1)
    exit()
stack=[(dh,dw)]
steps=[(0,1),(1,0),(-1,0),(0,-1)]
moves={(dh,dw)}
while stack:
    a,b=stack.pop()
    for i,j in steps:
        if 0<=a+i<h and 0<=b+j<w and S[a+i][b+j]=='.' and (a+i,b+j) not in moves:
            moves.add((a+i,b+j))
            stack.append((a+i,b+j))
if (ch,cw) in moves:
    out(0)
    exit()
moves1={(ch,cw)}
stack=[(ch,cw)]
cnt=0
while stack:
    stack1=[]
    cnt+=1
    while stack:
        a, b = stack.pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if 0 <= a + i < h and 0 <= b + j < w and S[a + i][b + j] == '.' and (a + i, b + j) not in moves1:
                    moves1.add((a + i, b + j))
                    stack1.append((a + i, b + j))
                    if (a + i, b + j) in moves:
                        out(cnt)
                        exit()
    stack=stack1
out(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    G = [[] for _ in range(H)] #G[h][w]
    for i in range(H):
        S=list(input())
        G[i] = S
    

    stack = deque([(Ch,Cw,0)])
    seen = set()
    ans = INF
    while stack:
        h,w,magic = stack.popleft()

        # print(h,w,magic)
        if (h,w) == (Dh,Dw):
            ans = min(magic,ans)
            continue

        if (h,w) in seen: continue

        seen.add((h,w))
        found_wall = False
        for dh,dw in [(-1,0),(1,0),(0,1),(0,-1)]:
            new_h,new_w = h+dh,w+dw
            if not (0<=new_h<H and 0<=new_w<W): continue
            if G[new_h][new_w] == "#": 
                found_wall = True
                continue
                
            stack.append((new_h,new_w,magic))

        if found_wall:
            for dh in range(-2,3):
                for dw in range(-2,3):
                    new_h,new_w = h+dh,w+dw
                    if new_h == 0 and new_w == 0: continue
                    if not (0<=new_h<H and 0<=new_w<W): continue
                    if G[new_h][new_w] == "#":  continue
                    
                    stack.append((new_h,new_w,magic+1))

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






if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

H,W=map(int,readline().split())

sy,sx = map(int,readline().split())
gy,gx = map(int,readline().split())

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

G = [None] * H
for i in range(H):
  G[i] = readline().rstrip()

# 幅優先探索
INF = 10 ** 10
costs = [[INF] * W for i in range(H)]

from collections import deque
q = deque([])
# y,x,魔法の回数,親y,親x
q.append((sy,sx,0,-1,-1))

cases = ((0,1),(0,-1),(1,0),(-1,0))
while q:
  y,x,co,py,px = q.popleft()
  if costs[y][x] <= co:
    continue
  if G[y][x] == "#":
    continue
  costs[y][x] = co
  nex = 0
  for c in cases:
    if y + c[0] == py and x + c[1] == px:
      continue
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      if G[y + c[0]][x + c[1]] == "#":
        continue
      if costs[y + c[0]][x + c[1]] <= co:
        continue
      q.append((y + c[0], x + c[1], co, y, x))
      nex += 1
  # 行先がないのでワープ検討
  if nex == 0:
    for i in range(-2,3):
      for j in range(-2,3):
        if 0 <= y + i < H and 0 <= x + j < W:
          if G[y + i][x + j] == "#":
            continue
          if costs[y + i][x + j] <= co + 1:
            continue
          q.append((y + i, x + j, co + 1, y, x))

if costs[gy][gx] == INF:
  print(-1)
else:
  print(costs[gy][gx])

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
import heapq as hq
H,W = map(int,input().split())
Sh,Sw = map(int,input().split())
Sh -= 1
Sw -= 1
Gh,Gw = map(int,input().split())
Gh -= 1
Gw -= 1
S = [list(input()) for _ in range(H)]
D = [[-1 for _ in range(W)] for _ in range(H)]
D[Sh][Sw] = -1

search = [(0, Sh, Sw)]

walk = [(1,0),(-1,0),(0,1),(1,0)]
warp = [(x,y) for x in range(-2,3) for y in range(-2,3) if abs(x) + abs(y) > 1]

def validPosition(h,w):
	return 0 <= h and h < H and 0 <= w and w < W

hq.heapify(search)
while len(search) > 0 and D[Gh][Gw] == -1:
	(d, h, w) = hq.heappop(search)
	if D[h][w] >= 0:
		continue
	D[h][w] = d
	for (x,y) in walk:
		hh,ww = h+x, w+y
		if validPosition(hh, ww) and D[hh][ww] == -1 and S[hh][ww] == ".":
			hq.heappush(search, (d, hh, ww))
	for (x,y) in warp:
		hh,ww = h+x, w+y
		if validPosition(hh, ww) and D[hh][ww] == -1 and S[hh][ww] == ".":
			hq.heappush(search, (d+1, hh, ww))

print(D[Gh][Gw])

Submission status: Wrong Answer

Solution code:
from collections import deque

def f1(x,y,xa,ya):
    if reach[xa][ya] == -1 and c[xa][ya] == ".":
        reach[xa][ya] = reach[x][y]
        r.append([xa,ya])
        q.append([xa,ya])

def f2(x,y,xa,ya):
    if 0 <= xa <= h and 0 <= ya <= w:
    
        if reach[xa][ya] == -1 and c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y] + 1
            q.append([xa,ya])

h,w = map(int,input().split())
cx, cy = map(int,input().split())
dx, dy = map(int,input().split())

c = [0]*(h+2)
for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[-1 for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0

while q:
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        for j in range(-2,3):
            f2(x,y,x+i,y+j)
            
            if x == dx and y == dy:
                sw = 1
                break
    
    

print(reach[dx][dy])

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())
maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]
# print(maze)

q = deque([(sy+1,sx+1)])
temp[sy+1][sx+1] = 0
# print(temp)
opt = [(0,1),(0,-1),(1,0),(-1,0)]
while q:
    y,x = q.popleft()
    # print(y,x)
    for i in opt:
        ty,tx = y+i[0],x+i[1]
        if maze[ty][tx] == "#":
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x]
            q.append((ty,tx))
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i,x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1:
                temp[ty][tx] = temp[y][x]+1
                q.append((ty,tx))

    # print(q)
# print(temp)
print(temp[gy+1][gx+1])

Submission status: Wrong Answer

Solution code:
def main():

    H, W = map(int, input().split())
    h1, w1 = map(int, input().split())
    h2, w2 = map(int, input().split())
    h1 = h1-1
    w1 = w1-1
    h2 = h2-1
    w2 = w2-1
    S = []
    for _ in range(H):
        S.append(input())

    cur = [[h1, w1]]
    visited = set([(h1, w1)])
    vis = set([(h1, w1)])
    count = 0
    mv = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    while cur:
        while cur:
            temp = []
            for h, w in cur:
                for i, j in mv:
                    x, y = h+i, w+j
                    if 0 <= x < H and 0<= y < W and (x, y) not in visited and S[x][y] == '.':
                        visited.add((x, y))
                        vis.add((x, y))
                        temp.append([x, y])
                        if (x, y) == (h2, w2):
                            return count
            cur = temp

        # print(cur)
        cur = []
        count += 1
        for h, w in vis:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    x, y = h+i, w+j
                    if 0 <= x < H and 0<= y < W and (x, y) not in visited and S[x][y] == '.':
                        cur.append([x, y])
                        visited.add((x, y))
                        if (x, y) == (h2, w2):
                            return  count
        # print(cur)
    return -1


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

Submission status: Wrong Answer

Solution code:
def main():
    import collections
    import sys
    input = sys.stdin.readline
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [input() for i in range(H)]

    q = collections.deque()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    G = [[H*W]*W for i in range(H)]
    q.append((Ch, Cw))
    G[Ch][Cw] = 0
    flag = True
    while(q):
        x, y = q.popleft()
        # for i, j in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
        #     if 0 <= i <= H and 0 <= j <= W and S[i][j] != '#' and G[i][j] == -1:
        if x == Dh and y == Dw:
            print(G[x][y])
            flag = False
            break
        for i in range(x-2, x+3):
            if 0 <= i <= H-1:
                for j in range(y-2, y+3):
                    if 0 <= j <= W-1:
                        if S[i][j] != '#':
                            if abs(i-x) + abs(j-y) == 1 and G[i][j] > G[x][y]:
                                q.append((i, j))
                                G[i][j] = G[x][y]
                            elif G[i][j] > G[x][y] + 1:
                                q.append((i, j))
                                G[i][j] = G[x][y] + 1

        # for i in range(H):
        #     print(G[i])
        # print()
    if flag:
        print(-1)


main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1
    S = [input().strip("\n") for _ in range(H)]
    M = [[-1 for w in range(W)] for h in range(H)]
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                M[h][w] = -2
    move = ((-1, 0), (0, -1), (1, 0), (0, 1))
    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            if h == fh and w == fw:
                print(dist)
                return 0
            M[h][w] = dist
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and M[h+dh][w+dw] == -1:
                        if (dh, dw) in move:
                            heappush(q, (dist, h+dh, w+dw))
                        else:
                            heappush(q, (dist + 1, h+dh, w+dw))

    return 0

if __name__ == "__main__":
    solve()

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[xi][yi]==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
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
ch, cw = mapint()
dh, dw = mapint()
maze = [list(input()) for _ in range(H)]

dirc = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
none = set([(-1, -1), (1, 1), (-1, 1), (1, -1)])
from collections import deque
Q = deque([(ch-1, cw-1)])

dist = [[10**18]*W for _ in range(H)]
dist[ch-1][cw-1] = 0
while Q:
    y, x = Q.popleft()
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if (dy, dx) in none:
                continue
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if (dy, dx) in dirc:
                if dist[ny][nx]>dist[y][x]:
                    dist[ny][nx] = dist[y][x]
                    Q.append((ny, nx))
            else:
                if dist[ny][nx]>dist[y][x]+1:
                    dist[ny][nx] = dist[y][x]+1
                    Q.append((ny, nx))
if dist[dh-1][dw-1]>=10**17:
    print(-1)
else:
    print(dist[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
import itertools
from heapq import *
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 = [list(input()) for _ in range(h)]

que = [(ch, cw, 0)]

directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
magic = [
    [
    [2, i],
    [1, i],
    [0, i],
    [-1, i],
    [-2, i],
    ] for i in range(-2, 2 + 1)
]
magic = list(itertools.chain(*magic))
del magic[12]
# print(magic, len(magic))
# print(magic[12])
# print("---")

visited = [[None] * w for _ in range(h)]
while que:
    y, x, cost = heappop(que)

    if visited[y][x] is not None:
        continue
    visited[y][x] = cost
    for d in directions:
        ny, nx = y + d[0], x + d[1]
        if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == ".":
            heappush(que, (ny, nx, cost))
    for d in magic:
        ny, nx = y + d[0], x + d[1]
        if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == ".":
            heappush(que, (ny, nx, cost + 1))

# for v in visited:print(v)
print(visited[dh][dw] if visited[dh][dw] is not None else -1)

Submission status: Wrong Answer

Solution code:
def main():

    H, W = map(int, input().split())
    h1, w1 = map(int, input().split())
    h2, w2 = map(int, input().split())
    h1 = h1-1
    w1 = w1-1
    h2 = h2-1
    w2 = w2-1
    S = []
    for _ in range(H):
        S.append(input())

    cur = [[h1, w1]]
    visited = set([(h1, w1)])
    vis = set([(h1, w1)])
    count = 0
    mv = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    while cur:
        while cur:
            temp = []
            for h, w in cur:
                for i, j in mv:
                    x, y = h+i, w+j
                    if 0 <= x < H and 0<= y < W and (x, y) not in visited and S[x][y] == '.':
                        visited.add((x, y))
                        vis.add((x, y))
                        temp.append([x, y])
                        if (x, y) == (h2, w2):
                            return count
            cur = temp

        # print(cur)
        cur = []
        count += 1
        for h, w in vis:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    x, y = h+i, w+j
                    if 0 <= x < H and 0<= y < W and (x, y) not in visited and S[x][y] == '.':
                        cur.append([x, y])
                        visited.add((x, y))
                        if (x, y) == (h2, w2):
                            return  count
        # print(cur)
    return -1


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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
S = [input() for _ in range(H)]

A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch-1][Cw-1] = 0

def isValid(h,w):
  if h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1:
    return True
  else:
    return False

warp = 0
BFS_now = [(Ch-1, Cw-1)]
BFS_search = [(Ch-1, Cw-1)]
ij = [(-1,0),(0,-1),(0,1),(1,0)]
while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = []
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_now += BFS_search_tmp
    BFS_search = BFS_search_tmp
  BFS_now_tmp = []
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp
  warp += 1

print(A[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
b = read().split()

sh -= 1; sw -= 1; gh -= 1; gw -= 1

#print(b)

from collections import deque

def nbd(nh,nw,cost,dv):
    if 0 <= nh < h and 0 <= nw < w and b[nh][nw]==".":
        dv += cost
        if dv < res[nh][nw]:
            res[nh][nw] = dv
            if cost: q.append((dv,nh,nw))
            else: q.appendleft((dv,nh,nw))
    return 


INF = 1<<30
res = [[INF]*w for _ in range(h)] #startからの最短距離
res[sh][sw] = 0
q = deque([(0,sh,sw)]) #(そこまでの距離、点)
while q:
    dv,vh,vw = q.popleft()
    if res[vh][vw] < dv: continue
    nbd(vh-1,vw,0,dv)
    nbd(vh,vw-1,0,dv)
    nbd(vh+1,vw,0,dv)
    nbd(vh,vw+1,0,dv)
    
    for i in range(-2,3):
        nbd(vh-2,vw+i,1,dv)
        nbd(vh+2,vw+i,1,dv)

    for i in range(-1,2):
        nbd(vh+i,vw-2,1,dv)
        nbd(vh+i,vw+2,1,dv)
    
    #print(res)
        
ans = res[gh][gw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(2_000_000)

def solve(H, W, CH, DH, CW, DW, S):
    visited = [[None] * W for _ in range(H)]
    def dfs(h, w, cost):
        if visited[h][w] is not None:
            return
        if S[h][w] == "#":
            return
        visited[h][w] = cost
        for dh, dw in zip((0, 0, 1, -1), (1, -1, 0, 0)):
            nh, nw = h + dh, w + dw
            if not (0 <= nh < H and 0 <= nw < W):
                continue
            dfs(nh, nw, cost)
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh, nw = h + dh, w + dw
                if not (0 <= nh < H and 0 <= nw < W):
                    continue
                dfs(nh, nw, cost+1)
    dfs(CH-1, CW-1, 0)
    cost = visited[DH-1][DW-1]
    return cost if cost is not None else -1

    
# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    S = [input() for _ in range(H)]
    print(solve(H, W, CH, DH, CW, DW, S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

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])
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
  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)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    import collections
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [input() for i in range(H)]

    q = collections.deque()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    G = [[H*W]*W for i in range(H)]

    q.append((Ch, Cw))
    G[Ch][Cw] = 0
    while(q):
        x, y = q.popleft()
        # for i, j in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
        #     if 0 <= i <= H and 0 <= j <= W and S[i][j] != '#' and G[i][j] == -1:
        if x == Dh and y == Dw:
            print(G[x][y])
            break
        for i in range(max(0, x-2), min(H-1, x+2)+1):
            for j in range(max(0, y-2), min(W-1, y+2)+1):
                if S[i][j] != '#':
                    if abs(i-x) + abs(j-y) == 1 and G[i][j] > G[x][y]:
                        q.append((i, j))
                        G[i][j] = G[x][y]
                    elif G[i][j] > G[x][y] + 1:
                        q.append((i, j))
                        G[i][j] = G[x][y] + 1

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
b = read().split()

sh -= 1; sw -= 1; gh -= 1; gw -= 1

#print(b)

from collections import deque

def nbd(nh,nw,cost,dv):
    if 0 <= nh < h and 0 <= nw < w and b[nh][nw]==".":
        dv += cost
        if dv < res[nh][nw]:
            res[nh][nw] = dv
            if cost: q.append((dv,nh,nw))
            else: q.appendleft((dv,nh,nw))
    return 


INF = 1<<30
res = [[INF]*w for _ in range(h)] #startからの最短距離
res[sh][sw] = 0
q = deque([(0,sh,sw)]) #(そこまでの距離、点)
while q:
    dv,vh,vw = q.popleft()
    if res[vh][vw] < dv: continue
    nbd(vh-1,vw,0,dv)
    nbd(vh,vw-1,0,dv)
    nbd(vh+1,vw,0,dv)
    nbd(vh,vw+1,0,dv)
    
    for i in range(-2,3):
        nbd(vh-2,vw+i,1,dv)
        nbd(vh+2,vw+i,1,dv)

    for i in range(-1,2):
        nbd(vh+i,vw+2,1,dv)
        nbd(vh+i,vw+2,1,dv)
    
    #print(res)
        
ans = res[gh][gw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
s = [input() for _ in range(h)]

sh-=1; sw-=1; gh-=1; gw-=1;

INF = 10**7
dist = [[INF]*w for _ in range(h)]
dist[sh][gw] = 0
q = [(0,gh,gw)]

while q:
    
    d,vsh,vsw = heapq.heappop(q)
    
    for dh in range(-2,3):
        for dw in range(-2,3):
            newh = vsh+dh
            neww = vsw+dw
            if newh<0 or h<=newh or neww<0 or w<=neww: continue
            if dh == 0 and dw==0: continue
            if s[newh][neww] == "#": continue
                
            if abs(dh)+abs(dw)==1:
                if dist[newh][neww] > d:
                    dist[newh][neww] = d
                    heapq.heappush(q,(d,newh,neww))
            else:
                if dist[newh][neww] > d+1:
                    dist[newh][neww] = d+1
                    heapq.heappush(q,(d+1,newh,neww))
                    
if dist[gh][gw] == INF: print(-1)
else: print(dist[gh][gw])

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

        while qn:
            y, x = qn.popleft()
            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])
    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:
import sys
from collections import deque
input = sys.stdin.readline


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    
    s = [input().replace("\n", "") for _ in range(h)]
    
    ans = [[-1]*w for _ in range(h)]
    ans[ch-1][cw-1] = 0
    not_yet = deque([(ch-1, cw-1)])
    one_time = deque([])
    while not_yet:
        x, y = not_yet.popleft()
        one_time.append((x, y))
        if x > 0 and ans[x-1][y] == -1 and s[x-1][y] == ".":
            not_yet.append((x-1, y))
            ans[x-1][y] = ans[x][y]
        if x < h-1 and ans[x+1][y] == -1 and s[x+1][y] == ".":
            not_yet.append((x+1, y))
            ans[x+1][y] = ans[x][y]
        if y > 0 and ans[x][y-1] == -1 and s[x][y-1] == ".":
            not_yet.append((x, y-1))
            ans[x][y-1] = ans[x][y]
        if y < w-1 and ans[x][y+1] == -1 and s[x][y+1] == ".":
            not_yet.append((x, y+1))
            ans[x][y+1] = ans[x][y]
        if not not_yet:
            while one_time:
                x2, y2 = one_time.popleft()
                for i in range(max(0, x2-2), min(h, x2+3)):
                    for j in range(max(0, y-2), min(w, y+3)):
                        if ans[i][j] == -1 and s[i][j] == ".":
                            ans[i][j] = ans[x][y]+1
                            not_yet.append((i, j))

    print(ans[dh-1][dw-1])
            
            
            
        
    
    
    
    
if __name__ == "__main__":
    main()