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:
def resolve():
    import sys
    input = sys.stdin.readline
    from collections import deque
    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
    s=[input() for _ in range(h)]
    d=[[1,0],[-1,0],[0,1],[0,-1]]
    INF=10**12
    path=[[INF]*w for _ in range(h)]
    ans=0
    st=[]
    st=deque()
    st.append((ch,cw,0))
    wp=[]
    wp=deque()
    while st:
      nx,ny,ncost=st.popleft()
      wp.append((nx,ny,ncost))
      path[nx][ny]=ncost
      for dx,dy in d:
        x=nx+dx
        y=ny+dy
        if (0<=x<=h-1) and (0<=y<=w-1):
          if s[x][y]!='#' and path[x][y]>ncost:
            path[x][y]=ncost
            st.append((x,y,ncost))
      if len(st)==0:
        while wp:
          nx,ny,ncost=wp.popleft()
          for i in range(-2,3):
            for j in range(-2,3):
              if (i,j)==(0,0) or (i,j)==(1,0) or (i,j)==(0,1) or (i,j)==(-1,0) or (i,j)==(0,-1):
                continue
              x,y=i+nx,j+ny
              if (0<=x<=h-1) and (0<=y<=w-1):
                if s[x][y]!='#' and path[x][y]>ncost+1:
                  path[x][y]=ncost+1
                  st.append((x,y,ncost+1))
    if path[dh][dw]==INF:
      print(-1)
    else:
      print(path[dh][dw])

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

    def bfs(S, start_h, start_w, goal_h, goal_w, H, W):
        que0 = deque()
        que1 = deque()
        dist = [[INF] * W for _ in range(H)]
        dist[start_h][start_w] = 0
        que0.append((start_h, start_w))
        while que0 or que1:
            nh, nw = que0.popleft() if que0 else que1.popleft()
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    next_h = nh + dh
                    next_w = nw + dw
                    cost = 0 if abs(dh) + abs(dw) <= 1 else 1
                    if not (0 <= next_h < H and 0 <= next_w < W):
                        continue
                    if S[next_h][next_w] == '#':
                        continue
                    if dist[next_h][next_w] > dist[nh][nw] + cost:
                        dist[next_h][next_w] = dist[nh][nw] + cost
                        if cost == 0:
                            que0.append((next_h, next_w))
                        else:
                            que1.append((next_h, next_w))
        return dist[goal_h][goal_w] if dist[goal_h][goal_w] != INF else - 1
        
    H, W = map(int, input().split())
    Ch, Cw = (int(i) - 1 for i in input().split())
    Dh, Dw = (int(i) - 1 for i in input().split())
    S = [input() for _ in range(H)]
    
    INF = 10 ** 6
    ans = bfs(S, Ch, Cw, Dh, Dw, H, W)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


def get_magic_movable_list(movable_list, candidate_list):
    return [(h, w) for h, w in candidate_list if any((t_h, t_w) in movable_list for t_h, t_w in product([h-2, h-1, h, h+1, h+2], [w-2, w-1, w, w+1, w+2]))]


def get_movable_list(h, w, movable_list, candidate_list):
    movable_list.append((h, w))
    candidate_list.remove((h, w))
    targets = [(h+1, w), (h-1, w), (h, w+1), (h, w-1)]
    for h, w in targets:
        if (h, w) in candidate_list:
            movable_list, candidate_list = get_movable_list(h, w, movable_list, candidate_list)
    return movable_list, candidate_list

H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
s = [list(input()) for i in range(H)]

candidate_list = [(h, w) for h in range(H) for w in range(W) if s[h][w] == '.']
movable_list, candidate_list = get_movable_list(s_h, s_w, [], candidate_list)
i = 0

while True:
    if (d_h, d_w) in movable_list:
        break
    magic_movable_list = get_magic_movable_list(movable_list, candidate_list)

    if not magic_movable_list:
        i = -1
        break

    i += 1

    for h, w in magic_movable_list:
        if (h, w) in candidate_list:
  	        movable_list, candidate_list = get_movable_list(h, w, movable_list, candidate_list)

print(i)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    from collections import deque
    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
    s=[input() for _ in range(h)]
    d=[[1,0],[-1,0],[0,1],[0,-1]]
    visit=[[False]*w for _ in range(h)]
    ans=0
    st=[]
    st=deque()
    st.append((ch,cw,0))
    while st:
      nx,ny,ncost=st.popleft()
      visit[nx][ny]=True
      if dh==nx and dw==ny:
        visit[dh][dw]=True
        ans=ncost
        break
      for dx,dy in d:
        x=nx+dx
        y=ny+dy
        if (0<=x<=h-1) and (0<=y<=w-1):
          if s[x][y]!='#' and visit[x][y]==False:
            st.appendleft((x,y,ncost))
      for i in range(-2,3):
        for j in range(-2,3):
          if (i,j)==(0,0) or (i,j)==(1,0) or (i,j)==(0,1) or (i,j)==(-1,0) or (i,j)==(0,-1):
            continue
          x,y=i+nx,j+ny
          if (0<=x<=h-1) and (0<=y<=w-1):
            if s[x][y]!='#' and visit[x][y]==False:
              st.append((x,y,ncost+1))
    if visit[dh][dw]==False:
      print(-1)
    else:
      print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

stack = deque()
stack.append([ch-1,cw-1])
INF=10**12
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
wapu = []
for m in range(-2,3):
    for n in range(-2,3):
        if m!=0 or n!=0:
            wapu += [[m,n]]

while stack:
    x,y = stack.pop()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]<cost[nx][ny]:
            cost[nx][ny]=cost[x][y]
            stack.append([nx,ny])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in wapu:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]+1<cost[nx][ny]:            
            cost[nx][ny]=cost[x][y]+1
            stack.append([nx,ny])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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
s=[input() for _ in range(h)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
visit=[[False]*w for _ in range(h)]
ans=0
st=[]
st=deque()
st.append((ch,cw,0))
while st:
  nx,ny,ncost=st.popleft()
  visit[nx][ny]=True
  if dh==nx and dw==ny:
    visit[dh][dw]=True
    ans=ncost
    break
  for dx,dy in d:
    x=nx+dx
    y=ny+dy
    if (0<=x<=h-1) and (0<=y<=w-1):
      if s[x][y]!='#' and visit[x][y]==False:
        st.appendleft((x,y,ncost))
  for i in range(-2,3):
    for j in range(-2,3):
      if (i,j)==(0,0) or (i,j)==(1,0) or (i,j)==(0,1) or (i,j)==(-1,0) or (i,j)==(0,-1):
        continue
      x,y=i+nx,j+ny
      if (0<=x<=h-1) and (0<=y<=w-1):
        if s[x][y]!='#' and visit[x][y]==False:
          st.append((x,y,ncost+1))
if visit[dh][dw]==False:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

stack = deque()
stack.append([ch-1,cw-1])
INF=10**8
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
wapu = []
for m in range(-2,3):
    for n in range(-2,3):
        if m!=0 or n!=0:
            wapu += [[m,n]]

while stack:
    x,y = stack.pop()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]<cost[nx][ny]:
            cost[nx][ny]=cost[x][y]
            stack.append([nx,ny])
    for dx,dy in wapu:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]+1<cost[nx][ny]:            
            cost[nx][ny]=cost[x][y]+1
            stack.append([nx,ny])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

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

stack = deque([[ch-1,cw-1]])
INF=10**8
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
wapu = []
for m in range(-2,3):
    for n in range(-2,3):
        if m!=0 or n!=0:
            wapu += [[m,n]]

while stack:
    x,y = stack.pop()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]<cost[nx][ny]:
            cost[nx][ny]=cost[x][y]
            stack.append([nx,ny])
    for dx,dy in wapu:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]+1<cost[nx][ny]:            
            cost[nx][ny]=cost[x][y]+1
            stack.append([nx,ny])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    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 = [list(input()) for _ in range(h)]

stack = [[ch-1,cw-1]]
INF=10**8
cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
wapu = []
for m in range(-2,3):
    for n in range(-2,3):
        if m!=0 or n!=0:
            wapu += [[m,n]]

while stack:
    x,y = stack.pop()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]<cost[nx][ny]:
            cost[nx][ny]=cost[x][y]
            stack.append([nx,ny])
    for dx,dy in wapu:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and cost[x][y]+1<cost[nx][ny]:            
            cost[nx][ny]=cost[x][y]+1
            stack.append([nx,ny])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]
dq1 = deque([])

while dq:
    r, c, cur_cost = dq.popleft()
    dq1.append((r, c, cur_cost))

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.append((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    if not dq:
        while dq1:
            r, c, cur_cost = dq1.popleft()

            for x in range(-2, 3):
                r_new = r + x
                if r_new < 0 or r_new >= H:
                    continue

                for y in range(-2, 3):
                    c_new = c + y

                    if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                        continue

                    dq.append((r_new, c_new, cur_cost + 1))
                    search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math


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

    d = deque()
    d.append([Ch - 1, Cw - 1])

    cost = [[math.inf for _ in range(W)] for _ in range(H)]
    cost[Ch - 1][Cw - 1] = 0

    while d:
        r, c = d.popleft()

        for dr, dc in [[-1, 0], [1, 0], [0, -1], [0, 1]]:  # 上下左右
            nr = r + dr
            nc = c + dc
            if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == "." and cost[nr][nc] > cost[r][c]:
                cost[nr][nc] = cost[r][c]
                d.appendleft([nr, nc])

        for dr in range(-2, 3, 1):  # ワープ
            for dc in range(-2, 3, 1):
                if dr == 0 and dc == 0:
                    continue
                nr = r + dr
                nc = c + dc
                if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == "." and cost[nr][nc] > cost[r][c]:
                    cost[nr][nc] = cost[r][c] + 1
                    d.append([nr, nc])

    if cost[Dh - 1][Dw - 1] == math.inf:
        ans = -1
    else:
        ans = cost[Dh - 1][Dw - 1]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import deque

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()
elif icase==1:
    h,w=4,4
    ch,cw=1,1
    dh,dw=4,4
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['..#.', '..#.', '.#..', '.#..']   
elif icase==2:
    h,w=4,4
    ch,cw=1,4
    dh,dw=4,1
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['.##.', '####', '####', '.##.']  
elif icase==3:
    h,w=4,5
    ch,cw=1,2
    dh,dw=2,5
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['#.###', '####.', '#..##', '#..##'] 
elif icase==4:
    h,w=4,4
    ch,cw=2,2
    dh,dw=3,3
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=['....', '....', '....', '....']
        
icnt=-1
pair=[-1]*(h*w)
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            idx=i*w+j
#            pair.append(idx)
            pair[idx]=idx
#print("A",pair)
               
def root(x):
    if x==-1:
        return -1
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    elif x>y:
        pair[x]=y
    else:
        pair[y]=x
        
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                pair[idx1]=idx
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                pair[idx1]=idx

for i in range(h):
    for j in range(w):
        idx=i*w+j
        if s[i][j]==".":
            if i<h-1 and s[i+1][j]==".":
                idx1=(i+1)*w+j
                unite(idx,idx1)
            if i>0 and s[i-1][j]==".":
                idx1=(i-1)*w+j
                unite(idx,idx1)
            if j<w-1 and s[i][j+1]==".":
                idx1=i*w+j+1
                unite(idx,idx1)
            if j>0 and s[i][j-1]==".":
                idx1=i*w+j-1
                unite(idx,idx1)

#print("B:",pair)
l=[root(ii) for ii in range(len(pair))]
#print("l:",l)
ll=list(set(l))    
ll.sort()
ll=ll[1:]
if len(ll)<1:
    print(0)
    sys.exit()

gg=[[] for i in range(max(ll)+1)]
for i in range(h):
    for j in range(w):
        idx=i*w+j
        if root(idx)!=-1:
#            gg[root(idx)].append((i,j))        
            if i<h-1 and s[i+1][j]=="#":
                gg[root(idx)].append((i,j))        
            elif i>0 and s[i-1][j]=="#":
                gg[root(idx)].append((i,j))        
            elif j<w-1 and s[i][j+1]=="#":
                gg[root(idx)].append((i,j))        
            elif j>0 and s[i][j-1]=="#":
                gg[root(idx)].append((i,j))        

ggg=[[] for i in range(max(ll)+1)]
for gi in gg:
    for gi2 in gg:
        if gi==gi2:
            continue
        yn=""
        for i,j in gi:
            idx=i*w+j
            for i2,j2 in gi2:
                idx2=i2*w+j2
                if root(idx2) in ggg[root(idx)]:
                    continue
                if abs(i-i2)<=2 and abs(j-j2)<=2:
                    ggg[root(idx)].append(root(idx2))
                    ggg[root(idx2)].append(root(idx))
                    yn="yes"
                    break
            if yn=="yes":
                break
            
#print("ll:",ll)
lenpair=len(ll)    
lenpair=max(ll)+1

qst=root(ch*w+cw)
qed=root(dh*w+dw)
q=deque([qst])

stack=[qst]
parent=[-1]*lenpair
parent[qst]=0
dist=[-1]*lenpair
dist[qst]=0
while q:
    state = q.popleft()
#    print("--- q:",q,"state:",state,"g:",g[state],"p:",parent)
    for v in ggg[state]:
#        print("  state:",state,"v:",v,"q:",q)
#        if parent[state] == v:
        if parent[v] !=-1:
            continue
        else:
#            print("parent:",parent,"xx:",xx,"stack",stack)
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
            if v==qed:
                print(dist[qed])   
                sys.exit()
#            print(" state:",state,"v:",v,"parent:",parent,"stack",stack,"dist[v]",dist[v])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  deq = deque()
  deq.append((C_h,C_w))

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]

  while len(deq):
    y,x = deq.popleft()
    for dy,dx in move_a:
      ny,nx = y+dy,x+dx
      if 0<=ny<H and 0<=nx<W and S[ny][nx] and dist[ny][nx]>dist[y][x]:
        dist[ny][nx] = dist[y][x]
        deq.appendleft((ny,nx))
    for dy,dx in move_b:
      ny,nx = y+dy,x+dx
      if not (0<=ny<H and 0<=nx<W):
        continue
      if not S[ny][nx]:
        continue
      if dist[ny][nx] <= dist[y][x]+1:
        continue
      flag = False
      for ddy,ddx in move_a:
        nny,nnx = ny+ddy,nx+ddx
        if 0<=nny<H and 0<=nnx<W and S[nny][nnx] and dist[nny][nnx]==dist[y][x]:
          flag = True
          break
      if flag:
        continue
      dist[ny][nx] = dist[y][x] + 1
      deq.append((ny,nx))
    
  ans = dist[D_h][D_w]
  print(ans if ans!=INF else -1)


H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = [[c=='.' for c in readline()] for _ in range(H)]

solve(H,W,C_h,C_w,D_h,D_w,S)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [input() for _ in range(H)]

    Q = deque([[Ch - 1, Cw - 1, 0]])  # 座標とワープ回数

    cost = [[-1 for _ in range(W)] for _ in range(H)]  # ワープ回数を記録

    while Q:
        r, c, cnt = Q.popleft()

        if cost[r][c] != -1:  # 訪れたことがある
            continue

        cost[r][c] = cnt

        for dr in range(-2, 3):
            for dc in range(-2, 3):
                nr = r + dr
                nc = c + dc

                if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == ".":
                    if abs(dr) + abs(dc) == 1:  # 上下左右
                        Q.appendleft([nr, nc, cnt])
                    elif abs(dr) + abs(dc) >= 2:  # ワープ
                        Q.append([nr, nc, cnt + 1])

    print(cost[Dh - 1][Dw - 1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
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
maze=[input() for _ in range(h)]

from collections import deque

dist=[[-1]*w for _ in range(h)]
q=deque()
p=[]
q.append((ch,cw))
dist[ch][cw]=0
cur=0 #ワープ回数
while q:
    while q:
        x,y=q.popleft()
        if dist[x][y]>cur:
            continue
        dist[x][y]=cur
        for i in range(-1,2):
            for j in range(-1,2):
                if abs(i)+abs(j)==1:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                dist[xx][yy]=cur
                                q.append((xx,yy))
                        if dist[xx][yy]>cur:
                            dist[xx][yy]=cur
                            q.append((xx,yy))
                                
        for i in range(-2,3):
            for j in range(-2,3):
                if abs(i)+abs(j)>=2:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                p.append((xx,yy))
    
    if len(q)==0:
        # print(p,q)
        for pp in p:
            if dist[pp[0]][pp[1]]==-1:
                q.append(pp)
        p=[]
        cur+=1
# pprint(dist)
print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
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
maze=[input() for _ in range(h)]

from collections import deque

dist=[[-1]*w for _ in range(h)]
q=deque()
p=[]
q.append((ch,cw))
dist[ch][cw]=0
cur=0 #ワープ回数
while q:
    # print("now cur:",cur)
    # print(q)
    while q:
        x,y=q.popleft()
        dist[x][y]=cur
        for i in range(-1,2):
            for j in range(-1,2):
                if abs(i)+abs(j)==1:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                dist[xx][yy]=cur
                                q.append((xx,yy))
                        if dist[xx][yy]>cur:
                            dist[xx][yy]=cur
                            q.append((xx,yy))
                                
        for i in range(-2,3):
            for j in range(-2,3):
                if abs(i)+abs(j)>=2:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                p.append((xx,yy))
    
    if len(q)==0:
        # print(p,q)
        for pp in p:
            if dist[pp[0]][pp[1]]==-1:
                q.append(pp)
        p=[]
        cur+=1
# pprint(dist)
print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = [int(x) for x in input().split()]

wizard = [int(x) - 1 for x in input().split()]
goal = [int(x) - 1 for x in input().split()]

field = []

for i in range(H):
    s = input()
    field.append(s)

def next_vertex(filed, cost, v):
    nv = []
    for e in [[-1,0], [1,0], [0,-1], [0,1]]:
        x_n = v[0] + e[0]
        y_n = v[1] + e[1]
        if 0 <= x_n < W and 0 <= y_n < H:
            if cost[y_n][x_n] == -1:
                if field[y_n][x_n] == ".":
                    nv.append([x_n, y_n])

    return nv

def magical_vertex(field, cost, v):
    mv = []
    for y_d in [-2, -1, 0, 1, 2]:
        for x_d in [-2, -1, 0, 1, 2]:
            x_m = v[0] + x_d
            y_m = v[1] + y_d
            if 0 <= x_m < W and 0 <= y_m < H:
                if cost[y_m][x_m] == -1:
                    if field[y_m][x_m] == ".":
                        mv.append([x_m, y_m])
    
    return mv

que_n = deque([(wizard[1], wizard[0])])
que_m = deque([])
cost = [[-1 for _ in range(W)] for _ in range(H)]

c = 0
while que_n:

    while que_n:
        v = que_n.popleft()
        if v not in que_m:
            que_m.append(v)
        nv = next_vertex(field, cost, v)
        cost[v[1]][v[0]] = c
        for w in nv:
            if w not in que_n:
                que_n.append(w)

    while que_m:
        v = que_m.popleft()
        mv = magical_vertex(field, cost, v)
        for w in mv:
            cost[w[1]][w[0]] = c + 1
            if w not in que_n:
                que_n += mv
    
    c += 1

print(cost[goal[0]][goal[1]])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque
import numpy as np
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
check_set = set()
check_set.add(tuple([ch, cw, 0]))
d = deque()
d.appendleft([ch, cw, 0])
inf = h * w
dist = np.full((h, w), inf)
f_list = []
for i in range(h):
    f_list.append(input())
now_no = 0
while True:
    hh, ww, no = d.popleft()
    if dh == hh and dw == ww:
        print(no)
        break
    if dist[hh, ww] == inf:
        if now_no != no:
            now_no += 1
        dist[hh, ww] = now_no
        for i in range(-2, 3):
            for j in range(-2, 3):
                if hh + i < 0 or h <= hh + i or ww + j < 0 or w <= ww + j or (i == 0 and j == 0):
                    continue
                if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):
                    if tuple([hh + i, ww + j, now_no]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                        check_set.add(tuple([hh + i, ww + j, now_no]))
                        d.appendleft([hh + i, ww + j, now_no])
                else:
                    if tuple([hh + i, ww + j, now_no + 1]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                        check_set.add(tuple([hh + i, ww + j, now_no + 1]))
                        d.append([hh + i, ww + j, now_no + 1])
    if len(d) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque
import numpy as np
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
# check_set = set()
# check_set.add(tuple([ch, cw, 0]))
d = deque()
d.appendleft([ch, cw, 0])
dist = np.full((h, w), float('inf'))
f_list = []
for i in range(h):
    f_list.append(input())
now_no = 0
while True:
    hh, ww, no = d.popleft()
    if dh == hh and dw == ww:
        print(no)
        break
    if dist[hh, ww] == float('inf'):
        if now_no != no:
            now_no += 1
        dist[hh, ww] = now_no
        for i in range(-2, 3):
            for j in range(-2, 3):
                if hh + i < 0 or h <= hh + i or ww + j < 0 or w <= ww + j or (i == 0 and j == 0):
                    continue
                if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):
                    if f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                    # if tuple([hh + i, ww + j, now_no]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                        # check_set.add(tuple([hh + i, ww + j, now_no]))
                        d.appendleft([hh + i, ww + j, now_no])
                else:
                    if f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                    # if tuple([hh + i, ww + j, now_no + 1]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                        # check_set.add(tuple([hh + i, ww + j, now_no + 1]))
                        d.append([hh + i, ww + j, now_no + 1])
    if len(d) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
m = ['#' for _ in range(h+2)]
m[0] += '#'*(w+1)
m[h+1] += '#'*(w+1)
que = deque()
que.append(c)
INF = 10**7
warp = [[INF for _ in range(w+1)] for _ in range(h+1)]
for i in range(1,h+1):  m[i] += input()+'#'
up = lambda x,y: 1 if 0<x-1 and m[x-1][y]=='.' else 0
down = lambda x,y: 1 if x+1<=h and m[x+1][y]=='.' else 0
right = lambda x,y: 1 if y+1<=w and m[x][y+1]=='.' else 0
left = lambda x,y: 1 if 0<y-1 and m[x][y-1]=='.' else 0

def jump(x,y,cost):
  deq = deque()
  for i in range(x-2,x+3):
    if i<=0 or h<i:  continue
    for j in range(y-2,y+3):
      if j<=0 or w<j:  continue
      if m[i][j] == '.' and warp[i][j]>cost+1:
        warp[i][j] = cost+1
        if (i,j) not in que:
          deq.append((i,j))
  return deq
  
warp[c[0]][c[1]] = 0
while que:
  q = que.popleft()
  row,col = q[0],q[1]
  cost = warp[row][col]
  if up(row,col) and warp[row-1][col]>cost:
    que.appendleft((row-1,col))
    warp[row-1][col] = cost
  if down(row,col) and warp[row+1][col]>cost:
    que.appendleft((row+1,col))
    warp[row+1][col] = cost
  if right(row,col) and warp[row][col+1]>cost:
    que.appendleft((row,col+1))
    warp[row][col+1] = cost
  if left(row,col) and warp[row][col-1]>cost:
    que.appendleft((row,col-1))
    warp[row][col-1] = cost
  que.extend(jump(row,col,cost))
if warp[d[0]][d[1]] != INF: print(warp[d[0]][d[1]])
else: print(-1)