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

INF = 10 ** 10
d = [INF] * (h*w)

A = 10**18
B = 10**9

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

d[(ch-1) * w + (cw-1)] = 0

T = ((-1,0), (1,0), (0,1), (0,-1))

q = [(ch-1)*A + (cw-1)*B + 0]
use = [0] * (h * w)

for x in q:
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B
    tmp = curh * w + curw
    if d[tmp] < cnt or use[tmp]: continue
    d[tmp] = cnt
    use[tmp] = 1

    for dh, dw in T:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt
            use[nh * w + nw] = 0
            q.append(nh*A + nw*B + cnt)
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt + 1
            use[nh * w + nw]
            q.append(nh*A + nw*B + cnt+1)

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

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

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

def bfs(ans):
  qu = deque([])
  qu.append((cw-1,ch-1))
  while qu:
    x,y=qu.popleft()
    
    if ans[y][x] != 0 or (y==ch-1 and x==cw-1):
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if (x==i and y==j):
            continue
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
              if (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1):
                qu.appendleft((i,j))
                ans[j][i] = ans[y][x]
              elif ans[j][i]>ans[y][x]+1 or ans[j][i]==-1:
                ans[j][i]=(ans[y][x]+1)
                qu.appendleft((i,j))

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

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

INF = h + w + 1
cost = [[INF] * w for _ in range(h)]
dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
dxy2 = []
dxy2 += [(i, j) for i in [-2, 2] for j in range(-2, 3)]
dxy2 += [(i, j) for j in [-2, 2] for i in range(-1, 2)]
dxy2 += [(-1, -1), (-1, +1), (+1, -1), (+1, +1)]
q = [(0, ch, cw)]
cost[ch][cw] = 0
while q:
    c, x, y = heappop(q)
    if cost[x][y] < c:
        continue

    if x == dh and y == dw:
        break

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c:
            continue
        cost[nx][ny] = c
        heappush(q, (c, nx, ny))

    for dx_, dy_ in dxy2:
        nx = x + dx_
        ny = y + dy_
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c + 1:
            continue
        cost[nx][ny] = c + 1
        heappush(q, (c + 1, nx, ny))

ans = -1 if cost[dh][dw] == INF else cost[dh][dw]
print(ans)
# print(*cost, sep='\n')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().strip().split())
Ch, Cw = map(int, input().strip().split())
Dh, Dw = map(int, input().strip().split())

maze = []

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

distances = {(i, j): 9999 for i in range(H) for j in range(W)}

movable = []
warpable = []

current = (Dh - 1, Dw - 1)
distances[current] = 0
d = 0
a = []

while True:

	i, j = current

	if i > 0 and maze[i - 1][j] == ".":
		if distances[(i - 1, j)] == 9999:
			distances[(i - 1, j)] = d
			movable.append((i - 1, j))
		if (i - 1, j) in warpable:
			distances[(i - 1, j)] = d
			movable.append((i - 1, j))
			warpable.remove((i - 1, j))

	if i < H - 1 and maze[i + 1][j] == ".":
		if distances[(i + 1, j)] > d:
			distances[(i + 1, j)] = d
			movable.append((i + 1, j))
		if (i + 1, j) in warpable:
			distances[(i + 1, j)] = d
			movable.append((i + 1, j))
			warpable.remove((i + 1, j))

	if j > 0 and maze[i][j - 1] == ".":
		if distances[(i, j - 1)] > d:
			distances[(i, j - 1)] = d
			movable.append((i, j - 1))
		if (i, j - 1) in warpable:
			distances[(i, j - 1)] = d
			movable.append((i, j - 1))
			warpable.remove((i, j - 1))

	if j < W - 1 and maze[i][j + 1] == ".":
		if distances[(i, j + 1)] > d:
			distances[(i, j + 1)] = d
			movable.append((i, j + 1))
		if (i, j + 1) in warpable:
			distances[(i, j + 1)] = d
			movable.append((i, j + 1))
			warpable.remove((i, j + 1))

	for _i in range(-2, 3):
		_i += i
		for _j in range(-2, 3):
			_j += j
			if _i >= 0 and _i < H and _j >= 0 and _j < W and maze[_i][_j] == "." and distances[(_i, _j)] == 9999:
				distances[(_i, _j)] = d + 1
				warpable.append((_i, _j))

	if movable:
		current = movable.pop()
		d = distances[current]
	elif warpable:
		current = warpable.pop()
		d = distances[current]
	else:
		break

	if current == (Ch - 1, Cw - 1):
		a.append(d)

if a:
	print(min(a))
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]


def bfs():
    for y in range(h):
        for x in range(w):
            if s[y][x]=='.':
                s[y][x]=math.inf


    s[c[0]-1][c[1]-1]=0
    que=deque([[c[0]-1,c[1]-1]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0<=y+i<h and 0<=x+j<w:
                nexty,nextx=y+i,x+j
                dist=s[nexty][nextx]
                if dist!='#':
                    if dist>s[y][x]:
                        s[nexty][nextx]=s[y][x]
                        que.append([nexty,nextx])
    que=deque([[c[0]-1,c[1]-1]])
    while que:
        y,x=que.popleft()
        for k,l in [(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)]:
            if 0<=y+k<h and 0<=x+l<w:
                warpy,warpx=y+k,x+l
                dist=s[warpy][warpx]
                if dist!='#':
                    if dist>s[y][x]+1:
                        s[warpy][warpx]=s[y][x]+1
                        que.append([warpy,warpx])
    if s[d[0]-1][d[1]-1]==math.inf:
        print(-1)
    else:
        print(s[d[0]-1][d[1]-1])

bfs()

Submission status: Wrong Answer

Solution code:
def copy(array):
    t = []
    for x in array:
      t.append(x)
    return t

def in2D(array, x):
    #print("検索 {}".format(x))
    for line in array:
        #print("line is {}".format(line))
        if x in line:
            return True
    return False

def interaction2D(x,y):
    xx = []
    for xi in x:
        for xij in xi:
            xx.append(xij)
    yy = []
    for yi in y:
        for yij in yi:
            yy.append(yij)
    return set(xx) & set(yy)

def walk(S, H, W, path):
    area = []
    area.append(path[0])
    while path:
        now = path.pop(0)
        if now[0] > 0:
            if S[now[0]-1][now[1]]=='.' and not (now[0]-1, now[1]) in area:
                path.append((now[0]-1,now[1]))
                area.append((now[0]-1,now[1]))
        if now[0] < H - 1:
            try:
                if S[now[0]+1][now[1]]=='.' and not (now[0]+1, now[1]) in area:
                    path.append((now[0]+1,now[1]))
                    area.append((now[0]+1,now[1]))
            except IndexError:
                print(now)
                print(H)
                
        if now[1] > 0:
            if S[now[0]][now[1]-1]=='.' and not (now[0], now[1]-1) in area:
                path.append((now[0],now[1]-1))
                area.append((now[0],now[1]-1))
        if now[1] < W - 1:
            if S[now[0]][now[1]+1]=='.' and not (now[0], now[1]+1) in area:
                path.append((now[0],now[1]+1))
                area.append((now[0],now[1]+1))
    return area

def warp(S, H, W, visit, area):
    #前後左右はいけるならwalkでいけるはずなので省略できる
    path = []
    while area:
        now = area.pop(0)
        #print(now)
        if now[0] > 0:
            if now[1] > 0:
                if S[now[0]-1][now[1]-1]=='.' and not in2D(visit, (now[0]-1, now[1]-1)):
                    path.append((now[0]-1,now[1]-1))
                    #print('add 左上')
            if now[1] < W - 1:
                if S[now[0]-1][now[1]+1]=='.' and not in2D(visit, (now[0]-1, now[1]+1)):
                    path.append((now[0]-1,now[1]+1))
                    #print('add 右上')
        if now[0] < H - 1:
            if now[1] > 0:
                if S[now[0]+1][now[1]-1]=='.' and not in2D(visit, (now[0]+1, now[1]-1)):
                    path.append((now[0]+1,now[1]-1))
                    #print('add 左下')
            if now[1] < W - 1:
                if S[now[0]+1][now[1]+1]=='.' and not in2D(visit, (now[0]+1, now[1]+1)):
                    path.append((now[0]+1,now[1]+1))
                    #print('add 右下')
        if now[0] > 1:
            if S[now[0]-2][now[1]]=='.' and not in2D(visit,(now[0]-2, now[1])):
                    path.append((now[0]-2,now[1]))
                    #print('add 二つ上')
            if now[1] > 0:
                if S[now[0]-2][now[1]-1]=='.' and not in2D(visit, (now[0]-2, now[1]-1)):
                    path.append((now[0]-2,now[1]-1))
                    #print('add 二つ上の左')
            if now[1] < W - 1:
                if S[now[0]-2][now[1]+1]=='.' and not in2D(visit, (now[0]-2, now[1]+1)):
                    path.append((now[0]-2,now[1]+1))
                    #print('add 二つ上の右')
        if now[0] < H - 2:
            if S[now[0]+2][now[1]]=='.' and not in2D(visit, (now[0]+2, now[1])):
                    path.append((now[0]+2,now[1]))
                    #print('add 二つ下')
            if now[1] > 0:
                if S[now[0]+2][now[1]-1]=='.' and not in2D(visit, (now[0]+2, now[1]-1)):
                    path.append((now[0]+2,now[1]-1))
                    #print('add 二つ下の左')
            if now[1] < W - 1:
                if S[now[0]+2][now[1]+1]=='.' and not in2D(visit, (now[0]+2, now[1]+1)):
                    path.append((now[0]+2,now[1]+1))
                    #print('add 二つ下の右')
        if now[1] > 2:
            if S[now[0]][now[1]-2]=='.' and not in2D(visit, (now[0], now[1]-2)):
                    path.append((now[0],now[1]-2))
                    #print('add 二つ左')
            if now[0] > 0:
                if S[now[0]-1][now[1]-2]=='.' and not in2D(visit, (now[0]-1, now[1]-2)):
                    path.append((now[0]-1,now[1]-2))
            if now[0] < H - 1:
                if S[now[0]+1][now[1]-2]=='.' and not in2D(visit, (now[0]+1, now[1]-2)):
                    path.append((now[0]+1,now[1]-2))
        if now[1] < W - 2:
            if S[now[0]][now[1]+2]=='.' and not in2D(visit, (now[0], now[1]+2)):
                    path.append((now[0],now[1]+2))
                    #print('add 二つ右')
            if now[0] > 0:
                if S[now[0]-1][now[1]+2]=='.' and not in2D(visit, (now[0]-1, now[1]+2)):
                    path.append((now[0]-1,now[1]+2))
            if now[0] < H - 1:
                if S[now[0]+1][now[1]+2]=='.' and not in2D(visit, (now[0]+1, now[1]+2)):
                    path.append((now[0]+1,now[1]+2))
    return path

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    S = []
    for i in range(H):
        S.append(list(input()))

    #cから歩いていける範囲
    #dから歩いていける範囲
    #二つがかぶっていれば歩いていける
    #二つがかぶっていなければワープが必要 1以上確定
    #範囲の狭い方の選択肢（#が接している）からワープして歩ける範囲
    #元の範囲、あるいは今まで歩けていた範囲は除外.
    #他方とかぶっているか判定
    #かぶっていなければ繰り返し

    c_visit = []
    d_visit = []
    
    c_path = [(Ch-1, Cw-1)]
    c_area = walk(S,H,W,c_path)
    #print(c_area)

    d_path = [(Dh-1, Dw-1)]
    d_area = walk(S,H,W,d_path)
    #print(d_area)

    c_visit.append(copy(c_area))
    d_visit.append(copy(d_area))

    ret = 0
    
    while True:
        #print('cArea is {}'.format(c_area))
        #print('dArea is {}'.format(d_area))
        if interaction2D(c_visit, d_visit):
            print(ret)
            return
        else:
            ret += 1
            if len(c_area) < len(d_area):
                c_path = warp(S,H,W,c_visit,c_area)
                #print('c warp {}'.format(c_path))
                if c_path == []:
                    d_path = warp(S,H,W,d_visit,d_area)
                    if d_path == []:
                        print(-1)
                        return
                    else:
                        d_area = walk(S,H,W,d_path)
                        d_visit.append(copy(d_area))
                        continue
                else:
                    c_area = walk(S,H,W,c_path)
                    c_visit.append(copy(c_area))
                    continue
            else:
                d_path = warp(S,H,W,d_visit,d_area)
                #print('d warp {}'.format(d_path))
                if d_path == []:
                    c_path = warp(S,H,W,c_visit,c_area)
                    if c_path == []:
                        print(-1)
                        return
                    else:
                        c_area = walk(S,H,W,c_path)
                        c_visit.append(copy(c_area))
                        continue
                else:
                    d_area = walk(S,H,W,d_path)
                    d_visit.append(copy(d_area))
                    continue
             
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = [(2,0),(2,1),(2,2),(1,2),(0,2),(-1,2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(2,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                        for dh, dw in self.move2:
                            r = (h + dh, w + dw)
                            broken_set.append((r, t))
                        continue
                    if q == goal:
                        return t
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    parent[q[0]][q[1]] = p
                    next_set.append((q, t))
            while broken_set != deque([]):
                q, t = broken_set.popleft()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  # 壁があったら進まない
                    continue
                if q == goal:
                    return t + 1
                parent[q[0]][q[1]] = 1
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


############################################################################################

from collections import deque
import sys
input = sys.stdin.readline



road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

WALL = -100
INI = -1
PASSED = 0

S = [[0] * w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        if tmp[j] == '#':
            S[i][j] = WALL
        else:
            S[i][j] = INI

S[Ch][Cw] = 0
direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]


def dfs(y, x, d):
    d.append((y, x))
    if y == Dh and x == Dw:
        print(S[y][x])
        exit()
    for dy, dx in direction:
        next_y = y + dy
        next_x = x + dx
        if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
            continue
        if S[next_y][next_x] == INI:
            #print("y = ", y, "x = ", x, "next_y = ", next_y, "next_x = ", next_x)
            S[next_y][next_x] = S[y][x]
            dfs(next_y, next_x, d)

def bfs(y, x, d):
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            next_y = y + dy
            next_x = x + dx
            if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
                continue
            if S[next_y][next_x] == INI:
                d.append((next_y, next_x))
                #print("S[u][x] = ", S[y][x])
                S[next_y][next_x] = S[y][x] + 1
    return False

def show(S):
    for y in range(h):
        for x in range(w):
            if S[y][x] == WALL:
                print("#", end="")
            elif S[y][x] == INI:
                print(".", end="")
            else:
                print(S[y][x], end="")
        print()

d = deque()
d.append((Ch, Cw))
while len(d):
    while(len(d)):
        y, x = d.popleft()
        d2 = deque()
        dfs(y, x, d2)

    while len(d2):
        y2, x2 = d2.popleft()
        #print("y2 = ", y2, "x2 = ", x2)
        #show(S)
        bfs(y2, x2, d)

print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(10000):
        for _ in range(100000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            for next_y in range(-2, 3):
                                for next_x in range(-2, 3):
                                    x, y = now_x + next_x, now_y + next_y
                                    if 0 <= x < w and 0 <= y < h:
                                        if c[y][x] not in "#=!":
                                            c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                            d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

imput = sys.stdin.readline

h,w = map(int,input().split())
sy,sx= map(int,input().split())
gy,gx= map(int,input().split())
S=[]



for i in range(h):
    S.append(input())
    
move = [[x,y] for x in range(-2,3) for y in range(-2,3)] 
walk = [[1,0],[-1,0],[0,1],[0,-1]]
dist = [[99999]*w for i in range(h)]
#visited = [[0]*w for i in range(h)]

q=deque()
q.append((sx-1,sy-1,0))
dist[sy-1][sx-1]=0
goaled = 0
endwarp=0
#while goaled==0:
while len(q):
    endwarp=0
    
    x,y,d = q.popleft()
    
    if x==gx-1 and y==gy-1:
        goaled=1
#        print(d)
#        break
    
#    print(x,y,d)
    for i in move:
        if 0<=x+i[0]<w and 0<=y+i[1]<h:
            if S[y+i[1]][x+i[0]]!="#" :
            
#                if visited[x+i[0]][y+i[1]] == 0:
                if dist[y+i[1]][x+i[0]] > d:
                
                    

                    if abs(i[0])+abs(i[1])==1:
                        dist[y+i[1]][x+i[0]] = d
                        q.append((x+i[0],y+i[1],d+0))
                    else:  
                        dist[y+i[1]][x+i[0]] = d+1
                        q.appendleft((x+i[0],y+i[1],d+1))
                        
                         
    
    

if goaled==0:
    print(-1)
    
else:
    print(dist[gy-1][gx-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

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

INF = h + w + 1
cost = [[INF] * w for _ in range(h)]
dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
dxy2 = []
dxy2 += [(i, j) for i in [-2, 2] for j in range(-2, 3)]
dxy2 += [(i, j) for j in [-2, 2] for i in range(-1, 2)]
dxy2 += [(-1, -1), (-1, +1), (+1, -1), (+1, +1)]
q = [(0, ch, cw)]
cost[ch][cw] = 0
while q:
    c, x, y = heappop(q)
    if cost[x][y] < c:
        continue

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] < c:
            continue
        cost[nx][ny] = c
        heappush(q, (c, nx, ny))

    for dx_, dy_ in dxy2:
        nx = x + dx_
        ny = y + dy_
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] < c + 1:
            continue
        cost[nx][ny] = c + 1
        heappush(q, (c + 1, nx, ny))

ans = -1 if cost[dh][dw] == INF else cost[dh][dw]
print(ans)
# print(*cost, sep='\n')

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(5000):
        for _ in range(100000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            for next_y in range(-2, 3):
                                for next_x in range(-2, 3):
                                    x, y = now_x + next_x, now_y + next_y
                                    if 0 <= x < w and 0 <= y < h:
                                        if c[y][x] not in "#=!":
                                            c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                            d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
c = [int(i) + 1 for i in input().split()]
d = [int(i) + 1 for i in input().split()]

s = []
s.append('#'*(W+4))
s.append('#'*(W+4))
for i in range(H):
    a = input()
    s.append('##' + a + '##')
s.append('#'*(W+4))
s.append('#'*(W+4))

q = deque([]) # 探索開始点
qq = deque([])
q.append((c[0], c[1], 0))
visited = [[False for __ in range(W+4)] for _ in range(H+4)]

while q:
    xx, yy, kaisuu = q.popleft()
    if visited[xx][yy] == True:
        continue
    qq.append((xx, yy, kaisuu))
    ls = []
    while qq:
        x, y, kaisuu = qq.popleft()
        visited[x][y] = True
        ls.append((x, y, kaisuu))
        if x == d[0] and y == d[1]:
            print(kaisuu)
            sys.exit()
        if s[x+1][y] == '.' and visited[x+1][y] == False:
            qq.append((x+1, y, kaisuu))
        if s[x-1][y] == '.' and visited[x-1][y] == False:
            qq.append((x-1, y, kaisuu))
        if s[x][y+1] == '.' and visited[x][y+1] == False:
            qq.append((x, y+1, kaisuu))
        if s[x][y-1] == '.' and visited[x][y-1] == False:
            qq.append((x, y-1, kaisuu))
    for u in ls:
        a, b, e = u
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if abs(i) == 1 and abs(j) == 1:
                    continue
                if s[a+i][b+j] == '.' and visited[a+i][b+j] == False:
                    q.appendleft((a+i, b+j, e+1))
print(-1)

Submission status: Wrong Answer

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


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

from collections import deque
q = deque()
q.append((ch, cw, 0))
while q:
    h, w, c = q.popleft()
    for hh, ww in y:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == ".":
            if used[h+hh][w+ww] < 0 or used[h+hh][w+ww] > c:
                used[h+hh][w+ww] = c
                q.append((h+hh, w+ww, c))
    for hh, ww in x:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == ".":
            if used[h+hh][w+ww] < 0 or used[h+hh][w+ww] > c+1: 
                used[h+hh][w+ww] = c + 1
                q.append((h+hh, w+ww, c+1))
if used[dh][dw] < 0:
    print(-1)
else:
    print(used[dh][dw])

Submission status: Wrong Answer

Solution code:
import sys, math

# input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [[1 if s=='.' else 0 for s in input()] for _ in range(H)]
costs = [[math.inf]*W for _ in range(H)]
costs[Ch-1][Cw-1] = 0
que = [(0, Ch-1, Cw-1)]
next_que = []

while len(next_que)>0 or len(que)>0:
    while len(que)>0:
        c, h, w = que.pop(0)
        for i, j in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
            if i < 0 or j < 0 or i>=H or j>=W:
                continue
            if i == Dh - 1 and j == Dw - 1:
                print(c)
                sys.exit()
            if S[i][j] and costs[i][j] > c:
                costs[i][j] = c
                que.append((c, i, j))
        for dw in [-2, -1, 0, 1, 2]:
            for dh in [-2, -1, 0, 1, 2]:
                if w+dw < 0 or h+dh < 0 or w+dw>=W or h+dh>=H:
                    continue
                if w+dw == Dw-1 and h+dh==Dh-1:
                    print(c+1)
                    sys.exit()
                if S[h+dh][w+dw] and costs[h+dh][w+dw] > c+1:
                    costs[h+dh][w+dw] = c+1
                    next_que.append((c+1, h+dh, w+dw))
    que = next_que
    next_que = []

print(-1)