Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
ch, cw = ch-1, cw-1
dh, dw = dh-1, dw-1

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

num = 10000*np.ones((h,w))
# for i in range(h):
#     for j in range(w):
#         num[i,j] = np.inf

num[dh,dw] = 0
q = deque([[dh,dw]])
walk = [[-1,0],[0,-1],[0,1],[1,0]]
warp = [[-2,i] for i in range(-2,3)] + [[i,-2] for i in range(-1,2)]  + [[i,2] for i in range(-1,2)] + [[2,i] for i in range(-2,3)]

while len(q)>0:
    now = q.popleft()
    for x in walk:
        next_point = [now[0]+x[0], now[1]+x[1]]
        if not (0 <= next_point[0] < h and 0 <= next_point[1] < w ): # 外に出てた場合
            continue
        next_num = num[next_point[0],next_point[1]]
        now_num = num[now[0],now[1]]
        if s[next_point[0]][next_point[1]] =='.'  and \
            (next_num== 10000 or\
            next_num > now_num): # まだやってない場合
            num[next_point[0],next_point[1]] = now_num
            q.append(next_point)
    for x in warp:
        next_point = [now[0]+x[0], now[1]+x[1]]
        if not (0 <= next_point[0] < h and 0 <= next_point[1] < w ): # 外に出てた場合
            continue
        next_num = num[next_point[0],next_point[1]]
        now_num = num[now[0],now[1]]
        if s[next_point[0]][next_point[1]] =='.'  and \
            (next_num == 10000 or\
            next_num > now_num + 1): # まだやってない場合
            num[next_point[0],next_point[1]] = now_num + 1
            q.append(next_point)
if num[ch,cw]==10000:
    print(-1)
else:
    print(int(num[ch,cw]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("#","1")
    maze.append(list(map(int, RRR)))
#print(maze)
dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[(2,0),(2,1),(2,2),(2,-1),(2,-2),(1,-2),(1,2),(0,2),(0,-2),(-1,2),(-1,-2),(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2)]
cand=[start]
dis[start[0]][start[1]]=0
done=[]
flag=False
while len(cand)>0:
    #print(cand)
    place=cand.pop()
    hh,ww,cost=place
    if hh==Dh and ww==Dw:
        flag=True
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost:
            dis[h1][w1]=cost
            cand.append((h1,w1,cost))
    for each in wap:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
            dis[h1][w1]=cost+1
            cand.append((h1,w1,cost+1))
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[int(ch == '#') for ch in input().rstrip()] for _ in range(H)]

from sys import exit
from collections import deque
from itertools import product
que = deque([c])
passed = set()
queued = set()
nque = set()
cnt = 0
while nque or que:
    while que:
        h,w = que.popleft()
#         print(f'{h=},{w=}')
        if (h,w) == d:
            print(cnt)
            exit()
        if (h,w) in passed:
            continue
        passed.add((h,w))
        for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and (nh,nw) not in queued and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
                que.append((nh,nw))
                queued.add((nh,nw))

        for dh,dw in product(range(-2, 3), repeat=2):
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and (nh,nw) not in queued and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
                nque.add((nh,nw))
    que = deque(nque)
    nque = set()
    cnt += 1
#     print(f'{que=}, {cnt=}')
print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
c,d = map(int,input().split())
e,f = map(int,input().split())
s = []
t = []
m = h*w
for i in range(h):
    s.append(input())
    t.append([m]*w)
c -= 1
d -= 1
t[c][d] = 0
cnt = 0
stc1 = [[c,d]]
stc2 = []
while(1):
#for i in range(10):
    if(c > 0):
        if(s[c-1][d] == '.' and t[c-1][d] > cnt):
            t[c-1][d] = cnt
            stc1.append([c-1,d])
    if(d > 0):
        if(s[c][d-1] == '.' and t[c][d-1] > cnt):
            t[c][d-1] = cnt
            stc1.append([c,d-1])
    if(c < h-1):
        if(s[c+1][d] == '.' and t[c+1][d] > cnt):
            t[c+1][d] = cnt
            stc1.append([c+1,d])
    if(d < w-1):
        if(s[c][d+1] == '.' and t[c][d+1] > cnt):
            t[c][d+1] = cnt
            stc1.append([c,d+1])
    for j in range(-2,3):
        for k in range(-2,3):
            if(abs(j)+abs(k) > 1):
                if(c+j >= 0 and c+j < h and d+k >= 0 and d+k < w):
                    if(s[c+j][d+k] == '.' and t[c+j][d+k] > cnt+1):
                        t[c+j][d+k] = min(t[c+j][d+k],cnt+1)
                        stc2.append([c+j,d+k])
    if(len(stc1) > 1):
        stc1 = stc1[1:]
        c = stc1[0][0]
        d = stc1[0][1]
    else:
        if(len(stc2) > 0):
            stc1 = stc2
            stc2 = []
            c = stc1[0][0]
            d = stc1[0][1]
            cnt += 1
        else:
            break
            
if(t[e-1][f-1] == m):
    print(-1)
else:
    print(t[e-1][f-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq

def ok(i, j):
    return 0 <= i < H and 0 <= j < W and S[i][j] == '.'

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1
S = []
for _ in range(H):
    row = list(input())
    S.append(row)
if S[D_h][D_w] == '#':
    print(-1)
else:
    queue = [(0, (C_h, C_w))]
    dist = {(C_h, C_w): 0}
    while queue:
        score, cur = heapq.heappop(queue)
        if cur == (D_h, D_w):
            print(score)
            break
        i, j = cur
        for offset in (1, -1):
            i_next = i + offset
            j_next = j + offset
            if ok(i_next, j) and ((i_next, j) not in dist or dist[i_next, j] > score):
                heapq.heappush(queue, (score, (i_next, j)))
                dist[i_next, j] = score
            if ok(i, j_next) and ((i, j_next) not in dist or dist[i, j_next] > score):
                heapq.heappush(queue, (score, (i, j_next)))
                dist[i, j_next] = score

        for a in [-2, -1, 0, 1, 2]:
            for b in [-2, -1, 0, 1, 2]:
                if a == b == 0:
                    continue
                i_jump = i + a
                j_jump = j + b
                if ok(i_jump, j_jump) and ((i_jump, j_jump) not in dist or dist[i_jump, j_jump] > score + 1):
                    heapq.heappush(queue, (score + 1, (i_jump, j_jump)))
                    dist[i_jump, j_jump] = score + 1
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
toGo = [[False if i != C[0] or j != C[1] else True for j in range(W)] for i in range(H)]
queue = [C]
ans = 0
 
while True:
    tmp = queue.pop()
    dfs = [tmp]
 
    while len(dfs):
        a = dfs.pop()
        for move in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            hh, ww = a[0] + move[0], a[1] + move[1]
            if hh >= H or hh < 0 or ww >= W or ww < 0:
                continue
 
            if not toGo[hh][ww] and S[hh][ww] == '.':
                toGo[hh][ww] = True
                dfs.append([hh, ww])
 
    if toGo[D[0]][D[1]]:
        break
 
    flag = True
    if not len(queue):
        ttogo = [[toGo[i][j] for j in range(W)] for i in range(H)]
        ans += 1
        for i in range(H):
            for j in range(W):
                if not toGo[i][j] and S[i][j] == ".":
                    t = False
                    for ii in range(-2, 3):
                        for jj in range(-2, 3):
                            hh, ww = i + ii, j + jj
                            if hh >= H or hh < 0 or ww >= W or ww < 0:
                                continue
 
                            if toGo[hh][ww]:
                                ttogo[i][j] = True
                                flag, t = False, True
                                queue.append([i, j])
                                break
                        if t:
                            break
        toGo = ttogo
        if flag:
            print(-1)
            exit()
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from heapq import heappop,heappush

h,w = map(int,readline().split())
ch,cw = map(int,readline().split())
dh,dw = map(int,readline().split())
s = read().split()

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

wall = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j] == '#'):
            wall[i][j] = 1

cost = [[-1] * w for _ in range(h)]
hq = [(0,ch,cw)]


while(hq):
    ci,xi,yi = heappop(hq)
    if(cost[xi][yi] > -1):
        continue
    cost[xi][yi] = ci

    for dx in range(-2,3):
        xj = xi+dx
        if(xj<0)|(xj>=h):
            continue
        for dy in range(-2,3):
            yj = yi+dy
            # print(xi,yi,xj,yj)
            if(yj<0)|(yj>=w):
                continue
            if(cost[xj][yj]!=-1):
                continue
            if(xi==xj)&(yi==yj):
                continue
            if(wall[xj][yj]==1):
                continue
            if(abs(xi-xj)+abs(yi-yj)==1):
                heappush(hq,(ci,xj,yj))
            else:
                heappush(hq,(ci+1,xj,yj))

print(cost[dh][dw])

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

grid = []
for i in range(H):
    grid.append(input().rstrip())

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

memo = [[[False] * W for _ in range(H)] for _ in range(1000)]
memo[0][Ch-1][Cw-1] = True

searched = [[False] * W for _ in range(H)]

ans = -1

while d:
    h, w, c = d.popleft()

    if searched[h][w]:
        continue

    searched[h][w] = True

    if h == Dh-1 and w == Dw-1:
        ans = c
        break

    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if 0 <= h+i < H and 0 <= w+j < W:
            if grid[h+i][w+j] == '.':
                if not memo[c][h+i][w+j]:
                    memo[c][h+i][w+j] = True
                    d.appendleft((h+i, w+j, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= h+i < H and 0 <= w+j < W:
                if grid[h+i][w+j] == '.':
                    if not memo[c][h+i][w+j] and not memo[c+1][h+i][w+j]:
                        memo[c+1][h+i][w+j] = True
                        d.append((h+i, w+j, c+1))

print(ans)

Submission status: Time Limit Exceeded

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

def main():
    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 = [list(input()) for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    visited[Ch][Cw] = True
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.':
                    if visited[nh][nw] == False:
                        cnt[nh][nw] = cnt[h][w]
                        visited[nh][nw] = True
                        Q.append([nh,nw])
                    else:
                        if cnt[nh][nw] > cnt[h][w]:
                            cnt[nh][nw] = cnt[h][w]
                            Q.append([nh,nw])
                else:
                    for j in range(-2,3):
                        for k in range(-2,3):
                            nh = h + j
                            nw = w + k
                            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                                if cnt[nh][nw] > cnt[h][w]:
                                    cnt[nh][nw] = cnt[h][w] + 1
                                    visited[nh][nw] = True
                                    Q.append([nh,nw])

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




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
HW = [list(input()) for _ in range(H)]


def check(ny, nx):
    if 0 <= ny < H and 0 <= nx < W and HW[ny][nx] == ".":
        return True
    else:
        return False


dist = [[float("inf")] * W for _ in range(H)]
# print("dist")
# pl(dist)
dist[ch - 1][cw - 1] = 0

deq = deque()
deq.append([(ch - 1, cw - 1)])  # insert indices
ddy = [-1, 0, 1, 0]
ddx = [0, -1, 0, 1]
warpy = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
warpx = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
step = 0
found = False
while deq[0]:
    nqueue = []
    cqueue = deq.popleft()
    # pl(HW)
    for val in cqueue:
        y, x = val
        # if val == (gy - 1, gx - 1):
        #     found = True
        #     break
        for dy, dx in zip(ddy, ddx):
            ny, nx = y + dy, x + dx
            if check(ny, nx):
                HW[ny][nx] = "#"
                dist[ny][nx] = min(dist[ny][nx], dist[y][x])
                nqueue.append((ny, nx))
        for dy, dx in zip(warpy, warpx):
            ny, nx = y + dy, x + dx
            if check(ny, nx):
                dist[ny][nx] = min(dist[ny][nx], dist[y][x] + 1)
                nqueue.append((ny, nx))
    # if found:
    #     break
    deq.append(nqueue)
    # step += 1

val = dist[dh - 1][dw - 1]
if val == float("inf"):
    print(-1)
else:
    print(val)
# print(dist[dh - 1][dw - 1])

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())
    inf = 10**10
    dp = [[inf]*w for _ in range(h)]
    s = [list(input()) for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    
    dp[ch-1][cw-1] = 0
    
    q = deque([[0, ch-1, cw-1]])
    
    while q:
        cost, px, py = q.pop()
        if dp[px][py] < cost:
            continue

        for xi, yj in zip(dx, dy):
            x = px + xi
            y = py + yj
            if x >= h or y >= w or x < 0 or y < 0:
                continue
            if s[x][y] == "#":
                continue
            if dp[x][y] > cost:
                dp[x][y] = cost
                q.appendleft([cost, x, y])
        cost += 1
        for di in range(-2, 3):
            x = px + di
            if x >= h or x < 0:
                continue
            for dj in range(-2, 3):
                y = py + dj
                if y >= w or y < 0:
                    continue
                if s[x][y] == "#":
                    continue
                if dp[x][y] > cost:
                    dp[x][y] = cost
                    q.appendleft([cost, x, y])
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(root):
    x, y, d = root
    dp[y, x] = 0
    stack = [root]
    while stack:
        x, y, d = stack.pop()
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                if dp[ny, nx] > d:
                    dp[ny, nx] = d
                    stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                if dp[ny, nx] > d+1:
                    dp[ny, nx] = d+1
                    stack.append((nx, ny, d+1))
dfs((cw-1, ch-1, 0))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = [int(x) for x in input().split()]
Ch, Cw = [int(x) - 1 for x in input().split()]
Dh, Dw = [int(x) - 1 for x in input().split()]

maze = []
warp_count = []
for _ in range(H):
    line = list([x for x in input()])
    maze.append(line)
    warp_count.append([10**9] * W)

queue = deque()
queue.appendleft((Ch, Cw, 0))

answer = 10**9
while queue:
    now_h, now_w, use_magic = queue.pop()
    warp_count[now_h][now_w] = use_magic

    if now_h == Dh and now_w == Dw:
        if answer > use_magic:
            answer = use_magic

        continue

    # 壁じゃない場合
    if not maze[now_h][now_w] == '#':

        # 上下左右に移動
        if now_h + 1 < H:
            if warp_count[now_h + 1][now_w] > use_magic:
                queue.appendleft((now_h+1, now_w, use_magic))
        if now_h - 1 >= 0:
            if warp_count[now_h - 1][now_w] > use_magic:
                queue.appendleft((now_h-1, now_w, use_magic))
        if now_w + 1 < W:
            if warp_count[now_h][now_w + 1] > use_magic:
                queue.appendleft((now_h, now_w + 1, use_magic))
        if now_w - 1 >= 0:
            if warp_count[now_h][now_w - 1] > use_magic:
                queue.appendleft((now_h, now_w - 1, use_magic))

        for h in range(-2, 3):
            for w in range(-2, 3):
                warp_h = now_h + h
                warp_w = now_w + w

                if warp_h >= 0 and warp_h < H:
                    if warp_w >= 0 and warp_w < W:
                        if warp_count[warp_h][warp_w] > use_magic + 1:
                            queue.append((warp_h, warp_w, use_magic + 1))


if answer == 10**9:
    print(-1)
else:
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd,deque as dq
import sys
inf=1000000
input=sys.stdin.readline
print=sys.stdout.write
n,m=map(int,input().split())
cx,cy=map(int,input().split())
cx-=1
cy-=1
dx,dy=map(int,input().split())
dx-=1
dy-=1
ll=[]
for i in range(n):
    ll.append(input().split()[0])
q=dq([cx*m+cy])
dis=[inf]*(n*m+1)
xx=[0,-1,0,1]
yy=[1,0,-1,0]
des=dx*m+dy
d=[[] for i in range(n*m)]
for x in range(n):
    for y in range(m):
        for i in range(4):
            X=x+xx[i]
            Y=y+yy[i]
            if(X<n and X>=0 and Y<m and Y>=0 and ll[X][Y]=='.'):
                d[x*m+y].append((X*m+Y,0))
        X=x-2
        Y=Y-2
        for i in range(5):
            for j in range(5):
                if(X+i>=0 and X+i<n and Y+j>=0 and Y+j<m and ll[X+i][Y+j]=='.'):
                    d[x*m+y].append(((X+i)*m+Y+j,1))
dis[q[0]]=0
lol=0
while q:
    curr=q.pop()
    #print(curr)
    if(curr==des):
        print(str(dis[curr]))
        lol=1
        break
    for j in d[curr]:
        temp,val=j
        if(dis[temp]>dis[curr]+val):
            dis[temp]=dis[curr]+val
            if(val==0):
                q.append(temp)
            else:
                q.appendleft(temp)
if(lol==0):
    print(str(-1))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

def explore(C, D):
    magic_n = 0

    queue = deque([[C[0]-1, C[1]-1]])
    maze_visited[C[0]-1][C[1]-1] = magic_n
    while queue:
        y, x = queue.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                if S[n_y][n_x] == '.':
                    if maze_visited[n_y][n_x] > maze_visited[y][x]:
                        maze_visited[n_y][n_x] = maze_visited[y][x]
                        queue.append([n_y, n_x])
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    if S[n_y][n_x] == '.':
                        if maze_visited[n_y][n_x] > maze_visited[y][x] + 1:
                            maze_visited[n_y][n_x] = maze_visited[y][x] + 1
                            queue.append([n_y, n_x])
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))

S = [list(input()) for i in range(H)]

maze_visited = [[math.inf] * W for i in range(H)]

explore(C,D)

if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 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())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
maze = [input() for _ in range(h)]
directions = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
              (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
              (0, -2),  (0, -1),           (0, 1),  (0, 2),
              (1, -2),  (1, -1),  (1, 0),  (1, 1),  (1, 2),
              (2, -2),  (2, -1),  (2, 0),  (2, 1),  (2, 2)]

INF = 10 ** 9
mp = [[INF for _ in range(w)] for _ in range(h)]
mp[ch][cw] = 0
q = [(ch, cw)]
for y, x in q:
    for dy, dx in directions:
        ny, nx = y + dy, x + dx
        if (ny < 0 or h <= ny) or (nx < 0 or w <= nx):
            continue
        if maze[ny][nx] == '#':
            continue
        is_teleported = abs(dy) + abs(dx) > 1
        cost = mp[y][x] + is_teleported
        if mp[ny][nx] > cost:
            mp[ny][nx] = cost
            q.append((ny, nx))

if mp[dh][dw] == INF:
    print(-1)
else:
    print(mp[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
def solve():
    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 = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            for dh in range(-2,2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2, 2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    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)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(n) for n in input().split(" ")]
Ch, Cw = [int(n) for n in input().split(" ")]
Dh, Dw = [int(n) for n in input().split(" ")]

M = []
for i in range(H):
    s = input()
    tmp = []
    for j in range(W):
        if s[j] == ".":
            tmp.append(0)
        else:
            tmp.append(-1)
    M.append(tmp)

def paint(m, startI, startJ, color):
    if m[startI][startJ] != 0:
        return
    m[startI][startJ] = color
    
    nextIJ = [
        [startI - 1, startJ],
        [startI, startJ + 1],
        [startI + 1, startJ],
        [startI, startJ - 1]
    ]

    for i in range(4):
        nextI = nextIJ[i][0]
        nextJ = nextIJ[i][1]
        if nextI >= 0 and nextI < H and nextJ >= 0 and nextJ < W:
            paint(m, nextI, nextJ, color)
    return

def checkNeighbor(m, startI, startJ):
    result = []
    mycolor = m[startI][startJ]
    nextIJ = [
        [startI - 2, startJ - 2],
        [startI - 2, startJ - 1],
        [startI - 2, startJ - 0],
        [startI - 2, startJ + 1],
        [startI - 2, startJ + 2],
        [startI - 1, startJ - 2],
        [startI - 1, startJ - 1],
        [startI - 1, startJ + 1],
        [startI - 1, startJ + 2],
        [startI - 0, startJ - 2],
        [startI - 0, startJ + 2],
        [startI + 2, startJ - 2],
        [startI + 2, startJ - 1],
        [startI + 2, startJ - 0],
        [startI + 2, startJ + 1],
        [startI + 2, startJ + 2],
        [startI + 1, startJ - 2],
        [startI + 1, startJ - 1],
        [startI + 1, startJ + 1],
        [startI + 1, startJ + 2]
    ]
    for i in range(len(nextIJ)):
        nextI = nextIJ[i][0]
        nextJ = nextIJ[i][1]
        if nextI >= 0 and nextI < H and nextJ >= 0 and nextJ < W:
            if m[nextI][nextJ] != -1 and mycolor != m[nextI][nextJ]:
                a = mycolor
                b = m[nextI][nextJ]
                if a > b:
                    result.append([b, a])
                else:
                    result.append([a, b])
    return result

#print(M)
nowcolor = 1
for i in range(H):
    for j in range(W):
        if M[i][j] == 0:
            paint(M, i, j, nowcolor)
            nowcolor += 1
#print(M)

neighbors = []
for a in range(1, nowcolor):
    tmp = [0 for _ in range(nowcolor - 1)]
    neighbors.append(tmp)

for i in range(H):
    for j in range(W):
        if M[i][j] != -1:
            neighbor = checkNeighbor(M, i, j)
            for a in neighbor:
                neighbors[a[0] - 1][a[1] - 1] = 1
                neighbors[a[1] - 1][a[0] - 1] = 1

#print(neighbors)

startColor = M[Ch - 1][Cw - 1]
goalColor = M[Dh - 1][Dw - 1]

if startColor == goalColor:
    print("0")
    exit(0)

depth = 0
queue = [startColor]
already = []
result = -1
while True:
    if len(queue) <= 0:
        break
    depth += 1
    now = queue[0]
    already.append(now)
    del(queue[0])
    nextNodes = []
    for c in range(1, nowcolor):
        #print("nextcheck", now, c)
        if neighbors[now - 1][c - 1] == 1 and c not in already:
            nextNodes.append(c)
            #print("push", c)
            if c == goalColor:
                result = depth
                queue = []
                nextNodes = []
                break
    queue += nextNodes
print(result)