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

import heapq

#点の数が10**5のオーダー以下で使える
#計算量はO(MlogN) M : 辺の数、N　：　頂点数
#頂点sからの各頂点への最短距離を出力
def dijkstra(s, n, edge): #s:始点、n:頂点の数、edge:重み付き辺の配列（edge[i]:iから出るtuple[重み、行き先]の配列)
    INF = 10**20
    d = [INF]*n # d[i]: sと点iとの距離
    used = [True]*n #Trueは未確定
    d[s] = 0 #初期条件
    used[s] = False # 初期条件
    edge_list = []
    for a, b in edge[s]:
        heapq.heappush(edge_list, a*(10**10)+b) #heapqの中に重みと辺の抱き合わせた情報を入れる
    while len(edge_list):
        min_edge = heapq.heappop(edge_list) #まだ使われていない頂点の中から最小の重みのものを取りだす
        if not used[min_edge%(10**10)]: # 確定していたらcontinue、確定していない時のみ以下の処理を行う
            continue
        v = min_edge%(10**10) #行き先の情報を復元
        d[v] = min_edge // (10**10) #重みの情報を復元し、sとvの最短距離d[v]を更新する
        used[v] = False
        for e in edge[v]:
            if used[e[1]]: #その行き先がまだ未確定の場合
                heapq.heappush(edge_list, (e[0]+d[v])*(10**10) + e[1])
        
    return d
#d[i] : 始点から i までの距離
h, w = map(int, input().split())
edge = [[] for _ in range((h+4)*(w+4))] # edge:重み付き辺の配列（edge[i]:iから出るtuple(重み、行き先)の配列)
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
start = (ch, cw)
end = (dh, dw)
g = []
g.append([1]*(w+4))
g.append([1]*(w+4))
for i in range(h):
    s = list(input())
    tmp = [1,1]
    for j in s:
        if j == '.':
            tmp.append(0)
        else:
            tmp.append(1)
    tmp.append(1)
    tmp.append(1)
    g.append(tmp)
g.append([1]*(w+4))
g.append([1]*(w+4))
#print(g)
def pp(height, width):
    return height*(w+4)+width
d = []
for i in range(-2, 3):
    for j in range(-2,3):
        d.append((i, j))
d2 = [(1, 0), (0,1)]

#print(d2)
for i in range(2, h+2):
    for j in range(2, w+2):
        for q in d:
            x, y = q
            if g[i][j] == 0 and g[i+x][j+y] == 0:
                edge[pp(i, j)].append((1, pp(i+x, j+y)))
        for q in d2:
            x, y = q
            if g[i][j] == 0 and g[i+x][j+y] == 0:
                edge[pp(i, j)].append((0, pp(i+x, j+y)))
#print(edge)
                
d = dijkstra(pp(ch+1, cw+1), (h+4)*(w+4), edge)

if d[pp(dh+1, dw+1)] >= 10**20:
    print(-1)
    #print(d[pp(dh+1, dw+1)])
    #print(pp(ch+1, cw+1))
    #print(pp(dh+1, dw+1))
else:
    print(d[pp(dh+1, dw+1)])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)

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

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

maze = [list(input()) for i in range(h)]
check = [[-1] * w for i in range(h)]
check[ch][cw] = 0

maze_d = deque([[ch, cw]])
warp_deque = deque([[ch, cw]])

warp = 0

while True:
    while maze_d:
        x, y = maze_d.pop()
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1], [0, 0]):
            tx, ty = x + i, y + j
            # 弾く
            if (
                not (0 <= tx < h)
                or not (0 <= ty < w)
                or maze[tx][ty] == "#"
                or check[tx][ty] != -1
            ):
                continue
            # 到達
            elif tx == dh and ty == dw:
                print(warp)
                sys.exit()
            # 探索
            else:
                check[tx][ty] = warp
                warp_deque.append([tx, ty])
                maze_d.append([tx, ty])

    warp += 1

    while warp_deque:
        x, y = warp_deque.pop()
        for ta in range(5):
            for tb in range(5):
                tx, ty = x - 2 + ta, y - 2 + tb
                if tx == dh and ty == dw:
                    print(warp)
                    sys.exit()
                elif (
                    (0 <= tx < h)
                    and (0 <= ty < w)
                    and maze[tx][ty] == "."
                    and check[tx][ty] == -1
                ):
                    check[tx][ty] = warp
                    maze_d.append([tx, ty])

    if len(maze_d) == 0:
        print(-1)
        sys.exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "#":
				continue
			if getMaze(x - 1, y) == ".":
				graph[y][x].append((x - 1, y, 0))
			if getMaze(x + 1, y) == ".":
				graph[y][x].append((x + 1, y, 0))
			if getMaze(x, y - 1) == ".":
				graph[y][x].append((x, y - 1, 0))
			if getMaze(x, y + 1) == ".":
				graph[y][x].append((x, y + 1, 0))
			for i in range(-2, 2+1):
				for j in range(-2, 2+1):
					if (i, j) == (0, 1):
						continue
					if (i, j) == (0, -1):
						continue
					if (i, j) == (1, 0):
						continue
					if (i, j) == (-1, 0):
						continue
					if (i, j) == (0, 0):
						continue
					if getMaze(x + i, y + j) == ".":
						graph[y][x].append((x + i, y + j, 1))


	# log.print(graph)
	stack = deque([(cw-1, ch-1)])
	dist = [[-1]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		d = dist[y][x]
		if d == -1:
			d = 0
		nexts = graph[y][x]
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] != -1:
				dist[ny][nx] = min(dist[ny][nx], d + cost)
				continue
			dist[ny][nx] = d + cost
			stack.append((nx, ny))
	log.print(dist)
	print(dist[dh-1][dw-1])
	
	


main()

Submission status: Wrong Answer

Solution code:
#D
from collections import deque
H,W=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
ch -=1
cw -=1
dh -=1
dw -=1
A= [list(input()) for _ in range(H)]
d= [ [ -1 for _ in range(W) ] for _ in range(H)]
ans=0
cnt=0
v = deque([ [ch,cw] ])
d[ch][cw]=0
move = [(1,0),(-1,0),(0,1),(0,-1)]  #y,xの順

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

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
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+1 and 0 <= ya <= w+1:
    
        if reach[xa][ya] == -1:
            if 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
sw = 0

while q:
    if sw == 1:
        break
    
    
    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):
        if sw == 1:
            break
        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:
h, w = map(int, input().split())
cy, cx = map(lambda x:int(x)-1, input().split())
gy, gx = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(h)]
seen = [[-1]*w for _ in range(h)]
def f(sy, sx, cnt):
    que = []
    que.append((sy, sx))
    seen[sy][sx] = cnt
    while que:
        y, x = que.pop()
        for dy, dx in ((-1,0),(0,-1),(1,0),(0,1)):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if seen[ny][nx] != -1:
                    continue
                if S[ny][nx] == "#":
                    continue
                seen[ny][nx] = cnt
                que.append((ny, nx))
cnt = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == "." and seen[i][j] == -1:
      f(i, j, cnt)
      cnt += 1
G = [set() for _ in range(cnt+1)]
for i in range(h):
  for j in range(w):
    for dy in range(-2, 3):
      for dx in range(-2, 3):
        y, x = i+dy, j+dx
        if 0 <= y < h and 0 <= x < w:
          if S[i][j] == "#":
            continue
          if S[y][x] == "#":
            continue
          G[seen[i][j]].add(seen[y][x])
          G[seen[y][x]].add(seen[i][j])
s = seen[cy][cx]
g = seen[gy][gx]
dist = [-1]*(cnt+1)
stack = []
dist[s] = 0
stack.append(s)
while stack:
  v = stack.pop()
  if g == v:
    print(dist[g])
    exit()
  for i in G[v]:
    if dist[i] != -1:
      continue
    dist[i] = dist[v]+1
    stack.append(i)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
    s.append(input().rstrip('\n'))

d = [[10 ** 18 for i in range(w)] for j in range(h)]

stack = deque([[ch-1, cw-1, 0]])

while stack:
    curh, curw, cnt = stack.popleft()
    if d[curh][curw] <= cnt:
        continue
    else:
        d[curh][curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh > 0 and nh < h and nw > 0 and nw < w and s[nh][nw] == '.':
            stack.append([nh, nw, cnt])
    for nh in range(curh-2, curh+3):
        if nh > 0 and nh < h:
            for nw in range(curw-2,curw+3):
                if nw > 0 and nw < w and s[nh][nw] == '.':
                     stack.append([nh, nw, cnt+1])

if d[gh-1][gw-1] == 10 ** 18:
    print(-1)
else:
    print(d[gh-1][gw-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 = []
for _ in range(h):
    s.append(input())
fl = [[100000 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j:j+1] == "#"):
            fl[i][j] = -1

fl[ch-1][cw-1] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ddx = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1,  2,  2, 2, 2, 2]
ddy = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
que = [[ch-1, cw-1]]
while(len(que) != 0):
    now = que.pop(0)
    x, y = now[0], now[1]
    for i in range(4):
        if((-1 < x+dx[i] < h) and (-1 < y+dy[i] < w)):
            if(fl[x+dx[i]][y+dy[i]] >= 0):
                if(fl[x+dx[i]][y+dy[i]] > 1000):
                    que.append([x+dx[i], y+dy[i]])
                fl[x+dx[i]][y+dy[i]] = min(fl[x][y], fl[x+dx[i]][y+dy[i]])
                
    for i in range(len(ddx)):
        if((-1 < x+ddx[i] < h) and (-1 < y+ddy[i] < w)):
            if(fl[x+ddx[i]][y+ddy[i]] >= 0):
                if(fl[x+ddx[i]][y+ddy[i]] > 1000):
                    que.append([x+ddx[i], y+ddy[i]])
                fl[x+ddx[i]][y+ddy[i]] = min(fl[x][y]+1, fl[x+ddx[i]][y+ddy[i]])
if(fl[dh-1][dw-1] == 100000):
  print(-1)
else:
  print(fl[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
import copy
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
S=[list(str(input())) for i in range(H)]
field=copy.deepcopy(S)
field2=copy.deepcopy(S)
move=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0

temp=[]
def dfs2(x,y):
    field2[x][y]='#'
    temp.append([x,y])
    for i in range(4):
        nx=x+move[i][0]
        ny=y+move[i][1]
        if 0<=nx and nx<H and 0<=ny and ny<W and field2[nx][ny]=='.':
            dfs2(nx,ny)
    return temp

start=dfs2(Ch-1,Cw-1)
while True:
    if field2[Dh-1][Dw-1]=='#':
        print(ans)
        exit()
    else:
        for i in range(len(start)):
            for hh in range(-2,3):
                for ww in range(-2,3):
                    nnx=start[0][0]+hh
                    nny=start[0][0]+ww
                    if 0<=nnx and nnx<H and 0<=nny and nny<W and field2[nnx][nny]=='.':
                        dfs2(nnx,nny)
            del(start[0])
        ans+=1
    if len(start)==0:
        print(-1)
        exit()

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = list(map(int, input().split()))
Ch, Cw = list(map(lambda x: int(x) - 1, input().split()))
Dh, Dw = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]

def walk(i, j):
    ans = []
    for h, w in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
        # print(h, w)
        if h >= 0 and w >= 0 and h < H and w < W:
            # print('hoen')
            if S[h][w] == '.':
                if lab[h][w] == -1:
                    ans.append((h, w))
    return ans

def warp(i, j):
    tmp = []
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if not (dh == 0 and dw == 0):
                tmp.append([i + dh, j + dw])
    ans = []
    for h, w in tmp:
        if h > 0 and w > 0 and h < H and w < W:
            if S[h][w] == '.':
                if lab[h][w] == -1:
                    ans.append((h, w))
    return ans

lab = [[-1]*W for _ in range(H)]
warp_n = 0
lab[Ch][Cw] = 0
walk_stack= deque(walk(Ch, Cw))
warp_set = set(warp(Ch, Cw))
# print(walk(Ch, Cw))
# print(warp(Ch, Cw))
# print('-----')
while walk_stack or warp_set:
    while walk_stack:
        h, w = walk_stack.pop()
        if lab[h][w] == -1:
            lab[h][w] = warp_n
            walk_stack.extend(walk(h, w))
            warp_set |= set(warp(h, w))
    warp_n += 1
    # print(*lab, sep='\n')
    # print('-----')
    next_warp = set()
    for h, w in warp_set:
        if lab[h][w] == -1:
            lab[h][w] = warp_n
            walk_stack.extend(walk(h, w))
            next_warp |= set(warp(h, w))
    warp_set = next_warp
print(lab[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappop, heappush

H, W = map(int, input().split())
Si, Sj = map(int, input().split())
Gi, Gj = map(int, input().split())
matrix = []
for i in range(H):
    matrix.append(list(input()))

que = [(0, Si-1, Sj-1, 0)]
heapify(que)
visited = set()

while que:
    priority, r, c, count = heappop(que)
    if not(0 <= r < H and 0 <= c < W):
        continue
    if (r, c) in visited:
        continue
    elif matrix[r][c] == '#':
        continue
    elif (r, c) == (Gi-1, Gj-1):
        print(count)
        exit()
    visited.add((r, c))
    for td, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        heappush(que, (priority+1, r+td, c+lr, count))
    for ud in range(-2, 3):
        for lr in range(-2, 3):
            heappush(que, (priority+abs(ud)+abs(lr)+1, r+ud, c+lr, count+1))
print('-1')

Submission status: Wrong Answer

Solution code:
from collections import deque

n , m = map(int, input().split())
ch , cw = map(int, input().split())
dh , dw = map(int, input().split())
maze = [['#','#']+list(input())+['#','#'] for i in range(n)]
maze = [['#']*(m+4)]+[['#']*(m+4)]+maze+[['#']*(m+4)]+[['#']*(m+4)]

step = [(0,1),(1,0),(-1,0),(0,-1)]
warp_u = [(-1,-1),(-1,1),(-2,0),(-2,-1),(-2,-2),(-2,1),(-2,2)]
warp_d = [(1,-1),(1,1),(2,0),(2,-1),(2,-2),(2,1),(2,2)]
warp_r = [(1,1),(-1,1),(-2,2),(-1,2),(0,2),(1,2),(2,2)]
warp_l = [(1,-1),(-1,-1),(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2)]

warp=0

v = [[-1]*(m+4) for i in range(n+4)]
d = deque()
d.append((ch+1,cw+1,0))
v[ch+1][cw+1]=0
while d:
    y,x,wa=d.popleft()
    for dy,dx in step:
        if maze[y+dy][x+dx]=='.' and (v[y+dy][x+dx]==-1 or v[y+dy][x+dx]>wa):
            v[y+dy][x+dx]=wa
            d.append((y+dy,x+dx,wa))
        elif maze[y+dy][x+dx]=='#' and dy>0:
            for dy2,dx2 in warp_d:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx>0:
            for dy2,dx2 in warp_r:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dy<0:
            for dy2,dx2 in warp_u:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
        elif maze[y+dy][x+dx]=='#' and dx<0:
            for dy2,dx2 in warp_l:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1))
print(v[dh+1][dw+1])

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)

H, W = nn()
Ch, Cw = nn()
Dh, Dw = nn()
S = sm(H)

T = [u"#"*(W+4)] * 2
for s in S:
    T.append("##" + s[0] + "##")
T += [u"#"*(W+4)] * 2

H += 4
W += 4
Ch += 2 - 1
Cw += 2 - 1
Dh += 2 - 1
Dw += 2 - 1

deq1 = deque()
deq1.append((Ch, Cw))
deq2 = deque()

cnt = 0

memo = array2(H, W, 10**6)
memo[Ch][Cw] = 0

for i in range(10**6):
    #pprint(T)
    #pprint(memo)
    #print("-"*30 + "\n")

    if len(deq1) == 0:
        print(-1)
        exit(0)

    while len(deq1) > 0:
        h, w = deq1.pop()

        if h == Dh and w == Dw:
            print(i)
            exit(0)

        def sch(x, y, i):
            #print(x, y, T[x][y])
            if T[x][y] == "." and i < memo[x][y]:
                memo[x][y] = i
                deq1.append((x, y))

        sch(h+1, w, i)
        sch(h-1, w, i)
        sch(h, w+1, i)
        sch(h, w-1, i)

    for j in range(H):
        for k in range(W):
            if memo[j][k] == i:
                for l in range(-2, 3, 2):
                    for m in range(-2, 3, 2):
                        if T[j+l][k+m] == "." and i + 1 < memo[j+l][k+m]:
                            memo[j+l][k+m] = i + 1
                            deq2.append((j+l, k+m))

    deq1 = deq2
    deq2 = deque()

Submission status: Wrong Answer

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

loc = []
move = []
checked = []
for i in range(h):
    line = input()
    loc.append([j for j in line])
    move.append([-1 for j in line])
    checked.append([0 for j in line])

move[ch][cw] = 0
cur = 0
walk = [(ch, cw)]
magic = []
while len(walk) > 0:
    node = walk.pop()
    checked[node[0]][node[1]] = 1
    if node[0] - 1 >= 0 and loc[node[0] - 1][node[1]] != "#" and checked[node[0] - 1][node[1]] == 0:
        walk.append((node[0] - 1, node[1]))
    if node[1] - 1 >= 0 and loc[node[0]][node[1] - 1] != "#" and checked[node[0]][node[1] - 1] == 0:
        walk.append((node[0], node[1] - 1))
    if node[0] + 1 < h and loc[node[0] + 1][node[1]] != "#" and checked[node[0] + 1][node[1]] == 0:
        walk.append((node[0] + 1, node[1]))
    if node[1] + 1 < w and loc[node[0]][node[1] + 1] != "#" and checked[node[0]][node[1] + 1] == 0:
        walk.append((node[0], node[1] + 1))
    move[node[0]][node[1]] = cur


for i in range(h):
    for j in range(w):
        if loc[i][j] == "." and checked[i][j] == 1:
            for k in range(-2, 3):
                for l in range(-2, 3):
                    if i + k >= 0 and i + k < h and j + l >= 0 and j + l < w \
                    and loc[i + k][j + l] == "." and checked[i + k][j + l] == 0:
                        magic.append((i + k, j + l))

cur += 1

while magic:
    walk = magic[:]
    magic = []

    while len(walk) > 0:
        node = walk.pop()
        checked[node[0]][node[1]] = 1
        if node[0] - 1 >= 0 and loc[node[0] - 1][node[1]] != "#" and checked[node[0] - 1][node[1]] == 0:
            walk.append((node[0] - 1, node[1]))
        if node[1] - 1 >= 0 and loc[node[0]][node[1] - 1] != "#" and checked[node[0]][node[1] - 1] == 0:
            walk.append((node[0], node[1] - 1))
        if node[0] + 1 < h and loc[node[0] + 1][node[1]] != "#" and checked[node[0] + 1][node[1]] == 0:
            walk.append((node[0] + 1, node[1]))
        if node[1] + 1 < w and loc[node[0]][node[1] + 1] != "#" and checked[node[0]][node[1] + 1] == 0:
            walk.append((node[0], node[1] + 1))
        move[node[0]][node[1]] = cur

    for i in range(h):
        for j in range(w):
            if loc[i][j] == "." and checked[i][j] == 1:
                for k in range(-2, 3):
                    for l in range(-2, 3):
                        if i + k >= 0 and i + k < h and j + l >= 0 and j + l < w \
                        and loc[i + k][j + l] == "." and checked[i + k][j + l] == 0:
                            magic.append((i + k, j + l))
                            checked[i + k][j + l] = 1

    cur += 1

print(move[dh][dw])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
H, W = map(int, input().split())
sx, sy = map(int, input().split())
sx -= 1
sy -= 1
gx, gy = map(int, input().split())
gx -= 1
gy -= 1
map = [list(input()) for i in range(H)]
cost_map = [[10**5]*W for i in range(H)]
d = deque()
cost_map[sx][sy] = 0
d.append([sx, sy])
while d:
    cx, cy = d.pop()
    if cx==gx and cy==gy:
        break
    ccost = cost_map[cx][cy]
    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and ccost < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost
                d.append([nx, ny])
    dxy = [[-2, -2],[-2, -1],[-2, 0],[-2, 1],[-2, 2],
           [-1, -2],[-1, -1],[-1, 1],[-1, 2],
           [0, -2],[0, 2],
           [1, -2],[1, -1],[1, 1],[1, 2],
           [2, -2],[2, -1],[2, 0],[2, 1],[2, 2]]
    for dx, dy in dxy:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and (ccost + 1) < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost + 1
                d.appendleft([nx, ny])
if cost_map[gx][gy] == 10**5:
    print(-1)
else:
    print(cost_map[gx][gy])

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(map(str, list(input()))) for i in range(H)]
floor = [[0] * W for i in range(H)]
floor[Ch-1][Cw-1] = 1


def water(x, y):

    if floor[y][x] != 0:

        # 上
        if y + 1 < H:
            if S[y + 1][x] != "#" and floor[y + 1][x] == 0:
                floor[y + 1][x] = floor[y][x]
                water(x, y + 1)
        # 下
        if y - 1 >= 0:
            if S[y - 1][x] != "#" and floor[y - 1][x] == 0:
                floor[y - 1][x] = floor[y][x]
                water(x, y - 1)
        # 右
        if x + 1 < W:
            if S[y][x + 1] != "#" and floor[y][x + 1] == 0:
                floor[y][x + 1] = floor[y][x]
                water(x + 1, y)
        # 左
        if x - 1 >= 0:
            if S[y][x - 1] != "#" and floor[y][x - 1] == 0:
                floor[y][x - 1] = floor[y][x]
                water(x - 1, y)


def warp(x, y, i):
    for Y in range(max(y - 2, 0), min(y + 2, H-1)+1):
        for X in range(max(x - 2, 0), min(x + 2, W-1)+1):
            if S[Y][X] != "#" and floor[Y][X] == 0:
                floor[Y][X] = i + 1
                water(X,Y)


# スタート地点に水を流す
water(Cw-1, Ch-1)
#print(floor)

# ワープ回数
for i in range(1, 500):
    for y in range(H):
        for x in range(W):
            if floor[y][x] == i:
                warp(x, y, i)
                water(x, y)

    if floor[Dh-1][Dw-1] != 0:
        print(floor[Dh-1][Dw-1]-1)
        #print(floor)
        sys.exit()

print("-1")

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1<<50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
from collections import deque
q = deque([])
q.append((ch-1,cw-1))
while len(q)>0:
    h,w = q.popleft()
    cnt = dps[h][w]
    tmp = 0
    for dh, dw in mvs:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] <= cnt:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn))
                dps[hn][wn] = min(dps[h][w], cnt)
                tmp += 1
    if tmp == 4:continue
    for dh in range(-2,3):
        for dw in range(-2,3):
            if (dh, dw) not in mvs:
                hn = h + dh
                wn = w + dw
                if 0<=hn<H and 0<wn<W:
                    if dps[hn][wn] <= cnt+1:continue
                    if fs[hn][wn] == ".":
                        q.append((hn,wn))
                        dps[hn][wn] = min(dps[hn][wn], cnt + 1)
# for r in dps:
#     print(*r)
ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
s = ['#'*(w+2)]
for _ in range(h):
  s.append('#' + input() + '#')
s.append('#'*(w+2))

from queue import Queue
q1 = Queue()
q2 = Queue()
q1.put(c)
now = c
count = [[-1 for j in range(w+2)] for i in range(h+2)]
num = 0
while not q1.empty() or not q2.empty():
  while not q1.empty():
    now = q1.get()
    for dxy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '.':
            count[tar[0]][tar[1]] = num
            q1.put(tar)
          else:
            count[tar[0]][tar[1]] = -2
            q2.put(tar)
    for dxy in [[1, 1], [-1, -1], [-1, 1], [1, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '#':
            count[tar[0]][tar[1]] = -2
            q2.put(tar)
            
  num += 1
            
  while not q2.empty():
    now = q2.get()
    for dxy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '.':
            count[tar[0]][tar[1]] = num
            q1.put(tar)
    for dxy in [[1, 1], [-1, -1], [-1, 1], [1, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '.':
            count[tar[0]][tar[1]] = num
            q1.put(tar)
            
print(count[d[0]][d[1]])