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:
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**6

counter[Ch][Cw] = 0

#print(counter)
#print(S)

now = [start]
for item in now:
  x = item[0]
  y = item[1]
  if counter[x+1][y] == 10**6:
    counter[x+1][y] = 0
    now.append((x+1, y))
  if counter[x][y+1] == 10**6:
    counter[x][y+1] = 0
    now.append((x, y+1))
  if counter[x-1][y] == 10**6:
    counter[x-1][y] = 0
    now.append((x-1, y))
  if counter[x][y-1] == 10**6:
    counter[x][y-1] = 0
    now.append((x, y-1))

#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 10**6:
  if len(now) == 0 and counter[Dh][Dw] == 10**6:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    if item == (Dh, Dw):
      print(ans)
      exit()
    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))
  if len(nextlist) == 0:
    print(-1)
    exit()
  
  for item in nextlist:
    if item == (Dh, Dw):
      print(ans)
      exit()
    x = item[0]
    y = item[1]
    if counter[x+1][y] > ans:
      counter[x+1][y] = ans
      nextlist.append((x+1, y))
    if counter[x][y+1] > ans:
      counter[x][y+1] = ans
      nextlist.append((x, y+1))
    if counter[x-1][y] > ans:
      counter[x-1][y] = ans
      nextlist.append((x-1, y))
    if counter[x][y-1] > ans:
      counter[x][y-1] = ans
      nextlist.append((x, y-1))
  now = nextlist
  if ans > 10**6:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int,input().split())

C = list(map(int,input().split()))
D = list(map(int,input().split()))

S = [input() for i in range(H)]

ido = [[1,0],[0,1],[-1,0],[0,-1]]

warp = [[2,2],[2,1],[1,2],[0,2],[2,0],[-2,-2],[-2,-1],[-1,-2],[0,-2],[-2,0],[2,-2],[2,-1],[1,-2],[-2,2],[-2,1],[-1,2],[1,1],[1,-1],[-1,1],[-1,-1]]

d = deque()
d.append([C[1]-1,C[0]-1])
cost = [[10000 for i in range(W)] for j in range(H)]
flg = [[-1 for i in range(W)] for j in range(H)]

cost[C[0]-1][C[1]-1] = 0
flg[C[0]-1][C[1]-1] = 1

while d:
    x,y = d.popleft()
    for dx, dy in ido:
        nx = x + dx
        ny = y + dy
        

        if 0>nx or W<=nx or 0>ny or H<=ny:
            continue

        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x],cost[ny][nx])
        if flg[ny][nx] != -1 :
            continue
        d.append([nx,ny])
        flg[ny][nx] = 1

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 > nx or W <= nx or 0 > ny or H <= ny:
            continue
        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x]+1, cost[ny][nx])
        if flg[ny][nx] != -1:
            continue
        d.append([nx, ny])
        flg[ny][nx] = 1
answer = cost[D[0]-1][D[1]-1]
if answer == 10000:
    print(-1)
else:
    print(answer)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int,input().split())
curX,curY = map(int,input().split())
goalX,goalY =  map(int,input().split())
goalX -= 1
goalY -= 1

graph = []
for _ in range(H):
  r = list(input())
  graph.append(r)

ans = float('inf')
q = deque([(curX-1,curY-1,0)])
visited = [ [False]*W for _ in range(H) ]
while q:
  new_q = deque()

  for _ in range(len(q)):
    r,c,hop = q.popleft()
    if r==goalX and c==goalY:
      ans = min(ans, hop)
      continue
    visited[r][c] = True

    # if be able to move 1 step
    for x,y in [(-1,0),(0,-1),(1,0),(0,1)]:
      nr,nc = r+x,c+y
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if graph[nr][nc] == "#": continue
      if visited[nr][nc]: continue
      new_q.append((nr,nc,hop))

    for i in range(-2, 3):
      for j in range(-2, 3):
        if abs(i+j) == 1: continue
        nr,nc = r+i,c+j
        if nr<0 or nc<0 or nr>=H or nc>=W: continue
        if graph[nr][nc] == "#": continue
        if visited[nr][nc]: continue
        new_q.append((nr,nc,hop+1))

  q = new_q

if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(maze, visited,Ch,Cw,Dh,Dw):
  queue = deque([[Ch,Cw]])
  visited[Ch][Cw] = 0
  while queue:
    y,x = queue.popleft()
    if [y,x] == [Dh,Dw]:
      return visited[y][x]
    for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
      new_y,new_x = y+j,x+k
      if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "."and visited[new_y][new_x] == "x":
        visited[new_y][new_x] = visited[y][x]
        queue.append([new_y,new_x])
      elif 0 <= new_y+j < H and 0 <= new_x+k < W and maze[new_y][new_x] == "#"and maze[new_y+j][new_x+k] == ".":
        if visited[new_y+j][new_x+k] == "x" or  visited[new_y+j][new_x+k] > visited[y][x]+1:
          visited[new_y+j][new_x+k] = visited[y][x] +1
          queue.append([new_y+j,new_x+k])
  return -1
        
        
                                      
      
  
H, W = map(int,input().split())
Ch,Cw =  map(int,input().split())
Dh,Dw = map(int,input().split())
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1

maze = [input() for i in range(H)]
visited = [["x"]*W for j in range(H)]
print(bfs(maze, visited,Ch,Cw,Dh,Dw))

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
s = [input() for i in range(h)]

reach = [[False]*w for i in range(h)]
reach[ch][cw] = True

import heapq
q = [[0,ch,cw]]
heapq.heapify(q)

ans = -1
while q:
    cnt,cx,cy = heapq.heappop(q)

    if cx==dh and cy==dw:
        ans = cnt
        break

    for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
        if not(0<=cx+dx<h and 0<=cy+dy<w):continue
        if s[cx+dx][cy+dy]=='.':
            if not reach[cx+dx][cy+dy]:
                heapq.heappush(q,[cnt,cx+dx,cy+dy])
                reach[cx+dx][cy+dy] = True
        else:
            for ddx in range(-1,2):
                for ddy in range(-1,2):
                    if not(0<=cx+dx+ddx<h and 0<=cy+dy+ddy<w):continue
                    if not reach[cx+dx+ddx][cy+dy+ddy]:
                        if s[cx+dx+ddx][cy+dy+ddy]=='.':
                            heapq.heappush(q,[cnt+1,cx+dx+ddx,cy+dy+ddy])
                            reach[cx+dx+ddx][cy+dy+ddy] = True

print(ans)

Submission status: Wrong Answer

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

        if 0 <= y+i+k < R and 0 <=  x+j+l < C:
          if c[y+i+k][x+j+l] == '.' and visited[y+i+k][x+j+l] == -1:
            warp[y+i+k][x+j+l] = warp[y][x]+1
            visited[y+i+k][x+j+l] = 0
            if [y+i+k,x+j+l] == [gy,gx]:
              print(warp[gy][gx])
              exit()
            Q.append([y+i+k,x+j+l])
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
graph = []
visited = []
for _ in range(H):
    graph.append(list(input()))
    visited.append([float('inf')] * W)
visited[sH][sW] = 0
q = deque()
m2_q = deque()
q.append([sW, sH])
m2_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while q or m2_q:
    while q:
        x, y = q.pop()
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny:
                continue
            if visited[ny][nx] > (visited[y][x] + 1) and graph[ny][nx] == '.':
                visited[ny][nx] = visited[y][x]
                q.appendleft([nx, ny])
                m2_q.append([nx, ny])

    while m2_q:
        x, y = m2_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny:
                    continue

                if visited[ny][nx] > visited[y][x] and graph[ny][nx] == '.':
                    q.append([nx, ny])
                    visited[ny][nx] = visited[y][x] + 1

# print(*visited,sep='\n')
print(visited[gH][gW])

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] + 1
            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:
def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int ,input().split())
    Dh, Dw = map(int, input().split())

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

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

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

    ans = 0
    while (Ch != Dh) and (Cw != Dw):

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

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

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

                        elif maze[y][x] == "." and arrived[y][x] == 0:
                            Ch = y
                            Cw = x
                            find = 1
                            ans += 1
                            break

                if find == 1:
                    break

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

    print(ans)

if __name__ == "__main__":
    main()

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(100000):
  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:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
sys.setrecursionlimit(10 ** 7)
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = []
    for i in range(2):
        maze.append(['#']*(w+4))
    for i in range(h):
        maze.append(['#']*2 + list(IS()) + ['#']*2)
    for i in range(2):
        maze.append(['#']*(w+4))

    def dfs(maze, y, x):
        if y == dh+1 and x == dw+1:
            return [(y, x)]
        maze[y][x] = '#'
        for dx in range(-2, 2+1, 1):
            for dy in range(-2, 2+1, 1):
                nx = x + dx
                ny = y + dy
                if maze[ny][nx] == '#':
                    continue
                route =  dfs(maze, ny, nx)
                if route:
                    return [(y, x)] + route

    seen = maze[:]
    def bfs(maze, y, x):
        dq = deque()
        dq.append((y, x, 0))
        ret = []
        while dq:
            now_y, now_x, now_count = dq.popleft()
            if now_y == dh+1 and now_x == dw+1:
                ret.append(now_count)
            seen[now_y][now_x] = '#'
            # for dx in range(-1, 2, 1):
            #     for dy in range(-1, 2, 1):
            for dx, dy in [(1,0), (0, 1), (0, -1), (-1, 0)]:
                nx = now_x + dx
                ny = now_y + dy
                if seen[ny][nx] == '#':
                    continue
                seen[ny][nx] == '#'
                dq.append((ny, nx, now_count))
            for dx in range(-2, 3, 1):
                for dy in range(-2, 3, 1):
                    nx = now_x + dx
                    ny = now_y + dy
                    if seen[ny][nx] == '#':
                        continue
                    seen[ny][nx] == '#'
                    dq.append((ny, nx, now_count+1))
        return ret

    # res = dfs(maze, ch+1, cw+1)
    res = bfs(maze, ch+1, cw+1)
    if res:
        print(min(res))
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    q2 = collections.deque()
    q2.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-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)]
    while len(q) != 0 and len(q2) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
        h, w = q2.popleft()
        d = dist[h][w]
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
                    q2.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))

Submission status: Wrong Answer

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

h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))

s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1

Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1

for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)

count = 0
best = 0

while True:
  while Q:
    new_Q = []
    for node in Q:
      i,j = node[0], node[1]
      couc = 0
      
      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          couc += 1
        
      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          couc += 1

      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          couc += 1

      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          couc += 1
          
      if couc==0:
        ALL.append((i,j))

    Q = new_Q

  if V[f1][f2]==1:
    print(count)
    break
  else:
    count += 1
    part= []
    
    ALL = list(set(ALL))
    
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>-1 and y>-1 and x<h and y<w and G[x][y] == '.' and V[x][y]==0:
            part.append((x,y))         	
       
    ALL = list(set(part))
    Q = list(ALL)

    if (f1,f2) in ALL:
      print(count)
      break

    if len(ALL)==0:
      print(-1)
      break

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(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)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = [(ch-1, cw-1)]
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    for i,j in q2:
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
    if not q:
        break
    tmp += 1
    q2 = []

print(v[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

xy=[(1,0),(-1,0),(0,1),(0,-1)]
wp=[(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]
#wp=[(-1,-1),(-1,1),(1,1),(1,-1),(2,0),(-2,0),(0,2),(0,-2),(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]

h,w=map(int,input().split())
c1,c2=map(int,input().split())
d1,d2=map(int,input().split())
d=[list(input()) for i in range(h)]
d[c1-1][c2-1]=0
p=set([(c1-1,c2-1)])
while len(p):
    a,b=p.pop()
    for x,y in xy:
        x+=a
        y+=b
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>d[a][b]:
                d[x][y]=d[a][b]
                p.add((x,y))
    for x2,y2 in xy:
        x+=x2
        y+=y2
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>d[a][b]+1:
                d[x][y]=d[a][b]+1
                p.add((x,y))
    for x,y in wp:
        x+=a
        y+=b
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>d[a][b]+1:
                d[x][y]=d[a][b]+1
                p.add((x,y))
#    print(p)
#    print(d)

print(-1 if (d[d1-1][d2-1]=="#" or d[d1-1][d2-1]==".") else d[d1-1][d2-1])

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    h, w = tuple(map(int, input().split()))
    c = tuple(map(int, input().split()))
    d = tuple(map(int, input().split()))
    s = [list(input()) for i in range(h)]

    flag = 0
    goal = (d[0] - 1, d[1] - 1)
    points_near_goal = tuple([(i, j) for i in range(max(0, goal[0] - 2), min(h, goal[0] + 3))
                                for j in range(max(0, goal[1] - 2), min(w, goal[1] + 3))
                              if not (i, j) == (d[0] - 1, d[1] - 1)])
    available_mat = [[(c[0] - 1, c[1] - 1)]]
    available_list = [(c[0] - 1, c[1] - 1)]

    while not len(available_mat[-1]) == 0:
        index = 0
        while index < len(available_mat[-1]):
            i, j = available_mat[-1][index]
            if i > 0 and s[i - 1][j] == '.':
                if not (i - 1, j) in available_list:
                    available_mat[-1].append((i - 1, j))
                    available_list.append((i - 1, j))
                    if (i - 1, j) in points_near_goal:
                        flag = 2
            if j > 0 and s[i][j - 1] == '.':
                if not (i, j - 1) in available_list:
                    available_mat[-1].append((i, j - 1))
                    available_list.append((i, j + 1))
                    if (i, j - 1) in points_near_goal:
                        flag = 2
            if i < h - 1 and s[i + 1][j] == '.':
                if not (i + 1, j) in available_list:
                    available_mat[-1].append((i + 1, j))
                    available_list.append((i + 1, j))
                    if (i + 1, j) in points_near_goal:
                        flag = 2
            if j < w - 1 and s[i][j + 1] == '.':
                if not (i, j + 1) in available_list:
                    available_mat[-1].append((i, j + 1))
                    available_list.append((i, j + 1))
                    if (i, j + 1) in points_near_goal:
                        flag = 2
            index += 1
        if flag == 2:
            break
        elif goal in available_list:
            flag = 1
            break
        available_mat.append([])
        for coordinate in available_mat[-2]:
            for i in range(max(0, coordinate[0] - 2), min(h, coordinate[0] + 3)):
                for j in range(max(0, coordinate[1] - 2), min(w, coordinate[1] + 3)):
                    if not (i, j) in available_list and s[i][j] == '.':
                        available_list.append((i, j))
                        available_mat[-1].append((i, j))
                        if (i, j) in points_near_goal:
                            flag = 2
        if flag == 2:
            break
        elif goal in available_list:
            flag = 1
            break


    print(len(available_mat) if flag==2 else len(available_mat) - 1 if flag == 1 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
  d = [[-1]*w for i in range(h)]
  
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]
  ex = [2, 1, 0, -1, -2, 2, -2, 2, -2, 2, -2, 2, 1, 0, -1, -2]
  ey = [2, 2, 2, 2, 2, 1, 1, 0, 0, -1, -1, -2, -2, -2, -2, -2]
  
  que = deque([])
  que.append((ch, cw))
  d[ch][cw] = 0
  
  while que:
    p = que.popleft()
    if p[0]==dh and p[1]==dw:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==-1:
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]]
      elif 0<=nx<h and 0<=ny<w and maze[nx][ny]=='#':
        for j in range(15):
          nx = p[0] + ex[j]
          ny = p[1] + ey[j]
          if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==-1:
            que.append((nx, ny)) 
            d[nx][ny] = d[p[0]][p[1]]+1
              
              
  return d[dh][dw]
        
  
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
maze = [list(input()) for i in range(h)]

print(bfs())