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:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
# Verified by
# https://atcoder.jp/contests/arc033/submissions/me
# https://atcoder.jp/contests/abc174/tasks/abc174_f
#
# speed up TIPS: delete update of el. non-use of getitem, setitem.
#
# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get bound of index where x1+x2+...+xi<w

class Bit: # 1-indexed
    def __init__(self,n,init=None):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        self.el=[0]*(2**self.m+1)
        if init!=None:
            for i in range(len(init)):
                self.add(i,init[i])
                self.el[i]=init[i]

    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        if not 0<i<=self.size:return NotImplemented
        self.el[i]+=x
        while i<=self.size:
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        if not 0<=i<=self.size:return NotImplemented
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def __getitem__(self,key):
        return self.el[key]
        return self.sum(key+1)-self.sum(key)

    def __setitem__(self,key,value):
        self.add(key,value-self.sum(key+1)+self.sum(key))

    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
class Bit0(Bit): # 0-indexed
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)

def compress(L):
    dc={v:i for i,v in enumerate(sorted(set(L)))}
    return [dc[i] for i in L]


show_flg=False
show_flg=True

ans=0

h,w=LI()
sh,sw=LI()
gh,gw=LI()

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='#'for i in s]+[1]
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h

dc=dict()
cn=0
def bfs(x):
    global cn
    q=[x]
    v[x]=x
    dc[x]=cn
    cn+=1
    while q:
        c=q.pop()
        for nx in [c+1,c-1,c+w,c-w]:
            if 0<=nx<n and m[nx]!=1 and v[nx]==-1:
                q+=nx,
                v[nx]=x
    return        
            
for i in range(n):
    if m[i]!=1 and v[i]==-1:
        bfs(i)

g=[set()for i in range(cn)]
nb=[-2*w+1,-2*w+2,-w+1,-w+2,1,2,2*w+1,2*w+2,w+1,w+2,+w,+2*w,-w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-1,-2,2*w-1,2*w-2,w-1,w-2]

u=[-1]*cn
for i in range(n):
    if m[i]==1:
        continue
    u[dc[v[i]]]=1
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1 and dc[v[i]]!=dc[v[nx]]:
            g[dc[v[i]]].add(dc[v[nx]])

q=[dc[v[sh*w+sw]]]
dist=[-1]*cn
dist[dc[v[sh*w+sw]]]=0
while q:
    c=q.pop()
    for nx in g[c]:
        if dist[nx]==-1:
            q+=nx,
            dist[nx]=dist[c]+1

print(dist[dc[v[gh*w+gw]]])

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())
    sh, sw = map(int, input().split())
    sh -= 1; sw -= 1
    start = (sh+2)*(W+4) + 2 + sw
    dh, dw = map(int, input().split())
    dh -= 1; dw -= 1
    goal = (dh+2)*(W+4) + 2 + dw

    field = "#"*(W+4)*2
    field += "##" + "####".join([ input() for _ in range(H)]) + "##"
    field += "#"*(W+4)*2

    move = [-1, 1, -(W+4), W+4]
    ex_up = [-2*(W+4)-2, -2*(W+4)-1, -2*(W+4), -2*(W+4)+1, -2*(W+4)+2]
    ex_down = [2*(W+4)-2, 2*(W+4)-1, 2*(W+4), 2*(W+4)+1, 2*(W+4)+2]
    ex_left = [-2*(W+4)-2, -(W+4)-2, -2, (W+4)-2, 2*(W+4)-2]
    ex_right = [-2*(W+4)+2, -(W+4)+2, +2, (W+4)+2, 2*(W+4)+2]

    INF = 10 ** 9
    num = [INF] * (H+4) * (W+4)
    warped = [False] * (H+4) * (W+4)

    def bfs(s):
        q = deque()
        num[s] = 0
        q.append((s, 0))
    
        while q:
            now, cost = q.popleft()
            if cost > num[now]:
                continue
            else:
                num[now] = cost
            for i, dx in enumerate(move):
                nx = now + dx
                if nx == goal:
                    num[nx] = cost
                    return
                if field[nx] == "." and num[nx] == INF:
                    q.appendleft((nx, cost))
                    num[nx] = cost

                elif field[nx] == "#":
                    if i == 0:
                        ex = ex_left
                    elif i == 1:
                        ex = ex_right
                    elif i == 2:
                        ex = ex_up
                    else:
                        ex = ex_down

                    for dx2 in ex:
                        nx2 = now + dx2
                        if field[nx2] == "." and num[nx2] == INF and not warped[nx2]:
                            q.append((nx2, cost+1))
                            warped[nx2] = True
    
    bfs(start)

    if num[goal] == INF:
        print(-1)
    else:
        print(num[goal])

    
    # for i in range(0, (H+4)*(W+4), W+4):
    #     print(field[i:i+W+4])
    
    # print(start)
    # print(start//(W+4), start%(W+4))
    # print(goal)
    # print(goal//(W+4), goal%(W+4))
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H,W = list(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())
c = [[-1]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
def f(h,w,i):
    # print(h,w)
    global visited ,c
    if visited[h][w] == 0:
        visited[h][w] = 1
        if not S[h][w] == "#":
            c[h][w] = i-1
        try:
            if S[h+1][w] == ".":
                f(h+1,w,i)
        except:
            pass
        try:
            if S[h][w+1] == ".":
                f(h,w+1,i)
        except:
            pass
        try:
            if S[h-1][w] == "." and not h-1 <0:
                f(h-1,w,i)
        except:
            pass
        try:
            if S[h][w-1] == "." and not w-1 <0:
                f(h,w-1,i)
        except:
            pass
h = C[0]-1
w = C[0]-1
k = 1
def f2(h,w,k):
    global c,visited
    f(h,w,k)
    for i in range(H):
        for j in range(W):
            if visited[i][j] == 0 and S[i][j] == ".":
                for i2 in range(-2,3):
                    for j2 in range(-2,3):
                        # print(i+i2,j+j2)
                        try:
                            if c[i+i2][j+j2] == k-1:
                                c[i][j] = k
                                # visited[i][j] = 1
                                f2(i,j,k+1)
                        except:
                            pass
f2(h,w,k)
print(c[D[0]-1][D[1]-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("#","1")
    maze.append(list(map(int, RRR)))
#print(maze)
dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
Es=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[]
for i in range(-2,3):
    for j in range(-2,3):
        wap.append((i,j))
wap.remove((0,0))
wap=list(set(wap))
cand=[start]
dis[start[0]][start[1]]=0
done=[]
flag=False

while len(cand)>0:
    #print("dis",dis[1:])
    #print("cand",cand)
    place=cand.pop()
    edges=[]
    #done.append(place)
    hh,ww,cost=place
    if hh==Dh and ww==Dw:
        flag=True
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost:
            dis[h1][w1]=cost
            cand.append((h1,w1,cost))
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==1 and Es[hh][ww]>cost:
            Es[hh][ww]=cost
            edges.append((hh,ww,cost))
    if len(cand)==0:
        #print("edge",edges)
        for place in edges:
            hh,ww,cost=place
            for each in wap:
                h1,w1=hh+each[0],ww+each[1]
                #print(h1,w1)
                if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
                    dis[h1][w1]=cost+1
                    cand.append((h1,w1,cost+1))
        #print("cand",cand)
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
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 = list()
for i in range(H):
  S.append(list(input()))

from collections import defaultdict
mincost = defaultdict(lambda:defaultdict(lambda:10**10))
mincost[C_h][C_w] = 0
cost0 = [(-1,0),(1,0),(0,-1),(0,1)]
import queue
q = queue.Queue()
q.put((C_h, C_w))

while not q.empty():
  now_h, now_w = q.get()
  for (h, w) in cost0:
    next_h = now_h + h
    next_w = now_w + w
    if next_h >= 0 and next_h < H and next_w >= 0 and next_w < W:
      if S[next_h][next_w] == ".":
        if mincost[next_h][next_w] > mincost[now_h][now_w]:
          mincost[next_h][next_w] = mincost[now_h][now_w]
          q.put((next_h, next_w))
  for i in range(max(now_h-2,0),min(now_h+2,H)):
    for j in range(max(now_w-2,0), min(now_w+2,W)):
      if S[i][j] == ".":
        if mincost[i][j] > mincost[now_h][now_w]+1:
          mincost[i][j] = mincost[now_h][now_w]+1
          q.put((i,j))
if mincost[D_h][D_w] != 10**10:
  print(mincost[D_h][D_w])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix


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

parent = [[(i, j) if s[i][j] == '.' else None for j in range(w)] for i in range(h)]
for i, row in enumerate(s):
    for j, p in enumerate(row):
        if p != '.':
            continue
        left = s[i][j-1] if j > 0 else '#'
        right = s[i][j+1] if j < w-1 else '#'
        up = s[i-1][j] if i > 0 else '#'
        down = s[i+1][j] if i < h-1 else '#'
        if left == '.':
            parent[i][j] = (i, j-1)
        elif up == '.':
            parent[i][j] = (i-1, j)
        elif right == '.':
            parent[i][j+1] = (i, j)
        elif down == '.':
            parent[i+1][j] = (i, j)


def root(i, j, parent):
    if (i, j) == parent[i][j]:
        return i, j
    else:
        result = root(*parent[i][j], parent)
        parent[i][j] = result
        return result


a, b = [], []
expanded = ['#'*(w+4), '#'*(w+4), *['##' + row + '##' for row in s], '#'*(w+4), '#'*(w+4)]
for i, row in enumerate(s):
    for j, p in enumerate(row):
        if p != '.':
            continue
        for k in range(5):
            for l in range(5):
                if expanded[i+k][j+l] == '.':
                    a.append(root(i, j, parent)[1]*w+root(i, j, parent)[0])
                    b.append(root(i-2+k, j-2+l, parent)[1]*w+root(i-2+k, j-2+l, parent)[0])
g = csr_matrix(([1]*len(a), (a, b))) > 0
shotest = dijkstra(g, indices=root(ch-1, cw-1, parent)[1]*w+root(ch-1, cw-1, parent)[0])
result = shotest[root(dh-1, dw-1, parent)[1]*w+root(dh-1, dw-1, parent)[0]]
print(-1 if result == float('inf') else int(result))

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 

    if s[a+1,b]=='.': 
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    if s[a,b+1]=='.':
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    if s[a-1,b]=='.':
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    if s[a,b-1]=='.':
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])


    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                wq.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1

    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.popleft()
        bfs(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return


H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= deque([])

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)

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())
field = set()

cnt = 0
for i in range(h):
  s = input()
  for j in range(w):
    if s[j] == ".":
      field.add((i, j))
      cnt += 1

ans = 0
dq = deque()
dq.append((ch - 1, cw - 1))

while (dh - 1, dw - 1) in field:
  field2 = set()
  field3 = set()
  field2.add((ch - 1, cw - 1))
  while len(dq) > 0:
    now_h, now_w = dq.popleft()
    if (now_h, now_w) in field:
      field.remove((now_h, now_w))
      cnt -= 1
    if (now_h - 1, now_w) in field:
      dq.append((now_h - 1, now_w))
      field2.add((now_h - 1, now_w))
    if (now_h + 1, now_w) in field:
      dq.append((now_h + 1, now_w))
      field2.add((now_h + 1, now_w))
    if (now_h, now_w - 1) in field:
      dq.append((now_h, now_w - 1))
      field2.add((now_h + 1, now_w))
    if (now_h, now_w + 1) in field:
      dq.append((now_h, now_w + 1))
      field2.add((now_h, now_w + 1))
  
  if (dh - 1, dw - 1) in field:
    flag = False
    for _h, _w in field2:
      for i in range(-2, 3):
        for j in range(-2, 3):
          if (_h + i, _w + j) in field and (_h + i, _w + j) not in field3:
            ans += 1
            dq.append((_h + i, _w + j))
            field3.add((_h + i, _w + j))
            flag = True
    if not flag:
      break

print(ans if cnt == 0 else -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 = [list(input()) for _ in range(h)]



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

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

Submission status: Wrong Answer

Solution code:
from heapq import *
from sys import stdin
input=stdin.readline
n,m=map(int,input().split())
a,b=map(int,input().split())
x,y=map(int,input().split())
x=x-1
y=y-1
arr=[]
from math import inf
for i in range(n):
    arr.append(list(input().strip()))
def isvalid(x,y):
    if x<0 or y<0 or x>=n or y>=m or arr[x][y]=="#" :
        return False
    return True
vis=[[0]*m for i in range(n)]
stack=[[0,a-1,b-1]]
heapify(stack)
if x==a-1 and y==b-1 and arr[x][y]=="#":
    print(-1)
    quit()

mi=inf
ans=[[inf]*m for i in range(n)]
ans[a-1][b-1]=0
while(stack):
    cost,xx,yy=heappop(stack)
    if xx==x and yy==y:
        mi=min(mi,cost)
        break

    for i in range(-2,3,1):
        for j in range(-2, 3, 1):
            if isvalid(xx+i,yy+j):
                if -1<=i<=1 and -1<=j<=1 and i!=j:
                    if ans[xx+i][yy+j]>cost:
                        ans[xx + i][yy + j] =cost
                        heappush(stack,[cost,xx+i,yy+j])
                else:
                    if ans[xx+i][yy+j] > cost+1:
                        ans[xx + i][yy + j] =cost+1
                        heappush(stack,[cost+1, xx+i, yy + j])
if mi==inf:
    print(-1)
else:
    print(mi)

Submission status: Wrong Answer

Solution code:
from collections import deque

# import sys

# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)


def main():
    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 = []
    S.append(["#"] * (4 + W))
    S.append(["#"] * (4 + W))
    for i in range(H):
        S.append(["#", "#"] + list(input()) + ["#", "#"])
    S.append(["#"] * (4 + W))
    S.append(["#"] * (4 + W))
    warp = [[-1] * (4 + W) for _ in range(H + 4)]
    # print(S, warp)
    dx = [-1, 0, 0, 1]
    dy = [0, 1, -1, 0]

    isvisited = [[False] * (4 + W) for _ in range(H + 4)]

    def bfs(i, j):
        q = deque()
        q.append((i, j))
        warp[i][j] = 0
        while q:
            a, b = q.popleft()
            isvisited[a][b] = True
            for k in range(4):
                # nx =max(0, min(H, a + dx[k]))
                # ny = max(0, min(W, b + dy[k]))

                # warpの処理を先に
                for aa in range(-2, 3):
                    for bb in range(-2, 3):
                        if aa == 0 and bb == 0:
                            continue
                        if S[a + aa][b + bb] == "#":
                            continue
                        if warp[a + aa][b + bb] != -1:
                            continue
                        warp[a + aa][b + bb] = warp[a][b] + 1
                        q.append((a + aa, b + bb))
                        # print(a, b, aa, bb, warp)

                # 移動Aで行けるなら処理を行う
                if S[a + dx[k]][b + dy[k]] == "#":
                    continue
                # if warp[a + dx[k]][b + dy[k]] != -1:
                if isvisited[a + dx[k]][b + dy[k]]:
                    continue
                warp[a + dx[k]][b + dy[k]] = min(warp[a + dx[k]][b + dy[k]], warp[a][b])
                q.append((a + dx[k], b + dy[k]))

    bfs(Ch + 2, Cw + 2)
    print(warp[Dh + 2][Dw + 2])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

def solve(now_x, now_y):
    for next_y in range(-2, 3):
        for next_x in range(-2, 3):
            x, y = now_x + next_x, now_y + next_y
            if 0 <= x < w and 0 <= y < h:
                if c[y][x] != "#" and c[y][x] != "=" and c[y][x] != "!":
                    c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                    d2.append([x, y])


from collections import deque
import sys

input = sys.stdin.readline

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
c = [input() for _ in range(h)]
cw -= 1
ch -= 1
dw -= 1
dh -= 1
c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
d1 = deque([[cw, ch]])
d2 = deque([])

cnt = 0
for _ in range(5000):
    for _ in range(5000):
        for _ in range(len(d1)):
            now_x, now_y = d1.popleft()
            for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                x, y = now_x + next_x, now_y + next_y
                if 0 <= x < w and 0 <= y < h:
                    if x == dw and y == dh:
                        print(cnt)
                        exit()
                    if c[y][x] == "#":
                        solve(now_x, now_y)
                    if c[y][x] != "#" and c[y][x] != "=":
                        c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                        d1.append([x, y])

    else:
        cnt += 1
        if [dw, dh] in d2:
            print(cnt)
            exit()
        if not d2:
            print(-1)
            exit()
        d1 = d2.copy()
        d2.clear()

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:
    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]=distance[i][j]+1

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
c = [int(i) + 1 for i in input().split()]
d = [int(i) + 1 for i in input().split()]

s = []
s.append('#'*(W+4))
s.append('#'*(W+4))
for i in range(H):
    a = input()
    s.append('##' + a + '##')
s.append('#'*(W+4))
s.append('#'*(W+4))

q = deque([]) # 探索開始点
qq = deque([])
q.append((c[0], c[1], 0))
visited = [[False for __ in range(W+4)] for _ in range(H+4)]

ans = 0

while q:
    xx, yy, kaisuu = q.popleft()
    qq.append((xx, yy, kaisuu))
    visited[xx][yy] = True
    ls = []
    while qq:
        x, y, kaisuu = qq.pop()
        visited[x][y] = True
        ls.append((x, y, kaisuu))
        if x == d[0] and y == d[1]:
            print(kaisuu)
            sys.exit()
        if s[x+1][y] == '.' and visited[x+1][y] == False:
            qq.append((x+1, y, kaisuu))
        if s[x-1][y] == '.' and visited[x-1][y] == False:
            qq.append((x-1, y, kaisuu))
        if s[x][y+1] == '.' and visited[x][y+1] == False:
            qq.append((x, y+1, kaisuu))
        if s[x][y-1] == '.' and visited[x][y-1] == False:
            qq.append((x, y-1, kaisuu))
    for u in ls:
        a, b, e = u
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if abs(i) == 1 and abs(j) == 1:
                    continue
                if s[a+i][b+j] == '.' and visited[a+i][b+j] == False:
                    q.append((a+i, b+j, e+1))
print(-1)