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
 
N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1
 
 
S = [["" for j in range(M)] for i in range(N)]#2行3列の場合
#iがyｊがx
 
 
 
 
 
 
for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]
 
if N==1 and M==1:
    if S[0][0]=="#":
        print(-1)
        exit()
    else:
        print(0)
        exit()
 
 
 
seen=[[-1 for j in range(M)] for i in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
 
 
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]
 
 
def dfs(y,x):
 
    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    count=0
    while len(todox) !=0:
        x=todox.popleft()
        y=todoy.popleft()
        count+=1
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                if nx==goalx and ny==goaly:
                    seen[ny][nx]=seen[y][x]
                    #print(seen)
                    return seen[ny][nx]
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                    elif seen[ny][nx] >seen[y][x]:
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                        
        for i in range(20):
            nx=x+ddx[i]
            ny=y+ddy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                
                    
                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]+1
                        todox.append(nx)
                        todoy.append(ny)
    
    #for i in seen:
        #print(*i)

            
    return seen[goaly][goalx]
 
            
print(dfs(starty,startx))

Submission status: Wrong Answer

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

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

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

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

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

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

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

                    if 0 <= y < H and 0 <= x < W:
                        if y == Dh and x == Dw:
                            Ch = Dh
                            Cw = Dw
                            find = 1
                            ans += 1
                            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()


if __name__ == "__main__":
    main2()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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

    H, W = map(int, readline().split())
    a, b = map(int, readline().split())
    c, d = map(int, readline().split())
    S = [readline().rstrip() for i in range(H)]

    a,b,c,d = (v - 1 for v in (a,b,c,d))

    INF = 10 ** 10

    groups = []

    visited = [[False] * W for i in range(H)]

    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    def dfs(x, y, group):
        if not (0 <= x < H and 0 <= y < W):
            return
        
        if visited[x][y]:
            return
        
        if S[x][y] == '#':
            return
        
        group.append((x,y))
        visited[x][y] = True

        for dx, dy in dirs:
            dfs(x + dx, y + dy, group)

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.' and not visited[i][j]:
                group = []
                dfs(i, j, group)
                groups.append(group)
    
    
    p2g = [[-1] * W for i in range(H)]
    for i,group in enumerate(groups):
        for x,y in group:
            p2g[x][y] = i
    
    G = len(groups)
    g_adj = [set() for i in range(G)]
    for i in range(H):
        for j in range(W):
            src = p2g[i][j]
            if src == -1:
                continue
            for x in range(max(0, i - 2), min(H - 1, i + 2) + 1):
                for y in range(max(0, j - 2), min(W - 1, j + 2) + 1):
                    if x == i and y == j:
                        continue
                    g_adj[src].add(p2g[x][y])
    
    
    src_g = p2g[a][b]
    dst_g = p2g[c][d]

    visited = [False] * G
    q = deque()
    q.append((src_g, 0))

    while q:
        node, depth = q.popleft()
        visited[node] = True

        if node == dst_g:
            print(depth)
            return

        for adj in g_adj[node]:
            if not visited[adj]:
                q.append((adj, depth + 1))
    
    print(-1)

solve()

Submission status: Wrong Answer

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


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

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

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

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

    return D


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

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

    return point


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

D=BFS()
ans=True if D[G[0]-1][G[1]-1]!=inf else False
if ans==False:print(-1);exit()
print(Check()-1)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
cy,cx = map(int,input().split())
dy,dx = map(int,input().split())
cx,cy = cx-1,cy-1
dx,dy = dx-1,dy-1

field = []
w_count = []
for h in range(H):
    line = input()
    line = [ p for p in line]
    field.append(line)
    line_c = [ H*W for i in line]
    w_count.append(line_c)
w_count[cy][cx] = 0

visited = set()
que = [(cx,cy)]
while len(que)!=0:
    x,y = que.pop()
    if (x,y) in visited:
        continue
    visited.add((x,y))
    x_min = x-2 if x>=2 else 0
    x_max = x+2 if x<=W-3 else W-1 
    y_min = y-2 if y>=2 else 0
    y_max = y+2 if y<=H-3 else H-1 
    for new_x in range(x_min,x_max+1):
        for new_y in range(y_min,y_max+1):
            if field[new_y][new_x]=='#':
                continue

            if ((new_x==x) and (new_y==y-1)) or ((new_x==x-1) and (new_y==y)) or ((new_x==x) and (new_y==y+1)) or ((new_x==x+1) and (new_y==y)):
                que.append((new_x,new_y))
                w_count[new_y][new_x] = min(w_count[y][x],w_count[new_y][new_x])
            else:
                que.append((new_x,new_y))
                w_count[new_y][new_x] = min(w_count[y][x]+1,w_count[new_y][new_x])




ans = -1 if w_count[dy][dx]==H*W else w_count[dy][dx]
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n,m=map(int,input().split())
    p1,p2=map(int,input().split())
    t1, t2 = map(int, input().split())
    ar=[]
    for i in range(n):
        ar.append(list(input()))
    if(ar[t1-1][t2-1]=='#'):
        print('-1')
        exit()
    st1=set()
    dif=[(-1,0),(1,0),(0,-1),(0,1)]
    ct=0
    for p in range(n):
        for r in range(m):
            if(ar[p][r]=='.'):
                ct+=1
                q = deque()
                q.append((p,r))
                while(q):
                    i,j=q.popleft()
                    ar[i][j] = ct
                    for a,b in dif:
                        if(0<=i+a<n and 0<=j+b<m):
                            if(ar[i+a][j+b]=='.'):
                                q.append((i+a,j+b))

    start=ar[p1-1][p2-1]
    end=ar[t1-1][t2-1]
    d=defaultdict(int)
    st=set()
    q=deque()
    if(start==end):
        print(0)
        exit()
    for i in range(n):
        for j in range(m):
            if(ar[i][j]==start):
                st.add((i,j))
                q.append((i,j))
    # print(st)
    # print(q)
    # print(d)
    # d[start]=0
    ans=-1
    while(q):
        i,j=q.popleft()
        for x in range(1,3):
            for y in range(1,3):
                temp=[(-x,y),(x,y),(x,-y),(x,y)]
                for a,b in temp:
                    c1,c2=i+a,j+b
                    if(0<=c1<n and 0<=c2<m and ar[c1][c2]!='#' and ar[c1][c2]!=ar[i][j]):
                        if((c1,c2) in st and d[ar[c1][c2]]<=d[ar[i][j]]+1):
                            continue

                        if((c1,c2) in d):
                            d[ar[c1][c2]]=min(d[ar[c1][c2]],d[ar[i][j]]+1)
                        else:
                            d[ar[c1][c2]]=d[ar[i][j]]+1
                        st.add((c1,c2))
                        q.append((c1,c2))
                        if(ar[c1][c2]==end):
                            ans=d[ar[c1][c2]]
    print(ans)



    # print(start,end)
    # for i in ar:
    #     print(i)












BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

moves=[]
updated=[]
for i in range(H+4):
    moves.append([1000000]*(W+4))
    updated.append([False]*(W+4))

for i in range(2,H+2):
    s = input().strip()
    for j in range(W):
        if s[j] == '#':
            moves[i][j+2] = -1

for i in range(H+4):
    for j in range(W+4):
        if i<=1 or i>=H+2 or j<=1 or j>=W+2:
            moves[i][j]=-1


moves[Ch][Cw]=0
sources_0 = [[-1,0],[1,0],[0,-1],[0,1]]
sources_1 = [[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2]]
sources_1 += [[-2,-1],[-1,-1],[0,-1],[1,-1],[2,-1]]
sources_1 += [[-2,0],[-1,0],[1,0],[2,0]]
sources_1 += [[-2,1],[-1,1],[0,1],[1,1],[2,1]]
sources_1 += [[-2,2],[-1,2],[0,2],[1,2],[2,2]]

n = 0
while (n <= H*W):
    n += 1
    for i in range(2,H+2):
        for j in range(2,W+2):
            if moves[i][j] <= 0:
                continue
            for src in sources_0:
                if updated[i+src[0]][j+src[1]]:
                    src_move = moves[i+src[0]][j+src[1]]
                    if src_move >= 0 and src_move < moves[i][j]:
                        moves[i][j] = src_move
                        updated[i][j] = True
            for src in sources_1:
                if updated[i+src[0]][j+src[1]]:
                    src_move = moves[i+src[0]][j+src[1]]
                    if src_move >= 0 and src_move + 1 < moves[i][j]:
                        moves[i][j] = src_move + 1
                        updated[i][j] = True

if moves[Dh][Dw] == 1000000:
    print(-1)
else:
    print(moves[Dh][Dw])

Submission status: Wrong Answer

Solution code:
def main():
    import heapq
    from collections import deque


    def normal_bfs():
        queue = deque([(C_h, C_w)])
        while queue:
            i, j = queue.popleft()
            if (i, j) == (D_h, D_w):
                return 0
            for offset in (1, -1):
                i_next = i + offset
                j_next = j + offset
                if ok(i_next, j) and (i_next, j) not in dist:
                    queue.append((i_next, j))
                    dist[i_next, j] = 0
                if ok(i, j_next) and (i, j_next) not in dist:
                    queue.append((i, j_next))
                    dist[i, j_next] = 0
        return -1



    def ok(i, j):
        return 0 <= i < H and 0 <= j < W and S[i][j] == '.'

    H, W = map(int, input().split())
    C_h, C_w = map(int, input().split())
    C_h -= 1
    C_w -= 1
    D_h, D_w = map(int, input().split())
    D_h -= 1
    D_w -= 1
    S = [[None] * W for _ in range(H)]
    for i in range(H):
        for j, c in enumerate(input()):
            S[i][j] = c

    dist = {(C_h, C_w): 0}
    if normal_bfs() == 0:
        print(0)
        exit()

    queue = [(0, (C_h, C_w))]
    while queue:
        score, cur = heapq.heappop(queue)
        if cur == (D_h, D_w):
            print(score)
            break
        i, j = cur
        for offset in (1, -1):
            i_next = i + offset
            j_next = j + offset
            if ok(i_next, j) and ((i_next, j) not in dist or dist[i_next, j] > score):
                heapq.heappush(queue, (score, (i_next, j)))
                dist[i_next, j] = score
            if ok(i, j_next) and ((i, j_next) not in dist or dist[i, j_next] > score):
                heapq.heappush(queue, (score, (i, j_next)))
                dist[i, j_next] = score

        for a in [-2, -1, 0, 1, 2]:
            for b in [-2, -1, 0, 1, 2]:
                if a == b == 0:
                    continue
                i_jump = i + a
                j_jump = j + b
                if not ok(i_jump, j_jump):
                    continue
                if (i_jump, j_jump) not in dist or dist[i_jump, j_jump] > score + 1:
                    heapq.heappush(queue, (score + 1, (i_jump, j_jump)))
                    dist[i_jump, j_jump] = score + 1
    else:
        print(-1)


main()

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 = []
scores = []
for _ in range(H):
    graph.append(list(input()))
    scores.append([float('inf')] * W)
scores[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 scores[ny][nx] == float('inf') and graph[ny][nx] == '.':
                scores[ny][nx] = scores[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 graph[ny][nx] == '.':
                    q.append([nx, ny])
                    scores[ny][nx] = min(scores[y][x] + 1, scores[ny][nx])


if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
start = list(map(int, input().split()))
goal = list(map(int, input().split()))
L = [list(input()) for _ in range(H)]
result = {}
def part(x, y, i, mem):
  if not (0<=x<H) or not (0<=y<W) or L[x][y]!=".":
    return
  L[x][y]=i
  mem.append((x,y))
  part(x-1, y, i, mem)
  part(x+1, y, i, mem)
  part(x, y-1, i, mem)
  part(x, y+1, i, mem)
mark = 0
for h in range(H):
  for w in range(W):
    if L[h][w]==".":
      mem = []
      part(h, w, mark, mem)
      result[mark]=mem
      mark += 1
dic = {i:10**8 for i in range(mark)}
s = L[start[0]-1][start[1]-1]
dic[0]=0
g = L[goal[0]-1][goal[1]-1]
queue = deque([s])
while queue:
    now = queue.popleft()
    if now==g:
        print(dic[now])
        exit()
    for (x,y) in result[now]:
        for i in range(max(x-2, 0), min(x+3, H)):
            for j in range(max(y-2, 0), min(y+3, W)):
              key = L[i][j]
              if str(key)=="#":
                continue
              if key != now and dic[key] == 10**8:
                dic[key]= dic[now]+1
                queue.append(key)             
print("-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]
      
      
      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))
          ALL.append((i-1,j))
 
      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))
          ALL.append((i,j-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))
          ALL.append((i+1,j))
 
      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))
          ALL.append((i,j+1))
 
    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(part)
    Q = list(ALL)
    
    if (f1,f2) in ALL:
      print(count)
      break
 
    if len(ALL)==0:
      print(-1)
      break
      
    ALL = []

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
INF = 1000000
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = []
maze.append(['#']*(W+2))
for i in range(H):
    maze.append(['#']+list(input())+['#'])
maze.append(['#']*(W+2))
dis = [[INF]*(W+2) for _ in range(H+2)]
d = deque()
nextd = []
dis[Ch][Cw] = 0
d.append((Ch,Cw))
dy = [0,1,0,-1]
dx = [1,0,-1,0]
cur = 0
while d:
    while d:
        y,x = d.popleft()
        if dis[y][x] == cur:
            for i in range(4):
                newy = y+dy[i]
                newx = x+dx[i]
                if maze[newy][newx] == '.':
                    if dis[newy][newx] > cur:
                        dis[newy][newx] = cur
                        d.append((newy,newx))
            for DY in range(-2,3):
                for DX in range(-2,3):
                    if abs(DX)+abs(DY) >= 2:
                        newy = y+DY
                        newx = x+DX
                        if newy <= H and newy >= 1 and newx <= W and newx >= 1: 
                            if maze[newy][newx] == '.':
                                if dis[newy][newx] > cur+1:
                                    dis[newy][newx] = cur+1
                                    nextd.append((newy,newx))
    cur += 1
    d = deque(nextd)
    nextd = []
if dis[Dh][Dw] == INF:
    print(-1)
else:
    print(dis[Dh][Dw])
print(dis)

Submission status: Wrong Answer

Solution code:
import heapq

def resolve():
    H,W = map(int,input().split())
    Sy,Sx = [int(i)-1 for i in input().split()]
    Gy,Gx = [int(i)-1 for i in input().split()]

    MP = [input() for i in range(H)]
    q =[]
    score=[[10**10]*W  for i in range(H)]
    score[Sy][Sx] = 0
    heapq.heappush(q,(Sx,Sy,0))
    visited = [[False for j in range(W)] for i in range(H)]

    while q:
        x,y,cs = heapq.heappop(q) 

        if visited[y][x]:
            continue
        visited[y][x]=True

        flg = False

        if y!=0 and MP[y-1][x]=='.' and score[y][x]<score[y-1][x]:
            flg=True
            score[y-1][x]=score[y][x]
            heapq.heappush(q,(x,y-1,cs))
        if y!=H-1 and MP[y+1][x]=='.' and score[y][x]<score[y+1][x]:
            flg=True

            score[y+1][x]=score[y][x]
            heapq.heappush(q,(x,y+1,cs))
  
        if x!=0 and MP[y][x-1]=='.' and score[y][x]<score[y][x-1]:
            flg=True
            score[y][x-1]=score[y][x]
            heapq.heappush(q,(x-1,y,cs))
        if x!=W-1 and MP[y][x+1]=='.' and score[y][x]<score[y][x+1]:
            flg=True
            score[y][x+1]=score[y][x]
            heapq.heappush(q,(x+1,y,cs))
        if flg==False:
            continue

        for i in range(max(0,y-2),min(H,y+3)):
            for j in range(max(0,x-2),min(W,x+3)):

                if MP[i][j]=='#':
                    continue
                if score[i][j]>score[y][x]+1:
                    score[i][j]=score[y][x]+1
                    heapq.heappush(q,(j,i,score[y][x]+1))

    if score[Gy][Gx]==10**10:
        print(-1)
    else:
        print(score[Gy][Gx])
    
resolve()

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:
    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)