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: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

icase=0
if icase==0:
    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=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

icase=0
if icase==0:
    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=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    g[i]=[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] 

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

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

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = ""
for h in range(H):
    S += input()
    
G = [{} for i in range(H*W)]
INF = 10**18
for h in range(H):
    for w in range(W):
        now = h * W + w
        if now != "#":
            # left
            t = now - 1
            if  h * W <= t:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # right
            t = now + 1
            if  h * W <= t < (h+1) * W:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # up
            t = now - W
            if 0 <= t < H*W:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # down
            t = now + W
            if 0 <= t < H*W:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
        
            # Warp
            for hh in range(-2, 3):
                t = (h+hh)*W + w
                #print(now)
                for i in range(-2, 3):
                    t_ = t + i
                    if 0<= t_ < H*W  and ((h+hh) * W <= t_ <(h+hh+1) * W):
                        if t_ != now and t_ not in G[now].keys() and S[t_] == ".":
                            G[now][t_] = 1
                        
import queue
def solve(s, t):
    global G
    fixed = {}
    q = queue.PriorityQueue()
    q.put((0, s)) # 0は累積コスト
    while q.empty() == False:
        w, x = q.get()
        if x == t: 
            return w
        if x in fixed: 
            continue;
        fixed[x] = w
        for y in G[x]:
              if y not in fixed:
                    q.put((w + G[x][y], y))
    return None

s = (Ch-1)*W + Cw-1
t = (Dh-1)*W + Dw-1
ans = solve(s, t)
if ans >= INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque

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

icase=0
if icase==0:
    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=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


for j in ww:
    for i in hh[0:-1]:
        if s[i+1][j]==".": g[i][j].append((i+1,j))        
        if s[i][j]==".": g[i+1][j].append((i,j))        
for i in hh:
    for j in ww[0:-1]:
        if s[i][j+1]==".": g[i][j].append((i,j+1))        
        if s[i][j]==".": g[i][j+1].append((i,j))        


#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

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

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = ""
for h in range(H):
    S += input()
    
G = [{} for i in range(H*W)]
INF = 10**18
for h in range(H):
    for w in range(W):
        now = h * W + w
        # left
        t = now - 1
        if  h * W <= t:
            if S[t] == "#":
                G[now][t] = INF
            else:
                G[now][t] = 0
        # right
        t = now + 1
        if  h * W <= t < (h+1) * W:
            if S[t] == "#":
                G[now][t] = INF
            else:
                G[now][t] = 0
        # up
        t = now - W
        if 0 <= t < H*W:
            if S[t] == "#":
                G[now][t] = INF
            else:
                G[now][t] = 0
        # down
        t = now + W
        if 0 <= t < H*W:
            if S[t] == "#":
                G[now][t] = INF
            else:
                G[now][t] = 0
        
        # Warp
        for hh in range(-2, 3):
            t = (h+hh)*W + w
            #print(now)
            for i in range(-2, 3):
                t_ = t + i
                if 0<= t_ < H*W  and ((h+hh) * W <= t_ <(h+hh+1) * W):
                    if t_ != now and t_ not in G[now].keys() and S[t_] == ".":
                        G[now][t_] = 1
                        
import queue
def solve(s, t):
    global G
    fixed = {}
    q = queue.PriorityQueue()
    q.put((0, s)) # 0は累積コスト
    while q.empty() == False:
        w, x = q.get()
        if x == t: 
            return w
        if x in fixed: 
            continue;
        fixed[x] = w
        for y in G[x]:
              if y not in fixed:
                    q.put((w + G[x][y], y))
    return None

s = (Ch-1)*W + Cw-1
t = (Dh-1)*W + Dw-1
ans = solve(s, t)
if ans >= INF:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque

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

icase=0
if icase==0:
    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=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


for j in ww:
    for i in hh[0:-1]:
#    if i+1<h:
        if s[i+1][j]==".":
            g[i][j].append((i+1,j))        
    for i in hh[1:]:
#    if 0<=i-1:
#    for j in ww:
        if s[i-1][j]==".":
            g[i][j].append((i-1,j))        
for i in hh:
    for j in ww[0:-1]:
#        if j+1<w:
        if s[i][j+1]==".":
            g[i][j].append((i,j+1))        
#for i in hh:
    for j in ww[1:]:
#        if 0<=j-1:
        if s[i][j-1]==".":
            g[i][j].append((i,j-1))        


#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


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


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


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))
    return dist


# MAGIC = ((-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2),
#          (-2, -1), (-1, -1), (0, -1), (1, -1), (2, -1),
#          (-2, 0), (-1, 0), (0, 0), (1, 0), (2, 0),
#          (-2, 1), (-1, 1), (0, 1), (1, 1), (2, 1),
#          (-2, -2), (-1, 2), (0, 2), (1, 2), (2, 2))

MAGIC = ((-2, -2), (-1, -2), (1, -2), (2, -2),
         (-2, -1), (-1, -1),  (1, -1), (2, -1),
         (-2, 1), (-1, 1), (1, 1), (2, 1),
         (-2, -2), (-1, 2), (1, 2), (2, 2))
H, W = zz()
c_h, c_w = zz()
d_h, d_w = zz()
board = []
N = H*W
for i in range(H):
    tmp = S()
    # N += tmp.count('.')
    board.append(tmp)

path = [[] for _ in range(N)]
for h in range(H):
    for w in range(W):
        if board[h][w] == '.':
            for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                new_h = h + dy
                new_w = w + dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if(board[new_h][new_w] == '.'):
                    path[h*W + w].append((0, new_h*W + new_w))
                    path[new_h*W + new_w].append((0, h*W + w))
                else:
                    #  隣は壁
                    new_h = h + dy*2
                    new_w = w + dx*2
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):  # 2個先は存在
                        path[h*W + w].append((1, new_h*W + new_w))
                        path[new_h*W + new_w].append((1, h*W + w))
                for dy, dx in MAGIC:
                    new_h = h + dy
                    new_w = w + dx
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):
                        path[h*W + w].append((1, new_h*W + new_w))
                        path[new_h*W + new_w].append((1, h*W + w))

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
dist = dijkstra(path, N, c_h*W + c_w)
print(dist[d_h*W+d_w])

"""

print(board)
que = deque([[c_h, c_w]])
visited = []
# bfs()
while que:
    h, w = que.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if board[new_h][new_w] == '.':  # セルが白('.')であるのと同義
            que.append((new_h, new_w))

    print(h, w)
"""

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = tuple(map(int, input().split()))

E = tuple(map(int, input().split()))


matrix = [[ c for c in input()] for _ in range(H)]
direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]
jump = [(x, y) for x in [-2, -1, 0, 1, 2] for y in [-2, -1, 0, 1, 2]]

q = [S]
q_idx = 0
jump_idx = 0
cost = 0
matrix[S[0]-1][S[1]-1] = cost

jump_point = {S}

while q_idx < len(q):
  if q[q_idx] == E:
    break
  while q_idx < len(q):
    d = q[q_idx]
    jump_point.add(d)
    
    q_idx += 1

    for t in direct:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))
        
  
  cost += 1
  for d in jump_point:
    for t in jump:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))
  jump_point.clear()

if matrix[E[0] -1][E[1] -1] == ".":
  print(-1)
else:
  print(matrix[E[0] -1][E[1] -1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = tuple(map(int, input().split()))

E = tuple(map(int, input().split()))


matrix = [[ c for c in input()] for _ in range(H)]
direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]
jump = [(x, y) for x in [-2, -1, 0, 1, 2] for y in [-2, -1, 0, 1, 2]]

q = []
q_idx = 0
jump_idx = 0
cost = 0
q.append(S)
matrix[S[0]-1][S[1]-1] = cost


while q_idx < len(q):
  if q[q_idx] == E:
    break
  while q_idx < len(q):
    d = q[q_idx]

    
    q_idx += 1

    for t in direct:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))
  
  cost += 1
  for d in set(q[jump_idx:q_idx]):
    for t in jump:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))
  jump_idx = q_idx

if matrix[E[0] -1][E[1] -1] == ".":
  print(-1)
else:
  print(matrix[E[0] -1][E[1] -1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = tuple(map(int, input().split()))

E = tuple(map(int, input().split()))


matrix = [[ c for c in input()] for _ in range(H)]
direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]
jump = [(x, y) for x in [-2, -1, 0, 1, 2] for y in [-2, -1, 0, 1, 2]]

q = []
q_idx = 0
jump_idx = 0
cost = 0
q.append(S)
matrix[S[0]-1][S[1]-1] = cost


while q_idx < len(q):
  if q[q_idx] == E:
    break
  while q_idx < len(q):
    d = q[q_idx]

    
    q_idx += 1

    for t in direct:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))
  
  cost += 1
  for d in q[jump_idx:q_idx]:
    for t in jump:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))
  jump_idx = q_idx

if matrix[E[0] -1][E[1] -1] == ".":
  print(-1)
else:
  print(matrix[E[0] -1][E[1] -1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = tuple(map(int, input().split()))

E = tuple(map(int, input().split()))


matrix = [[ c for c in input()] for _ in range(H)]
direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]
jump = [(x, y) for x in [-2, -1, 0, 1, 2] for y in [-2, -1, 0, 1, 2]]

q = []
q_idx = 0
jump_idx = 0
cost = 0
q.append(S)
matrix[S[0]-1][S[1]-1] = cost


while q_idx < len(q):
  while q_idx < len(q):
    d = q[q_idx]

    
    q_idx += 1

    for t in direct:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))
  
  cost += 1
  for d in q[jump_idx:q_idx]:
    for t in jump:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))
  jump_idx = q_idx

if matrix[E[0] -1][E[1] -1] == ".":
  print(-1)
else:
  print(matrix[E[0] -1][E[1] -1])

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = tuple(map(int, input().split()))

E = tuple(map(int, input().split()))


matrix = [[ c for c in input()] for _ in range(H)]
direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]
jump = [(x, y) for x in [-2, -1, 0, 1, 2] for y in [-2, -1, 0, 1, 2]]

q = []
q_idx = 0
jump_idx = 0
cost = 0
q.append(S)
matrix[S[0]-1][S[1]-1] = cost


while q_idx < len(q):
  while q_idx < len(q):
    d = q[q_idx]

    
    q_idx += 1

    for t in direct:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))
  
  cost += 1
  for d in q[jump_idx:q_idx]:
    for t in jump:
      x = d[1] - 1 + t[1]
      y = d[0] - 1 + t[0]
      if 0 <= x < W and 0 <= y < H and matrix[y][x] == ".":
        matrix[y][x] = cost
        q.append((y+1, x+1))

if matrix[E[0] -1][E[1] -1] == ".":
  print(-1)
else:
  print(matrix[E[0] -1][E[1] -1])

Submission status: Time Limit Exceeded

Solution code:
#-----モジュールの読み込み-----
from collections import deque
 
#-----入力受け取り-----
H ,W = map(int,input().split())
Sa,Sb = map(int,input().split())
Ga,Gb = map(int,input().split())
maze_list = [input() for i in range(H)]
 
Sa = Sa - 1
Sb = Sb - 1
Ga = Ga - 1
Gb = Gb - 1
 
que1 = []
que1.append((Sa,Sb))
quelist = []
 
#-----全ての座標に-1の値を代入-----
 
dist = [[10**9]*W for i in range(H)]
dist[Sa][Sb] = 0
 
#-----------動作
 
count = 0
 
while len(que1) > 0 and dist[Ga][Gb] == 10**9:
    quelist = que1
    que1 = deque(que1)
    
   
    while  len(que1) > 0:
        i,j = que1.popleft()
        for i2, j2 in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
            if not (0 <= i2 <= H-1 and 0 <= j2 <= W-1):
                continue
            if maze_list[i2][j2] == "." and dist[i2][j2] > count:
                dist[i2][j2] = count
                que1.append((i2,j2))
                quelist.append((i2,j2))
    
    que2 = deque(quelist)
    count += 1
    que1 = []
    
    while len(que2) > 0:
        i,j = que2.popleft()
        for di in range(-2,3):
            for dj in range(-2,3):
                i3 = i+di
                j3 = j+dj
 
                if not (0 <= i3 <= H-1 and 0 <= j3 <= W-1):
                    continue
                if maze_list[i3][j3] == "." and dist[i3][j3] > count:
                    dist[i3][j3] = count
                    que1.append((i3,j3))
                else:
                    pass
                
 
if dist[Ga][Gb] == 10**9:
    print(-1)
else:
    print(dist[Ga][Gb])

Submission status: Time Limit Exceeded

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

maze = []
for hh in range(H):
    maze.append(input())

stepx = [-1, 0, 1, 0]
stepy = [0, -1, 0, 1]
visited = [[0]*(W+2) for _ in range(H+2)]
def floodfill(comp, src):
    count = 0
    while len(src) > 0:
        stak = []
        for (sy, sx) in src:
            #add to new component
            visited[sy][sx] = comp
            if sy == dy and sx == dx: break
            count += 1
            for i in range(4):
                ny, nx = sy + stepy[i], sx + stepx[i]
                if nx >= 0 and nx < W and ny >= 0 and ny < H\
                        and visited[ny][nx] == 0 and maze[ny][nx] == '.':
                    visited[ny][nx] = -1
                    stak.append((ny, nx))
        src = stak
    return count


def findnext(comp):
    count = 0
    nxt = []
    for h in range(0, H):
        for w in range(0, W):
            if visited[h][w] == comp:
                for ii in range(-2, 3):
                    nh = h + ii
                    if nh >= 0 and nh < H:
                        for jj in range(-2, 3):
                            nw = w + jj
                            if nw >= 0 and nw < W and visited[nh][nw] == 0 and maze[nh][nw] == '.':
                                visited[nh][nw] = -1
                                nxt.append((nh, nw))

    return nxt

ans = 0
total = 0
comp = 1

#floodfill source
if maze[cy][cx] == '.' and visited[cy][cx] == 0:
    count = floodfill(comp, [(cy, cx)])

# #floodfill dest
# if maze[dy][dx] == '.' and visited[dy][dx] == 0:
#     count = floodfill(comp, (dy, dx))
#     if count > 0:
#         total += count
#         comp += 1
#
#
while count > 0 and visited[dy][dx] <= 0:
    total += count
    src = findnext(comp)
    comp += 1
    if len(src) > 0:
        count = floodfill(comp, src)
    else: count = 0

print(visited[dy][dx] - 1)