Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Wrong Answer

Solution code:
from collections import deque
 
H, W = [int(x) for x in 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

cell = [list(input()) for i in range(H)]

dp = [[-1]*W for _ in range(H)]

stack = deque()
stack.append([Ch,Cw])

dp[Ch][Cw] = 0

while len(stack) > 0:
    h,w = stack.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = h + dy
        nw = w + dx
        if 0 <= nh < H and 0 <= nw < W and (dp[nh][nw] == -1 or dp[nh][nw] > dp[h][w]):
            if cell[nh][nw] == '.':
                dp[nh][nw] = dp[h][w]
                stack.append([nh,nw])
            else:
                if dy == 0:
                    for ddx in [dx, dx*2]:
                        for ddy in range(-2,3):
                            if ddy == 0:
                                continue
                            nnh = h + ddy
                            nnw = w + ddx
                            if 0 <= nnh < H and 0 <= nnw < W:
                                if cell[nnh][nnw] == '.' and (dp[nnh][nnw] == -1 or dp[nnh][nnw] > dp[h][w]+1):
                                    dp[nnh][nnw] = dp[h][w] + 1
                                    stack.append([nnh,nnw])
                else:
                    for ddy in [dy, dy*2]:
                        for ddx in range(-2,3):
                            if ddx == 0:
                                continue
                            nnh = h + ddy
                            nnw = w + ddx
                            if 0 <= nnh < H and 0 <= nnw < W:
                                if cell[nnh][nnw] == '.' and (dp[nnh][nnw] == -1 or dp[nnh][nnw] > dp[h][w]+1):
                                    dp[nnh][nnw] = dp[h][w] + 1
                                    stack.append([nnh,nnw])
                
if dp[Dh][Dw] != -1:
    print(dp[Dh][Dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:

import queue
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=queue.Queue()
q.put((sx-1,sy-1,0))
dist[sy-1][sx-1]=0
goaled = 0

#while goaled==0:
while not q.empty():
    
    x,y,d = q.get()
    
    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.put((x+i[0],y+i[1],d+0))
                    else:  
                        dist[y+i[1]][x+i[0]] = d+1
                        q.put((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:
import copy
from collections import deque

H, W = [int(i) for i in input().split()]
C = tuple([int(i) - 1 for i in input().split()])
D = tuple([int(i) - 1 for i in input().split()])
S = []
for i in range(H):
  s = list(input())
  S.append(s)
  
  
# 領域を計算
def dfs(arr, h, w):
  arr[h][w] = "#"
  region = set([tuple([h, w])])
  for i, j in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
      nh = h + i
      nw = w + j
      if 0 <= nh and 0 <= nw and nh < H and nw < W and arr[nh][nw] == ".":
        region |= dfs(arr, nh, nw)
  return region

regions = []
field = copy.deepcopy(S)

for h in range(H):
  for w in range(W):
    if field[h][w] == ".":
      region = dfs(field, h, w);
      regions.append(region)

s_reg = -1
g_reg = -1

for i in range(len(regions)):
  if C in regions[i]:
    s_reg = i
  if D in regions[i]:
    g_reg = i

count = 0
d = deque()
arrived = set()
arrived_pos = set()
d.append(s_reg)
arrived.add(s_reg)

while d:
  pos = d.popleft()
  if pos == g_reg:
    break
  # ワープできる領域を計算
  for p in regions[pos]:
    for h in range(-2, 3):
      for w in range(-2, 3):
        pw = p[0] + h
        ph = p[1] + w
        if pw < 0 or W <= pw or ph < 0 or H <= ph:
          # 欄外
          continue
        if tuple([ph, pw]) in arrived_pos:
          continue
        arrived_pos.add(tuple([ph, pw]))
        for i in range(len(regions)):
          if i not in arrived:
            if tuple([ph, pw]) in regions[i]:
              arrived.add(i)
              d.append(i)
  count += 1
  
if g_reg not in arrived:
  print(-1)
else:
  print(count)

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の順

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]==-1:
                    if A[j][i]==".":
                        d[j][i]=10**6
                        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 d[t][s]>=0:
                                    d[j][i] = min(d[j][i],d[t][s]+1)
                        if d[j][i]==10**6:
                            d[j][i]=-1
                        else:
                            v.append([j,i])
                            if j==dh and i==dw:
                                print(d[j][i])
                                exit()
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import queue
import heapq

# input
H, W = map(int, sys.stdin.readline().strip().split())
Ch, Cw = map(int, sys.stdin.readline().strip().split())
Dh, Dw = map(int, sys.stdin.readline().strip().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

S = []
for _ in range(H):
    s = str(input())
    S.append(list(s))


# solve
q = []
heapq.heappush(q, (0, (Ch, Cw)))
fp = [[float('inf')] * W for _ in range(H)]
fp[Ch][Cw] = 0
while q:
    count, coo = heapq.heappop(q)
    uh, uw = coo

    # if count > fp[uh][uw]:
    #     continue

    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        vh = uh + dh
        vw = uw + dw

        # 盤上にいるか確認
        if vh < 0 or vh >= H:
            continue
        if vw < 0 or vw >= W:
            continue

        # 壁の確認
        if S[vh][vw] == "#":
            continue

        # 到達済みか確認
        if fp[vh][vw] <= fp[uh][uw]:
            continue

        # 探索候補地に追加
        fp[vh][vw] = fp[uh][uw]
        heapq.heappush(q, (fp[vh][vw], (vh, vw)))

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                continue

            vh = uh + dh
            vw = uw + dw

            # 盤上にいるか確認
            if vh < 0 or vh >= H:
                continue
            if vw < 0 or vw >= W:
                continue

            # 壁の確認
            if S[vh][vw] == "#":
                continue

            # 到達済みか確認
            if fp[vh][vw] <= fp[uh][uw] + 1:
                continue

            # 探索候補地に追加
            fp[vh][vw] = fp[uh][uw]
            heapq.heappush(q, (fp[vh][vw] + 1, (vh, vw)))


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

Submission status: Wrong Answer

Solution code:
from collections import deque

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



def clear_maze(h, w, ch, cw, dh, dw, S):
    visited = [[-1] * w for _ in range(h)]
    visited[ch - 1][cw - 1] = 0
    queue = deque([[ch - 1 , cw - 1]])
    while queue:
        y, x = queue.popleft()
        if [y, x] == [dh - 1, dw - 1]:
            return visited[y][x]
        num = 0
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y = y + i
            n_x = x + j
            if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.':
                if visited[n_y][n_x] == -1:
                    visited[n_y][n_x] = visited[y][x]
                    queue.append([n_y, n_x])
                else:
                    visited[n_y][n_x] = min(visited[n_y][n_x], visited[y][x])
                    if visited[y][x] < visited[n_y][n_x]:
                        queue.append([n_y, n_x])
        for i in range(-2, 2 + 1):
            for j in range(-2, 2 + 1):
                if not [i, j] in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                    n_y = y + i
                    n_x = x + j
                    if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.':
                        if visited[n_y][n_x] == -1:
                            visited[n_y][n_x] = visited[y][x] + 1
                            queue.append([n_y, n_x])
                        else:
                            visited[n_y][n_x] = min(visited[n_y][n_x], visited[y][x] + 1)
                            if visited[y][x] + 1 < visited[n_y][n_x]:
                                queue.append([n_y, n_x])
    return -1

print(clear_maze(h, w, ch, cw, dh, dw, S))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh, gw = map(int, readline().split())
    gh -= 1
    gw -= 1
    S = read().split()
    dist = [[INF] * W for _ in range(H)]
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(1, 1), (1, -1), (-1, 1), (-1, -1), \
            (2, 0), (2, 1), (2, 2), (2, -1), (2, -1), (2, -2), \
            (-2, 0), (-2, 1), (-2, 2), (-2, -1), (-2, -1), (-2, -2), \
            (0, 2), (1, 2), (-1, 2), (0, -2), (1, -2), (-1, -2)]
    Q = deque()
    Q.append((sh, sw))
    dist[sh][sw] = 0
    while Q:
        h, w = Q.popleft()
        if h == gh and w == gw:
            continue
        flag = False
        for dh, dw in walk:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] != '#':
                    if dist[nh][nw] > dist[h][w]:
                        dist[nh][nw] = dist[h][w]
                        Q.append((nh,nw))
                else:
                    flag = True
        if flag:
            for dh, dw in warp:
                nh = h + dh
                nw = w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if dist[nh][nw]==INF:
                        dist[nh][nw] = dist[h][w] + 1
                        Q.append((nh,nw))

    if dist[gh][gw]==INF:
        print(-1)
    else:
        print(dist[gh][gw])




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import pprint
import sys
sys.setrecursionlimit(10**8)
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

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

visited = [[-1 for _ in range(W)] for _ in range(H)]

def dfs(x, y, count):

    if (not (0 <= x < W)) or (not (0 <= y < H)):
        return

    if visited[y][x] > -1:
        return

    if x == Dw and y == Ch:
        visited[y][x] = count
        return

    if city[y][x] == "#":
        return

    if visited[y][x] == -1:
        visited[y][x] = count

    dfs(x+1, y, count)
    dfs(x, y+1, count)
    dfs(x-1, y, count)
    dfs(x, y-1, count)
    for i in range(-2, 3):
        for j in range(-2, 3):
            if (not (0 <= x+j < W)) or (not (0 <= y+i < H)):
                continue
            if visited[y+i][x+j] > -1:
                continue
            if city[y+i][x+j] != "#":
                dfs(x+j, y+i, count+1)
            else:
                continue


dfs(Cw, Ch, 0)
ans = visited[Dh][Dw]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def walk(h, w):
    q = deque([[h, w]])
    coord = []
    while q:
        y, x = q.popleft()
        for i, j in [(0,1), (0,-1), (1,0),(-1,0)]:
            if (y+i<0 or y+i>H-1) or (x+j<0 or x+j>W-1):
                continue
            if s[y+i][x+j] == '#':
                continue
            if m[y+i][x+j] != -1:
                continue
            q.append([y+i, x+j])
            m[y+i][x+j] = m[h][w]
            coord.append([y+i, x+j])
    return coord


def warp(h, w):
    coord = []
    v = m[h][w]
    h_s = max(0, h-2)
    h_e = min(H-1, h+2)
    w_s = max(0, w-2)
    w_e = min(W-1, w+2)
    for h1 in range(h_s, h_e+1):
        for w1 in range(w_s, w_e+1):
            if h==h1 and w==w1:
                continue
            if m[h1][w1] == -1 and s[h1][w1] != '#':
                m[h1][w1] = v + 1
                coord.append([h1, w1])
    return coord

    
m = [[-1] * W for _ in range(H)]
m[ch][cw] = 0
queue = [[ch, cw]]
f = True
while True:
    coord = []
    co = []
    for y, x in queue:
        coord += walk(y, x)
    if f:
        coord.append([ch, cw])
    f = False
    for h, w in coord:
        co = warp(h, w)
    if len(co) == 0:
        break
    queue = co.copy()

print(m[dh][dw])

Submission status: Wrong Answer

Solution code:
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
from collections import deque
mod = 10**9 + 7

def main():
  h, w = I()
  ch, cw = I()
  dh, dw = I()
  s = ['$'*(w+4)]*(h+4)
  for i in range(h):
    s[i+2] = '$$' + input() + '$$'

  dist = [[-1]*(w+4) for _ in range(h+4)]
  dist[ch + 1][cw + 1] = 0
  q = deque()
  q.append((ch+1, cw+1))
  while q:
    x, y = q.popleft() # 探索地点を取り出す

    vx = [-1,0,1,0]
    vy = [0,-1,0,1]
    flag = [False, False, False, False]
    for i in range(4):
      nx = x + vx[i]
      ny = y + vy[i]
      if s[nx][ny] == '$': 
        flag[i] = True
        continue # 壁なら通れないね！
      if s[nx][ny] == '#':
        flag[i] = True
        continue
      if dist[nx][ny] != -1:
        if dist[nx][ny] > dist[x][y]:
          dist[nx][ny] = dist[x][y]
        flag[i] = True
        continue # もう最短距離がわかってるなら飛ばす
      dist[nx][ny] = dist[x][y]
      q.append((nx, ny)) # 新しい地点の周りも探索したいからキューに入れておく
    if not False in flag: # もし4つのflagがTrueの時5×5以内に飛べるか探す
      vvx = [-2,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2]
      vvy = [0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2,1,1,1,1,2,2,2,2,2]
      for i in range(20):
        nnx = x + vvx[i]
        nny = y + vvy[i]
        if s[nnx][nny] == '$': 
          continue # 壁なら通れないね！
        if s[nnx][nny] == '#':
          continue
        if dist[nnx][nny] != -1:
          if dist[nnx][nny] > dist[x][y] + 1:
            dist[nnx][nny] = dist[x][y] + 1
          continue # もう最短距離がわかってるなら飛ばす
        dist[nnx][nny] = dist[x][y] + 1
        q.append((nnx, nny))
  
  print(dist[dh+1][dw+1])

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
from collections import deque 
inf = 10**9+1
def do():
    dyx = [(-1,0),(1,0),(0,1),(0,-1)]
    dd1 = [(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-1),(-1,1)]
    dd2 = [(2,-1),(2,0),(2,1),(2,2),(1,-1),(1,1)]
    dd3 = [(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)]
    dd4 = [(-1,-2),(0,-2),(1,-2),(-2,-1),(-1,-1),(1,-1),]
    h,w=INTM()
    sh,sw=INTM()
    sh-=1
    sw-=1
    gh,gw=INTM()
    gh-=1
    gw-=1
    dist=[[inf]*w for i in range(h)]
    dist[sh][sw]=0
    s=[]
    for i in range(h):
        s.append(STR())
    
    que=deque()
    que.append(sh*w+sw)
    while que:
        q=que.popleft()
        th=q//w
        tw=q%w
        for dy,dx in dyx:
            if (0 <= th+dy <h) and (0 <= tw+dx <w):
                if s[th+dy][tw+dx]=="#":
                    if (dy,dx)==(-1,0):
                        ddt=dd1
                    if (dy,dx)==(1,0):
                        ddt=dd2
                    if (dy,dx)==(0,1):
                        ddt=dd3
                    if (dy,dx)==(0,-1):
                        ddt=dd4
#                    for ddy in range(-2,3,1):
 #                       for ddx in range(-2,3,1):
                    for ddy,ddx in ddt:        
                         if (ddy,ddx) in dyx or ((ddy,ddx) == (0,0)):
                                continue
                         if (0 <= th+ddy <h) and (0 <= tw+ddx <w):
                            if  s[th+ddy][tw+ddx]==".":
                                if dist[th+ddy][tw+ddx] >dist[th][tw]+1:
                                    que.append((th+ddy)*w+(tw+ddx))
                                    dist[th+ddy][tw+ddx] =dist[th][tw]+1
                                    
                else:
                    if dist[th+dy][tw+dx] >dist[th][tw]:
                        que.append((th+dy)*w+(tw+dx))
                        dist[th+dy][tw+dx] =dist[th][tw]
        
    if dist[gh][gw]==inf:
        print(-1)
    else:
        print(dist[gh][gw])
        
    # print(dist)
                                
                                
    
if __name__ == '__main__':
    do()

Submission status: Wrong Answer

Solution code:
import queue
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=queue.Queue()
q.put((sx-1,sy-1,0))
dist[sy-1][sx-1]=0
goaled = 0

#while goaled==0:
while not q.empty():
    
    x,y,d = q.get()
    
    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.put((x+i[0],y+i[1],d+0))
                    else:  
                        dist[y+i[1]][x+i[0]] = d+1
                        q.put((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:
import queue
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=queue.Queue()
q.put((sx-1,sy-1,0))
dist[sy-1][sx-1]=0
goaled = 0

#while goaled==0:
while not q.empty():
    
    x,y,d = q.get()
    
    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.put((x+i[0],y+i[1],d+0))
                    else:  
                        dist[y+i[1]][x+i[0]] = d+1
                        q.put((x+i[0],y+i[1],d+1))

Submission status: Wrong Answer

Solution code:
import collections
import sys
import math
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
def dfs(i,j):
  if i+1!=H:
    if L[i+1][j]!="#":
      if str(i+1)+" "+str(j) not in finish:
        finish.add(str(i+1)+" "+str(j))
        if L[i+1][j]==".":
          L[i+1][j]=p
          dfs(i+1,j)
        else:
          print(p)
          exit()
  if i!=0:
    if L[i-1][j]!="#":
      if str(i-1)+" "+str(j) not in finish:
        finish.add(str(i-1)+" "+str(j))
        if L[i-1][j]==".":
          L[i-1][j]=p
          dfs(i-1,j)
        else:
          print(p)
          exit()
  if j+1!=W:
    if L[i][j+1]!="#":
      if str(i)+" "+str(j+1) not in finish:
        finish.add(str(i)+" "+str(j+1))
        if L[i][j+1]==".":
          L[i][j+1]=p
          dfs(i,j+1)
        else:
          print(p)
          exit()
  if j!=0:
    if L[i][j-1]!="#":
      if str(i)+" "+str(j-1) not in finish:
        finish.add(str(i)+" "+str(j-1))
        if L[i][j-1]==".":
          L[i][j-1]=p
          dfs(i,j-1)
        else:
          print(p)
          exit()
H,W=MAP()
st1,st2=MAP()
go1,go2=MAP()
L=NIJIGEN(H)
st1-=1
st2-=1
go1-=1
go2-=1
ans=0
L[go1][go2]="$"
for p in range(1000):
  if p==0:
    c=st1
    d=st2
    L[c][d]=p
    finish=set()
    finish.add(str(c)+" "+str(d))
    dfs(c,d)
    continue
  for j in finish:
    a,b=j.split()
    a=int(a)
    b=int(b)
    for k in range(25):
      n=k//5
      m=k%5
      c=a-2+n
      d=b-2+m
      if 0<=c<H and 0<=d<W:
        if L[c][d]=="." or L[c][d]=="$":
          if L[c][d]=="$":
            print(ans+1)
            exit()
          ans+=1
          L[c][d]=p
          finish=set()
          finish.add(str(c)+" "+str(d))
          dfs(c,d)
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(u, n, g):
    queue = deque([u])
    d = [None] * n  # uからの距離の初期化
    d[u] = 0  # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d


def main():
    h, w = map(int, input().split())
    c_h, c_w = map(lambda x: int(x) - 1, input().split())
    d_h, d_w = map(lambda x: int(x) - 1, input().split())
    s = [None] * h
    for i in range(h):
        s[i] = input()
    area = [[None] * w for i in range(h)]
    area_cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue

            if i > 0 and area[i - 1][j] is not None:
                area[i][j] = area[i - 1][j]
            elif j > 0 and area[i][j - 1] is not None:
                area[i][j] = area[i][j - 1]
            else:
                area[i][j] = area_cnt
                area_cnt += 1

    c_area = area[c_h][c_w]
    d_area = area[d_h][d_w]

    if c_area == d_area:
        print(0)
        return

    can_move = [set([]) for _ in range(area_cnt)]
    for i in range(h):
        for j in range(w):
            if area[i][j] is None:
                continue
            for k in range(-2, 3):
                if i + k < 0 or area_cnt <= i + k:
                    continue
                for m in range(-2, 3):
                    if j + m < 0 or area_cnt <= j + m:
                        continue
                    try:
                        if area[i + k][j + m] is None:
                            continue
                    except IndexError:
                        continue

                    if area[i][j] != area[i + k][j + m]:
                        can_move[area[i][j]].add(area[i + k][j + m])
                        can_move[area[i + k][j + m]].add(area[i][j])
    d = bfs(c_area, area_cnt, can_move)[d_area]
    if d is None:
        print(-1)
    else:
        print(d)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, read().split())
    start = tuple(int(i) - 1 for i in input().split())
    goal = tuple(int(i) - 1 for i in input().split())
    s = [input() for _ in range(h)]
    todo = deque([start])
    seen = set()
    while todo:
        y, x = todo.popleft()
        if (y, x) == goal:
            print(0)
            return
        if s[y][x] == "#":
            continue
        if (y, x) in seen:
            continue
        seen.add((y, x))
        for (ny, nx) in [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)]:
            if 0 <= nx < w and 0 <= ny < h:
                todo.append((ny, nx))
    left, right = 0, 2 * (h + w)
    while right - left > 1:
        mid = (left + right) // 2
        todo = deque([(*start, mid)])
        seen = set()
        while todo:
            y, x, k = todo.popleft()
            if (y, x) == goal:
                right = mid
                break
            if s[y][x] == "#":
                continue
            if (y, x, k) in seen:
                continue
            seen.add((y, x, k))
            for ny in range(max(y - 2, 0), min(y + 2 + 1, h)):
                for nx in range(max(x - 2, 0), min(x + 2 + 1, w)):
                    d = abs(x - nx) + abs(y - ny)
                    if d == 0:
                        continue
                    elif d == 1:
                        todo.append((ny, nx, k))
                    elif k > 0:
                        todo.append((ny, nx, k - 1))
        else:
            left = mid
    print(right if right < h * w else -1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
from collections import deque 
inf = 10**9+1
def do():
    dyx = [(-1,0),(1,0),(0,1),(0,-1)]
    dd1 = [(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-1)]
    dd2 = [(2,-1),(2,0),(2,1),(2,2),(1,-1)]
    dd3 = [(-1,2),(0,2),(1,2),(2,2),(-1,1)]
    dd4 = [(-1,-2),(0,-2),(1,-2),(-2,-1),(-1,-1)]
    h,w=INTM()
    sh,sw=INTM()
    sh-=1
    sw-=1
    gh,gw=INTM()
    gh-=1
    gw-=1
    dist=[[inf]*w for i in range(h)]
    dist[sh][sw]=0
    s=[]
    for i in range(h):
        s.append(STR())
    
    que=deque()
    que.append(sh*w+sw)
    while que:
        q=que.popleft()
        th=q//w
        tw=q%w
        for dy,dx in dyx:
            if (0 <= th+dy <h) and (0 <= tw+dx <w):
                if s[th+dy][tw+dx]=="#":
                    if (dy,dx)==(-1,0):
                        ddt=dd1
                    if (dy,dx)==(1,0):
                        ddt=dd2
                    if (dy,dx)==(0,1):
                        ddt=dd3
                    if (dy,dx)==(0,-1):
                        ddt=dd4
#                    for ddy in range(-2,3,1):
 #                       for ddx in range(-2,3,1):
                    for ddy,ddx in ddt:        
                         if (ddy,ddx) in dyx or ((ddy,ddx) == (0,0)):
                                continue
                         if (0 <= th+ddy <h) and (0 <= tw+ddx <w):
                            if  s[th+ddy][tw+ddx]==".":
                                if dist[th+ddy][tw+ddx] >dist[th][tw]+1:
                                    que.append((th+ddy)*w+(tw+ddx))
                                    dist[th+ddy][tw+ddx] =dist[th][tw]+1
                                    
                else:
                    if dist[th+dy][tw+dx] >dist[th][tw]:
                        que.append((th+dy)*w+(tw+dx))
                        dist[th+dy][tw+dx] =dist[th][tw]
        
    if dist[gh][gw]==inf:
        print(-1)
    else:
        print(dist[gh][gw])
        
    # print(dist)
                                
                                
    
if __name__ == '__main__':
    do()