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())
sy,sx = map(int,input().split())
sy -= 1
sx -= 1
gy,gx = map(int,input().split())
grid = [0]*H
for i in range(H):
    grid[i] = input()
cost = [[float('inf')]*W for _ in range(H)]
cost[sy][sx] = 0
done = [[0]*W for _ in range(H)]
done[sy][sx] = 1
walk_q = deque()
walk_q.append([sy,sx])
magic_q = deque()
magic_q.append([sy,sx])
def walk(y,x):
    for new_y, new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0 <= new_y < H and 0 <= new_x < W and grid[new_y][new_x] == '.':
            cost[new_y][new_x] = min(cost[new_y][new_x],cost[y][x])
            if not done[new_y][new_x]:
                walk_q.append([new_y,new_x])
                magic_q.append([new_y,new_x])
                done[new_y][new_x] = 1
def magic(y,x):
    for y_add in [i for i in range(-2,3)]:
        for x_add in [i for i in range(-2,3)]:
            if 0 <= y+y_add < H and 0 <= x+x_add < W and grid[y+y_add][x+x_add] == '.':
                cost[y+y_add][x+x_add] = min(cost[y+y_add][x+x_add],cost[y][x]+1)
                if not done[y+y_add][x+x_add]:
                    walk_q.append([y+y_add,x+x_add])
                    magic_q.append([y+y_add,x+x_add])
                    done[y+y_add][x+x_add] = 1

while walk_q or magic_q:
    while walk_q:
        y,x = walk_q.popleft()
        walk(y,x)
    while magic_q:
        y,x = magic_q.popleft()
        magic(y,x)
if not done[gy-1][gx-1]:
    print(-1)
else:
    print(cost[gy-1][gx-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())
slist = [input() for i in range(h)]

que = deque()
memo_que = deque()
que.append([ch - 1, cw - 1, 0])
memo_que.append([ch - 1, cw - 1, 0])
memo = {}
memo[(ch - 1, cw - 1)] = 0
ans = float("inf")
while len(que) != 0:
    while len(que) != 0:
        sh, sw, count = que.popleft()
        print(sh, sw, count)
        for ph, pw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if 0 <= sh + ph < h and 0 <= sw + pw < w:
                if sh + ph == dh - 1 and sw + pw == dw - 1:
                    if ans > count:
                        memo[(sh, sw)] = count
                        ans = count
                    print(ans)
                    exit()
                if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count:
                    continue
                if slist[sh + ph][sw + pw] == ".":
                    que.append([sh + ph, sw + pw, count])
                    memo[(sh + ph, sw + pw)] = count
                    for ph2, pw2 in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
                        if 0 <= sh + ph2 < h and 0 <= sw + pw2 < w:
                            if slist[ph2 + sh][pw2 + sw] == "#":
                                memo_que.append([sh + ph, sw + pw, count])
                                break

    for sh, sw, count in list(memo_que):
        print(sh, sw, count)
        for ph in range(-2, 3):
            for pw in range(-2, 3):
                if [ph, pw] not in [[-1, 0], [1, 0], [0, 1], [0, -1], [0, 0]]:
                    if 0 <= sh + ph < h and 0 <= sw + pw < w:
                        if sh + ph == dh - 1 and sw + pw == dw - 1:
                            if ans > count + 1:
                                memo[(sh, sw)] = count + 1
                                ans = count + 1
                            print(ans)
                            exit()
                        if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count + 1:
                            continue
                        if slist[sh + ph][sw + pw] == ".":
                            que.append([sh + ph, sw + pw, count + 1])
                            memo[(sh + ph, sw + pw)] = count + 1
                            memo_que.append([sh + ph, sw + pw, count + 1])
    memo_que.clear()

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():

    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cur_coor, r):
        for i1 in range(4):
            nextx = cur_coor[1] + movex[i1]
            nexty = cur_coor[0] + movey[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                rs.append(r)
                return
            elif nextg == '.':
                maze[nexty][nextx] = '-'
                dfs1((nexty, nextx), r)
            else:
                pass
        for j1 in range(20):
            nextx = cur_coor[1] + warpx[j1]
            nexty = cur_coor[0] + warpy[j1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                rs.append(r + 1)
                return
            elif nextg == '.' or nextg == '-':
                maze[nexty][nextx] = '+'
                dfs1((nexty, nextx), r + 1)
            else:
                pass
    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
    dummy = ['#'] * (w + 4)
    maze = []
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[dh][dw] = 'g'

    rs = []
    dfs1((ch, cw), 0)
    if rs:
        print(min(rs))
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ch-=1
cw-=1
dh-=1
dw-=1

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
my=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]
mx=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]

from collections import deque
ans=0

d=[[-1]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
visited=deque()
visited.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.popleft()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==-1:
            d[new_y][new_x]=d[y][x]
            queue.append((new_y, new_x))
            visited.append((new_y, new_x))

    if not queue:
        while visited:
            y,x=visited.popleft()
            for m_y, m_x in zip(my, mx):
                new_y=y+m_y
                new_x=x+m_x
                if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
                    continue
                if s[new_y][new_x]=='.' and d[new_y][new_x]==-1:
                    d[new_y][new_x]=d[y][x]+1
                    queue.append((new_y, new_x))

print(d[dh][dw])

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


        if y!=0 and MP[y-1][x]=='.' and score[y][x]<score[y-1][x]:
            dwy = 0
            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]:
            upx = 0
            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]:
            dwx = 0
            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]:
            upx = 0
            score[y][x+1]=score[y][x]
            heapq.heappush(q,(x+1,y,cs))

        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:
inf=10**4
H,W=map(int,input().split())
S=list(map(int,input().split()))
G=list(map(int,input().split()))
arr=[list(map(str,input())) for i in range(H)]
A=[(0,-1,0),(0,1,0),(-1,0,0),(1,0,0)]
B=[(0,-2,1),(0,2,1),(-2,0,1),(2,0,1),(-1,1,1),(-1,2,1),(-2,1,1),(-2,2,1),(-1,-1,1),(-1,-2,1),(-2,-1,1),(-2,-2,1),(1,1,1),(1,2,1),(2,1,1),(2,2,1),(1,-1,1),(1,-2,1),(2,-1,1),(2,-2,1)]
C=A+B
vist=[[0]*W for i in range(H)]
ans=[[inf]*W for i in range(H)]

d=[(S[0]-1,S[1]-1,0)]
ans[S[0]-1][S[1]-1]=0


while d:
    x,y,cost=d.pop()
    vist[x][y]=1
    
    for dx,dy,c in C:
        if H>x+dx>=0 and W>y+dy>=0:
           if vist[x+dx][y+dy]==0 and arr[x+dx][y+dy]==".":
            
                ans[x+dx][y+dy]=min(cost+c,ans[x+dx][y+dy])
                d.append((x+dx,y+dy,ans[x+dx][y+dy]))


if ans[G[0]-1][G[1]-1]==inf:
    print(-1)
else:
    print(ans[G[0]-1][G[1]-1])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from time import time


def main():
    start = time()

    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())
    s = [input() for _ in range(h)]
    INF = 10 ** 9

    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1

    hp = [[0, f(sh, sw)]]
    dist = [[INF] * w for _ in range(h)]
    dist[sh][sw] = 0

    while hp:
        if time() - start >= 1.8:
            break
        d, i = heappop(hp)
        hi, wi = divmod(i, w)

        if d != dist[hi][wi]:
            continue

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = hi + dh
                nw = wi + dw
                if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                    if abs(dh) + abs(dw) == 1:
                        cost = 0
                    else:
                        cost = 1

                    dist_now = d + cost
                    if dist_now < dist[nh][nw]:
                        dist[nh][nw] = dist_now
                        heappush(hp, [dist_now, f(nh, nw)])

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

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

def main():
    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)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.append((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.append((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    """  
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
                    """
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

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):
                            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().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=[list(input()) for _ in range(h)]

ch-=1
cw-=1
dh-=1
dw-=1

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
my=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]
mx=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]

from collections import deque
ans=0

d=[[-1]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
visited=deque()
visited.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.popleft()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==-1:
            d[new_y][new_x]=d[y][x]
            queue.append((new_y, new_x))
            visited.append((new_y, new_x))

    if not queue:
        while visited:
            y,x=visited.popleft()
            for m_y, m_x in zip(my, mx):
                new_y=y+m_y
                new_x=x+m_x
                if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
                    continue
                if s[new_y][new_x]=='.' and d[new_y][new_x]==-1:
                    d[new_y][new_x]=d[y][x]+1
                    queue.append((new_y, new_x))

print(d)
print(d[dh][dw])

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    h,w= map(int, input().split())
    cx,cy = map(int, input().split())
    dx,dy = map(int, input().split())
    s=[]
    s.append(list("#"*(w+4)))
    s.append(list("#"*(w+4)))
    for i in range(h):
        temp=input()
        temp="##"+temp+"##"
        s.append(list(temp))
    s.append(list("#"*(w+4)))
    s.append(list("#"*(w+4)))
#    for i in range(h+4):
#        print(s[i])

    visited = [[0 for i in range(w+4)] for _ in range(h+4)]
    warp = [[INFI for i in range(w+4)] for _ in range(h+4)]
    visited[cx+1][cy+1]=1
    warp[cx+1][cy+1]=0

    walkqueue = deque([])
    warpqueue = deque([])
    warpdire=[[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2],
           [-2,-1],[-1,-1],[1,-1],[2,-1],
           [-2,0],[2,0],
           [-2,1],[-1,1],[1,1],[2,1],
           [-2,2],[-1,2],[0,2],[1,2],[2,2],
              [0,-1],[-1,0],[1,0],[0,1]]
    walkdire=[[0,-1],[-1,0],[1,0],[0,1]]


    def warploop():
        nowx = cx + 1
        nowy = cy + 1
        for i in warpdire:
            if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] == 0:
                warpqueue.append([nowx + i[0], nowy + i[1]])
                warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy] + 1, warp[nowx + i[0]][nowy + i[1]])
                visited[nowx + i[0]][nowy + i[1]] = 1

        while warpqueue:
            if len(warpqueue) <= 0:
                break
            now = warpqueue.popleft()
            nowx = now[0]
            nowy = now[1]

            for i in warpdire:
                if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] == 0:
                    warpqueue.append([nowx + i[0], nowy + i[1]])
                    warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy] + 1, warp[nowx + i[0]][nowy + i[1]])
                    visited[nowx + i[0]][nowy + i[1]] = 1
        return
    warploop()

    def walkloop(aaa, bbb):
        nowx = aaa
        nowy = bbb
        walkvisited = []
        walkmin = warp[nowx][nowy]
        for i in walkdire:
            if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] <= 1:
                walkqueue.append([nowx + i[0], nowy + i[1]])
                warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy], warp[nowx + i[0]][nowy + i[1]])

                visited[nowx + i[0]][nowy + i[1]] = 2

        while walkqueue:
            if len(walkqueue) <= 0:
                break
            now = walkqueue.popleft()
            nowx = now[0]
            nowy = now[1]
            walkmin = min(warp[nowx][nowy], walkmin)
            walkvisited.append([nowx, nowy])
            for i in walkdire:
                if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] <= 1:
                    walkqueue.append([nowx + i[0], nowy + i[1]])
                    warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy], warp[nowx + i[0]][nowy + i[1]])
                    visited[nowx + i[0]][nowy + i[1]] = 2
        for i in walkvisited:
            warp[i[0]][i[1]] = walkmin

    if visited[dx + 1][dy + 1] != 0:
        while visited[dx + 1][dy + 1] <= 1:
            walkloop(cx + 1, cy + 1)
            for ii in range(h+4):
                for j in range(w+4):
                    if visited[ii][j]>=2 or s[ii][j]=="#":
                        continue
                    walkloop(ii,j)
                    visited[ii][j]=2



    if visited[dx+1][dy+1]==0:
        print("-1")
    else:
        print(warp[dx+1][dy+1])

#    for i in range(h+4):
 #       print(visited[i])
 #   for i in range(h+4):
 #       print(warp[i])




if __name__ == "__main__":

    main()

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 = []
for i in range(H):
	S.append(input())
que = deque([])
que.append([C[0]-1, C[1]-1, 0])
visited = [[1000 for i in range(W)] for j in range(H)]
visited[C[0]-1][C[1]-1] = 0
while que:
	cur = que.popleft()
	visited[cur[0]][cur[1]] = cur[2]
	for i in range(-2,3):
		for j in range(-2,3):
			if (i != 0 or j != 0) and cur[0] + i < H and cur[0] + i >= 0 and cur[1] + j < W and cur[1] + j >= 0:
				if S[cur[0] + i][cur[1] + j] == '.':
					if (i == 0 and j == 1) or (i == 0 and j == -1) or (i == 1 and j == 0) or (i == -1 and j == 0):
						if visited[cur[0] + i][cur[1] + j] > cur[2]:
							que.append([cur[0]+i, cur[1]+j, cur[2]])
					else:
						if visited[cur[0] + i][cur[1] + j] > cur[2]+1:
							que.append([cur[0]+i, cur[1]+j, cur[2]+1])
if visited[D[0]-1][D[1]-1] != 1000:
	print(visited[D[0]-1][D[1]-1])
else:
	print(-1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
ch, cw = map(lambda x: int(x)-1, input().split())
dh, dw = map(lambda x: int(x)-1, input().split())
S = [list(input()) for _ in range(h)]

from collections import deque
# 座標, 座標, ワープカウント
q = deque([[ch, cw, 0]])
wall = deque()
visited = [[-1] * w for _ in range(h)]
visited[ch][cw] = 0
ans = -2
while True:
    while q:
        i, j, wc = q.popleft()
        if i == dh and j == dw:
            ans = wc
            break
        for mi, mj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ni, nj = i + mi, j + mj
            if 0 <= nj < w and 0 <= ni < h:
                if S[ni][nj] == '.' and visited[ni][nj] != wc:
                    visited[ni][nj] = wc
                    q.append([ni, nj, wc])
                elif S[ni][nj] == '#':
                    wall.append([i, j, wc])
                    break
    else:
        if not wall:
            ans = -1
    if ans > -2:
        break

    while wall:
        i, j, wc = wall.popleft()
        for wi, wj in ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
                        (-1, -2), (-1, -1), (-1, 1), (-1, 2),
                        (0, -2), (0, 2),
                        (1, -2), (1, -1), (1, 1), (1, 2),
                        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)):
            ni, nj = i+wi, j+wj
            if (0 <= nj < w and 0 <= ni < h and S[ni][nj] == '.' and
                (visited[ni][nj] == -1 or visited[ni][nj] > wc+1)):
                visited[ni][nj] = wc+1
                q.append([ni, nj, wc+1])
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
Cy, Cx = map(int,input().split())
Dy, Dx = map(int,input().split())

S = ["n" * W]
for _ in range(H):
    S.append("n" + input())
present_x = Cx
present_y = Cy

def judge(present_a, goal):
    if present_a <= goal:
        return 1
    else:
        return -1

direction_x = judge(Cx, Dx)
direction_y = judge(Cy, Dy)

flag_break = False
ans = 0
while present_x != Dx or present_y != Dy:
    if flag_break == True:
        print(-1)
        exit()
    # 歩く
    if present_x != Dx:
        if S[present_y][present_x + direction_x] != "#":
            present_x += direction_x
            continue
    if present_y != Dy:
        if S[present_y + direction_y][present_x] != "#":
            present_y += direction_y
            continue
    
    # ワープ
    length_dx = abs(Dx - present_x)
    length_dy = abs(Dy - present_y)
    flag_break = True
    for i in range(3):
        for j in range(3):
            if i == 0 and j == 0:
                continue
            
            i_x = i*direction_x
            j_y = j*direction_y
            if (1 <= present_x + i_x and present_x + i_x <= W) and (1 <= present_y + j_y and present_y + j_y <= H):
                if S[present_y + j_y][present_x + i_x] != "#":
                    if length_dx <= abs(Dx - present_x + i_x) and length_dy <= abs(Dy - present_y + j_y):
                        length_dx = abs(Dx - present_x)
                        length_dy = abs(Dy - present_y)
                        present_x += i_x
                        present_y += j_y
                        flag_break = False
    direction_x = judge(present_x, Dx)
    direction_y = judge(present_y, Dy)
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import sys
H, W = map(int, input().split())
C = tuple(int(x) - 1 for x in input().split())
D = tuple(int(x) - 1 for x in input().split())
S = [sys.stdin.readline() + "###" for _ in range(H)]
S.append("#" * (W + 3))
S.append("#" * (W + 3))

ans = 0
todo = collections.deque()
todo.append(C)
done = set()
while todo:
    pdone = []
    while todo:
        p = todo.popleft()
        done.add(p)
        pdone.append(p)
        h, w = p
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nh, nw = (h + dh, w + dw)
            if S[nh][nw] == "#":
                continue
            np = (nh, nw)
            if np == D:
                print(ans)
                sys.exit()
            if np in done:
                continue
            todo.append(np)

    ans += 1
    for h, w in pdone:
        for nh in range(h - 2, h + 2 + 1):
            for nw in range(w - 2, w + 2 + 1):
                if S[nh][nw] == "#":
                    continue
                np = (nh, nw)
                if np == D:
                    print(ans)
                    sys.exit()
                if np in done:
                    continue
                todo.append(np)
print(-1)