Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
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=[[10**10 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]])
while que:
    p=que.popleft()
    for i in range(3):
        if i<=3:
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]           
            if nx>=0 and ny>=0 and nx<h and ny<w and s[nx][ny]!="#" and d[nx][ny]>d[p[0]][p[1]]:
                d[nx][ny]=d[p[0]][p[1]]
                que.append([nx,ny])
    for i in range(19):
        nx=p[0]+ddx[i]
        ny=p[1]+ddy[i]
        if nx>=0 and ny>=0 and nx<h and ny<w and s[nx][ny]!="#" and d[nx][ny]>d[p[0]][p[1]]+1:
            d[nx][ny]=d[p[0]][p[1]]+1
            que.append([nx,ny])

if d[dh][dw]==10**10:
    print(-1)
else:
    print(d[dh][dw])

Submission status: Wrong Answer

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

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

def dist(x1, y1, x2, y2):
    return (x1-x2) ** 2 + (y1-y2) ** 2

import heapq
seen = set()
queue = [(0, dist(CH-1, CW-1, DH-1, DW-1), CH-1, CW-1)]



while queue:
    move, _, row, col = heapq.heappop(queue)

    if (row, col) in seen:
        continue
    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            heapq.heappush(queue, (move, dist(new_row, new_col, DH-1, DW-1), new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            if -1 <= i <= j <= 1:
                continue
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                heapq.heappush(queue, (move+1, dist(new_row, new_col, DH-1, DW-1), new_row, new_col))

print(-1)

Submission status: Wrong Answer

Solution code:
import queue

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
#c->d

s=[input() for i in range(h)]

seen=[[0 for _ in range(w)] for _ in range(h)]
distance=[[10**7 for _ in range(w)] for _ in range(h)]

q=queue.Queue()

distance[ch][cw]=0
seen[ch][cw]=1
q.put([ch,cw])


while not q.empty():
  sth,stw=q.get()
  qi=queue.Queue()
  qi.put([sth,stw])
  ph=0
  pw=0
  wlis=[]
  while not qi.empty():
    ph,pw=qi.get()
    cntp=0
    for nearh,nearw in [[ph-1,pw],[ph+1,pw],[ph,pw-1],[ph,pw+1]]:
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="." and seen[nearh][nearw]==0:
        qi.put([nearh,nearw])
        seen[nearh][nearw]=1
        distance[nearh][nearw]=distance[ph][pw]
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="#":
        cntp+=1
    if cntp!=0:
      wlis.append([ph,pw])
  for i,j in wlis:
    dij=distance[i][j]
    for warph,warpw in [[i-2,j-2],[i-2,j-1],[i-2,j],[i-2,j+1],[i-2,j+2],
                        [i-1,j-2],[i-1,j-1],[i-1,j],[i-1,j+1],[i-1,j+2],
                        [i,j-2],[i,j-1],[i,j+1],[i,j+2],
                        [i+1,j-2],[i+1,j-1],[i+1,j],[i+1,j+1],[i+1,j+2],
                        [i+2,j-2],[i+2,j-1],[i+2,j],[i+2,j+1],[i+2,j+2]]:
      if 0<=warph<=h-1 and 0<=warpw<=w-1 and s[warph][warpw]=="." and seen[warph][warpw]==0:
        q.put([warph,warpw])
        seen[warph][warpw]=1
        distance[warph][warpw]=dij+1

if distance[dh][dw]==10**7:
  print(-1)
else:
  print(distance[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())

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

dx=[0,1,0,-1]
dy=[1,0,-1,0]
count=0
#niko(x,y,ans[y][x]+1)とする。
def niko(x,y,k,ans):
  for i in range(x-2,x+2):
    for j in range(y-2,y+2):
      if 0<=i<w and 0<=j<h:
        if maze[j][i]=="." and (ans[j][i]>k or ans[j][i]==-1):
          ans[j][i]=k
  return ans
ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if 0<=i<w and 0<=j<h:
          if (x==i and y==j+1):
            continue
          elif (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1):
            if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
              qu.append([i,j])
              ans[j][i] = ans[y][x]
          elif maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
            ans[j][i]=(ans[y][x]+1)
            qu.append([i,j])

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

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs(sl, visited, sy, sx, gy, gx, h, w):
    q = deque([[sy,sx]])
    q_warp = deque([])
    visited[sy][sx] = 0

    while q:
        while q:
            y, x = q.popleft()
            if [y, x] == [gy, gx]:
                return visited[gy][gx]
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y+j, x+k
                if ny >= h or nx >= w or ny < 0 or nx < 0:
                    continue
                if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x]
                    q.appendleft([ny,nx])

            for j in range(-2,3):
                for k in range(-2,3):
                    ny, nx = y+j, x+k
                    if ny >= h or nx >= w or ny < 0 or nx < 0: continue
                    if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                        visited[ny][nx] = visited[y][x] + 1
                        q.append([ny,nx])

    return -1


h, w = map(int, input().split()) 
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
sl = [list(input()) for _ in range(h)]
visited = [ [-1]*w for i in range(h)]
ans = bfs(sl,visited,ch-1,cw-1,dh-1,dw-1,h,w)
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())
maze=[]

for i in range(H):
  l=list(input())
  for j in range(len(l)):
    if l[j]=='.':l[j]=-1
    if l[j]=='#':l[j]=-2
  maze.append(l)

def isIn(h,w):
  if h<0 or h>=H or w<0 or w >=W:return False
  return True
l=[[Ch-1,Cw-1]]
l=deque(l)
maze[Ch-1][Cw-1]=0
while l:
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]

  target=l[0]
  h,w=target
  l.popleft()
  for vector in vectors:
    if not isIn(h+vector[0],w+vector[1]):continue
    if maze[target[0]+vector[0]][target[1]+vector[1]]>maze[target[0]][target[1]] or maze[target[0]][target[1]]==-1:
      maze[target[0]+vector[0]][target[1]+vector[1]]=maze[target[0]][target[1]]
      l.appendleft([target[0]+vector[0],target[1]+vector[1]])
  for i in range(25):
    if not isIn(h+i//5-2,w+i%5-2):continue
    if maze[h+i//5-2][w+i%5-2]>maze[h][w] or maze[h+i//5-2][w+i%5-2]==-1:
      maze[h+i//5-2][w+i%5-2]=maze[h][w]+1
      l.append([h+i//5-2,w+i%5-2])

print(maze[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:

from collections import deque


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

warp_list = [(-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)]

maze = []
warp_count = []
for _ in range(H):
    line = list([x for x in input()])
    maze.append(line)
    warp_count.append([-1] * W)

queue = deque()
queue.appendleft((Ch, Cw, 0))

answer = -1
while queue:
    print(queue)
    def maze_check(h, w, use_magic):
        if h < 0 or H <= h:
            return False
        if w < 0 or W <= w:
            return False
        if maze[h][w] == '#':
            return False
        if warp_count[h][w] == -1:
            return True
        if warp_count[h][w] <= use_magic:
            return False

        return True

    now_h, now_w, use_magic = queue.popleft()
    warp_count[now_h][now_w] = use_magic

    if now_h == Dh and now_w == Dw:
        if answer == -1:
            answer = use_magic
        elif answer > use_magic:
            answer = use_magic

        continue

    # 上下左右に移動
    do_warp = True
    if maze_check(now_h+1, now_w, use_magic):
        queue.appendleft((now_h + 1, now_w, use_magic))
        do_warp = False
    if maze_check(now_h-1, now_w, use_magic):
        queue.appendleft((now_h - 1, now_w, use_magic))
        do_warp = False
    if maze_check(now_h, now_w+1, use_magic):
        queue.appendleft((now_h, now_w + 1, use_magic))
        do_warp = False
    if maze_check(now_h, now_w-1, use_magic):
        queue.appendleft((now_h, now_w - 1, use_magic))
        do_warp = False

    if do_warp:
        for y, x in warp_list:
            warp_h = now_h + y
            warp_w = now_w + x

            if maze_check(warp_h, warp_w, use_magic+1):
                queue.appendleft((warp_h, warp_w, use_magic+1))

print(answer)

Submission status: Wrong Answer

Solution code:
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

start = (Ch, Cw)

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

counter = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      counter[k][j] = 10**7

counter[Ch][Cw] = 0

#print(counter)
#print(S)

now = [start]
now_2 = [start]
while len(now_2) > 0:
  new = []
  for item in now_2:
    x = item[0]
    y = item[1]
    if counter[x+1][y] == 10**7:
      counter[x+1][y] = 0
      new.append((x+1, y))
    if counter[x][y+1] == 10**7:
      counter[x][y+1] = 0
      new.append((x, y+1))
    if counter[x-1][y] == 10**7:
      counter[x-1][y] = 0
      new.append((x-1, y))
    if counter[x][y-1] == 10**7:
      counter[x][y-1] = 0
      new.append((x, y-1))
  now += new
  now_2 = new
#print(now)
#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 10**7:
  if len(now) == 0:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    x = item[0]
    y = item[1]
    if counter[x+2][y+2] > ans:
      counter[x+2][y+2] = ans
      nextlist.append((x+2, y+2))
    if counter[x+2][y+1] > ans:
      counter[x+2][y+1] = ans
      nextlist.append((x+2, y+1))
    if counter[x+2][y] > ans:
      counter[x+2][y] = ans
      nextlist.append((x+2, y))
    if counter[x+2][y-1] > ans:
      counter[x+2][y-1] = ans
      nextlist.append((x+2, y-1))
    if counter[x+2][y-2] > ans:
      counter[x+2][y-2] = ans
      nextlist.append((x+2, y-2))
    if counter[x+1][y+2] > ans:
      counter[x+1][y+2] = ans
      nextlist.append((x+1, y+2))
    if counter[x+1][y-2] > ans:
      counter[x+1][y-2] = ans
      nextlist.append((x+1, y-2))
    if counter[x][y+2] > ans:
      counter[x][y+2] = ans
      nextlist.append((x, y+2))
    if counter[x][y-2] > ans:
      counter[x][y-2] = ans
      nextlist.append((x, y-2))
    if counter[x-2][y+2] > ans:
      counter[x-2][y+2] = ans
      nextlist.append((x-2, y+2))
    if counter[x-2][y+1] > ans:
      counter[x-2][y+1] = ans
      nextlist.append((x-2, y+1))
    if counter[x-2][y] > ans:
      counter[x-2][y] = ans
      nextlist.append((x-2, y))
    if counter[x-2][y-1] > ans:
      counter[x-2][y-1] = ans
      nextlist.append((x-2, y-1))
    if counter[x-2][y-2] > ans:
      counter[x-2][y-2] = ans
      nextlist.append((x-2, y-2))
    if counter[x-1][y+2] > ans:
      counter[x-1][y+2] = ans
      nextlist.append((x-1, y+2))
    if counter[x-1][y-2] > ans:
      counter[x-1][y-2] = ans
      nextlist.append((x-1, y-2))
  
  now_2 = nextlist
  while len(now_2) > 0:
    new = []
    for item in now_2:
      x = item[0]
      y = item[1]
      if counter[x+1][y] == 10**7:
        counter[x+1][y] = 0
        new.append((x+1, y))
      if counter[x][y+1] == 10**7:
        counter[x][y+1] = 0
        new.append((x, y+1))
      if counter[x-1][y] == 10**7:
        counter[x-1][y] = 0
        new.append((x-1, y))
      if counter[x][y-1] == 10**7:
        counter[x][y-1] = 0
        new.append((x, y-1))
    nextlist += new
    now_2 = new
  now = nextlist
  #print(now)
  if ans > 10**7:
    print(-1)
    exit()
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())
maze = [list(input()) for _ in range(H)]

def BFS(maze,s,g):
  q = deque([s])
  checked = []
  while q:
    h,w,n = q.popleft()
    if (h,w)==g: return n
    dp = [(i-2,j-2) for i in range(5) for j in range(5) if (i-2,j-2)!=(0,0)]
    for i in dp:
      if (h+i[0],w+i[1]) in checked: continue
      else: checked.append((h+i[0],w+i[1]))

      if (0<h+i[0]<len(maze)) and (0<w+i[1]<len(maze[0])):
        if maze[h+i[0]][w+i[1]]==".":
          if i[0]%2==0 or i[1]%2==0:
            q.append((h+i[0],w+i[1],n+1))
          else:
            q.appendleft((h+i[0],w+i[1],n))
  return -1

print(BFS(maze,(CH-1,CW-1,0),(DH-1,DW-1)))

Submission status: Wrong Answer

Solution code:
import sys, math, heapq

def calcweight_dijkstra(N_vertices, start, edges, inf = 10**7):
    is_confirmed = [False] * N_vertices

    distances = [inf] * N_vertices
    distances[start] = 0
    queues = [ [distances[start], start] ] # 1

    while( len(queues)>0 ):
        queue = heapq.heappop(queues)
        if( is_confirmed[ queue[1] ]==False ):
            is_confirmed[ queue[1] ] = True
            for i in range( len(edges[ queue[1] ] ) ):
                destination = edges[ queue[1] ][i]
                distance = queue[0] + 1
                if(is_confirmed[destination]==False and distances[destination] > distance):
                    distances[destination] = distance
                    heapq.heappush(queues, [ distances[destination], destination ] )
    return distances

def search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y, parent):

    if(flag_searched[pos_y][pos_x]==True or Mazes[pos_y][pos_x] == "#"):
        return


    parents[pos_y][pos_x] = parent
    flag_searched[pos_y][pos_x] = True
    x = len(Mazes[0])
    y = len(Mazes)

    if(pos_y+1 < y and flag_searched[pos_y+1][pos_x]==False and Mazes[pos_y+1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y+1, parent)
    if(pos_y > 0 and flag_searched[pos_y-1][pos_x]==False and Mazes[pos_y-1][pos_x] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x, pos_y-1, parent)
    if(pos_x+1 < x and flag_searched[pos_y][pos_x+1]==False and Mazes[pos_y][pos_x+1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x+1, pos_y, parent)
    if(pos_x > 0 and flag_searched[pos_y][pos_x-1]==False and Mazes[pos_y][pos_x-1] == "."):
        search_with_DFS_using_recursion(Mazes, flag_searched, parents, pos_x-1, pos_y, parent)



def check(Mazes, flag_searched, parents, pos_x, pos_y, Edges, road_types):
    x = len(Mazes[0])
    y = len(Mazes)
    parentsnum= [-1] * 9

    index = 0
    for i in range( max(pos_y-1, 0), min(pos_y+2, y) ):
        for j in range( max(pos_x-1, 0), min(pos_x+2, x) ):
            if(Mazes[i][j] == "."):
                flag_searched[i][j] = True
                parentsnum[index] = parents[i][j]
            index += 1
    for k in range(8):
        for m in range(k+1, 9):
            if(parentsnum[k] != -1 and parentsnum[m] != -1 and parentsnum[k] != parentsnum[m]):
                point1 = road_types.index( parentsnum[k] )
                point2 = road_types.index( parentsnum[m] )
                Edges[point1].append(point2)
                Edges[point2].append(point1)



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) )
    goal = list( map(int, input().strip().split() ) )
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    parents = [ [ i*H+j for j in range(W)] for i in range(H) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    road_types = []
    for i in range(H):
        for j in range(W):
            parent = i*H+j
            if(parents[i][j] == parent and flag_searched[i][j] == False and Maps[i][j] == "."):
                search_with_DFS_using_recursion(Maps, flag_searched, parents, j, i, parent)

                road_types.append(parent)
    # print(parents)

    """
    昇順のはず
    road_types[i]がその頂点に対応
    """
    start_index = road_types.index( parents[start[0]][start[1]] )
    # print(parents[ goal[0]][ goal[1]])
    goal_index = road_types.index( parents[ goal[0]][ goal[1]] )
    N_vertices = len(road_types)
    Edges = [ [] for _ in range(N_vertices) ]
    flag_searched =  [ [ False for j in range(W)] for i in range(H) ]

    #print(road_types)
    for i in range(H):
        for j in range(W):
            """
            if(Maps[i][j] == "#" and flag_searched[i][j] == False):
                flag_searched[i][j] = True
                check(Maps, flag_searched, parents, j, i, Edges, road_types)
            """

            if(Maps[i][j] == "." and flag_searched[i][j] == False):
                flag_searched[i][j] = True
                #print("i, j ", i, j, min(H-i, 3)-1, "X", max(-j, -2) , min(W-j, 3)-1 )
                for dy in range( min(H-i, 3) ):
                    for dx in range( max(-j, -2), min(W-j, 3) ):
                        if( flag_searched[i+dy][j+dx]==False):
                            flag_searched[i+dy][j+dx] = True

                            if( Maps[i+dy][j+dx] == "." and parents[i+dy][j+dx] != parents[i][j]):
                                point1 = road_types.index( parents[i+dy][j+dx] )
                                point2 = road_types.index( parents[i][j] )
                                Edges[point1].append(point2)
                                Edges[point2].append(point1)

    if(parents[start[0]][start[1]]== parents[goal[0]][goal[1]]):
        print(0)
    else:
        inf = 10**7
        dist= calcweight_dijkstra(N_vertices, start_index, Edges, inf)
        if(dist[goal_index] == inf):
            print(-1)
        else:
            print(dist[goal_index])

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(1000)

def yn(b):
    print("Yes" if b==1 else "No")
    return
def aaa(g,memo,www,c):
    ww = www[g]
    memo[g]=c
    c2 = (c+1)
    for i in range(len(ww)):
        w=ww[i]
        if w==1 and i!=g:
            if memo[i]==-1 or memo[i] > c2:
                aaa(i,memo,www,c2)

def tansaku(y,x,mp,done,grp,wrp,w,h,gm,xxx):
    wlkh=[y,y,y-1,y+1]
    wlkw=[x-1,x+1,x,x]
    nun=y*w+x
    grp.add(nun)
    gm[nun]=xxx
    for zzz in range(4):
        zh=wlkh[zzz]
        zw=wlkw[zzz]
        if zh < 0:
            continue
        if zh >= h:
            continue
        if zw < 0:
            continue
        if zw >= w:
            continue
        if mp[zh][zw] == "." and done[zh][zw]==0:
            done[zh][zw]=1
            tansaku(zh,zw,mp,done,grp,wrp,w,h,gm,xxx)
    for i in range(y-2,y+3):
        for j in range(x-2,x+3):
            if i < 0:
                continue
            if i >= h:
                continue
            if j < 0:
                continue
            if j >= w:
                continue
            if mp[i][j]==".":
                wrp.add(i*w+j)

def resolve():
    readline=sys.stdin.readline

    h,w=map(int, readline().rstrip().split())
    ch,cw=map(int, readline().rstrip().split())
    dh,dw=map(int, readline().rstrip().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    mp=[]

    cN=ch*w+cw
    dN=dh*w+dw

    done=[[0 for i in range(w)] for j in range(h)]
    gm=[-1] * ((h*w)+3)

    road=0
    for i in range(h):
        ss=readline().rstrip()
        road+=ss.count(".")
        mp.append(ss)

    gs = []
    ws=[]
    xxx=-1
    for y in range(h):
        for x in range(w):
            masu=y*w+x
            if mp[y][x] == "." and done[y][x]==0:
                grp=set()
                wrp=set()
                xxx+=1
                tansaku(y,x,mp,done,grp,wrp,w,h,gm,xxx)
                gs.append(grp)
                ws.append(wrp)
            else:
                done[y][x]=1
    cnt=len(gs)
    www=[[0 for i in range(cnt)] for j in range(cnt)]
    for i in range(cnt):
        gp = gs[i]
        wp = ws[i]
        for pp in wp:
            j=gm[pp]
            www[i][j]=1
            www[j][i]=1
    memo=[-1]*cnt
    #aaa(gm[cN],memo,www,0)
    print(memo[gm[dN]])
    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

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

for i in range(H):
  l=list(input())
  for j in range(len(l)):
    if l[j]=='.':l[j]=-1
    if l[j]=='#':l[j]=-2
  maze.append(l)

def isIn(h,w):
  if h<0 or h>=H or w<0 or w >=W:return False
  return True
l=[[Ch-1,Cw-1]]
maze[Ch-1][Cw-1]=0
while l:
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]

  target=l[0]
  h,w=target
  l.pop(0)
  for vector in vectors:
    if not isIn(h+vector[0],w+vector[1]):continue
    if maze[target[0]+vector[0]][target[1]+vector[1]]>maze[target[0]][target[1]] or maze[target[0]][target[1]]==-1:
      maze[target[0]+vector[0]][target[1]+vector[1]]=maze[target[0]][target[1]]
      l.insert(0,[target[0]+vector[0],target[1]+vector[1]])
  for i in range(25):
    if not isIn(h+i//5-2,w+i%5-2):continue
    if maze[h+i//5-2][w+i%5-2]>maze[h][w] or maze[h+i//5-2][w+i%5-2]==-1:
      maze[h+i//5-2][w+i%5-2]=maze[h][w]+1
      l.append([h+i//5-2,w+i%5-2])

print(maze[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = float('inf')


def LI(): return list(map(int, sys.stdin.readline().split()))


def I(): return int(sys.stdin.readline())


def LS(): return sys.stdin.readline().split()


def S(): return sys.stdin.readline().strip()


def IR(n): return [I() for i in range(n)]


def LIR(n): return [LI() for i in range(n)]


def SR(n): return [S() for i in range(n)]


def LSR(n): return [LS() for i in range(n)]


def SRL(n): return [list(S()) for i in range(n)]


def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7


h, w = LI()
sy, sx = LI()
gy, gx = LI()
sy-=1; sx-=1; gy-=1; gx-= 1
grid = SR(h)
dp = [[INF]*w for _ in range(h)]
q1 = deque()
q2 = deque([(sy, sx)])
dp[sy][sx]=0


while q2:
    uy,ux=q2.popleft()
    for i in range(-2,3):
        for j in range(-2, 3):
            ny=uy+i
            nx=ux+j
            if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == "." and dp[ny][nx] > dp[uy][ux] + 1:
                dp[ny][nx]=dp[uy][ux]+1
                q2 += [(ny, nx)]
                q1 += [(ny, nx)]
                while q1:
                    uy, ux = q1.popleft()
                    for i, j in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                        ny = uy + i
                        nx = ux + j
                        if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == "." and dp[ny][nx] > dp[uy][ux]:
                            dp[ny][nx] = dp[uy][ux]
                            q1 += [(ny, nx)]
                            q2 += [(ny, nx)]



print(dp[gy][gx] if dp[gy][gx] != INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append((CY, CX))  # スタート地点
# 各頂点について2*2の幅優先する？
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[10**10]*W for _ in range(H)]
distant[CY][CX] = 0
warp_y = list(range(-2, 3, 1))
warp_x = list(range(-2, 3, 1))
happend = set()
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            # 道の場合はコスト0で移動できる
            distant[ny][nx] = distant[cy][cx]
            if (ny, nx) not in happend:
                q.append((ny, nx))
                happend.add((ny, nx))
    # 周囲5*5の道に+1で到達する
    for i in warp_y:
        for j in warp_x:
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    if (target_y, target_x) not in happend:
                        q.append((target_y, target_x))
                        happend.add((target_y, target_x))
if distant[DY][DX] == 10**10:
    print(-1)
else:
    print(distant[DY][DX])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1<<50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
from collections import deque
q = deque([])
q.append((ch-1,cw-1))
while len(q)>0:
    h,w = q.popleft()
    cnt = dps[h][w]
    # 先に魔法を使っておく
    for dh in range(-2,3):
        for dw in range(-2,3):
            hn = h + dh
            wn = w + dw
            if (dh,dw) in mvs:
                if 0<=hn<H and 0<=wn<W:
                    if dps[hn][wn] <= cnt:continue
                    if fs[hn][wn] == ".":
                        q.append((hn, wn))
                        dps[hn][wn] = min(dps[h][w], cnt)
            else:
                if 0<=hn<H and 0<wn<W:
                    if dps[hn][wn] <= cnt+1:continue
                    if fs[hn][wn] == ".":
                        q.appendleft((hn,wn))
                        dps[hn][wn] = min(dps[hn][wn], cnt + 1)

# for r in dps:
#     print(*r)
ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Wrong Answer

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

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
S = [input().rstrip() for _ in [0]*H]
print(S[0])

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch*W+Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)
    if D[i][j] > d:
        D[i][j] = d
    else:
        continue
    if i == Dh and j == Dw:
        break

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if S[_i][_j] == '.':
                if D[_i][_j] <= d:
                    continue
                heappush(q, (d, _i*W+ _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and S[_i][_j] == '.':
                        if D[_i][_j] <= d+1:
                            continue
                        heappush(q, (d+1, _i*W+_j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)