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:
from heapq import heappush,heappop
h,w=map(int,input().split())
sx,sy=map(int,input().split())
sx-=1
sy-=1
gx,gy=map(int,input().split())
gx-=1
gy-=1
g=[list(input()) for _ in range(h)]
v=[[0 for j in range(w)] for i in range(h)]
q=[]
heappush(q,[0,sx,sy])
k=[[0,1],[0,-1],[1,0],[-1,0]]
while q:
    c,x,y=heappop(q)
    if x==gx and y==gy:
        print(c)
        exit()
    if v[x][y]==1:
        continue
    v[x][y]=1
    for a,b in k:
        nx=x+a
        ny=y+b
        if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
            heappush(q,[c,nx,ny])
    for a in range(-2,3):
        for b in range(-2,3):
            nx=x+a
            ny=y+b
            if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                heappush(q,[c+1,nx,ny])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
inf = 10**10
dxdy = ((0,1),(0,-1),(1,0),(-1,0)) 
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = ['#'*(w+2)] + ['#' + input() + '#' for _ in range(h)] + ['#'*(w+2)]
d = [[inf]*(w+1) for _ in range(h+1)]
d[ch][cw] = 0
q = deque([(ch,cw)])
while q: 
    y,x = q.pop() 
    for dx,dy in dxdy: 
        if s[y+dy][x+dx]=='.' and d[y+dy][x+dx] > d[y][x]:
            d[y+dy][x+dx] = d[y][x]
            q.append((y+dy,x+dx))
    for i in range(-2,3):
        for j in range(-2,3):
            if i==j==0:
                continue 
            elif 1<=y+i<=h and 1<=x+j<=w and s[y+i][x+j]=='.' and d[y+i][x+j]>d[y][x]+1:
                
                d[y+i][x+j] = d[y][x]+1
                q.append((y+i,x+j)) 
ans = d[dh][dw] 
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    vis = set()

    mw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    mj = list(set((i, j) for i in range(-2, 3) for j in range(-2, 3)) - set(mw) - {(0, 0)})

    q = deque()
    q.append((start[0], start[1], 0))
    while q:
        y, x, c = q.popleft()
        if (y, x) in vis or maze[y][x] == '#':
            continue
        vis.add((y, x))
        if (y, x) == goal:
            print(c)
            break
        for a, b in mw:
            if 0 <= y + a < h and 0 <= x + b < w:
                q.appendleft((y + a, x + b, c))
        for a, b in mj:
            if 0 <= y + a < h and 0 <= x + b < w:
                q.append((y + a, x + b, c + 1))
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())  # 縦H X 横W マス
C = list(map(int, input().split()))  #[Ch, Cw]　　*1多いことに注意
D = list(map(int, input().split()))  #[Dh, Dw]　　*1多いことに注意
S = [list(input()) for _ in range(H)]  #Sij = S[i][j]  

T = [[C[0]-1,C[1]-1]]
ans = 0

# 繰り返し
while T:
    K = []
    while T:
        y,x = T.pop(0)
        if 0 <= y < H and 0 <= x < W and S[y][x] =="." :
            K.append([y,x])
            S[y][x] = "#"
            for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
                T.append([y+i,x+j])
    if [D[0]-1,D[1]-1] in K:
        print(ans)
        break
    ans += 1
    for z,w in K:
        for s_y in [-2,-1,0,1,2]:
                for s_x in [-2,-1,0,1,2]:
                    if 0 <= z+s_y < H and 0 <= w+s_x < W and S[z+s_y][w+s_x] ==".":
                        if not S[z+s_y][w+s_x] in K and not [z+s_y,w+s_x] in T:
                            T.append([z+s_y, w+s_x])
else:
    print(-1)

Submission status: Time Limit Exceeded

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

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    vis = [[False] * w for _ in range(h)]

    mw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    mj = list(set((i, j) for i in range(-2, 3) for j in range(-2, 3)) - set(mw) - {(0, 0)})

    q = deque()
    q.append((start[0], start[1], 0))
    while q:
        y, x, c = q.popleft()
        if not (0 <= y < h and 0 <= x < w) or vis[y][x] or maze[y][x] == '#':
            continue
        vis[y][x] = True
        if (y, x) == goal:
            print(c)
            break
        for a, b in mw:
            q.appendleft((y + a, x + b, c))
        for a, b in mj:
            q.append((y + a, x + b, c + 1))
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
ch, cw =  map(int, input().split())
gh, gw =  map(int, input().split())
 
f = [[s=="." for s in input()] for h in range(H)]
ans = [[-1 for w in range(W)]for h in range(H)]
 
nextQ = [(ch-1)*1000 + cw-1]
ans[ch-1][cw-1] = 0
while len(nextQ)>0:
  Q = list(nextQ)
  nextQ = set()
  i = 0
  while i<len(Q):
    nh = Q[i]
    i += 1
    nw = nh%1000
    nh = nh//1000
    for dh in range(0-min(nh,2), 3):
      if nh+dh>=H:
        break
      for dw in range(0-min(nw,2), 3):
        if nw + dw>=W:
          break
        if dh==0 and dw==0:
          continue
        if dh*dw==0 and (abs(dh)==1 or abs(dw)==1):
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              Q.append((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]
            else:
              ans[nh+dh][nw+dw]=-2
          elif ans[nh+dh][nw+dw]>ans[nh][nw]:
            Q.append((nh+dh)*1000 + nw+dw)
            nextQ -= {(nh+dh)*1000 + nw+dw}
            ans[nh+dh][nw+dw]=ans[nh][nw]
        else:
          if ans[nh+dh][nw+dw]==-1:
            if f[nh+dh][nw+dw]:
              nextQ.add((nh+dh)*1000 + nw+dw)
              ans[nh+dh][nw+dw]=ans[nh][nw]+1
            else:
              ans[nh+dh][nw+dw]=-2
print(ans[gh-1][gw-1])

Submission status: Time Limit Exceeded

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

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    vis = [[False] * w for _ in range(h)]

    mw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    mj = list(set((i, j) for i in range(-2, 3) for j in range(-2, 3)) - set(mw) - {(0, 0)})

    q = deque()
    q.append((start[0], start[1], 0))
    while q:
        y, x, c = q.popleft()
        vis[y][x] = True
        if (y, x) == goal:
            print(c)
            break
        for a, b in mw:
            if 0 <= y + a < h and 0 <= x + b < w:
                if maze[y + a][x + b] == '.' and not vis[y + a][x + b]:
                    q.appendleft((y + a, x + b, c))
        for a, b in mj:
            if 0 <= y + a < h and 0 <= x + b < w:
                if maze[y + a][x + b] == '.' and not vis[y + a][x + b]:
                    q.append((y + a, x + b, c + 1))
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(1000000)

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    vis = [[False] * w for _ in range(h)]

    mw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    mj = list(set((i, j) for i in range(-2, 3) for j in range(-2, 3)) - set(mw) - {(0, 0)})

    q = deque()
    q.append((start[0], start[1], 0))
    while q:
        y, x, c = q.popleft()
        if vis[y][x]:
            continue
        vis[y][x] = True
        if (y, x) == goal:
            print(c)
            break
        for a, b in mw:
            if 0 <= y + a < h and 0 <= x + b < w:
                if maze[y + a][x + b] == '.':
                    q.appendleft((y + a, x + b, c))
        for a, b in mj:
            if 0 <= y + a < h and 0 <= x + b < w:
                if maze[y + a][x + b] == '.':
                    q.append((y + a, x + b, c + 1))
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------

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

ad = [(-1,0), (0,-1), (1,0), (0,1)]
warp = [(-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)]

def bfs3():
    '''
    queue2つ
    '''
    que1=[]
    que2=[] # queueというよりはメモリ
    m[ch][cw]=str(0)
    que1.append((ch,cw))

    while que1!=[]:
        l1=len(que1)
        r1=0 # que1における使用済みindex
        # que1の要素(座標)から歩いていけるマス
        while r1<l1:
            i, j=que1[r1]
            r1+=1
            # 隣接したマスへの移動
            for si, sj in ad:
                if 0<=i+si<h and 0<=j+sj<w and m[i+si][j+sj]=='.': 
                    m[i+si][j+sj]=m[i][j]
                    que1.append((i+si, j+sj))
                    l1+=1

        # 歩いていけないマス
        for i,j in que1:
            for si, sj in warp:
                if 0<=i+si<h and 0<=j+sj<w and m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=str(int(m[i][j])+1)
                    que2.append((i+si, j+sj))

        que1=que2
        que2=[]

bfs3()

if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import copy
(H,W) = map(int,input().split())
(ch,cw) = map(int,input().split())
(dh,dw) = map(int,input().split())
l = []
for i in range(H):
    k=input()
    l.append([k[j] for j in range(W)])
t = copy.deepcopy(l)
s = [[-1 for i in range(W)] for j in range(H)]
ans = 0
rn = 0
u = []
cn = -1
dn = -1
k = []

def black(h,w):
    global k

    if (ch-1,cw-1) == (h,w):
        global cn
        cn = rn
    if (dh-1,dw-1) == (h,w):
        global dn
        dn = rn
    if s[h][w] != -1:
        if [s[h][w],rn] not in u:
            u.append([s[h][w],rn])

    t[h][w]="#"
    k.append([h,w])
    if w<(W-1):
        if t[h][w+1]==".":
            black(h,w+1)
    if h<(H-1):
        if t[h+1][w]==".":
            black(h+1,w)
    if w>0:
        if t[h][w-1]==".":
            black(h,w-1)
    if h>0:
        if t[h-1][w]==".":
            black(h-1,w)

def wrap(k):
    for i in range(len(k)):
        for pi in range(-2,3):
            for pj in range(-2,3):
                if 0<=(k[i][0]+pi) and ((k[i][0]+pi)<H and (0<=(k[i][1]+pj) and (k[i][1]+pj)<W)):
                    if t[k[i][0]+pi][k[i][1]+pj] == ".":
                        s[k[i][0]+pi][k[i][1]+pj] = rn

for i in range(H):
    for j in range(W):
        if t[i][j] == ".":
            black(i,j)
            wrap(k)
            k = []
            rn += 1
            l = copy.deepcopy(t)

mat = [cn]
mit = []
v = [[0 for i in range(rn)] for j in range(rn)]
for i in range(len(u)):
    v[u[i][0]][u[i][1]] = 1

count = len(u)
if dn == cn:
    print(0)
while dn not in mat:
    mit = []
    for x in mat:
        for i in range(rn):
            if v[min(x,i)][max(x,i)] == 1:
                mit.append(i)
                v[min(x,i)][max(x,i)] = 0
                count -= 1
        mat.remove(x)
        mat = copy.deepcopy(mit)
    ans += 1
    if dn in mat:
        print(ans)
    elif count == 0:
        print(-1)
        break

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

    l = [list(input().strip()) for i in range(h)]
    ans = [[-1]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if l[i][j] == "#":
                ans[i][j] = -2
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    
    """
    base = ["#" * (w + 4)]
    base.append("#" * (w + 4))
    for n in range(h):
        base.append("##" + input() + "##")
    base.append("#" * (w + 4))
    base.append("#" * (w + 4))
    ans = [[-1] * (w + 4) for _ in range(h + 4)]
    for i in range(h + 4):
        for j in range(w + 4):
            if base[i][j] == "#":
                ans[i][j] = -2
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    """
    
    ans[ch][cw] = 0
    move1 = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    move2 = [
        [-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]
    ]
    q1 = deque([[ch, cw]])
    q2 = deque([])

    while q1:
        x1, y1 = q1.popleft()
        q2.append([x1, y1])
        for i, j in move1:
            nx, ny = x1 + i, y1 + j
            if nx < 0 or h <= nx or ny < 0 or w <= ny:
                continue
            if ans[nx][ny] == -1:
                ans[nx][ny] = ans[x1][y1]
                q1.append([nx, ny])
        if len(q1) == 0:
            while q2:
                x2, y2 = q2.popleft()
                for i, j in move2:
                    mx, my = x2 + i, y2 + j
                    if mx < 0 or h <= mx or my < 0 or w <= my:
                        continue
                    if ans[mx][my] == -1:
                        ans[mx][my] = ans[x2][y2] + 1
                        q1.append([mx, my])
    print(ans[dh][dw])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(lambda x:int(x)-1,input().split())
    Dh,Dw = map(lambda x:int(x)-1,input().split())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    # s = V[Ch][Cw]
    # g = V[Dh][Dw]

    # dist = [-1 for _ in range(vertex)]
    # que = deque()
    # dist[s] = 0
    # que.append(s)
    # while que:
    #     u = que.popleft()
    #     for v in G[u]:
    #         if dist[v] != -1:
    #             continue
    #         dist[v] = dist[u] + 1
    #         que.append(v)
    
    # print(dist[g])

    start_area_num = V[Ch][Cw]
    goal_area_num = V[Dh][Dw]

    visited = [False] * vertex
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

if __name__ == '__main__':
    solve()

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

"""
l = [list(input().strip()) for i in range(h)]
ans = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            ans[i][j] = -2
ch -= 1
cw -= 1
dh -= 1
dw -= 1
"""

base = ["#" * (w + 4)]
base.append("#" * (w + 4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w + 4))
base.append("#" * (w + 4))
ans = [[-1] * (w + 4) for _ in range(h + 4)]
for i in range(h + 4):
    for j in range(w + 4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch += 1
cw += 1
dh += 1
dw += 1

ans[ch][cw] = 0
move1 = [[1, 0], [-1, 0], [0, 1], [0, -1]]
move2 = [
        [-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]
        ]
q1 = deque([[ch, cw]])
q2 = deque([])

while q1:
    x1, y1 = q1.popleft()
    q2.append([x1, y1])
    for i, j in move1:
        nx, ny = x1 + i, y1 + j
        """
        if nx < 0 or h <= nx or ny < 0 or w <= ny:
            continue
        """
        if ans[nx][ny] == -1:
            ans[nx][ny] = ans[x1][y1]
            q1.append([nx, ny])
    if len(q1) == 0:
        while q2:
            x2, y2 = q2.popleft()
            for i, j in move2:
                mx, my = x2 + i, y2 + j
                """
                if mx < 0 or h <= mx or my < 0 or w <= my:
                    continue
                """
                if ans[mx][my] == -1:
                    ans[mx][my] = ans[x2][y2] + 1
                    q1.append([mx, my])
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]
dict={".":10000000,"#":-1}
sy,sx,gy,gx=c[0]-1,c[1]-1,d[0]-1,d[1]-1
s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
s[sy][sx]=0
que=deque([[sy,sx]])
temp=[(1,0),(0,1),(-1,0),(0,-1),(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 que:
    y,x=que.popleft()
    for i,j in temp:
        if 0<=y+i<h and 0<=x+j<w and s[y+i][x+j]>=0:
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if i*i+j*j==1 and dist>s[y][x]:
                s[nexty][nextx]=s[y][x]
                que.append([nexty,nextx])
            elif dist>s[y][x]+1:
                s[nexty][nextx]=s[y][x]+1
                que.append([nexty,nextx])

if s[gy][gx]==10000000:
    print(-1)
else:
    print(s[gy][gx])

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=["0"]*H
for i in range(H):
    s=input()
    grid[i]=s

Inf=10**12
cost=[[Inf] * W for i in range(H)]

walk=[(0, 1), (0, -1), (-1, 0), (1, 0)]
warp=[]
for i in range(-2, 3):
    for j in range(-2, 3):
        if i==0 and j==0:
            continue
        if (i, j) not in walk:
            warp.append((i, j))

q=deque()
cost[ch][cw]=0
q.append((ch, cw, 0))

while q:
    x, y, c=q.popleft()
    for dx, dy in walk:
        nx = x+dx
        ny = y+dy
        if 0<= nx < H and 0<= ny < W and grid[nx][ny]=="." and cost[nx][ny]>c:
            cost[nx][ny]=c
            q.appendleft((nx, ny, c))
    
    for dx, dy in warp:
        nx = x+dx
        ny = y+dy
        if 0<= nx < H and 0<= ny < W and grid[nx][ny]=="." and cost[nx][ny]>c+1:
            cost[nx][ny]=c+1
            q.append((nx, ny, c+1))


if cost[dh][dw]==Inf:
    print(-1)
else:
    ans=cost[dh][dw]
    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())
Ch -= 1; Cw -= 1; Dh -= 1; Dw -= 1;
S = []

for _ in range(H):
    S.append(input())

dq = deque()
dq.append((Cw, Ch))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

visited = [[-1 for _ in range(W)] for _ in range(H)]
visited[Ch][Cw] = 0
while dq:
    x, y = dq.popleft()

    #コスト無しで行けるエリアを列挙
    for dx_, dy_ in zip(dx, dy):
        if (not 0 <= x+dx_ < W) or (not 0 <= y+dy_ < H):
            continue
        if S[y+dy_][x+dx_] == "#":
            continue
        #まだ訪れていない or 実はノーコストで到達可能な点だった
        if visited[y+dy_][x+dx_] == -1 or visited[y+dy_][x+dx_] > visited[y][x]:
            visited[y+dy_][x+dx_] = visited[y][x]
            dq.appendleft((x+dx_, y+dy_))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if (not 0 <= x+i < W) or (not 0 <= y+j < H):
                continue
            if S[y+j][x+i] == '#':
                continue

            if visited[y+j][x+i] == -1:
                visited[y+j][x+i] = visited[y][x] + 1
                dq.append((x+i, y+j))

ans = visited[Dh][Dw]
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())
l = [list(input().strip()) for i in range(h)]
ans = [[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            ans[i][j] = -2
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ans[ch][cw] = 0
move1 = [[1, 0], [-1, 0], [0, 1], [0, -1]]
move2 = [
        [-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]
        ]
q1 = deque([[ch, cw]])
q2 = deque([])

while q1:
    x1, y1 = q1.popleft()
    q2.append([x1, y1])
    for i, j in move1:
        nx, ny = x1 + i, y1 + j
        if nx < 0 or h <= nx or ny < 0 or w <= ny:
            continue
        if ans[nx][ny] == -1:
            ans[nx][ny] = ans[x1][y1]
            q1.append([nx, ny])
    if len(q1) == 0:
        while q2:
            x2, y2 = q2.popleft()
            for i, j in move2:
                mx, my = x2 + i, y2 + j
                if mx < 0 or h <= mx or my < 0 or w <= my:
                    continue
                if ans[mx][my] == -1:
                    ans[mx][my] = ans[x2][y2] + 1
                    q1.append([mx, my])
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(lambda x:int(x)-1,input().split())
    Dh,Dw = map(lambda x:int(x)-1,input().split())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] != -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
ch, cw =  map(int, input().split())
gh, gw =  map(int, input().split())

f = [[s=="." for s in input()] for h in range(H)]
ans = [[-1 for w in range(W)]for h in range(H)]

Q = [[ch-1, cw-1]]
ans[ch-1][cw-1] = 0
while len(Q)>0:
  nh, nw = Q.pop(0)
  for dh in range(0-min(nh,2), 3):
    if nh+dh>=H:
      break
    for dw in range(0-min(nw,2), 3):
      if nw + dw>=W:
        break
      if dh==0 and dw==0:
        continue
      if dh*dw==0 and (abs(dh)==1 or abs(dw)==1):
        if ans[nh+dh][nw+dw]==-1:
          if f[nh+dh][nw+dw]:
            Q.insert(0, [nh+dh,nw+dw])
            ans[nh+dh][nw+dw]=ans[nh][nw]
          else:
            ans[nh+dh][nw+dw]=-2
        elif ans[nh+dh][nw+dw]>ans[nh][nw]:
          Q.insert(0, [nh+dh,nw+dw])
          ans[nh+dh][nw+dw]=ans[nh][nw]
      else:
        if ans[nh+dh][nw+dw]==-1:
          if f[nh+dh][nw+dw]:
            Q.append([nh+dh,nw+dw])
            ans[nh+dh][nw+dw]=ans[nh][nw]+1
          else:
            ans[nh+dh][nw+dw]=-2
        elif ans[nh+dh][nw+dw]>ans[nh][nw]:
          Q.append([nh+dh,nw+dw])
          ans[nh+dh][nw+dw]=ans[nh][nw]+1
print(ans[gh-1][gw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]
dict={".":1000000,"#":-1}
s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]

s[c[0]-1][c[1]-1]=0
que=deque([[c[0]-1,c[1]-1]])
temp=[(1,0),(0,1),(-1,0),(0,-1),(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 que:
    y,x=que.popleft()
    for i,j in temp:
        if 0<=y+i<h and 0<=x+j<w and s[y+i][x+j]>=0:
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if i*i+j*j==1 and dist>s[y][x]:
                s[nexty][nextx]=s[y][x]
                que.append([nexty,nextx])
            elif dist>s[y][x]+1:
                s[nexty][nextx]=s[y][x]+1
                que.append([nexty,nextx])

if s[d[0]-1][d[1]-1]==1000000:
    print(-1)
else:
    print(s[d[0]-1][d[1]-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]
dict={".":10000000,"#":-1}
s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]

s[c[0]-1][c[1]-1]=0
que=deque([[c[0]-1,c[1]-1]])
temp=[(1,0),(0,1),(-1,0),(0,-1),(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 que:
    y,x=que.popleft()
    for i,j in temp:
        if 0<=y+i<h and 0<=x+j<w and s[y+i][x+j]>=0:
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if i*i+j*j==1 and dist>s[y][x]:
                s[nexty][nextx]=s[y][x]
                que.append([nexty,nextx])
            elif dist>s[y][x]+1:
                s[nexty][nextx]=s[y][x]+1
                que.append([nexty,nextx])

if s[d[0]-1][d[1]-1]==10000000:
    print(-1)
else:
    print(s[d[0]-1][d[1]-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
import numpy as np
from collections import deque
H,W = map(int, input().rstrip().split())
CH,CW = map(int, input().rstrip().split())
DH,DW = map(int, input().rstrip().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input().rstrip()) for i in range(H)])
M = H * W
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q = deque([])
q.append([nowH,nowW])
for n in range(0,M):
  if len(q) != 0:
    [nowH,nowW] = q.popleft()
  else:
    break
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        dis = (abs(i) + abs(j))
        if dis >= 1:
          cost = min(2,dis) - 1
          if S[nowH+i,nowW+j] == '.' and Distance[nowH,nowW] + cost < Distance[nowH+i,nowW+j]:
            if [nowH+i,nowW+j] in q:
              q.remove([nowH+i,nowW+j])
            if dis == 1:
              q.appendleft([nowH+i,nowW+j])
            else:
              q.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = Distance[nowH,nowW] + cost
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))