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:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
graph = []
scores = []
for _ in range(H):
    graph.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
q = deque()
m2_q = deque()
q.append([sW, sH])
m2_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while q or m2_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動aで出来る範囲をすべて探索
    while q:
        x, y = q.pop()
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny:
                continue
            if scores[ny][nx] == float('inf') and graph[ny][nx] == '.':
                scores[ny][nx] = scores[y][x]
                q.appendleft([nx, ny])
                m2_q.append([nx, ny])

    # 移動bで動けるマスをqに格納
    while m2_q:
        x, y = m2_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny:
                    continue

                if scores[ny][nx] > scores[y][x] and graph[ny][nx] == '.':
                    q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
graph = []
scores = []
for _ in range(H):
    graph.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
q = deque()
m2_q = deque()
q.append([sW, sH])
m2_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while q or m2_q or scores[gH][gW] == float('inf'):
    # 移動aで出来る範囲をすべて探索
    while q:
        x, y = q.pop()
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny:
                continue
            if scores[ny][nx] == float('inf') and graph[ny][nx] == '.':
                scores[ny][nx] = scores[y][x]
                q.appendleft([nx, ny])
                m2_q.append([nx, ny])

    # 移動bで動けるマスをqに格納
    while m2_q:
        x, y = m2_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny:
                    continue

                if scores[ny][nx] > scores[y][x] and graph[ny][nx] == '.':
                    q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Wrong Answer

Solution code:
from itertools import product
from collections import deque
INF = 1e7
def main():
    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 = [["#"]*(W+4) for _ in range(H+4)]
    # whites = [] #　道であるindex
    # for i in range(2, H+2):
    #     tmp = input()
    #     for j in range(2, W+2):
    #         S[i][j] = tmp[j-2]
    #         if S[i][j] == ".":
    #             whites.append((i,j))

    dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
    magic = list(product(range(-2, 3), repeat=2))
    magic.remove((0, 0))
    for to_remove in dxdy:
        magic.remove(to_remove)
    
    # graph = {idx: deque() for idx in whites}
    # for idx in whites:
    #     x = idx[0]
    #     y = idx[1]
    #     for dx, dy in dxdy:
    #         if S[x+dx][y+dy] == ".":
    #             graph[idx].append((x+dx, y+dy))
    # graph2 = {idx: deque() for idx in whites}
    # for idx in whites:
    #     x = idx[0]
    #     y = idx[1]
    #     for mx, my in magic:
    #         if S[x+mx][y+my] == ".":
    #             graph2[idx].append((x+mx, y+my))
    
    def bfs(u,v):
        dist = [[INF] * (W+4) for _ in range(H+4)] #indexed from 1
        # seen = [[0] * (W+4) for _ in range(H+4)] #indexed from 1
        queue = deque()
        # seen[u][v] = 1
        dist[u][v] = 0
        queue.append((u,v))
        while queue:
            p, q = queue.popleft()
            # if not graph[(p,q)]:
            #     queue.popleft()
            #     continue
            # g,h = graph[(p,q)].popleft()
            # if seen[g][h]:
            #     continue
            # seen[g][h] = 1
            # dist[g][h] = min(dist[g][h], dist[p][q])
            for dx, dy in dxdy:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]:
                    dist[g][h] = dist[p][q]
                    queue.appendleft((g,h))
            for dx, dy in magic:
                g = p+dx
                h = q+dy
                if S[g][h]=="." and dist[g][h] > dist[p][q]+1:
                    dist[g][h] = dist[p][q]+1
                    queue.append((g,h))
            # dist[g][h] = min(dist[g][h], dist[p][q]+1)
            # queue.append((g,h))
        return dist

    D = bfs(ch, cw)
    ans = D[dh][dw]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

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)
            q.append(p)  
        print(telepo_cnt)
    print(-1)
                        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#-----モジュールの読み込み-----
from collections import deque

#-----入力受け取り-----
H ,W = map(int,input().split())
Sa,Sb = map(int,input().split())
Ga,Gb = map(int,input().split())
maze_list = [input() for i in range(H)]

Sa = Sa - 1
Sb = Sb - 1
Ga = Ga - 1
Gb = Gb - 1

que1 = []
que1.append((Sa,Sb))
quelist = []

#-----全ての座標に-1の値を代入-----

dist = [[10**9]*W for i in range(H)]
dist[Sa][Sb] = 0

#-----------動作

count = 0

while len(que1) > 0:
    que1 = deque(que1)
   
    while  len(que1) > 0:
        i,j = que1.popleft()
        for i2, j2 in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if not (0 <= i2 <= H-1 and 0 <= j2 <= W-1):
                continue
            if maze_list[i2][j2] == "." and dist[i2][j2] > count:
                dist[i2][j2] = count
                que1.append((i2,j2))
                quelist.append((i2,j2))
    
    que2 = deque(quelist)
    count += 1
    que1 = []
    
    while len(que2) > 0:
        i,j = que2.popleft()
        for di in range(-2,3):
            for dj in range(-2,3):
                i3 = i+di
                j3 = j+dj

                if not (0 <= i3 <= H-1 and 0 <= j3 <= W-1):
                    continue
                if maze_list[i3][j3] == "." and dist[i3][j3] > count:
                    dist[i3][j3] = count
                    que1.append((i3,j3))
                else:
                    pass
                

if dist[Ga][Gb] == 10**9:
    print(-1)
else:
    print(dist[Ga][Gb])

Submission status: Wrong Answer

Solution code:
#-----モジュールの読み込み-----
from collections import deque

#-----入力受け取り-----
H ,W = map(int,input().split())
Sa,Sb = map(int,input().split())
Ga,Gb = map(int,input().split())
maze_list = [input() for i in range(H)]

Sa = Sa - 1
Sb = Sb - 1
Ga = Ga - 1
Gb = Gb - 1

que1 = []
que1.append((Sa,Sb))
quelist = []

#-----全ての座標に-1の値を代入-----

dist = [[10**9]*W for i in range(H)]
dist[Sa][Sb] = 0

#-----------動作

count = 0

while len(que1) > 0:
    que1 = deque(que1)
   
    while  len(que1) > 0:
        i,j = que1.popleft()
        for i2, j2 in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if not (0 <= i2 <= H-1 and 0 <= j2 <= W-1):
                continue
            if maze_list[i2][j2] == "." and dist[i2][j2] > count:
                dist[i2][j2] = count
                quelist.append((i2,j2))
    
    que2 = deque(quelist)
    count += 1
    que1 = []
    
    while len(que2) > 0:
        i,j = que2.popleft()
        for di in range(-2,3):
            for dj in range(-2,3):
                i3 = i+di
                j3 = j+dj

                if not (0 <= i3 <= H-1 and 0 <= j3 <= W-1):
                    continue
                if maze_list[i3][j3] == "." and dist[i3][j3] > count:
                    dist[i3][j3] = count
                    que1.append((i3,j3))
                else:
                    pass
                

if dist[Ga][Gb] == 10**9:
    print(-1)
else:
    print(dist[Ga][Gb])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    def warp(cury2, curx2):
        curg2 = maze[cury2][curx2]
        nexts2 = []
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                sys.exit()
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                nexts2.append((nexty2, nextx2))
        return nexts2

    def dfs1(cury, curx, called):
        flag = False
        curg = maze[cury][curx]
        next_koho = []
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                next_koho += dfs1(nexty, nextx, True)
            elif nextg == '#':
                flag = True
        if called:
            if flag:
                next_koho += [(cury, curx)]
            return next_koho
        else:
            nexts = []
            if flag:
                next_koho += [(cury, curx)]
            for ne1 in next_koho:
                nexts += warp(ne1[0], ne1[1])
            if nexts:
                for ne in nexts:
                    dfs1(ne[0], ne[1], False)

    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
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'
    dfs1(ch, cw, False)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

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

CH -= 1
CW -= 1
DH -= 1
DW -= 1

def add(next, i, j, cost):
    if 0 <= i < H and 0 <= j < W and S[i][j] == ".":
        next.append((i, j, cost))

cost = [[10000] * W for _ in range(H)]
cost[CH][CW] = 0
prev = [[None] * W for _ in range(H)]
Q = []
# for i in range(H):
#     for j in range(W):
#         heapq.heappush(Q, (cost[i][j], i, j))
heapq.heappush(Q, (0, CH, CW))


while len(Q) > 0:
    _, i, j = heapq.heappop(Q)
    next = []
    for di in [-2, -1, 0, 1, 2]:
        for dj in [-2, -1, 0, 1, 2]:
            if di == 0 and dj == 0:
                continue
            elif di == 0 and abs(dj) == 1:
                add(next, i + di, j + dj, 0)
            elif abs(di) == 1 and dj == 0:
                add(next, i + di, j + dj, 0)
            else:
                add(next, i + di, j + dj, 1)
    for i2, j2, c in next:
        alt = cost[i][j] + c
        if cost[i2][j2] > alt:
            cost[i2][j2] = alt
            prev[i2][j2] = (i, j)
            heapq.heappush(Q, (alt, i2, j2))
#     if cost[DH][DW] != 10000:
#         print(cost[DH][DW])
#         exit()

# print(-1)
# exit()
ans = cost[DH][DW]
if ans == 10000:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    def warp(cury2, curx2):
        curg2 = maze[cury2][curx2]
        nexts2 = []
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                sys.exit()
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                nexts2.append((nexty2, nextx2))
        return nexts2

    def dfs1(cury, curx):
        flag = False
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                dfs1(nexty, nextx)
            elif nextg == '#':
                flag = True
        if flag:
            nexts = warp(cury, curx)
            if nexts:
                for ne in nexts:
                    dfs1(ne[0], ne[1])

    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
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'
    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
cy, cx = map(lambda x: int(x) - 1, input().split())
dy, dx = map(lambda x: int(x) - 1, input().split())
table = [list(input()) for _ in range(h)]
if cy == dy and cx == dx:
    print(0)
    exit()
if table[cy][cx] == "#" or table[dy][dx] == "#":
    print(-1)
    exit()
stack = deque()
stack.append([cy, cx])
table[cy][cx] = 0
step = [0, 1, 0, -1, 0]
step2 = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, 2],
         [0, -2], [0, 2], [1, -2], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1],
         [2, 2], [-1, -1], [-1, 1], [1, -1], [1, 1]]
while len(stack) > 0:
    cur = stack.pop()
    for [i, j] in step2:
        ny, nx = cur[0] + i, cur[1] + j
        if 0 <= ny < h and 0 <= nx < w and table[ny][nx] != "#":
            if table[ny][nx] == ".":
                table[ny][nx] = table[cur[0]][cur[1]] + 1
                stack.appendleft([ny, nx])
            elif table[ny][nx] > table[cur[0]][cur[1]] + 1:
                table[ny][nx] = table[cur[0]][cur[1]] + 1
                stack.appendleft([ny, nx])

    cur2 = cur
    for i in range(4):
        ny, nx = cur2[0] + step[i], cur2[1] + step[i + 1]
        if 0 <= ny < h and 0 <= nx < w and table[ny][nx] != "#":
            if table[ny][nx] == ".":
                table[ny][nx] = table[cur2[0]][cur2[1]]
                stack.appendleft([ny, nx])
            elif table[ny][nx] > table[cur2[0]][cur2[1]]:
                table[ny][nx] = table[cur2[0]][cur2[1]]
                stack.appendleft([ny, nx])
    if table[dy][dx] != ".":
        break
print(-1 if table[dy][dx] == "." else table[dy][dx])

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
cy, cx = map(lambda x: int(x) - 1, input().split())
dy, dx = map(lambda x: int(x) - 1, input().split())
table = [list(input()) for _ in range(h)]
if cy == dy and cx == dx:
    print(0)
    exit()
if table[cy][cx] == "#" or table[dy][dx] == "#":
    print(-1)
    exit()
stack = deque()
stack.append([cy, cx])
table[cy][cx] = 0
step = [0, 1, 0, -1, 0]
step2 = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, 2],
         [0, -2], [0, 2], [1, -2], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1],
         [2, 2], [-1, -1], [-1, 1], [1, -1], [1, 1]]
while len(stack) > 0:
    cur = stack.pop()
    for [i, j] in step2:
        ny, nx = cur[0] + i, cur[1] + j
        if 0 <= ny < h and 0 <= nx < w and table[ny][nx] != "#":
            if table[ny][nx] == ".":
                table[ny][nx] = table[cur[0]][cur[1]] + 1
                stack.appendleft([ny, nx])
            elif table[ny][nx] > table[cur[0]][cur[1]] + 1:
                table[ny][nx] = table[cur[0]][cur[1]] + 1
                stack.appendleft([ny, nx])

    cur2 = cur
    for i in range(4):
        ny, nx = cur2[0] + step[i], cur2[1] + step[i + 1]
        if 0 <= ny < h and 0 <= nx < w and table[ny][nx] != "#":
            if table[ny][nx] == ".":
                table[ny][nx] = table[cur2[0]][cur2[1]]
                stack.appendleft([ny, nx])
            elif table[ny][nx] > table[cur2[0]][cur2[1]]:
                table[ny][nx] = table[cur2[0]][cur2[1]]
                stack.appendleft([ny, nx])
    if table[ny][nx] != ".":
        break
print(-1 if table[dy][dx] == "." else table[dy][dx])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #print "fro_h, fro_w, q :: ",fro_h, fro_w, d[(fro_h, fro_w)], q
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        try:
            if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]
                q.appendleft((to_h, to_w))
        except: pass
        #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        try:
            if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.appendleft((to_h, to_w))
        except: pass

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = [int(s) for s in input().split()]
Ch, Cw = [int(s) for s in input().split()]
Dh, Dw = [int(s) for s in input().split()]

fields = [list(input()) for _ in range(H)]
fields_num = [[-1] * W for _ in range(H)]
ok_field = '.'


def get_search_obj(i, j):
    ret = []
    moving_range = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    for dx, dy in moving_range:
        if 0 <= i + dx <= (H - 1) and 0 <= j + dy <= (W - 1) and fields[i + dx][j + dy] == ok_field:
            ret.append((i + dx, j + dy))
    return ret


def bfs(sx, sy, f_num):
    start = (sx, sy)
    fields_num[sx][sy] = f_num
    dq = deque([start])
    visited = [[False] * W for _ in range(H)]
    while dq:
        sx, sy = dq.pop()
        for x, y in get_search_obj(sx, sy):
            if not visited[x][y]:
                dq.appendleft((x, y))
                visited[x][y] = True
                fields_num[x][y] = f_num


f_num = 0
for h in range(H):
    for w in range(W):
        if fields[h][w] == ok_field and fields_num[h][w] == -1:
            bfs(h, w, f_num)
            f_num += 1

edge = {}

for h in range(H):
    for w in range(W):
        if fields[h][w] == ok_field:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    if 0 < (h + dx) < H and 0 < (w + dy) < W and fields[h+dx][w+dy] == ok_field:
                        if fields_num[h][w] != fields_num[h + dx][w + dy] and not (fields_num[h][w], fields_num[h + dx][w + dy]) in edge.keys() and not (fields_num[h + dx][w + dy], fields_num[h][w]) in edge.keys():
                            edge[(fields_num[h][w], fields_num[h + dx][w + dy])] = 1


graph = [[] for _ in range(f_num)]
for i, j in edge.keys():
    graph[i].append(j)
    graph[j].append(i)

start_num = fields_num[Ch - 1][Cw - 1]
end_num = fields_num[Dh - 1][Dw - 1]

if start_num == end_num:
    print(0)
    exit()

visited = [False] * (f_num)

dq = deque([(start_num, 0)])
while(dq):
    search_obj, cnt = dq.pop()
    for candidate_obj in graph[search_obj]:
        if not visited[candidate_obj]:
            dq.appendleft((candidate_obj, cnt + 1))
            visited[candidate_obj]=True
            if candidate_obj == end_num:
                print(cnt + 1)
                exit()
print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

#visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf"))

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    #print "fro_h, fro_w, q :: ",fro_h, fro_w, q
    #print "fro_h, fro_w, q :: ",fro_h, fro_w
    #print "d :: ",d
    #歩いて移動
    try:
        for dh,dw in D:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]
                q.appendleft((to_h, to_w))
        #ワープ
        for dh,dw in WARP:
            to_h, to_w=fro_h+dh, fro_w+dw
            if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
                d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
                q.appendleft((to_h, to_w))
    except:
        pass

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

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

L=[]
for h in range(H):
    s=list(input())
    L.append(s)

def isOK(h,w):
    if 0<=h<H and 0<=w<W:
        if L[h][w]!="#":
            return True
        
    return False


DX=[1,0,-1,0]
DY=[0,1,0,-1]

que=deque([])
count=0
que.append((ch-1,cw-1, 0))
cost=[[-1]*W for _ in range(H)]
cost[ch-1][cw-1]=0
lis=[(ch-1,cw-1)]
while que:
    while que:
        t=que.popleft()
        x,y,now=t
        for i in range(4):
            dx,dy=DX[i],DY[i]
            nx=x+dx
            ny=y+dy
            if isOK(nx,ny):
                if cost[nx][ny]==-1:
                    cost[nx][ny]=now
                    que.append((nx,ny,now))
                    lis.append((nx,ny))
    for t in lis:
        x,y=t
        for dx in range(-2,3):
            for dy in range(-2,3):
                if dx==0 and dy==0:
                    continue
                nx=x+dx
                ny=y+dy
                if isOK(nx,ny):
                    if cost[nx][ny]==-1:
                        cost[nx][ny]=count+1
                        que.append((nx,ny,count+1))
    count+=1
    lis=[]

print(cost[dh-1][dw-1])

#print(cost)

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

L=[]
for h in range(H):
    s=list(input())
    L.append(s)

def isOK(h,w):
    if 0<=h<H and 0<=w<W and L[h][w]!="#":
        return True
    else:
        return False


DX=[1,0,-1,0]
DY=[0,1,0,-1]

que=deque([])
count=0
que.append((ch-1,cw-1, 0))
cost=[[-1]*W for _ in range(H)]
cost[ch-1][cw-1]=0
lis=[(ch-1,cw-1)]
while que:
    while que:
        t=que.popleft()
        x,y,now=t
        for i in range(4):
            dx,dy=DX[i],DY[i]
            nx=x+dx
            ny=y+dy
            if isOK(nx,ny):
                if cost[nx][ny]==-1:
                    cost[nx][ny]=now
                    que.append((nx,ny,now))
                    lis.append((nx,ny))
    for t in lis:
        x,y=t
        for dx in range(-2,3):
            for dy in range(-2,3):
                if dx==0 and dy==0:
                    continue
                nx=x+dx
                ny=y+dy
                if isOK(nx,ny):
                    if cost[nx][ny]==-1:
                        cost[nx][ny]=count+1
                        que.append((nx,ny,count+1))
    count+=1
    lis=[]

print(cost[dh-1][dw-1])

#print(cost)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    def warp(cury2, curx2):
        curg2 = maze[cury2][curx2]
        nexts2 = []
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.' and maze2[nexty2][nextx2]:
                maze[nexty2][nextx2] = curg2 + 1
                nexts2.append((nexty2, nextx2))
        return nexts2

    def dfs1(cury, curx):
        flag = False
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                dfs1(nexty, nextx)
            elif nextg == '#':
                flag = True
        if flag:
            maze2[cury][curx] = 0
            nexts = warp(cury, curx)
            if nexts:
                for ne in nexts:
                    dfs1(ne[0], ne[1])

    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
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze2 = [[1] * (w + 4) for _ in range(h + 4)]
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'
    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()