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 heapq
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
dh=DH-1
dw=DW-1
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=[(0,0,CH-1,CW-1)]
heapq.heapify(q)
checked=set()
def check(h,w,c):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    p=(abs(dh-h),abs(dw-w))
    heapq.heappush(q,(c,p,h,w))
    return True

def main():
    while q:
        c,_,h,w=heapq.heappop(q)
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c)
        check(h-0,w-1,c)
        check(h+1,w+0,c)
        check(h+0,w+1,c)
        # warp
        for i in [-2,-1,1,2]:
            for j in [-2,-1,1,2]:
                check(h+i,w+j,c+1)
    return -1
print(main())

Submission status: Wrong Answer

Solution code:
import heapq
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
dh=DH-1
dw=DW-1
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=[(0,0,CH-1,CW-1)]
heapq.heapify(q)
checked=set()
def check(h,w,c):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    p = (abs(dh-h), abs(dw-w))
    heapq.heappush(q,(c,p,h,w))

def main():
    while q:
        c,_,h,w=heapq.heappop(q)
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c)
        check(h-0,w-1,c)
        check(h+1,w+0,c)
        check(h+0,w+1,c)
        # warp
        for i in [-1,+1]:
            for j in range(-1,1):
                check(h+i,w+j,c+1)
        for i in [-2,+2]:
            for j in range(-2,3):
                check(h+i,w+j,c+1)
                check(h+j,w+i,c+1)
    return -1
print(main())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

co_num = lambda x: x[0] * W + x[1]
H, W = map(int, input().split())
c, d = map(int, input().split())
ori = (c-1, d-1)
c, d = tuple(map(int, input().split()))
dis = (c-1, d-1)
S = [0] * H
for i in range(H):
    S[i] = input()

Q = []
res = defaultdict(lambda: 10**7)
res[ori] = 0
heapq.heappush(Q, (0, ori))

while Q:
    d, (x, y) = heapq.heappop(Q)
#     print(x, y)
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not (0 <= x + i < H and 0 <= y + j < W): continue
            if S[x+i][y+j] == '#': continue
            if abs(i) + abs(j) == 1:
                if res[(x+i, y+j)] > d:
                    res[(x+i, y+j)] = d
                    heapq.heappush(Q, (d, (x+i, y+j)))
            else:
                if res[(x+i, y+j)] > d+1:
                    res[(x+i, y+j)] = d + 1
                    heapq.heappush(Q, (d+1, (x+i, y+j)))

print(res[dis])

Submission status: Wrong Answer

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

def main():
    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
    S = [list(input()) for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            c = cnt[h][w]
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if cnt[nh][nw] > c:
                    cnt[nh][nw] = c
                    Q.append([nh,nw])
        nc = c + 1
        for j in range(-2,3):
            for k in range(-2,3):
                nh = h + j
                nw = w + k
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if cnt[nh][nw] > nc:
                        cnt[nh][nw] = nc
                        Q.append([nh,nw])

    if cnt[Dh][Dw] == float('inf'):
        print(-1)
    else:
        print(cnt[Dh][Dw])




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
sy,sx = map(int,input().split())
sy-=1
sx-=1
gy,gx = map(int,input().split())
gy,gx = gy-1,gx-1
grid = [0] * H
done = [[0]*W for _ in range(H)]
cost = [[float('inf')]*W for _ in range(H)]
cost[sy][sx] = 0
done[sy][sx] =1
for i in range(H):
    grid[i] = input()

walk_q = deque()
magic_q = deque()
def walk_bfs(magic_count):
    y,x = walk_q.popleft()
    for new_y,new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0<=new_y<H and 0<=new_x<W and grid[new_y][new_x] == '.':
            if not done[new_y][new_x]:
                done[new_y][new_x] = 1
                cost[new_y][new_x] = min(cost[new_y][new_x],magic_count)

                walk_q.append([new_y,new_x])
                magic_q.append([new_y,new_x])

def magic_bfs(magic_count):
    y,x = magic_q.popleft()
    for y_add in range(-2,3):
        for x_add in range(-2,3):
            if y_add == 0 and x_add == 0:
                continue
            new_y = y+y_add
            new_x = x+x_add

            if 0<=new_y<H and 0<=new_x<W and grid[new_y][new_x] == '.':
                if not done[new_y][new_x]:
                    done[new_y][new_x] = 1
                    cost[new_y][new_x] = min(cost[new_y][new_x],magic_count+1)

                    walk_q.append([new_y,new_x])

walk_q.append([sy,sx])
magic_q.append([sy,sx])
magic_count = 0
# 毎回、既にqueueにあるやつ（初回を除く）が、done、costの処理をされない？
# や、初回以外は常にどっかしらで「発見」される
while walk_q or magic_q:
    while walk_q:
        walk_bfs(magic_count)
    while magic_q:
        magic_bfs(magic_count)
    magic_count += 1
if done[gy][gx]:
    print(cost[gy][gx])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
sy,sx = map(int,input().split())
sy-=1
sx-=1
gy,gx = map(int,input().split())
gy,gx = gy-1,gx-1
grid = [0] * H
done = [[0]*W for _ in range(H)]
cost = [[float('inf')]*W for _ in range(H)]
cost[sy][sx] = 0
done[sy][sx] =1
for i in range(H):
    grid[i] = input()

walk_q = deque()
magic_q = deque()
def walk_bfs(magic_count):
    y,x = walk_q.popleft()
    for new_y,new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0<=new_y<H and 0<=new_x<W and grid[new_y][new_x] == '.':
            if not done[new_y][new_x]:
                done[new_y][new_x] = 1
                cost[new_y][new_x] = min(cost[new_y][new_x],magic_count)

                walk_q.append([new_y,new_x])
                magic_q.append([new_y,new_x])

def magic_bfs(magic_count):
    y,x = magic_q.popleft()
    for y_add in range(-2,3):
        for x_add in range(-2,3):
            new_y = y+y_add
            new_x = x+x_add

            if 0<=new_y<H and 0<=new_x<W and grid[new_y][new_x] == '.':
                if not done[new_y][new_x]:
                    done[new_y][new_x] = 1
                    cost[new_y][new_x] = magic_count+1

                    walk_q.append([new_y,new_x])

walk_q.append([sy,sx])
magic_q.append([sy,sx])
magic_count = 0
while walk_q or magic_q:
    while walk_q:
        walk_bfs(magic_count)
    while magic_q:
        magic_bfs(magic_count)
    magic_count += 1
if done[gy][gx]:
    print(cost[gy][gx])
else:
    print(-1)

Submission status: Wrong Answer

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

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

while v:
    while v:
        a = v.pop()
        for mv in move:
            y = a[0]+mv[0]
            x = a[1]+mv[1]
            if 0<=y<=H-1 and 0<=x<=W-1:
                if d[y][x]== -1:
                    if A[y][x]==".":
                        d[y][x] = d[a[0]][a[1]]
                        v.appendleft([y,x])
                        if y==dh and x==dw:
                            print(d[y][x])
                            exit()
    else:
        for i in range(0,W):
            for j in range(0,H):
                if d[j][i]==cnt:
                    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 A[t][s]=="." and d[t][s]==-1:
                                d[t][s] = d[j][i]+1
                                v.append([j,i])
                                if t==dh and s==dw:
                                    print(d[t][s])
                                    exit()
        else:
            cnt += 1
        
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import itertools
   


def main():
    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
    maze = [input() for i in range(h)]
    visited = [[-1]*w for j in range(h)]
    
    def flatten(l):
        return list(itertools.chain.from_iterable(l))

    def list_unique(arr):
        return list(map(list, set(map(tuple, arr))))

    def maze_solver(maze, visited, sy, sx, gy, gx):
        mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        _yx = list()
        _yx.append([sy, sx])
        while q:
            y, x = q.popleft()
            if y == gy and x == gx:
                ans = visited[y][x]
                _yx = list(map(list, set(map(tuple, _yx))))
                return ans, visited, _yx
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                        _yx.append([ny, nx])
                else:
                    continue
        ans = -1
        _yx = list(map(list, set(map(tuple, _yx))))
        return ans, visited, _yx

    def telepo(maze, visited, _yx, h, w):
        n_yx = list()
        for y, x in _yx:
            for ny in range(-2, 3):
                for nx in range(-2, 3):
                    if 0 <= y+ny < h and \
                        0 <= x+nx < w and \
                        visited[y+ny][x+nx] == -1 and \
                        maze[y+ny][x+nx] != '#': 
                        n_yx.append([y+ny, x+nx])
        # n_yx_s = list(map(list, set(map(tuple, n_yx))))
        n_yx_s = n_yx
        return n_yx_s

    telepo_cnt = 0
    ans, _visited, _yx = maze_solver(maze, visited, ch, cw, dh, dw)
    if ans != -1:
        # '一発目ワープ不要'
        print(telepo_cnt)
        exit()
    else:
        q = deque([telepo(maze, visited, _yx, h, w)])
        while len(q[0]) > 0:
            p = list()
            r = list()
            n_yx_s = q.popleft()
            telepo_cnt += 1
            for nyx in n_yx_s:
                # print(maze)
                # print(_visited)
                # print(nyx[0])
                # print(nyx[1])
                ans, _visted, _yx = maze_solver(maze, _visited, nyx[0], nyx[1], dh, dw)
                if ans != -1:
                    # 'ワープからのゴール'
                    print(telepo_cnt)
                    exit()
                else:
                    # for i in telepo(maze, visited, _yx, h, w):
                    #     p.append(i)
                    #     print('p', p)
                    # #     p = list(map(list, set(map(tuple, p))))
                    # #     print('p#', p)
                    # # print(telepo(maze, visited, _yx, h, w))
                    r.append(telepo(maze, visited, _yx, h, w))
            r = list_unique(flatten(r))
            print('r', r)           
            q.append(r)
        # 'ワープしても無理'
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

# D - Wizard in Maze
def conv_index(s):
	return int(s) - 1


def search(h, w, magic):
	global Dh
	global Dw
	global is_reached
	global ans

	if h == Dh and w == Dw:
		is_reached[Dh][Dw] = True
		ans.append(magic)
	elif not can_go(h, w):
		return
	else:
		is_reached[h][w] = True

		if need_to_use_magic(h, w):
			m = magic + 1

			for i in range(-2, 3):
				search(h - 2, w + i, m)
				search(h + 2, w + i, m)

			for i in range(-2, 3):
				if i != 0:
					search(h - 1, w + i, m)
					search(h + 1, w + i, m)

			search(h, w - 2, m)
			search(h, w + 2, m)
		else:
			search(h - 1, w, magic)
			search(h + 1, w, magic)
			search(h, w - 1, magic)
			search(h, w + 1, magic)


def can_go(h, w):
	global H
	global W
	global is_reached
	global maze

	if h < 0 or h > H - 1 or w < 0 or w > W - 1:
		return False
	elif is_reached[h][w]:
		return False
	elif maze[h][w] == '#':
		return False
	else:
		return True


def need_to_use_magic(h, w):
	any_can_go = False

	if can_go(h - 1, w):
		any_can_go = True

	if can_go(h + 1, w):
		any_can_go = True

	if can_go(h, w - 1):
		any_can_go = True

	if can_go(h, w + 1):
		any_can_go = True

	if not any_can_go:
		return True


sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
Ch, Cw = map(conv_index, input().split())
Dh, Dw = map(conv_index, input().split())

maze = []

for _ in range(H):
	maze.append(input())

is_reached = [[False] * W for _ in range(H)]

ans = []

search(Ch, Cw, 0)

if not is_reached[Dh][Dw]:
	print(-1)
elif len(ans) == 0:
	print(0)
else:
	print(min(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    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
    maze = [input() for i in range(h)]
    visited = [[-1]*w for j in range(h)]
    
    def maze_solver(maze, visited, sy, sx, gy, gx):
        mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        q = deque([[sy, sx]])
        visited[sy][sx] = 0 
        _yx = list()
        _yx.append([sy, sx])
        while q:
            y, x = q.popleft()
            if y == gy and x == gx:
                ans = visited[y][x]
                _yx = list(map(list, set(map(tuple, _yx))))
                return ans, visited, _yx
            for i, j in mv:
                if (0 <= y + i < h) and (0 <= x + j < w):  
                    ny = y+i
                    nx = x+j
                    if visited[ny][nx] != -1:
                        continue
                    if maze[ny][nx] == '.':
                        visited[ny][nx] = visited[y][x] + 1 
                        q.append([ny, nx])
                        _yx.append([ny, nx])
                else:
                    continue
        ans = -1
        _yx = list(map(list, set(map(tuple, _yx))))
        return ans, visited, _yx

    def telepo(maze, visited, _yx, h, w):
        n_yx = list()
        for y, x in _yx:
            for ny in range(-2, 3):
                for nx in range(-2, 3):
                    if 0 <= y+ny < h and \
                        0 <= x+nx < w and \
                        visited[y+ny][x+nx] == -1 and \
                        maze[y+ny][x+nx] != '#': 
                        n_yx.append([y+ny, x+nx])
        n_yx_s = list(map(list, set(map(tuple, n_yx))))
        return n_yx_s
    
    telepo_cnt = 0
    ans, visited, _yx = maze_solver(maze, visited, ch, cw, dh, dw)
    if ans != -1:
        print(telepo_cnt)
        exit()
    else:
        # print(telepo(maze, visited, _yx, h, w))
        q = deque([telepo(maze, visited, _yx, h, w)])
        while len(q[0]) > 0:
            # print('q', q)
            pop = q.popleft()
            telepo_cnt += 1  
            # print('pop', pop)
            p = list()
            for n_yx in pop:
                # print('n_yx', n_yx)
                ans, visted, _yx = maze_solver(maze, visited, n_yx[0], n_yx[1], dh, dw)
                if ans != -1:
                    print(telepo_cnt)
                    exit()
                else:
                    for i in telepo(maze, visited, _yx, h, w):
                        p.append(i)
                        print('p', p)
                        p = list(map(list, set(map(tuple, p))))
                        print('p#', p)
            q.append(p)  
        #print(telepo_cnt)
        print(-1)
                        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def good(x,y):
    if (x>=0 and x<h) and (y>=0 and y<w):
        return (mat[x][y] != "#")
h, w = map(int,input().split())
sh, sw = map(int,input().split())
eh, ew = map(int,input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)
x = [1,-1,0,0]
y = [0,0,-1,1]
dist = [[float('inf') for i in range(w)]for j in range(h)]
sh -= 1
sw -= 1
eh -= 1
ew -= 1
dist[sh][sw] = 0
queue = deque()
queue.appendleft((sh,sw))
while queue:
    m = queue.popleft()
    for d in range(4):
        nx = m[0] + x[d]
        ny = m[1] + y[d]
        if good(nx,ny):
            if dist[nx][ny] > dist[m[0]][m[1]]:
                dist[nx][ny] =  dist[m[0]][m[1]]
                queue.appendleft((nx,ny))
    for i in range(m[0]-2,m[1]+3):
        for j in range(m[1]-2,m[1]+3):
            if good(i,j):
                if dist[i][j] > dist[m[0]][m[1]] + 1:
                    dist[i][j] = dist[m[0]][m[1]] + 1
                    queue.append((i,j))
if dist[eh][ew] == float('inf'):
    print(-1)
else:
    print(dist[eh][ew])

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

meiro = []
for i in range(H):
    meiro.append(list(map(str, input())))

check_list = deque()   
num = 0

def check0(i,k):   
    global H, W
    global check_list
    global num
    
    if k > 0:
        if meiro[i][k-1] == '.' or meiro[i][k-1] == num+1:
            meiro[i][k-1] = num  
            check_list.appendleft([i,k-1])
    if k < W-1:
        if meiro[i][k+1] == '.' or meiro[i][k+1] == num+1:
            meiro[i][k+1] = num  
            check_list.appendleft([i,k+1])
    if i < H-1:
        if meiro[i+1][k] == '.' or meiro[i+1][k] == num+1:
            meiro[i+1][k] = num 
            check_list.appendleft([i+1,k])
    if i > 0:
        if meiro[i-1][k] == '.' or meiro[i-1][k] == num+1:
            meiro[i-1][k] = num  
            check_list.appendleft([i-1,k])
    
    return check_list

def check1(i,k):
    global H,W
    global check_list
    global num
    for w in range(-2,3):
        for h in range(-2,3):
            ind = max(0,i+h)
            col = max(0,k+w)
            ind = min(H-1,ind)
            col = min(W-1,col)
            if meiro[ind][col] == '.':
                meiro[ind][col] = num+1
                check_list.append([ind, col])
                

meiro[Ch-1][Cw-1] = num
check_list.append([Ch-1,Cw-1])
while check_list != deque([]):

    position = check_list.popleft()
    if meiro[position[0]][position[1]] != num:
        num +=1
    check0(position[0],position[1])
    check1(position[0],position[1])
    
    
if meiro[Dh-1][Dw-1] == '.':
    print(-1)
else:
    print(meiro[Dh-1][Dw-1])

Submission status: Wrong Answer

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

meiro = []
for i in range(H):
    meiro.append(list(map(str, input())))

check_list = deque()   
num = 0

def check0(i,k):   
    global H, W
    global check_list
    global num
    
    if k > 0:
        if meiro[i][k-1] == '.' or meiro[i][k-1] == num+1:
            meiro[i][k-1] = num  
            check_list.appendleft([i,k-1])
    if k < W-1:
        if meiro[i][k+1] == '.' or meiro[i][k+1] == num+1:
            meiro[i][k+1] = num  
            check_list.appendleft([i,k+1])
    if i < H-1:
        if meiro[i+1][k] == '.' or meiro[i+1][k] == num+1:
            meiro[i+1][k] = num 
            check_list.appendleft([i+1,k])
    if i > 0:
        if meiro[i-1][k] == '.' or meiro[i-1][k] == num+1:
            meiro[i-1][k] = num  
            check_list.appendleft([i-1,k])
    
    return check_list

def check1(i,k):
    global H,W
    global check_list
    global num
    for w in range(-2,3):
        for h in range(-2,3):
            ind = max(0,i+h)
            col = max(0,k+w)
            ind = min(H-1,ind)
            col = min(W-1,col)
            if meiro[ind][col] == '.':
                meiro[ind][col] = num+1
                check_list.append([ind, col])
                

meiro[Ch-1][Cw-1] = num
check_list.append([Ch-1,Cw-1])
while check_list != deque([]):

    position = check_list.popleft()
    if meiro[position[0]][position[1]] != num:
        num +=1
    check0(position[0],position[1])
    check1(position[0],position[1])
    
    
if meiro[Dh-1][Dw-1] == '.':
    print(-1)
else:
    print(meiro[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = (int(T) for T in input().split())
SH,SW = (int(T)-1 for T in input().split())
EH,EW = (int(T)-1 for T in input().split())
S = [[] for T in range(0,H)]
for TH in range(0,H):
    S[TH] = [True if T=='.' else False for T in input()]
    
Visited = [[False]*W for TH in range(0,H)]
Visited[SH][SW] = True
Queue = deque()
Queue.append([SH,SW])
Now = deque()
Now.append([SH,SW])
Cost = 0
Flag = False
while Queue: 
    while Queue:
        NowH,NowW = Queue.popleft()
        for WalkH,WalkW in [[NowH-1,NowW],[NowH+1,NowW],[NowH,NowW-1],[NowH,NowW+1]]:
            if 0<=WalkH<H and 0<=WalkW<W:
                if S[WalkH][WalkW] and not Visited[WalkH][WalkW]:
                    Visited[WalkH][WalkW] = True
                    Now.append([WalkH,WalkW])
                    Queue.append([WalkH,WalkW])
    if Visited[EH][EW]:
        Flag = True
        break
    Cost += 1
    while Now:
        NextH,NextW = Now.popleft()
        for WarpH in range(NextH-2,NextH+3):
            for WarpW in range(NextW-2,NextW+3):
                if 0<=WarpH<H and 0<=WarpW<W:
                    if S[WarpH][WarpW] and not Visited[WarpH][WarpW]:
                        Visited[WarpH][WarpW] = True
                        Queue.append([WarpH,WarpW])
print(['-1',Cost][Flag])

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

meiro = []
for i in range(H):
    meiro.append(list(map(str, input())))

check_list = deque()   
num = 0

def check0(i,k):   
    global H, W
    global check_list
    global num
    
    if k > 0:
        if meiro[i][k-1] == '.' or meiro[i][k-1] == num+1:
            meiro[i][k-1] = num  
            check_list.appendleft([i,k-1])
    if k < W-1:
        if meiro[i][k+1] == '.' or meiro[i][k+1] == num+1:
            meiro[i][k+1] = num  
            check_list.appendleft([i,k+1])
    if i < H-1:
        if meiro[i+1][k] == '.' or meiro[i+1][k] == num+1:
            meiro[i+1][k] = num 
            check_list.appendleft([i+1,k])
    if i > 0:
        if meiro[i-1][k] == '.' or meiro[i-1][k] == num+1:
            meiro[i-1][k] = num  
            check_list.appendleft([i-1,k])
    
    return check_list

def check1(i,k):
    global H,W
    global check_list
    global num
    for w in range(-2,3):
        for h in range(-2,3):
            ind = max(0,i-1+h)
            col = max(0,k-1+w)
            ind = min(H-1,ind)
            col = min(W-1,col)
            if meiro[ind][col] == '.':
                meiro[ind][col] = num+1
                check_list.append([ind, col])
                

meiro[Ch-1][Cw-1] = num
check_list.append([Ch-1,Cw-1])
while check_list != deque([]):

    position = check_list.popleft()
    if meiro[position[0]][position[1]] != num:
        num +=1
    check0(position[0],position[1])
    check1(position[0],position[1])
    
    
if meiro[Dh-1][Dw-1] == '.':
    print(-1)
else:
    print(meiro[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
from collections import*
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
I=h*w
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 if d[y][x]>c:
  d[y][x]=c
  for i in range(y-2,y+3):
   for j in range(x-2,x+3):h>i>-1<j<w<I==d[i][j]!=m[i][j]>'#'!=(abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c))or q.append((i,j,c+1)))
print(d[f-1][g-1]%I-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())

meiro = []
for i in range(H):
    meiro.append(list(map(str, input())))

check_list = deque()   
num = 0

def check0(i,k):   
    global H, W
    global check_list
    global num
    
    if k > 0:
        if meiro[i][k-1] == '.' or meiro[i][k-1] == num+1:
            meiro[i][k-1] = num  
            check_list.appendleft([i,k-1])
    if k < W-1:
        if meiro[i][k+1] == '.' or meiro[i][k+1] == num+1:
            meiro[i][k+1] = num  
            check_list.appendleft([i,k+1])
    if i < H-1:
        if meiro[i+1][k] == '.' or meiro[i+1][k] == num+1:
            meiro[i+1][k] = num 
            check_list.appendleft([i+1,k])
    if i > 0:
        if meiro[i-1][k] == '.' or meiro[i-1][k] == num+1:
            meiro[i-1][k] = num  
            check_list.appendleft([i-1,k])
    
    return check_list

def check1(i,k):
    global H,W
    global check_list
    global num
    for w in range(-2,3):
        for h in range(-2,3):
            ind = max(0,k-h)
            col = max(0,i-w)
            ind = min(H-1,ind)
            col = min(W-1,col)
            if meiro[ind][col] == '.':
                meiro[ind][col] = num+1
                check_list.append([ind, col])
                

meiro[Ch-1][Cw-1] = num
check_list.append([Ch-1,Cw-1])
while check_list != deque([]):

    position = check_list.popleft()
    if meiro[position[0]][position[1]] != num:
        num +=1
    check0(position[0],position[1])
    check1(position[0],position[1])
    
    
if meiro[Dh-1][Dw-1] == '.':
    print(-1)
else:
    print(meiro[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
import queue
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
graphlist = []
grapht = [[-1 for i in range(w+2)] for i in range(h+2)]
meiro = [["#" for i in range(w+2)]]+[["#"]+list(input())+["#"] for i in range(h)]+[["#" for i in range(w+2)]]
lastnum=[0]
donelist = set()
for i in range(1, h+1):
    for j in range(1, w+1):
        if(meiro[i][j] == "."):
            if(grapht[i-1][j] != -1):
                grapht[i][j] = grapht[i-1][j]
            elif(grapht[i][j-1] != -1):
                grapht[i][j] = grapht[i][j-1]
            elif(grapht[i+1][j] != -1):
                grapht[i][j] = grapht[i+1][j]
            elif(grapht[i][j+1] != -1):
                grapht[i][j] = grapht[i][j+1]
            else:
                grapht[i][j] = lastnum
                graphlist.append(set())
                lastnum = [lastnum[0] + 1]
            if(meiro[i+1][j] == "."):
                grapht[i+1][j] = grapht[i][j]
            if(meiro[i][j+1] == "."):
                if(grapht[i][j+1] == -1):
                    grapht[i][j+1] = grapht[i][j]
                elif(grapht[i][j][0] < grapht[i][j+1][0]):
                    donelist.add(grapht[i][j+1][0])
                    graphlist[grapht[i][j][0]] = graphlist[grapht[i][j][0]] | (graphlist[grapht[i][j+1][0]] - set(grapht[i][j]))
                    for k in graphlist[grapht[i][j+1][0]]:
                        graphlist[k].add(grapht[i][j][0])
                    grapht[i][j+1][0] = grapht[i][j][0]
                elif(grapht[i][j][0] > grapht[i][j+1][0]):
                    donelist.add(grapht[i][j][0])
                    graphlist[grapht[i][j+1][0]] = graphlist[grapht[i][j+1][0]] | (graphlist[grapht[i][j][0]] - set(grapht[i][j+1]))
                    for k in graphlist[grapht[i][j][0]]:
                        graphlist[k].add(grapht[i][j+1][0])
                    grapht[i][j][0] = grapht[i][j+1][0]
            for k in range(i-2, i+3):
                if(k >= h+1):
                    continue
                for l in range(j-2, j+3):
                    if(l >= w+1):
                        continue
                    if(grapht[k][l] != -1 and grapht[k][l] != grapht[i][j]):
                        graphlist[grapht[i][j][0]].add(grapht[k][l][0])
                        graphlist[grapht[k][l][0]].add(grapht[i][j][0])
start = grapht[ch][cw][0]
end = grapht[dh][dw][0]
nextlist = queue.Queue()
depthlist = [-1]*len(graphlist)
donelist.add(start)
depthlist[start] = 0
while True:
    for i in graphlist[start]:
        if(i not in donelist):
            nextlist.put(i)
            depthlist[i] = depthlist[start]+1
            donelist.add(i)
    if(nextlist.empty()):
        break
    start = nextlist.get()
#import pprint        
#pprint.pprint(grapht)
#print(graphlist)
print(depthlist[end])