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:

l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[[x=='#' for x in list(input())] for _ in range(H)]
d={(CH-1,CW-1):0}
q=[(CH-1,CW-1,0)]
def check(h,w,c,o):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    key=(h,w)
    if key in d:
        if d[key]<=c:
            return False
    if S[h][w]:
        return False
    if o:
        q.append((h,w,c))
        d[key]=c
    else:
        q.insert(0,(h,w,c+1))
        d[key]=c+1
    return True
while q:
    h,w,c=q.pop()
    # walk
    check(h-1,w-0,c,True)
    check(h-0,w-1,c,True)
    check(h+1,w+0,c,True)
    check(h+0,w+1,c,True)
    # warp
    check(h-1,w-1,c,False)
    check(h+1,w+1,c,False)
    for i in [-2,+2]:
        for j in range(-2,3):
            check(h+i,w+j,c,False)
            check(h+j,w+i,c,False)
key=(DH-1,DW-1)
if key in d:
    print(d[key])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# import queue
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
table = []
for i in range(h):
    table.append(input())
# print(table)

def check(h_tmp, w_tmp, steps):
    if h_tmp < 0 or w_tmp < 0 or h_tmp >= h or w_tmp >= w:
        return False
    elif visit[h_tmp][w_tmp] <= steps:
        return False
    elif table[h_tmp][w_tmp] == '#':
        return False
    else:
        return True


# q = queue.Queue()
q = deque()
q.append((ch, cw, 0, 0))
ans = 1000000000
visit = [[1000000000 for _ in range(w)] for __ in range(h)]
# print(visit)
while not len(q) == 0:
    now = q.popleft()
    visit[now[0]][now[1]] = min(visit[now[0]][now[1]], now[3])
    # print(q.qsize())
    # print(now)
    if now[0] == dh and now[1] == dw:
        # print(now[0], now[1])
        # ans = visit[now[0]][now[1]]
        ans = min(ans, now[3])
        continue
        # break
    # print(now[0], now[1])

    if check(now[0]+1, now[1], now[3]):
        q.appendleft((now[0]+1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]+1, now[3]):
        q.appendleft((now[0], now[1]+1, now[2] + 1, now[3]))
    if check(now[0]-1, now[1], now[3]):
        q.appendleft((now[0]-1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]-1, now[3]):
        q.appendleft((now[0], now[1]-1, now[2] + 1, now[3]))

    if check(now[0]+1, now[1]+1, now[3]+1):
        q.append((now[0]+1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+1, now[3]+1):
        q.append((now[0]-1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-1, now[3]+1):
        q.append((now[0]+1, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-1, now[3]+1):
        q.append((now[0]-1, now[1]-1, now[2] + 1, now[3]+1))

    if check(now[0]+2, now[1], now[3]+1):
        q.append((now[0]+2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+1, now[3]+1):
        q.append((now[0]+2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+2, now[3]+1):
        q.append((now[0]+2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-1, now[3]+1):
        q.append((now[0]+2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-2, now[3]+1):
        q.append((now[0]+2, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1], now[3]+1):
        q.append((now[0]-2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+1, now[3]+1):
        q.append((now[0]-2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+2, now[3]+1):
        q.append((now[0]-2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-1, now[3]+1):
        q.append((now[0]-2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-2, now[3]+1):
        q.append((now[0]-2, now[1]-2, now[2] + 1, now[3]+1))

    if check(now[0], now[1]+2, now[3]+1):
        q.append((now[0], now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+2, now[3]+1):
        q.append((now[0]-1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]+2, now[3]+1):
        q.append((now[0]+1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0], now[1]-2, now[3]+1):
        q.append((now[0], now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-2, now[3]+1):
        q.append((now[0]+1, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-2, now[3]+1):
        q.append((now[0]-1, now[1]-2, now[2] + 1, now[3]+1))
if not ans == 1000000000:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[[x=='#' for x in list(input())] for _ in range(H)]
d={(CH-1,CW-1):0}
q=[(CH-1,CW-1,0)]
def check(h,w,c):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    key=(h,w)
    if key in d:
        if d[key] <= c:
            return False
    if S[h][w]:
        return False
    q.append((h,w,c))
    d[key]=c
    return True
while q:
    h,w,c=q.pop()
    # walk
    check(h-1,w-0,c)
    check(h-0,w-1,c)
    check(h+1,w+0,c)
    check(h+0,w+1,c)
    # warp
    check(h-1,w-1,c+1)
    check(h+1,w+1,c+1)
    for i in [-2,+2]:
        for j in range(-2,3):
            check(h+i,w+j,c+1)
    for i in range(-2,3):
        for j in [-2,+2]:
            check(h+i,w+j,c+1)
key=(DH-1,DW-1)
if key in d:
    print(d[key])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import collections

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))
num = [[float("inf") for i in range(w)] for i in range(h)]
flag = [[False for i in range(w)] for i in range(h)]
num[ch - 1][cw - 1] = 0
queue = collections.deque([[ch, cw]])
d1 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
d2 = [[-1, -1], [-1, 1], [1, -1], [1, 1], [-2, 0], [2, 0], [0, -2], [0, 2]]
d3 = [[-2, -1], [-1, -2], [2, -1], [1, -2], [-2, 1], [-1, 2], [2, 1], [1, 2]]
d4 = [[-2, -2], [-2, 2], [2, -2], [2, 2]]
while queue:
    test = queue.popleft()
    x = test[1]
    y = test[0]
    if flag[y - 1][x - 1] == True:
        continue
    #print(num)
    #print(test)
    flag[y - 1][x - 1] = True
    temp = num[y - 1][x - 1]
    for i in d1:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(num[y2 - 1][x2 - 1], temp)
            queue.appendleft([y2, x2])
    for i in d2:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([y2, x2])
    for i in d3:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([y2, x2])
    for i in d4:
        x2 = x + i[0]
        y2 = y + i[1]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            queue.append([y2, x2])
if num[dh - 1][dw - 1] == float("inf"):
    print(-1)
else:
    print(num[dh - 1][dw - 1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
 
H, W = [int(x) for x in input().split()]
c_h, c_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
d_h, d_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
s = [['.' for w in range(W)] for h in range(H)]
for h in range(H):
    s[h] = input()
 
def in_the_map(x):
    if x[0] < 0 or H <= x[0] or x[1] < 0 or W <= x[1]:
        return False
    return True
 
visited = [[False for w in range(W)] for h in range(H)]
queue = []
heapq.heappush(queue, (0, (c_h, c_w)))  # Push start point with cost (number of warps) 0
 
while len(queue) > 0:
    cost, p = heapq.heappop(queue)
 
    if visited[p[0]][p[1]]:  # Skip if already visited (the priority queue assures we can visit to the point with the smallest cost)
        continue
    visited[p[0]][p[1]] = True
 
    if p[0] == d_h and p[1] == d_w:  # Finally reach to the goal
        print(cost)
        break
    # print(f'Visit {p}: {cost}')
 
    # Explore neighbours where can be reached by walk (with the same cost as p)
    neighbours = ((p[0], p[1] - 1), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0] + 1, p[1]))
    for n in neighbours:
        if not in_the_map(n) or visited[n[0]][n[1]]:
            continue
        if s[n[0]][n[1]] == '.':  # not wall
            heapq.heappush(queue, (cost, n))  # For later exploration
 
    # Explore points where can be reached by warp from visited points(with +1 cost from p)
    for diff_h in range(-2, 3, 1):
        for diff_w in range(-2, 3, 1):
            h = p[0] + diff_h
            w = p[1] + diff_w
            if not in_the_map((h, w)) or visited[h][w]:
                continue
            if s[h][w] == '.': # not wall
                heapq.heappush(queue, (cost + 1, (h, w)))
 
if not visited[d_h][d_w]:  # Cannot reach to the goal
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

H, W = [int(x) for x in input().split()]
c_h, c_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
d_h, d_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
s = [['.' for w in range(W)] for h in range(H)]
for h in range(H):
    s[h] = input()

def in_the_map(x):
    if x[0] < 0 or H <= x[0] or x[1] < 0 or W <= x[1]:
        return False
    return True

visited = [[False for w in range(W)] for h in range(H)]
queue = []
heapq.heappush(queue, (0, (c_h, c_w)))  # Push start point with cost (number of warps) 0

while len(queue) > 0:
    # First, explore neighbours where can be reached by walk (with the same cost as p)
    while len(queue) > 0:
        cost, p = heapq.heappop(queue)

        if visited[p[0]][p[1]]:  # Skip if already visited (the priority queue assures we can visit to the point with the smallest cost)
            continue
        visited[p[0]][p[1]] = True

        if p[0] == d_h and p[1] == d_w:  # Finally reach to the goal
            print(cost)
            break
        # print(f'Visit {p}: {cost}')

        neighbours = ((p[0], p[1] - 1), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0] + 1, p[1]))
        for n in neighbours:
            if not in_the_map(n) or visited[n[0]][n[1]]:
                continue
            if s[n[0]][n[1]] == '.':  # not wall
                heapq.heappush(queue, (cost, n))  # For later exploration

    # Then, explore points where can be reached by warp from visited points (with +1 cost from the point)
    for h0 in range(H):
        for w0 in range(W):
            if not visited[h0][w0]:
                continue
            for diff_h in range(-2, 3, 1):
                for diff_w in range(-2, 3, 1):
                    h = h0 + diff_h
                    w = w0 + diff_w
                    if not in_the_map((h, w)) or visited[h][w]:
                        continue
                    if s[h][w] == '.': # not wall
                        heapq.heappush(queue, (cost + 1, (h, w)))

if not visited[d_h][d_w]:  # Cannot reach to the goal
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# q2 = set()
q2 = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
# visited = {}
visited = [[float("inf") for _ in range(W)] for _ in range(H)]
# visited[(cx, cy)] = 0
visited[cy][cx] = 0
ans = float("inf")
# 01 BFS
while q:
    while q:
        x, y, c = q.popleft()
        # if (x, y) in visited and visited[(x, y)] < c:
        if visited[y][x] < c:
            # print("here1")
            continue
        # print(x, y, c, d, e)
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H:
                if grid[ny][nx] == "#":
                    # q2.add((x, y, c))
                    q2.append((x, y, c))
                else:
                    # if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
                    if visited[ny][nx] <= c:
                        # print("here2")
                        continue
                    # visited[(nx, ny)] = c
                    visited[ny][nx] = c
                    if nx == gx and ny == gy:
                        continue
                    q.append((nx, ny, c))

    # for x, y, c in q2:
    while q2:
        x, y, c = q2.popleft()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                    continue
                nx = x + dx
                ny = y + dy
                # print("warp", dx, dy)
                if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                    # print("warp append")
                    # if (nx, ny) in visited and visited[(nx, ny)] < c + 1:
                    if visited[ny][nx] < c + 1:
                        # print("here3")
                        continue
                    # visited[(nx, ny)] = c + 1
                    visited[ny][nx] = c + 1
                    if nx == gx and ny == gy:
                        continue
                    q.append((nx, ny, c+1))
    # q2 = set()

# print(visited)
if visited[gy][gx] == float("inf"):
    print(-1)
else:
    print(visited[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
def main():
    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)]
    v2=[[0 for j in range(w)] for i in range(h)]
    q=[]
    heappush(q,[0,sx+h*sy])
    while q:
        c,xy=heappop(q)
        x=xy%h
        y=xy//h
        if x==gx and y==gy:
            print(c)
            exit()
        if v[x][y]==1:
            continue
        v[x][y]=1
        for a in range(-2,3):
            for b in range(-2,3):
                if a==b==0:
                    continue
                if a*b==0 and abs(a+b)==1:
                    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+h*ny])
                    continue
                nx=x+a
                ny=y+b
                if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0 and v2[nx][ny]==0:
                    heappush(q,[c+1,nx+h*ny])
                    v2[nx][ny]=1
    print(-1)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
def main():
    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)]
    v2=[[0 for j in range(w)] for i in range(h)]
    q=[]
    heappush(q,[0,sx,sy])
    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 in range(-2,3):
            for b in range(-2,3):
                if a==b==0:
                    continue
                if a*b==0 and abs(a+b)==1:
                    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])
                    continue
                nx=x+a
                ny=y+b
                if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0 and v2[nx][ny]==0:
                    heappush(q,[c+1,nx,ny])
                    v2[nx][ny]=1
    print(-1)
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 = int(V[Ch][Cw])
    goal_area_num = int(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 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)]
v2=[[0 for j in range(w)] for i in range(h)]
q=[]
heappush(q,[0,sx,sy])
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 in range(-2,3):
        for b in range(-2,3):
            if a==b==0:
                continue
            if a*b==0 and abs(a+b)==1:
                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])
                continue
            nx=x+a
            ny=y+b
            if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0 and v2[nx][ny]==0:
                heappush(q,[c+1,nx,ny])
                v2[nx][ny]=1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

def check_func(h, w, check, meiro):
    if (h >= 0 and w >= 0) and (h < len(meiro) and w < len(meiro[0])) and meiro[h][w] == '.' and not (h, w) in check:
        return True
    else:
        return False
def main():
    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())
    s_meiro = []
    for i in range(h):
        s_meiro.append(list(input()))
    check_list = np.full((h, w), -1)
    start = [sh-1, sw-1]
    goal = [gh-1, gw-1]
    now_cost = 0
    checked_point = set()
    cost_1_set = set()
    point_que = deque([start])
    cost_dict = {tuple(start): now_cost}

    move_walk = [[-1, 0], [1, 0], [0, -1,], [0, 1]]
    move_warp = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not [i, j] in move_walk and [i, j] != [0,0]:
                move_warp.append([i, j])

    ans = -1
    while(1):
        # print('----------------')
        # print(point_que)
        # print(cost_dict)
        check_point = point_que.popleft()
        # 歩く
        for masu in move_walk:
            ph, pw = check_point[0] - masu[0], check_point[1] - masu[1]
            cost = cost_dict[tuple(check_point)]
            if (ph, pw) in cost_1_set and [ph, pw] in point_que:
                cost_1_set.discard((ph, pw))
                point_que.remove([ph, pw])
                point_que.appendleft([ph, pw])
                cost_dict[(ph, pw)] = cost
            if check_func(ph, pw, checked_point, s_meiro):
                checked_point.add((ph, pw))
                point_que.appendleft([ph, pw])
                cost_dict[(ph, pw)] = cost
        # 魔法で移動
        for masu in move_warp:
            ph, pw = check_point[0] - masu[0], check_point[1] - masu[1]
            cost = cost_dict[tuple(check_point)]
            if check_func(ph, pw, checked_point, s_meiro):
                cost += 1
                checked_point.add((ph, pw))
                point_que.append([ph, pw])
                cost_dict[(ph, pw)] = cost
                cost_1_set.add((ph, pw))
            
        if len(point_que) == 0:
            break
    try:
        print(cost_dict[tuple(goal)])
    except:
        print(-1)
        
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

H, W = [int(x) for x in input().split()]
c_h, c_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
d_h, d_w = [int(x) - 1 for x in input().split()]  # Convert to 0-origin
s = [['.' for w in range(W)] for h in range(H)]
for h in range(H):
    s[h] = input()

def in_the_map(x):
    if x[0] < 0 or H <= x[0] or x[1] < 0 or W <= x[1]:
        return False
    return True

visited = [[False for w in range(W)] for h in range(H)]
queue = []
heapq.heappush(queue, (0, (c_h, c_w)))  # Push start point with cost (number of warps) 0

while len(queue) > 0:
    cost, p = heapq.heappop(queue)

    if visited[p[0]][p[1]]:  # Skip if already visited (the priority queue assures we can visit to the point with the smallest cost)
        continue
    visited[p[0]][p[1]] = True

    if p[0] == d_h and p[1] == d_w:  # Finally reach to the goal
        print(cost)
        break
    # print(f'Visit {p}: {cost}')

    # Explore neighbours where can be reached by walk (with the same cost as p)
    neighbours = ((p[0], p[1] - 1), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0] + 1, p[1]))
    for n in neighbours:
        if not in_the_map(n) or visited[n[0]][n[1]]:
            continue
        if s[n[0]][n[1]] == '.':  # not wall
            heapq.heappush(queue, (cost, n))  # For later exploration

    # Explore points where can be reached by warp from visited points(with +1 cost from p)
    for diff_h in range(-2, 3, 1):
        for diff_w in range(-2, 3, 1):
            h = p[0] + diff_h
            w = p[1] + diff_w
            if not in_the_map((h, w)) or visited[h][w]:
                continue
            if s[h][w] == '.': # not wall
                heapq.heappush(queue, (cost + 1, (h, w)))

if not visited[d_h][d_w]:  # Cannot reach to the goal
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    H, W = map(int, input().split())

    sy, sx = map(int, input().split())
    start = (sx-1, sy-1)
    gy, gx = map(int, input().split())
    goal = (gx-1, gy-1)
    field = [[c for c in input()] for i in range(H)]

    visited = set()
    queue = deque()
    queue.append((start, 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))

    result = -1
    while queue:
        now_pos, dist = queue.popleft()
        if now_pos in visited:
            continue
        visited.add(now_pos)

        if now_pos == goal:
            result = dist
            break

        now_x, now_y = now_pos

        for dx, dy in move1:
            nxt_x, nxt_y = now_x + dx, now_y + dy
            if (nxt_x, nxt_y) in visited or not(0<=nxt_x<W and 0<=nxt_y<H) or field[nxt_y][nxt_x]=='#':
                continue
            queue.appendleft(((nxt_x, nxt_y), dist))
        
        for dx, dy in move2:
            nxt_x, nxt_y = now_x + dx, now_y + dy
            if (nxt_x, nxt_y) in visited or not(0<=nxt_x<W and 0<=nxt_y<H) or field[nxt_y][nxt_x]=='#':
                continue
            queue.append(((nxt_x, nxt_y), dist+1))

    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    h, w, ch, cw, dh, dw, *m, = open(0).read().split()
    h, w = int(h), int(w)
    start = (int(ch) - 1, int(cw) - 1)
    goal = (int(dh) - 1, int(dw) - 1)
    maze = [tuple(list(i)) for i in m]

    vis = set()

    mw = tuple([(1, 0), (0, 1), (-1, 0), (0, -1)])
    mj = tuple(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:
import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append([cost, Y])

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, [0, st])
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p[0]
            node = p[1]
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to[0]
                to_node = to[1]
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, [to_cost, to_node])

h, w = map(int, input().split())
sh, sw = map(int, input().split())
eh, ew = map(int, input().split())

sh -= 1
sw -= 1
eh -= 1
ew -= 1

S = [input() for _ in range(h)]

di = Dijkstra(h*w)
for x in range(h):
    for y in range(w):
        if S[x][y] == '#': continue
        for i in range(-2, 3):
            for j in range(-2, 3):
                X = x + i
                Y = y + j
                if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                D = abs(i) + abs(j)

                if D == 1: di.insert(x * w + y, X * w + Y, 0)
                if D >= 2: di.insert(x * w + y, X * w + Y, 1)

di.dijkstra(sh * w + sw)
ans = di.dist[eh * w + ew]
if ans == 10**18: print(-1)
else: print(ans)

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)]
v2=[[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):
            if a*b==0 and abs(a+b)<=1:
                continue
            nx=x+a
            ny=y+b
            if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0 and v2[nx][ny]==0:
                heappush(q,[c+1,nx,ny])
                v2[nx][ny]=1
print(-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):
            if a*b==0 and abs(a+b)<=1:
                continue
            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)