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 sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

#setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def pprint(M):
	for row in M:
		print(row)
	print("~~~")


def main():
	rows, cols = rli()
	r0, c0 = rli()
	r0 -= 1
	c0 -= 1
	r1, c1 = rli()
	r1 -= 1
	c1 -= 1
	G = []
	for _ in range(rows):
		s = rll()[0]
		row = []
		for c in s: 
			if c == ".":
				row.append(0)
			else:
				row.append(1)
		G.append(row)	
	
	inside = lambda r, c: r>=0 and c>=0 and r<rows and c<cols

	ans = INF
	cnt = 0
	def do_bfs():
		nonlocal ans, cnt
		seen = defaultdict(lambda: False)
		Q = deque() #(r, c, num_magics_used)
		Q.appendleft((r0, c0, 0))
		while Q:
			for _ in range(len(Q)):
				r, c, magics = Q.pop()
				cnt += 1
				if cnt > 100000: return
				if r1 == r and c1 == c: 
					ans = min(ans, magics)
				for dr in range(-2, 3):
					for dc in range(-2, 3):
						nr, nc = r + dr, c + dc 
						if not inside(nr, nc) or seen[(nr, nc)] or G[nr][nc] == 1: continue
						n_magics = magics 
						if abs(dr) + abs(dc) > 1:
							n_magics += 1
						Q.appendleft((nr, nc, n_magics))
	do_bfs()
	print(ans if ans < INF else -1)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

#setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def pprint(M):
	for row in M:
		print(row)
	print("~~~")


def main():
	rows, cols = rli()
	r0, c0 = rli()
	r0 -= 1
	c0 -= 1
	r1, c1 = rli()
	r1 -= 1
	c1 -= 1
	G = []
	for _ in range(rows):
		s = rll()[0]
		row = []
		for c in s: 
			if c == ".":
				row.append(0)
			else:
				row.append(1)
		G.append(row)	
	
	inside = lambda r, c: r>=0 and c>=0 and r<rows and c<cols

	ans = INF
	cnt = 0
	def do_bfs():
		nonlocal ans, cnt
		seen = defaultdict(lambda: False)
		Q = deque() #(r, c, num_magics_used)
		Q.appendleft((r0, c0, 0))
		while Q:
			for _ in range(len(Q)):
				r, c, magics = Q.pop()
				cnt += 1
				if cnt > 10000: return
				if r1 == r and c1 == c: 
					ans = min(ans, magics)
				for dr in range(-2, 3):
					for dc in range(-2, 3):
						nr, nc = r + dr, c + dc 
						if not inside(nr, nc) or seen[(nr, nc)] or G[nr][nc] == 1: continue
						n_magics = magics 
						if abs(dr) + abs(dc) > 1:
							n_magics += 1
						Q.appendleft((nr, nc, n_magics))
	do_bfs()
	print(ans if ans < INF else -1)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    h, w = map(int, input().split())
    S = list(map(lambda x: int(x) + 1, input().split()))
    G = list(map(lambda x: int(x) + 1, input().split()))
    A = ['#' * (w + 4)] * 2 + ['##' + input() + '##' for _ in range(h)] + ['#' * (w + 4)] * 2
    INF = 100000
    score = [INF] * ((w + 2) * (h + 2))
    score[S[0] * w + S[1]] = 0
    stack = deque([S])
    walk = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    warp = [[i, j] for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in walk + [[0, 0]]]
    visited = set()
    while stack:
        y, x = stack.popleft()
        if (y, x) in visited:
            continue
        else:
            visited.add((y, x))
        for i, j in walk:
            X = x + j
            Y = y + i
            if A[Y][X] == '#': continue
            if score[(ind := Y * w + X)] > (s := score[y * w + x]):
                stack.appendleft([Y, X])
                score[ind] = s
        for i, j in warp:
            X = x + j
            Y = y + i
            if A[Y][X] == '#': continue
            if score[(ind := Y * w + X)] > (s := score[y * w + x] + 1):
                stack.append([Y, X])
                score[ind] = s
    print(ans if (ans := score[G[0] * w + G[1]]) != INF else -1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
start= tuple(map(int, input().split()))
goal = tuple(map(int, input().split()))
cost = {(i,j): h * w for i in range(1, h + 1) for j in range(1, w + 1)}
cost[start] = 0
deque = [start]
maze = {}

for i in range(h):
    row = input()
    for j in range(len(row)):
        maze[(i+1, j+1)] = row[j]


def check_bound(cor):
    if cor[0] < 1 or h < cor[0]:
        return False
    elif cor[1] < 1 or w < cor[1]:
        return False
    else:
        return True


def add(cor1, cor2):
    return (cor1[0] + cor2[0], cor1[1] + cor2[1])


jump_direction = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]
jump_direction.remove((0,0))

while len(deque) != 0:
    cor = deque.pop(0)
    for dir in [(1,0),(-1,0),(0,1),(-1,0)]:
        new_cor = add(cor , dir)
        if check_bound(new_cor):
            if maze[new_cor] == '.' and cost[new_cor] > cost[cor]:
                cost[new_cor] = cost[cor]
                deque.insert(0, new_cor)

    for dir in jump_direction:
        new_cor = add(cor , dir)
        if check_bound(new_cor):
            if maze[new_cor] == '.' and cost[new_cor] > cost[cor] + 1:
                cost[new_cor] = cost[cor] + 1
                deque.append(new_cor)

if cost[goal] == h * w:
    print(-1)
else:
    print(cost[goal])

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())
stage = ['#'+input()+'#' for i in range(h)]
stage = ['#'*(w+2)] + stage + ['#'*(w+2)]
queue = deque([])
check = [(ch,cw)]
searched_temp = [(ch,cw)]
count = 0

while True:
  searched = searched_temp
  
  for st in searched_temp:
    queue.append(st)
    while len(queue):
      v = queue.popleft()
      if v == (dh,dw):
        print(count)
        exit()

      if stage[v[0]-1][v[1]] == '.' and (v[0]-1,v[1]) not in check:
        queue.append((v[0]-1,v[1]))
        check.append((v[0]-1,v[1]))
        searched.append((v[0]-1,v[1]))
      if stage[v[0]+1][v[1]] == '.' and (v[0]+1,v[1]) not in check:
        queue.append((v[0]+1,v[1]))
        check.append((v[0]+1,v[1]))
        searched.append((v[0]+1,v[1]))
      if stage[v[0]][v[1]-1] == '.' and (v[0],v[1]-1) not in check:
        queue.append((v[0],v[1]-1))
        check.append((v[0],v[1]-1))
        searched.append((v[0],v[1]-1))
      if stage[v[0]][v[1]+1] == '.' and (v[0],v[1]+1) not in check:
        queue.append((v[0],v[1]+1))
        check.append((v[0],v[1]+1))
        searched.append((v[0],v[1]+1))
  
  print(searched)
  count += 1
  searched_temp = []
  for s in searched:
    for i in range(-2,3):
      for j in range(-2,3):
        y = s[0] + i
        x = s[1] + j
        if 1 <= y and y <= h and 1 <= x and x <= w and stage[y][x] == '.' and (y,x) not in check:
          check.append((y,x))
          searched_temp.append((y,x))
  if len(searched_temp) == 0:
    print(-1)
    break

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    h, w = map(int, input().split())
    S = list(map(lambda x: int(x) + 1, input().split()))
    G = list(map(lambda x: int(x) + 1, input().split()))
    A = [['#'] * (w + 4)] * 2 + [['#', '#'] + list(input()) + ['#', '#'] for _ in range(h)] + [['#'] * (w + 4)] * 2
    INF = 10000
    score = [[INF] * (w + 2) for _ in range(h + 2)]
    score[S[0]][S[1]] = 0
    stack = deque([S])
    dxy = ((1, 0), (-1, 0), (0, 1), (0, -1))
    visited = set()
    while stack:
        y, x = stack.popleft()
        if (y, x) in visited:
            continue
        else:
            visited.add((y, x))
        for dx, dy in dxy:
            X = x + dx
            Y = y + dy
            if A[Y][X] == '#': continue
            if score[Y][X] > (s := score[y][x]):
                stack.appendleft([Y, X])
                score[Y][X] = s
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + j
                Y = y + i
                if A[Y][X] == '#': continue
                if score[Y][X] > (s := score[y][x] + 1):
                    stack.append([Y, X])
                    score[Y][X] = s
    print(ans if (ans := score[G[0]][G[1]]) != INF else -1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

def solve2(s_flag,h,w,goal_h,goal_w,que):
    while que:
        ch,cw=que.popleft()
        ## 現在地のコスト
        now=s_flag[ch][cw]
        for d_h,d_w in [(1,0),(0,1),(0,-1),(-1,0)]:
            ## 迷路の外に出ない
            if ch+d_h<0 or h-1<ch+d_h:
                continue
            if cw+d_w<0 or w-1<cw+d_w:
                continue
            ## 進行方向のコスト
            dest=s_flag[ch+d_h][cw+d_w]
            if dest=='#': ## wall
                # jump=[(d_h*2,d_w*2)]
                # for tmp in range(1,3):
                #     jump.append((d_h*2+d_w*tmp,d_w*2+d_h*tmp))
                #     jump.append((d_h*2-d_w*tmp,d_w*2-d_h*tmp))
                jump=[  (d_h+d_w,d_w+d_h),
                        (d_h-d_w,d_w-d_h),
                        (d_h*2,d_w*2),
                        (d_h*2+d_w,d_w*2+d_h),
                        (d_h*2-d_w,d_w*2-d_h),
                        (d_h*2+d_w*2,d_w*2+d_h*2)]
                for jump_h,jump_w in jump:
                    if ch+jump_h<0 or h-1<ch+jump_h:
                        continue
                    if cw+jump_w<0 or w-1<cw+jump_w:
                        continue
                    ## ワープ先のコスト
                    dest_jump=s_flag[ch+jump_h][cw+jump_w]
                    if dest_jump!='#' and dest_jump>now+1:
                        s_flag[ch+jump_h][cw+jump_w]=now+1
                        que.append([ch+jump_h,cw+jump_w])
            else: ## 道
                if dest>now:
                    s_flag[ch+d_h][cw+d_w]=now
                    que.append([ch+d_h,cw+d_w])
    # for i in range(h):
    #     print(s_flag[i])
    return s_flag[goal_h][goal_w]

def main():
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch,cw=ch-1,cw-1
    dh,dw=map(int,input().split())
    dh,dw=dh-1,dw-1
    s=[input() for i in range(h)]
    ## .=0 #=2 visited=1 goal=-1
    # s_flag=[[0 if s[i][j]=='.' else 2 for j in range(w)] for i in range(h)]
    # s_flag[ch][cw]=1
    # s_flag[dh][dw]=-1
    # ans=solve(s_flag,h,w,ch,cw,0)
    # if not ans:
    #     ans=-1
    # else:
    #     ans=ans[-1][2]
    # return ans
    ## .=inf #=# visited=cost
    s_flag=[[math.inf if s[i][j]=='.' else '#' for j in range(w)] for i in range(h)]
    s_flag[ch][cw]=0
    que=deque([[ch,cw]])
    ans=solve2(s_flag,h,w,dh,dw,que)
    if ans==math.inf:
        ans=-1
    return ans

if __name__=='__main__':
    ans=main()
    print(ans)

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

# 0始まりにあわせる
CH -= 1; CW -= 1; DH -= 1; DW -= 1

# マップの上下左右２ずつ# で埋める
# 左右から
for i in range(H):
    S[i] = ['#']*2 + S[i] + ['#']*2
# 上下を埋める
S = [['#']*(W+4)]*2 + S + [['#']*(W+4)]*2

# マップの上下左右に＋２ずつ# を付けたので、スタート、ゴール位置の調整
CH += 2; CW += 2; DH += 2; DW += 2


walk = [(0,-1),(-1,0),(0,1),(1,0)]
warp = [(-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)]

walkQue = deque() # 歩いて行くところ
warpQue = deque() # ワープして行くところ
tempQue = deque()

walkQue.append((CH,CW)) # スタート位置をキューに追加
S[CH][CW] = 0 # スタート位置はワープ0回で行ける。
tempQue.append((CH,CW))

while len(walkQue) > 0:
    x,y = walkQue.pop()
    # 歩いて行けるところを調べる
    for dx,dy in walk:
        if S[x+dx][y+dy] == '.':
            walkQue.append((x+dx,y+dy))
            tempQue.append((x+dx,y+dy))
            S[x+dx][y+dy] = S[x][y]
    # 歩きつくしたらワープで行けるところを調べる
    if len(walkQue) == 0:
        for x,y in tempQue:
            for dx,dy in warp:
                if S[x+dx][y+dy] == '.':
                    warpQue.append((x+dx,y+dy))
                    S[x+dx][y+dy] = S[x][y] + 1
    # 歩いて行けるところが無かったら、ワープキューをコピー
    if len(walkQue) == 0:
        walkQue = warpQue
        tempQue.clear()
    

# 表示させるためのテスト関数
# for s in S:
#     for i in range(len(s)):
#         print(s[i],end='')
#     print()

if S[DH][DW] == '.':
    print(-1)
else:
    print(S[DH][DW])

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

def solve2(s_flag,h,w,goal_h,goal_w,que):
    while que:
        ch,cw=que.popleft()
        now=s_flag[ch][cw] ## 現在地のコスト
        for dh,dw in [(1,0),(0,1),(0,-1),(-1,0)]:
            ## 迷路の外に出ない
            if ch+dh<0 or h-1<ch+dh:
                continue
            if cw+dw<0 or w-1<cw+dw:
                continue
            dest=s_flag[ch+dh][cw+dw] ## 進行方向のコスト
            if dest=='#': ## wall
                # jump=[(dh*2,dw*2)]
                # for tmp in range(1,3):
                #     jump.append((dh*2+dw*tmp,dw*2+dh*tmp))
                #     jump.append((dh*2-dw*tmp,dw*2-dh*tmp))
                jump=[(dh*2,dw*2),(dh*2+dw,dw*2+dh),(dh*2-dw,dw*2-dh),(dh*2+dw*2,dw*2+dh*2)]
                for jump_h,jump_w in jump:
                    if ch+jump_h<0 or h-1<ch+jump_h:
                        continue
                    if cw+jump_w<0 or w-1<cw+jump_w:
                        continue
                    dest_jump=s_flag[ch+jump_h][cw+jump_w]  ## ワープ先のコスト
                    if dest_jump!='#' and dest_jump>now+1:
                        s_flag[ch+jump_h][cw+jump_w]=now+1
                        que.append([ch+jump_h,cw+jump_w])
            else: ## 道
                if dest>now:
                    s_flag[ch+dh][cw+dw]=now
                    que.append([ch+dh,cw+dw])
    return s_flag[goal_h][goal_w]

def solve(s_flag,h,w,ch,cw,jump_cnt):
    # print(ch,cw,jump_cnt)
    # print(s_flag)
    if s_flag[ch][cw]==-1:
        return [(ch,cw,jump_cnt)]
    s_flag[ch][cw]=1 ## 1:visited
    for dh,dw in [(1,0),(0,1),(0,-1),(-1,0)]:
        if ch+dh<0 or h-1<ch+dh:
            continue
        if cw+dw<0 or w-1<cw+dw:
            continue
        if s_flag[ch+dh][cw+dw]==2: ## 2:wall
            jump=[(dh*2,dw*2)]
            for tmp in range(1,3):
                jump.append((dh*2+dw*tmp,dw*2+dh*tmp))
                jump.append((dh*2-dw*tmp,dw*2-dh*tmp))
            for jump_h,jump_w in jump:
                if ch+jump_h<0 or h-1<ch+jump_h:
                    continue
                if cw+jump_w<0 or w-1<cw+jump_w:
                    continue
                if s_flag[ch+jump_h][cw+jump_w]<=0:
                    route=solve(s_flag,h,w,ch+jump_h,cw+jump_w,jump_cnt+1)
                    if route:
                        return [(ch,cw,jump_cnt)]+route
        elif s_flag[ch+dh][cw+dw]<=0: ## 0:road -1:goal
            route=solve(s_flag,h,w,ch+dh,cw+dw,jump_cnt)
            if route:
                return [(ch,cw,jump_cnt)]+route


def main():
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch,cw=ch-1,cw-1
    dh,dw=map(int,input().split())
    dh,dw=dh-1,dw-1
    s=[input() for i in range(h)]
    ## .=0 #=2 visited=1 goal=-1
    # s_flag=[[0 if s[i][j]=='.' else 2 for j in range(w)] for i in range(h)]
    # s_flag[ch][cw]=1
    # s_flag[dh][dw]=-1
    # ans=solve(s_flag,h,w,ch,cw,0)
    # if not ans:
    #     ans=-1
    # else:
    #     ans=ans[-1][2]
    # return ans
    ## .=inf #=# visited=cost
    s_flag=[[math.inf if s[i][j]=='.' else '#' for j in range(w)] for i in range(h)]
    s_flag[ch][cw]=0
    que=deque([[ch,cw]])
    ans2=solve2(s_flag,h,w,dh,dw,que)
    if ans2==math.inf:
        ans2=-1
    return ans2

if __name__=='__main__':
    ans=main()
    print(ans)

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

# 0始まりにあわせる
CH -= 1; CW -= 1; DH -= 1; DW -= 1

# マップの上下左右２ずつ# で埋める
# 左右から
for i in range(H):
    S[i] = ['#']*2 + S[i] + ['#']*2
# 上下を埋める
S = [['#']*(W+4)]*2 + S + [['#']*(W+4)]*2

# マップの上下左右に＋２ずつ# を付けたので、スタート、ゴール位置の調整
CH += 2; CW += 2; DH += 2; DW += 2


walk = [(0,-1),(-1,0),(0,1),(1,0)]
warp = [(-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)]

walkQue = deque() # 歩いて行くところ
warpQue = deque() # ワープして行くところ

walkQue.append((CH,CW)) # スタート位置をキューに追加
S[CH][CW] = 0 # スタート位置はワープ0回で行ける。

while len(walkQue) > 0:
    x,y = walkQue.pop()
    # 歩いて行けるところを調べる
    for dx,dy in walk:
        if S[x+dx][y+dy] == '.' or S[x+dx][y+dy] == S[x][y]+1:
            walkQue.append((x+dx,y+dy))
            S[x+dx][y+dy] = S[x][y]
    # ワープで行けるところを調べる
    for dx,dy in warp:
        if S[x+dx][y+dy] == '.':
            warpQue.append((x+dx,y+dy))
            S[x+dx][y+dy] = S[x][y] + 1
    # 歩いて行けるところが無かったら、ワープキューをコピー
    if len(walkQue) == 0:
        walkQue = warpQue
    

# 表示させるためのテスト関数
# for s in S:
#     for i in range(len(s)):
#         print(s[i],end='')
#     print()

if S[DH][DW] == '.':
    print(-1)
else:
    print(S[DH][DW])

Submission status: Wrong Answer

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
y=0

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

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e:
      f.append(e)


while len(c)>0:
  ch,cw=c[0]
  c.pop(0)
  if a[ch][cw]==".":
    a[ch][cw]=str(warp)
  if ch==dh-1 and cw==dw-1:
    c=[]
  else:
    ch1,cw1=ch-1,cw
    def1()
    ch1,cw1=ch+1,cw
    def1()
    ch1,cw1=ch,cw-1
    def1()
    ch1,cw1=ch,cw+1
    def1()

    for i in range(5):
      ch2=ch-2+i
      for j in range(5):
        cw2=cw-2+j
        def2()
  if len(c)==0:
    for i in f:
      if i not in d:
      	c.append(i)
    f=[]
    warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Wrong Answer

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
y=0

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

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e:
      f.append(e)

while len(c)+len(f)>0 :
  while len(c)>0:
    ch,cw=c[0]
    c.pop(0)
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
    if ch==dh-1 and cw==dw-1:
      c,f=[],[]
    else:
      ch1,cw1=ch-1,cw
      def1()
      ch1,cw1=ch+1,cw
      def1()
      ch1,cw1=ch,cw-1
      def1()
      ch1,cw1=ch,cw+1
      def1()

      for i in range(5):
        ch2=ch-2+i
        for j in range(5):
          cw2=cw-2+j
          def2()
  for i in f:
    if i not in d:
      c.append(i)
  f=[]
  warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Wrong Answer

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
y=0

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

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e:
      f.append(e)

while len(c)+len(f)>0 :
  while len(c)>0:
    ch,cw=c[0]
    c.pop(0)
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
    if ch==dh-1 and cw==dw-1:
      c=[]
    else:
      ch1,cw1=ch-1,cw
      def1()
      ch1,cw1=ch+1,cw
      def1()
      ch1,cw1=ch,cw-1
      def1()
      ch1,cw1=ch,cw+1
      def1()

      for i in range(5):
        ch2=ch-2+i
        for j in range(5):
          cw2=cw-2+j
          def2()
  for i in f:
    if i not in d:
      c.append(i)
  f=[]
  warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Wrong Answer

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)
y=0

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

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e:
      f.append(e)

while len(c)+len(f)>0 :
  while len(c)>0:
    ch,cw=c[0]
    c.pop(0)
    if ch==dh-1 and cw==dw-1:
      c=[]
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
    ch1,cw1=ch-1,cw
    def1()
    ch1,cw1=ch+1,cw
    def1()
    ch1,cw1=ch,cw-1
    def1()
    ch1,cw1=ch,cw+1
    def1()

    for i in range(5):
      ch2=ch-2+i
      for j in range(5):
        cw2=cw-2+j
        def2()
  for i in f:
    if i not in d:
      c.append(i)
  f=[]
  warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Wrong Answer

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)

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

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e:
      f.append(e)

while len(c)>0 or len(f)>0:
  while len(c)>0:
    ch,cw=c[0]
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
    c.pop(0)
    ch1,cw1=ch-1,cw
    def1()
    ch1,cw1=ch+1,cw
    def1()
    ch1,cw1=ch,cw-1
    def1()
    ch1,cw1=ch,cw+1
    def1()

    for i in range(5):
      ch2=ch-2+i
      for j in range(5):
        cw2=cw-2+j
        def2()
  for i in f:
    if i not in d:
      c.append(i)
  f=[]
  warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Wrong Answer

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)

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

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e:
      f.append(e)

while len(c)>0 or len(f)>0:
  while len(c)>0:
    ch,cw=c[0]
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
    c.pop(0)
    ch1,cw1=ch-1,cw
    def1()
    ch1,cw1=ch+1,cw
    def1()
    ch1,cw1=ch,cw-1
    def1()
    ch1,cw1=ch,cw+1
    def1()

    for i in range(5):
      ch2=ch-2+i
      for j in range(5):
        cw2=cw-2+j
        def2()
  c=f
  f=[]
  warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Wrong Answer

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)

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

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e and d not in f:
      f.append(e)

while len(c)>0 or len(f)>0:
  while len(c)>0:
    ch,cw=c[0]
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
    c.pop(0)
    ch1,cw1=ch-1,cw
    def1()
    ch1,cw1=ch+1,cw
    def1()
    ch1,cw1=ch,cw-1
    def1()
    ch1,cw1=ch,cw+1
    def1()

    for i in range(5):
      ch2=ch-2+i
      for j in range(5):
        cw2=cw-2+j
        def2()
  c=f
  warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Wrong Answer

Solution code:
#ABC176
#D - Wizard in Maze

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
b=[ch-1,cw-1]
a,c,d,f=[],[],[],[]
c.append(b)
d.append(b)

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

warp=0

def def1():
  global c,d
  if 0<=ch1<h and 0<=cw1<w:
    e=[ch1,cw1]
    if a[ch1][cw1]=="." and d not in e:
      c.append(e)
      d.append(e)
def def2():
  global f
  if 0<=ch2<h and 0<=cw2<w:
    e=[ch2,cw2]
    if a[ch2][cw2]=="." and f not in e:
      f.append(e)

while len(c)>0 or len(f)>0:
  while len(c)>0:
    ch,cw=c[0]
    if a[ch][cw]==".":
      a[ch][cw]=str(warp)
    c.pop(0)
    ch1,cw1=ch-1,cw
    def1()
    ch1,cw1=ch+1,cw
    def1()
    ch1,cw1=ch,cw-1
    def1()
    ch1,cw1=ch,cw+1
    def1()

    for i in range(5):
      ch2=ch-2+i
      for j in range(5):
        cw2=cw-2+j
        def2()
  c=f
  warp=warp+1
z=a[dh-1][dw-1]
if z==".":
  print(1)
else:
  print(z)

Submission status: Wrong Answer

Solution code:
import queue

#入力
H,W = list(map(int,input().split()))
X_S, Y_S = list(map(int,input().split()))
X_G, Y_G = list(map(int,input().split()))

#壁と道を数字に
field = []
for _ in range(H):
    temp1 = input()
    temp2 = []
    for j in range(len(temp1)):
        if temp1[j] == ".":
            temp2.append(100000)
        elif temp1[j] == "#":
            temp2.append(-1)
    field.append(temp2)

#スタートとゴールを設定
field[X_S - 1][Y_S - 1] = 0
field[X_G - 1][Y_G - 1] = "G"

next_to_check = queue.Queue()    
next_to_check.put([X_S - 1, Y_S - 1])
changed = queue.Queue()

#ウォークとワープ
def walk(z):
    x,y = z
    count = field[x][y]
    #次のワープにつなげるための一句
    for i,j in [[0,1],[0,-1],[1,0],[-1,0]]:
        if x + i >= 0 and y + j >= 0 and x + i < H and y + j < W:
            try:
                if field[x + i][y + j] > count:
                    field[x + i][y + j] = count
                    next_to_check.put([x + i, y + j])
                    changed.put([x + i,y + j])
            except:
                print(count)
                exit()
    else:
        changed.put([x, y])
            
def warp(z):
    x,y = z
    count = field[x][y] + 1
    for i,j 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 + i >= 0 and y + j >= 0 and x + i < H and y + j < W:
            try:
                if field[x + i][y + j] > count:
                    field[x + i][y + j] = count
                    next_to_check.put([x + i, y + j])
            except:
                print(count)
                exit()
                
#実行部分

while not (next_to_check.empty() and changed.empty()):
    
    #walk
    while not next_to_check.empty():
        walk(next_to_check.get())
    #warp
    while not changed.empty():
        warp(changed.get())
        
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import queue

#入力
H,W = list(map(int,input().split()))
X_S, Y_S = list(map(int,input().split()))
X_G, Y_G = list(map(int,input().split()))

#壁と道を数字に
field = []
for _ in range(H):
    temp1 = input()
    temp2 = []
    for j in range(len(temp1)):
        if temp1[j] == ".":
            temp2.append(100000)
        elif temp1[j] == "#":
            temp2.append(-1)
    field.append(temp2)

#スタートとゴールを設定
field[X_S - 1][Y_S - 1] = 0
field[X_G - 1][Y_G - 1] = "G"

next_to_check = queue.Queue()    
next_to_check.put([X_S - 1, Y_S - 1])
changed = queue.Queue()

#ウォークとワープ
def walk(z):
    x,y = z
    count = field[x][y]
    #次のワープにつなげるための一句
    changed.put([x,y])
    for i,j in [[0,1],[0,-1],[1,0],[-1,0]]:
        if x + i >= 0 and y + j >= 0 and x + i < H and y + j < W:
            try:
                if field[x + i][y + j] > count:
                    field[x + i][y + j] = count
                    next_to_check.put([x + i, y + j])
                    changed.put([x + i,y + j])
            except:
                print(count)
                exit()
            
def warp(z):
    x,y = z
    count = field[x][y] + 1
    for i,j 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 + i >= 0 and y + j >= 0 and x + i < H and y + j < W:
            try:
                if field[x + i][y + j] > count:
                    field[x + i][y + j] = count
                    next_to_check.put([x + i, y + j])
            except:
                print(count)
                exit()
                
#実行部分

while not (next_to_check.empty() and changed.empty()):
    
    #walk
    while not next_to_check.empty():
        walk(next_to_check.get())
    #warp
    while not changed.empty():
        warp(changed.get())
        
else:
    print(-1)