Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Wrong Answer

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

res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0

que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0

while (que or que_warp):
    for i in range(len(que)):
        que_warp.append(que[i])
    while (que):
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    if not (nx,ny) in que_warp:
                        que_warp.append((nx,ny))
                    if (nx == Dh) and (ny == Dw):
                        print(res_S[Dh - 1][Dw - 1])
                        exit()
        que.pop(0)

    count += 1

    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
                    if (nx == Dh) and (ny == Dw):
                        print(res_S[Dh - 1][Dw - 1])
                        exit()
        que_warp.pop(0)

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

Submission status: Wrong Answer

Solution code:
import heapq
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=[]
heapq.heappush(p,(0,c1-1,c2-1))
while len(p):
    a,b,c=heapq.heappop(p)
    for x,y in xy:
        x+=b
        y+=c
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a:
                d[x][y]=a
                heapq.heappush(p,(a,x,y))
    for x,y in wp:
        x+=b
        y+=c
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a+1:
                d[x][y]=a+1
                heapq.heappush(p,(a+1,x,y))
    if a>2000:
        print(-1)
#    print(p)
#    if d[d1-1][d2-1]==a:
#        print(a)
#        exit()
#    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:
h, w = map(int, input().split(" "))
sr, sc = map(int, input().split(" "))
er, ec = map(int, input().split(" "))

board=[['' for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        board[i][j]= s[j]
rs,cs=[],[]
rs.append(sr-1)
cs.append(sc-1)
magic=[[h*w for i in range(w)] for j in range(h)]
dr=[-1,1,0,0]
dc=[0,0,-1,1]
magic[sr-1][sc-1]=0
while len(rs)>0:
    r,c=rs.pop(0),cs.pop(0)
    for i in range(4):
        nr,nc= r+dr[i],c+dc[i]
        if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
            continue
        if magic[nr][nc]>magic[r][c]:
            magic[nr][nc]= magic[r][c]
            rs.insert(0,nr)
            cs.insert(0,nc)
    #wizard
    for nr in range(r-2,r+3):
        for nc in range(c-2,c+3):
            if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
                continue
            if magic[nr][nc] > magic[r][c]+1:
                    magic[nr][nc] = magic[r][c]+1
                    rs.append(nr)
                    cs.append(nc)
print(magic[er-1][ec-1] if magic[er-1][ec-1]<1e6 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = list(map(int, input().strip().split()))
ch, cw = list(map(int, input().strip().split()))
dh, dw = list(map(int, input().strip().split()))
ch -= 1
cw -= 1
dh -= 1
dw -= 1

s = []
for i in range(h):
    row = input().strip()
    s.append(row)

dirs = ((0, 0), (1, 0), (-1, 0), (0, 1), (0, -1))
sx , sy = cw, ch

def walk(sx, sy):
    cnt = 0
    gfp = set()
    fp = set()
    wq = []
    q = deque()
    q.appendleft((cw, ch))
    while q:
        bx, by = q.pop()
        for dx, dy in dirs:
            x, y = (bx + dx, by + dy)
            if (x,y) in fp:
                continue
            if x < 0 or w <= x or y < 0 or h <= y:
                continue
            if s[y][x] == '#':
                continue
            if (x, y) == (dw, dh):
                return cnt
            fp.add((x, y))
            q.appendleft((x, y))

        if q:
            continue
        # 行けるところがなくなったらワープ先を探す
        gfp |= fp
        if fp and not wq:
            for bx, by in fp:
                for dx in range(-2, 3):
                    for dy in range(-2, 3):
                        x, y = (bx + dx, by + dy)
                        if 0 <= x < w and 0 <= y < h and s[y][x] == '.' and (x, y) not in gfp:
                            wq.append(((x, y), cnt+1))
        if wq:
            t, cnt = wq.pop()
            q.appendleft(t)

        fp = set()
    return -1

print(walk(cw, ch))

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
ch, cw = map(lambda x: int(x)-1, input().split())
dh, dw = map(lambda x: int(x)-1, input().split())
S = [list(input()) for _ in range(H)]
dist = [[float("inf")] * W for _ in range(H)]

warp = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        warp.append((i-2, j-2))
warp = set(warp)
walk = {(0, 1), (1, 0), (-1, 0), (0, -1)}
warp = warp - walk

q = deque()
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    for hh, ww in walk:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w]:
            dist[h+hh][w+ww] = dist[h][w]
            q.appendleft((h+hh, w+ww)) # 徒歩は前に追加
    for hh, ww in warp:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w] + 1:
            dist[h+hh][w+ww] = dist[h][w] + 1
            q.append((h+hh, w+ww)) # ワープは後ろに追加

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

Submission status: Wrong Answer

Solution code:
import heapq
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=[]
heapq.heappush(p,(0,c1-1,c2-1))
while len(p):
    a,b,c=heapq.heappop(p)
    for x,y in xy:
        x+=b
        y+=c
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a:
                d[x][y]=a
                heapq.heappush(p,(a,x,y))
    for x,y in wp:
        x+=b
        y+=c
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a+1:
                d[x][y]=a+1
                heapq.heappush(p,(a+1,x,y))
    if a>1500:
        print(-1)
#    print(p)
#    if d[d1-1][d2-1]==a:
#        print(a)
#        exit()
#    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:
from collections import deque

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
M = [[0]*(W+2) for _ in range(H+2)]
S = []
for i in range(H):
    S.append(list(input()))

for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i-1][j-1] == ".":
            M[i][j] = 1
H += 2
W += 2

searched_map = [[10**9]*W for _ in range(H)]
searched_map[Ch][Cw] = 0

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

q = deque()
q.append([Ch,Cw,0])
biM[Ch][Cw] = 1
while q:
    while 1 and q:
        xy = q.pop()
        y = xy[0]
        x = xy[1]
        w = xy[2]
        if biM[y][x] == 0:
            break
    biM[y][x] = 1
    if M[y][x-1] == 1 and searched_map[y][x-1] > w:
        q.appendleft([y,x-1,w])
        searched_map[y][x-1] = w
    if M[y][x+1] == 1 and searched_map[y][x+1] > w:
        q.appendleft([y,x+1,w])
        searched_map[y][x+1] = w
    if M[y-1][x] == 1 and searched_map[y-1][x] > w:
        q.appendleft([y-1,x,w])
        searched_map[y-1][x] = w
    if M[y+1][x] == 1 and searched_map[y+1][x] > w:
        q.appendleft([y+1,x,w])
        searched_map[y+1][x] = w
    
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=y+i<=H-1 and 0<=x+j<=W-1:
                if searched_map[y+i][x+j] > w+1 and M[y+i][x+j] == 1:
                    searched_map[y+i][x+j] = w+1
                    q.append([y+i,x+j,w+1])

if searched_map[Dh][Dw] < 10**9:
    print(searched_map[Dh][Dw])
else:
    print(-1)

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=[list(input()) for _ in range(H)]

dp=[[100000 for _ in range(W)] for _ in range(H)]

def walk_bfs(y,x,v):
  # 歩ける範囲で歩き潰す
  dp[y][x] = v
  path = deque()
  path.append([y,x])
  ret = deque()
  while path:
    y,x = path.popleft()
    ret.append([y,x])
    for i,j in ((0,1),(0,-1),(1,0),(-1,0)):
      if not (0 <= y+i < H and 0 <= x+j < W):
        continue
      if s[y+i][x+j] == '#':
        dp[y+i][x+j] = -1
      elif dp[y+i][x+j] == 100000:
        dp[y+i][x+j] = v
        path.append([y+i,x+j])
  return ret

def warp_bfs():
  # ワープ回数でbfsとる
  deq = walk_bfs(c[0]-1,c[1]-1,0)
  while deq:
    y,x = deq.popleft()
    for yi in range(max(0,y-2),min(H,y+3)):
      for xi in range(max(0,x-2),min(W,x+3)):
        if s[yi][xi]=='#':
          dp[yi][xi] = -1
          continue
        if dp[yi][xi]==100000:
          deq.extend(walk_bfs(yi,xi,dp[y][x]+1))

warp_bfs()
ans = dp[d[0]-1][d[1]-1]
if ans == 100000 or ans < 0:
  print(-1)
else:
  print(ans)
#print(dp)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

def p(arr):
	print("_______________________")
	for i in arr:
		for j in i:
			print(j,end=" ")
		print()

h,w = readInts()
ch,cw = readInts()
dh,dw = readInts()
s = [["#" for i in range(w+2)]]+[["#"]+ list(input())+["#"] for i in range(h)]+[["#" for i in range(w+2)]]

q = deque()
visited = [[-1]*(w+2) for i in range(h+2)]
count = (w+2)*(h+2)
for i in range(h+2):
	for j in range(w+2):
		if s[i][j]=="#":
			visited[i][j] = float("inf")
			count -= 1

from pprint import pprint
visited[ch][cw] = 0

q = {(ch,cw)}
set_list = set()
cost = 0
while count:
	if len(q)==0:
		print(-1)
		exit()
	while len(q) !=0:
		x,y = q.pop()
		set_list.add((x,y))
		visited[x][y] = cost
		count-=1
		if s[x-1][y]=="." and visited[x-1][y]==-1:
			q.add((x-1,y))
		if s[x][y-1]=="." and visited[x][y-1]==-1:
			q.add((x,y-1))
		if s[x+1][y]=="." and visited[x+1][y]==-1:
			q.add((x+1,y))
		if s[x][y+1]=="." and visited[x][y+1]==-1:
			q.add((x,y+1))

	cost+=1
	while len(set_list) != 0:
		x,y = set_list.pop()
		for i in range(max(0,y-2),min(y+3,w+2)):
			if s[max(0,x-2)][i] == "." and visited[max(0,x-2)][i]==-1:
				q.add((x-2,i))
			if s[min(h+1,x+2)][i] == "." and visited[min(h+1,x+2)][i] == -1:
				q.add((x+2,i))
		for i in range(x-1,x+2):
			if s[i][max(y-2,0)]=="." and visited[i][max(y-2,0)]==-1:
				q.add((i,y-2))
			if s[i][min(y+2,w+1)]=="." and visited[i][min(y+2,w+1)]==-1:
				q.add((i,y+2))

print(visited[dh][dw])

Submission status: Wrong Answer

Solution code:
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	for i, j in list(setmada):
		settansaku.add((i, j))
		stock.add((i, j))
		setmada.remove((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if 0 <= k[0] < h and 0 <= k[1] < w:
				if not k in kabeset:
					if not k in setmada:
						if not k in settansaku:
							setmada.add(k)
							kouho += 1
							if k == goal:
								mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	for i, j in list(stock):
		stock.remove((i, j))
		kouho -= 1
		for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
			if 0 <= k[0] < h and 0 <= k[1] < w:
				if not k in kabeset:
					if not k in setmada:
						if not k in settansaku:
							setmada.add(k)
							kouho += 1
							if k == goal:
								mode = 0
								
	if mode == 0:
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from heapq import heappush, heappop

def resolve():
    H, W = iim()
    Ch, Cw = iim()
    Dh, Dw = iim()
    W1 = W+4; H1 = H+4

    ok = "."
    X = "X"
    X2 = "XX"
    XX = X2 * W1

    S = XX + "".join(X2 + input() + X2 for i in range(H)) + XX

    pos1 = W1 * (Ch+1) + (Cw+1)
    pos2 = W1 * (Dh+1) + (Dw+1)

    inf = H1*W1+1
    dp = [inf] * (H1*W1)
    step = [1+W1, W1-1,-1-W1, 1-W1]

    dq = []
    heappush(dq, (0, pos1))
    vis = set()

    while dq:
        n, p0 = heappop(dq)

        if p0 in vis:
            continue
        if p0 == pos2:
            print(n)
            return

        vis.add(p0)
        dp[p0] = min(dp[p0], n)

        x1 = 0
        for i, j, x in ((1, W1, 9), (-1, W1, 6), (W1, 1, 3), (-W1, 1, 12)):
            p1 = p0 + i

            if S[p1] == ok:
                heappush(dq, (n, p1))
                continue
            elif S[p1] == X:
                continue

            x1 |= x
            n1 = n + 1
            for k in (i-j, i, i+j):
                p2 = p1 + k
                if S[p2] == ok:
                    heappush(dq, (n1, p1))
                    continue

        if not x1:
            continue

        for i in range(4):
            if 1<<i & x1 == 0:
                continue

            p1 = p0
            j = step[i]
            for i in range(2):
                p1 += j
                if S[p1] == ok:
                    heappush(dq, (n1, p1))
                elif S[p1] == X:
                    break
    print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
M = [[0]*(W+2) for _ in range(H+2)]
S = []
for i in range(H):
    S.append(list(input()))

for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i-1][j-1] == ".":
            M[i][j] = 1
H += 2
W += 2

searched_map = [[10**9]*W for _ in range(H)]
searched_map[Ch][Cw] = 0

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

q = deque()
q.append([Ch,Cw,0])
biM[Ch][Cw] = 1
while q:
    while 1 and q:
        xy = q.pop()
        y = xy[0]
        x = xy[1]
        w = xy[2]
        if biM[y][x] == 0:
            break
    biM[y][x] = 1
    if M[y][x-1] == 1 and searched_map[y][x-1] > w:
        q.append([y,x-1,w])
        searched_map[y][x-1] = w
    if M[y][x+1] == 1 and searched_map[y][x+1] > w:
        q.append([y,x+1,w])
        searched_map[y][x+1] = w
    if M[y-1][x] == 1 and searched_map[y-1][x] > w:
        q.append([y-1,x,w])
        searched_map[y-1][x] = w
    if M[y+1][x] == 1 and searched_map[y+1][x] > w:
        q.append([y+1,x,w])
        searched_map[y+1][x] = w
    
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=y+i<=H-1 and 0<=x+j<=W-1:
                if searched_map[y+i][x+j] > w+1 and M[y+i][x+j] == 1:
                    searched_map[y+i][x+j] = w+1
                    q.append([y+i,x+j,w+1])

if searched_map[Dh][Dw] < 10**9:
    print(searched_map[Dh][Dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
i0, j0 = map(lambda x: int(x) - 1, input().split())
i1, j1 = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
D = [[-1] * w for i in range(h)]
Q = deque([(i0, j0, 0)])
while Q:
    i, j, cnt = Q.popleft()
    if D[i][j] != -1:
        continue
    D[i][j] = cnt
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if 0 <= i + di < h and 0 <= j + \
                    dj < w and S[i + di][j + dj] == "." and D[i + di][j + dj] == -1:
                if abs(di + dj) == 1:
                    Q.appendleft((i + di, j + dj, cnt))
                else:
                    Q.append((i + di, j + dj, cnt + 1))
print(D[i1][j1])

Submission status: Wrong Answer

Solution code:
import queue
from numba import jit
h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
ans = float('inf')
q = queue.Queue()
q.put([c[0], c[1], 0])

route = [['#']*(w+2)]
for i in range(h):
    route += [list('#'+input()+'#')]
route += [['#']*(w+2)]

@jit
def cal(q, ans):
    while not q.empty():
        now = q.get()
        if route[now[0]][now[1]] == '.':
            route[now[0]][now[1]] = '#'
            
        if now[0] == d[0] and now[1] == d[1]:
            ans = min(ans, now[2])
        else:
            if route[now[0]+1][now[1]] != '#':
                q.put([now[0]+1, now[1], now[2]])
            if route[now[0]-1][now[1]] != '#':
                q.put([now[0]-1, now[1], now[2]])
            if route[now[0]][now[1]+1] != '#':
                q.put([now[0], now[1]+1, now[2]])
            if route[now[0]][now[1]-1] != '#':
                q.put([now[0], now[1]-1, now[2]])
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if 0 <= now[0]+i <= h+1 and 0 <= now[1]+j <= w+1:
                        if route[now[0]+i][now[1]+j] != '#':
                            q.put([now[0]+i, now[1]+j, now[2]+1])
    return ans
ans = cal(q, ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def Dijkstra(graph,s):
    INF = 10**9
    dist = [INF]*len(graph)
    dist[s] = 0
    #nn_node = [-1]*len(graph) #nearest neighborのnode
    #checked=[False]*len(graph) #dist 確定
    heap = [(0,s)]
    while heap:
        cost,node = hq.heappop(heap)
        if cost>dist[node]:continue
        for weight,nex in graph[node]:
            d = cost+weight
            if d<dist[nex]:
                dist[nex] = d
                #nn_node[nex] = node
                hq.heappush(heap,(d,nex))
    for i in range(len(dist)):
        if dist[i] == INF:
            dist[i] = -1
    return dist #,nn_node

dyx = [(-1,0),(1,0),(0,1),(0,-1)]
INF=10**9
H,W = ma()
ch,cw = ma()
ch-=1;cw-=1
dh,dw=ma()
dh-=1;dw-=1
area= []
for h in range(H):
    area.append(input())

group = [[-1]*W for h in range(H)]
def BFS(sy,sx,cnt):
    que = collections.deque()
    que.append((sy,sx))
    group[sy][sx]=idx
    while que:
        h,w = que.popleft()
        for dy,dx in dyx:
            if (0<=h+dy<H )and (0<=w+dx<W):
                if area[h+dy][w+dx] =="." and group[h+dy][w+dx] ==-1:
                    group[h+dy][w+dx] = idx
                    que.append((h+dy,w+dx))


idx = 0
for h in range(H):
    for w in range(W):
        if area[h][w] =="." and group[h][w] ==-1:
            BFS(h,w,idx)
            idx+=1
            #print(group)

tree = [set() for _ in range(idx)]
dyx2 = [(-1,0),(1,0),(0,1),(0,-1),(-2,0),(2,0),(0,2),(0,-2)]
for h in range(H):
    for w in range(W):
        g = group[h][w]
        for dy,dx in dyx2:
            if (0<=h+dy<H )and (0<=w+dx<W) and (area[h+dy][w+dx]=="."):
                if (g !=group[h+dy][w+dx]):
                    tree[g].add((1,group[h+dy][w+dx]))
dist = Dijkstra(tree,group[ch][cw])

#print(group)
#print(tree)
#print(dist)
print(dist[group[dh][dw]])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

def p(arr):
	print("_______________________")
	for i in arr:
		for j in i:
			print(j,end=" ")
		print()

h,w = readInts()
ch,cw = readInts()
dh,dw = readInts()
s = [["#" for i in range(w+2)]]+[["#"]+ list(input())+["#"] for i in range(h)]+[["#" for i in range(w+2)]]

q = deque()
visited = [[-1]*(w+2) for i in range(h+2)]
count = (w+2)*(h+2)
for i in range(h+2):
	for j in range(w+2):
		if s[i][j]=="#":
			visited[i][j] = float("inf")
			count -= 1

from pprint import pprint
visited[ch][cw] = 0

q = {(ch,cw)}
set_list = set()
cost = 0
while count:
	if len(q)==0:
		print(-1)
		exit()
	while len(q) !=0:
		x,y = q.pop()
		set_list.add((x,y))
		visited[x][y] = cost
		count-=1
		if s[x-1][y]=="." and visited[x-1][y]==-1:
			q.add((x-1,y))
		if s[x][y-1]=="." and visited[x][y-1]==-1:
			q.add((x,y-1))
		if s[x+1][y]=="." and visited[x+1][y]==-1:
			q.add((x+1,y))
		if s[x][y+1]=="." and visited[x][y+1]==-1:
			q.add((x,y+1))

	cost+=1
	while len(set_list) != 0:
		x,y = set_list.pop()
		for i in range(max(0,y-2),min(y+3,w+2)):
			if s[max(0,x-2)][i] == "." and visited[max(0,x-2)][i]==-1:
				q.add((x-2,i))
			if s[min(h+1,x+2)][i] == "." and visited[min(h+1,x+2)][i] == -1:
				q.add((x+2,i))

print(visited[dh][dw])

Submission status: Wrong Answer

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

res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0

que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0

while (que or que_warp):
    while (que):
        if count > 0:
            que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    if not (nx,ny) in que_warp:
                        que_warp.append((nx,ny))
                    if (nx == Dh) and (ny == Dw):
                        print(res_S[Dh - 1][Dw - 1])
                        exit()
        que.pop(0)

    count += 1

    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
                    if (nx == Dh) and (ny == Dw):
                        print(res_S[Dh - 1][Dw - 1])
                        exit()
        que_warp.pop(0)

print (res_S[Dh-1][Dw-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 = [list(input()) for _ in range(H)]
dist = [[float("inf")] * W for _ in range(H)]

x = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        x.append((i-2, j-2))
x = set(x)
y = {(0, 1), (1, 0), (-1, 0), (0, -1)}
x = x - y

from collections import deque
q = deque()
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    for hh, ww in y:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w]:
            dist[h+hh][w+ww] = dist[h][w]
            q.appendleft((h+hh, w+ww))
    for hh, ww in x:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w] + 1:
            dist[h+hh][w+ww] = dist[h][w] + 1
            q.append((h+hh, w+ww))

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

Submission status: Wrong Answer

Solution code:
import queue
from numba import jit
h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
ans = float('inf')
q = queue.Queue()
q.put([c[0], c[1], 0])

route = [['#']*(w+2)]
for i in range(h):
    route += [list('#'+input()+'#')]
route += [['#']*(w+2)]

@jit
def cal(q, ans):
    while not q.empty():
        now = q.get()
        if route[now[0]][now[1]] == '.':
            route[now[0]][now[1]] = '#'
        if now[0] == d[0] and now[1] == d[1]:
            ans = min(ans, now[2])
        if route[now[0]+1][now[1]] != '#':
            q.put([now[0]+1, now[1], now[2]])
        if route[now[0]-1][now[1]] != '#':
            q.put([now[0]-1, now[1], now[2]])
        if route[now[0]][now[1]+1] != '#':
            q.put([now[0], now[1]+1, now[2]])
        if route[now[0]][now[1]-1] != '#':
            q.put([now[0], now[1]-1, now[2]])
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0 <= now[0]+i <= h+1 and 0 <= now[1]+j <= w+1:
                    if route[now[0]+i][now[1]+j] != '#':
                        q.put([now[0]+i, now[1]+j, now[2]+1])
    return ans
ans = cal(q, ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set([])

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	for i, j in list(setmada):
		settansaku.add((i, j))
		stock.add((i, j))
		setmada.remove((i, j))
		for k in itertools.product(range(i-1, i+2), range(j-1, j+2)):
			if 0 <= k[0] < h and 0 <= k[1] < w:
				if not k in kabeset:
					if not k in setmada:
						if not k in settansaku:
							setmada.add(k)
							kouho += 1
							if k == goal:
								mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	for i, j in list(stock):
		stock.remove((i, j))
		kouho -= 1
		for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
			if 0 <= k[0] < h and 0 <= k[1] < w:
				if not k in kabeset:
					if not k in setmada:
						if not k in settansaku:
							setmada.add(k)
							kouho += 1
							if k == goal:
								mode = 0
								
	if mode == 0:
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Wrong Answer

Solution code:

from collections import deque
def main():
    H,W = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    field = [input() for _ in range(H)]

    wmap = [[-1] * W for _ in range(H)]
    wmap[start[0]-1][start[1]-1] = 0

    d = deque()
    d.appendleft((start[1]-1,start[0]-1))

    warpd = d.copy()

    def flood():
        while len(d) > 0:
            posx, posy = d.pop()
            w = wmap[posy][posx]
            for x,y in [(posx-1, posy), (posx+1, posy), (posx, posy-1), (posx, posy+1)]:
                if 0 <= x < W and 0 <= y < H and field[y][x] == "." and wmap[y][x] == -1:
                    wmap[y][x] = w
                    d.appendleft((x,y))
                    warpd.append((x,y))

    # くばる
    def warp():
        movable = set()
        while len(warpd) > 0:
            x,y = warpd.pop()
            w = wmap[y][x]
            
            for my in range(-2, 3):
                for mx in range(-2, 3):
                    px = x + mx
                    py = y + my
                    if 0 <= px < W and 0 <= py < H and field[py][px] == "." and wmap[py][px] == -1:
                        wmap[py][px] = w+1
                        movable.add((px,py))

        for item in movable:
            d.append(item)

    while len(d) != 0 and wmap[goal[0]-1][goal[1]-1] == -1:
        flood()
        warp()

    print(wmap[goal[0]-1][goal[1]-1])

if __name__ == "__main__":
    main()