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:
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 dfs1(cur_coor):
        for i1 in range(4):
            nextx = cur_coor[1] + movex[i1]
            nexty = cur_coor[0] + movey[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(0)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = '-'
                dfs1((nexty, nextx))
            else:
                pass
    def dfs1a(cur_coor):
        for i1 in range(4):
            nextx = cur_coor[1] + movex[i1]
            nexty = cur_coor[0] + movey[i1]
            nextg = maze[nexty][nextx]
            if nextg == '.':
                maze[nexty][nextx] = '!'
                dfs1((nexty, nextx))
            else:
                pass
    def dfs2(cur_coor, r):
        for j1 in range(20):
            nextx = cur_coor[1] + warpx[j1]
            nexty = cur_coor[0] + warpy[j1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                rs.append(r + 1)
                return
            elif nextg == '.' or nextg == '-':
                maze[nexty][nextx] = '+'
                dfs2((nexty, nextx), r + 1)
            else:
                pass

    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 = []
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[dh][dw] = 'g'

    dfs1((ch, cw))
    #dfs1a((dh, dw))
    rs = []
    dfs2((ch, cw) ,0)
    if rs:
        print(min(rs))
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
R,C = map(int, input().split())
sy,sx = map(int, input().split())
gy,gx = map(int, input().split())
sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
c = [input() for i in range(R)]
visited = [[-1]*C for _ in range(R)]
warp = [[0]*C for _ in range(R)]
visited[sy][sx] = 0
Q = deque([[sy,sx]])
while Q:
  y,x = Q.popleft()
  if [y,x] == [gy,gx]:
    print(warp[y][x])
    exit()
  for i,j in [(0,1),(1,0),(-1,0),(0,-1)]:
    if y+i >= R or y+i < 0 or x+j >= C or x+j < 0:
      continue
    if c[y+i][x+j] == '.' and visited[y+i][x+j] == -1:
      visited[y+i][x+j] = visited[y][x]+1
      warp[y+i][x+j] = warp[y][x]
      Q.append([y+i,x+j])
    elif c[y+i][x+j] == '#':
      for k,l in [(0,1),(1,0),(-1,0),(0,-1),(-1,-1),(1,1),(1,-1),(-1,1)]:
 
        if 0 <= y+i+k < R and 0 <=  x+j+l < C:
          if c[y+i+k][x+j+l] == '.' and visited[y+i+k][x+j+l] == -1:
            warp[y+i+k][x+j+l] = warp[y][x]+1
            visited[y+i+k][x+j+l] = 0
            if [y+i+k,x+j+l] == [gy,gx]:
              print(warp[gy][gx])
              exit()
            Q.append([y+i+k,x+j+l])
print(-1)

Submission status: Wrong Answer

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

sh = Ch - 1
sw = Cw - 1

ans = 0

c = []
for i in range(H):
  c.append(str(input()))

Submission status: Wrong Answer

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

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    maze = list()
    arrived = [[0 for i in range(W)] for j in range(H)]
    arrived[Ch][Cw] = 1

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

    ans = 0
    for i in range(10**6):
        if Ch == Dh and Cw == Dw:
            print(ans)
            exit()

        update_flag = 0
        if Cw + 1 < W and maze[Ch][Cw + 1] == "." and arrived[Ch][Cw + 1] == 0:
            Cw += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch + 1 < H and maze[Ch + 1][Cw] == "." and arrived[Ch + 1][Cw] == 0:
            Ch += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Cw - 1 > 0 and maze[Ch][Cw - 1] == "." and arrived[Ch][Cw - 1] == 0:
            Cw -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch - 1 > 0 and maze[Ch - 1][Cw] == "." and arrived[Ch - 1][Cw] == 0:
            Ch -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1

        if update_flag == 0:
            find = 0
            for i in range(2, -3, -1):
                for j in range(2, -3, -1):
                    x = Cw + j
                    y = Ch + i

                    if 0 <= y < H and 0 <= x < W:
                        if y == Dh and x == Dw:
                            Ch = Dh
                            Cw = Dw
                            find = 1
                            ans += 1
                            update_flag = 1
                            break

                if find == 1:
                    break

            if update_flag == 0:
                find = 0
                for i in range(2, -3, -1):
                    for j in range(2, -3, -1):
                        x = Cw + j
                        y = Ch + i

                        if 0 <= y < H and 0 <= x < W:
                            if maze[y][x] == "." and arrived[y][x] == 0:
                                Ch = y
                                Cw = x
                                find = 1
                                ans += 1
                                break

                    if find == 1:
                        break

            if find == 0:
                print(-1)
                exit()

    if Ch != Dh and Cw != Dw:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main3()

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [0]*h
for i in range(h):
	s[i] =  input()
	s[i] = list(s[i])
 
def clear_maze(sx, sy, gx, gy, maze):
 
	INF = 100000000

	field_x_length = len(maze)
	field_y_length = len(maze[0])
	distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
#	distance = [[INF]*field_y_length]*field_x_length
 
	def bfs():
		count = 0
		queue = []

		queue.insert(0, (sx, sy))
 
		distance[sx][sy] = 0
 
		while len(queue):
			x, y = queue.pop()
 
			if x == gx and y == gy:
				break
 
			for i in range(0, 24):
				if i <= 3:
					nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
				if i >= 4:
					nx, ny = x + [-1, 1, 1, -1, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2][i-4], y + [1, 1, -1, -1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1][i-4]
				if (i <= 3 and 0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
					count += 1
					queue.insert(0, (nx, ny))
					distance[nx][ny] = distance[x][y]
				if (i >= 4 and count ==0 and 0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
					queue.insert(0, (nx, ny))
					distance[nx][ny] = distance[x][y] + 1
			count = 0
		return distance[gx][gy]
	return bfs()
if clear_maze(ch-1, cw-1, dh-1, dw-1, s) == 100000000:
	print(-1)
else:
	print(clear_maze(ch-1, cw-1, dh-1, dw-1, s))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

import heapq

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
import math
import numpy as np
import itertools

MAX = pow(10,10)
if __name__ == '__main__':
    H, W = list(map(lambda x: int(x), sys.stdin.readline().split()))
    Ch, Cw = list(map(lambda x: int(x), sys.stdin.readline().split()))
    Dh, Dw = list(map(lambda x: int(x), sys.stdin.readline().split()))
    
    Ch, Cw = Ch-1, Cw-1
    Dh, Dw = Dh-1, Dw-1
    S = []
    for i in range(H):
        S.extend(sys.stdin.readline().split())
    # print(S)

    ## CからDの縦横の距離を出す
    ## combinationsで組み合わせを出す
    ## その順路に何個#があるか探す、N連続#があればその順路を捨てる
    ## 一番低い順路を出力、なければ-1を出力
    h = Dh - Ch
    w = Dw - Cw

    # l1 = [[np.sign(h), 0]] * abs(h)
    # l2 = [[0, np.sign(w)]] * abs(w)
    l1 = ['h'] * abs(h)
    l2 = ['w'] * abs(w)
    Ugoki = {'h': [np.sign(h), 0], 'w': [0, np.sign(w)]}
    min = MAX
    for junro in list(set(itertools.permutations(l1+l2))):
        posx, posy = Ch, Cw
        tmp = 0
        lastx, lasty = posx, posy # ワープせずにおれた最後の場所
        for ugoki_id in junro:
            ugoki = Ugoki[ugoki_id]
            posx += ugoki[0]
            posy += ugoki[1]
            if S[posx][posy] == '#':
                tmp += 1
                if abs(lastx-posx) > 2 or abs(lasty-posy) > 2:
                    tmp = MAX
                    break
            else:
                lastx = posx
                lasty = posy
            
        if tmp < min:
            min = tmp

    if min == MAX:
        print(-1)
    else:
        print(min)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
Done = [[False]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([])
Q.append([C,0])
while Q:
  z, score = Q.popleft()
  x = z[0];y=z[1]
  #print(z,reach[x][y],Done[x][y])
  #if reach[x][y] < score:
    #print(z,score,"X")
  #  continue
  if Done[x][y]:
    #print(z,reach[x][y],"DONE")
    continue
  Done[x][y] = True
  #print(z,reach[x][y],Done[x][y])
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      if Done[nx][ny]: #すでに訪問済みならやらない
        continue
      Q.append([u,score])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      if Done[mx][my]:
        continue
      Q.append([p,score+1])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])

Submission status: Wrong Answer

Solution code:
from sys import *
H, W = map(int, stdin.readline().split())
personY, personX = map(int, stdin.readline().split())
gH, gW = map(int, stdin.readline().split())

grid = [list(stdin.readline().strip()) for x in range(H)]
visited = [[1001 for j in range(W)] for i in range(H)]
options = [(personY-1, personX-1)]

visited[personY-1][personX-1] = 0
while(options):
    y,x = options.pop()

    if y+1 < H and  grid[y+1][x] == ".":
        if visited[y+1][x] > visited[y][x]:
            options.append((y+1, x))
            visited[y+1][x] = visited[y][x]

    if  y-1 >= 0 and grid[y-1][x] == ".":
        if visited[y-1][x] > visited[y][x]:
            options.append((y-1, x))
            visited[y-1][x] = visited[y][x]

    if x+1 < W and grid[y][x+1] == ".":
        if visited[y][x+1] > visited[y][x]:
            options.append((y, x+1))
            visited[y][x+1] = visited[y][x]

    if x-1 >= 0 and grid[y][x-1] == ".":
        if visited[y][x-1] > visited[y][x]:
            options.append((y, x-1))
            visited[y][x-1] = visited[y][x]
   #-------------------------------------------
    for Y,X 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 x+X >= 0 and x+X < W and y+Y >= 0 and y+Y < H and grid[y+Y][x+X] == ".":
           if visited[y+Y][x+X] > visited[y][x] +1:
               options.append((y+Y, x+X))
               visited[y+Y][x+X] = visited[y][x]+1

print(-1 if visited[gH-1][gW-1] == 1001 else visited[gH-1][gW-1] )

Submission status: Wrong Answer

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
readline = sys.stdin.readline
S = [''.join([i for i in readline().split()]) for _ in range(h)]

sx, sy = ch-1, cw-1  # スタートの座標
gx, gy = dh-1, dw-1  # ゴールの座標

INF = 10**8
d = [[0]*w for i in range(h)]  # 各点までの最短距離の配列
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]  # 移動4方向のベクトル

# ワープ5*5の範囲のベクトル
dx_w = []
dy_w = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if abs(i) + abs(j) >= 2:
            dx_w.append(i)
            dy_w.append(j)
d_w = [[0]*w for i in range(h)]  # 各点までの最小ワープ回数


def bfs():
    que = queue.Queue()
    # 全ての点をINFで初期化（たどりつけないとINF）
    for i in range(h):
        for j in range(w):
            d[i][j] = INF
    # スタート地点をキューに入れ、その点の距離を0にする
    que.put([sx, sy])
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que.qsize():
        # キューの先頭を取り出す
        p = que.get()
        # 取り出してきた状態がゴールなら探索を辞める
        if p[0] == gx and p[1] == gy:
            break

        # 移動4方向をループ
        for i in range(len(dx)):
            # 移動した後の点を(nx, ny)とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定と既に訪れたことがあるかの判定(d[nx][ny] != INF なら訪れたことあり)
            if 0 <= nx and nx < h and 0 <= ny and ny < w and S[nx][ny] != '#' and d[nx][ny] == INF:
                # 移動できるならキューに入れ、その点の距離をpからの距離+1で確定する
                que.put([nx, ny])
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


def bfs_w():
    que = queue.Queue()
    # 全ての点をINFで初期化
    for i in range(h):
        for j in range(w):
            d_w[i][j] = INF
    # スタート地点をキューに入れ、その点の距離を0にする
    que.put([sx, sy])
    d_w[sx][sy] = 0

    # キューが空になるまでループ
    while que.qsize():
        # キューの先頭を取り出す
        p = que.get()
        # 取り出してきた状態がゴールなら探索を辞める
        if p[0] == gx and p[1] == gy:
            break

        for i in range(len(dx_w)):
            nx = p[0] + dx_w[i]
            ny = p[1] + dy_w[i]

            if 0 <= nx and nx < h and 0 <= ny and ny < w and S[nx][ny] != '#' and d_w[nx][ny] == INF:
                que.put([nx, ny])
                if d[nx][ny] == INF:
                    d_w[nx][ny] = d_w[p[0]][p[1]] + 1
                else:
                    d_w[nx][ny] = 0

    return d_w[gx][gy]


res = bfs()
if res != INF:
    print(0)
else:
    res = bfs_w()
    if res != INF:
        print(res)
    else:
        print(-1)

# print(d)
# print(d_w)

Submission status: Wrong Answer

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    color[x][y]="gray"
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if color[X][Y]=="white":
                    D[X][Y]=0
                    queue.append([X,Y])
                    color[X][Y]="gray"
        color[x][y]="black"

    return D


def Check():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if D[i][j]==inf:
                color[i][j]="black"

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if D[i][j]==0 and color[i][j]=="white":
                queue.append([i,j])
                color[i][j]="gray"
                while len(queue)>0:
                    x,y=queue.popleft()
                    for a,b in [[1,0],[0,1],[0,-1],[-1,0]]:
                        X,Y=x+a,y+b
                        if 0<=X<h and 0<=Y<w:
                            if color[X][Y]=="white":
                                color[X][Y]="gray"
                                queue.append([X,Y])
                    color[x][y]="black"
                point +=1

    return point


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
ans=True if D[G[0]-1][G[1]-1]!=inf else False
if ans==False:print(-1);exit()
print(Check()-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.append([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
def main():
    H,W = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    field = [input() for _ in range(H)]

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

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

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

    def worp():
        init_v = 10**5
        for y in range(H):
            for x in range(W):
                if field[y][x] == "#":
                    continue
                if wmap[y][x] >= 0:
                    continue

                w = init_v
                for my in range(-2, 3):
                    for mx in range(-2, 3):
                        px = x + mx
                        py = y + my
                        if 0 <= px < W and 0 <= py < H and field[py][px] == "." and wmap[py][px] >= 0:
                            w = min(w, wmap[py][px]+1)

                if w != init_v:
                    wmap[y][x] = w
                    d.append((x,y))


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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [input() for _ in range(H)]

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


dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = deque([(ch-1, cw-1, 0)])
used = {(ch-1, cw-1)}
warp = [(ch-1, cw-1, 0)]
ddd = []
for i in range(-2,3):
    for j in range(-2,3):
        if i == j == 0:
            continue
        ddd.append((i,j))    

idx = 0
while que:
    while que:
        s, t, cost = que.popleft()
        if s == dh-1 and t == dw-1: 
            print(cost)
            sys.exit()
            break
        for di, dj in dd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost))
            warp.append((xi,yj, cost)) 
            
    while idx <= len(warp) - 1:
        s, t, cost = warp[idx]
        for di, dj in ddd:
            xi = s + di; yj = t + dj
            if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == '#' or (xi, yj) in used:
                continue
            used.add((xi, yj))
            que.append((xi, yj, cost+1))
            warp.append((xi,yj, cost+1))
        idx += 1
        break

print(-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())
s=[]
ch-=1
cw-=1
dh-=1
dw-=1

for i in range(h):
    s.append(input())

d=[[0 for i in range(w)] for j in range(h)]
d=list(d)
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[-2,-2,-2,-2,-2,-1,-1,-1,-1, 0,0, 1, 1,1,1, 2, 2,2,2,2]
ddy=[-2,-1, 0, 1, 2,-2,-1, 1, 2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
ans=[]
d[ch][cw]=1
que=deque([[ch,cw,0,list(d)]])

while que:
    p=que.popleft()
    for i in range(20):
        if i<=3:
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if p[0]==dh and p[1]==dw:
                ans.append(p[2])            
            if nx>=0 and ny>=0 and nx<h and ny<w and s[nx][ny]!="#" and p[3][nx][ny]==0:
                p[3][nx][ny]=1
                que.append([nx,ny,p[2],list(p[3])])

if len(ans)==0:
    d=[[0 for i in range(w)] for j in range(h)]
    d=list(d)
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    ddx=[-2,-2,-2,-2,-2,-1,-1,-1,-1, 0,0, 1, 1,1,1, 2, 2,2,2,2]
    ddy=[-2,-1, 0, 1, 2,-2,-1, 1, 2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
    ans=[]
    d[ch][cw]=1
    que=deque([[ch,cw,0,list(d)]])
    while que:
        p=que.popleft()
        for i in range(20):
            if i<=3:
                nx=p[0]+dx[i]
                ny=p[1]+dy[i]
                if p[0]==dh and p[1]==dw:
                    ans.append(p[2])
                if nx>=0 and ny>=0 and nx<h and ny<w and s[nx][ny]!="#" and p[3][nx][ny]==0:
                    p[3][nx][ny]=1
                    que.append([nx,ny,p[2],list(p[3])])
            nx=p[0]+ddx[i]
            ny=p[1]+ddy[i]
            if p[0]==dh and p[1]==dw:
                ans.append(p[2])
                
            if nx>=0 and ny>=0 and nx<h and ny<w and s[nx][ny]!="#" and p[3][nx][ny]==0:
                p[3][nx][ny]=1
                que.append([nx,ny,p[2]+1,list(p[3])])
    if len(ans)==0:
        print(-1)
    else:
        print(min(ans))
else:
    print(min(ans))

Submission status: Wrong Answer

Solution code:
import queue

H,W=map(int,input().split())
C=[int(i)-1 for i in input().split()]
D=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())
    
    
dicA=[(-1,0),(1,0),(0,1),(0,-1),(0,0)]
dicB=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dicB.append((i,j))
    
vis=[[-1]*W for _ in [0]*H]

q=queue.Queue()
q.put((C[1],C[0]))
res=-1
mag=0
pre=[]

while 1:
    while not q.empty():
        x,y=q.get()
        if (x,y) in pre:
                pre.remove((x,y))
        for dx,dy in dicA:
            nx,ny=x+dx,y+dy
            if (nx,ny)==(D[1],D[0]):
                res=vis[ny][nx]
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]!='#':
                    q.put((nx,ny))
                    vis[ny][nx]=mag
        for dx,dy in dicB:
            nx,ny=x+dx,y+dy
            if 0<=nx<=W-1 and 0<=ny<=H-1:
                if vis[ny][nx]<0 and c[ny][nx]=='.':
                    if not (nx,ny) in pre:
                        pre.append((nx,ny))
    if res>-1:
        break
    if pre:
        mag+=1
        q.put(pre[0])
        pre=[]
    else:
        break

                
print(res)

Submission status: Wrong Answer

Solution code:
h,  w  = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []

for i in range(h):
    s.append(list(str(input())))

#縦
hSize = dh - ch
if hSize < 0:
    moveH = -1
else:
    moveH = 1
#横
wSize = dw - cw
if wSize < 0:
    moveW = -1
else:
    moveW = 1


currentH = ch - 1
currentW = cw - 1
warpCount = 0
errorH = False
errorW = False
while dh - 1 != currentH and dw - 1 != currentW and (errorH == False or errorW == False):
    while dh - 1 != currentH:
        if s[currentH + moveH][currentW] == "#":
            if 2 <= abs(dh - 1 - currentH):
                if s[currentH + moveH * 2][currentW] == ".":
                    currentH += moveH * 2
                    warpCount += 1
                else:
                    errorH = True
                    break
            else:
                errorH = True
                break
        else:
            currentH += moveH
        print(currentH, currentW)
        errorW = False

    while dw - 1 != currentW:
        if s[currentH][currentW + moveW] == "#":
            if 2 <= abs(dw - 1 - currentW):
                if s[currentH][currentW + moveW * 2] == ".":
                    currentW += moveW * 2
                    warpCount += 1
                else:
                    errorW = True
                    break
            else:
                errorW = True
                break
        else:
            currentW += moveW
        print(currentH, currentW)
        errorH == False

if errorH == True and errorW == True:
    warpCount = -1

print(warpCount)