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:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

#input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


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
arr = [list(input()) for i in range(h)]
#print(arr)
can_vis = []
dist = [[float("inf")]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury = q.popleft()
	#can_vis.append((curx,cury))
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.append((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# 方針は分かったのでヨシ！ (dist[nx][ny] > dist[x][y] を忘れてた　後コードきたねえ)
INF = float("inf")
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF]*W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx, ny))
        for nx, ny in [(x-1, y-1), (x-1, y+1), (x+1, y+1), (x+1, y-1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
        for nx in range(x-2, x+3):
            for ny in [y+2, y-2]:
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))
        for nx in [x+2, x-2]:
            for ny in range(y-1, y+2):
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))            
    return dist[gx][gy]

H, W = map(int, input().split())

cx, cy = map(int, input().split()); sx, sy = cx - 1, cy - 1
dx, dy = map(int, input().split()); gx, gy = dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math


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


def bfs():
    for y in range(h):
        for x in range(w):
            if s[y][x]=='.':
                s[y][x]=math.inf


    s[c[0]-1][c[1]-1]=0
    que=deque([[c[0]-1,c[1]-1]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0<=y+i<h and 0<=x+j<w:
                nexty,nextx=y+i,x+j
                dist=s[nexty][nextx]
                if dist!='#':
                    if dist>s[y][x]:
                        s[nexty][nextx]=s[y][x]
                        que.append([nexty,nextx])

        for k,l in [(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)]:
            if 0<=y+k<h and 0<=x+l<w:
                warpy,warpx=y+k,x+l
                dist=s[warpy][warpx]
                if dist!='#':
                    if dist>s[y][x]+1:
                        s[warpy][warpx]=s[y][x]+1
                        que.append([warpy,warpx])
    if s[d[0]-1][d[1]-1]==math.inf:
        print(-1)
    else:
        print(s[d[0]-1][d[1]-1])

bfs()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():

    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())

    s = [input() for _ in range(h)]
    INF = 10 ** 9

    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1

    dq = deque([f(sh, sw)])
    dist = [[INF] * w for _ in range(h)]
    dist[sh][sw] = 0

    while dq:
        i = dq.popleft()
        hi, wi = divmod(i, w)

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    continue
                nh = hi + dh
                nw = wi + dw
                if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                    if abs(dh) + abs(dw) == 1:
                        if dist[hi][wi] < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi]
                            dq.appendleft(f(nh, nw))
                    else:
                        if dist[hi][wi] + 1 < dist[nh][nw]:
                            dist[nh][nw] = dist[hi][wi] + 1
                            dq.append(f(nh, nw))

    ans = dist[gh][gw]
    if ans == INF:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

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()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # 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 and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            q.appendleft((nx, ny, e))
    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] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e+1))

print(-1 if ans == float("inf") else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area.copy()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

#input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


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
arr = [list(input()) for i in range(h)]
#print(arr)
can_vis = []
dist = [[float("inf")]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw,0))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury,magic = q.popleft()
	#can_vis.append((curx,cury))
	f = 0
	if curx == dh and cury == dw:
		ans = min(ans, magic)
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.append((curx+dx, cury+dy,magic))
			f = 1
	if f: continue
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy,magic+1))


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

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
sh,sw = map(int, input().split())
gh,gw = map(int, input().split())
ab = [list(input()) for _ in range(h)]

import math
from collections import deque

ap =list('#'*w)
ab.insert(0,ap)
ab.insert(0,ap)
ab.append(ap)
ab.append(ap)

ab_t = [list(x) for x in zip(*ab)]

app = list('#'*(h+4))
ab_t.insert(0,app)
ab_t.insert(0,app)
ab_t.append(app)
ab_t.append(app)

ab = [list(x) for x in zip(*ab_t)]

for y in range(h+4):
    for x in range(w+4):
        if ab[y][x]=='.':
            ab[y][x]=math.inf

ab[sh+1][sw+1]=0
que=deque([[sh+1,sw+1]])
while que:
    y,x=que.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
        nexty,nextx=y+i,x+j
        dist=ab[nexty][nextx]
        if dist!='#' :
            if dist>ab[y][x]:
                ab[nexty][nextx]=ab[y][x]
                que.append([nexty,nextx])
    for i,j in [(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)]:
        nexty,nextx=y+i,x+j
        dist=ab[nexty][nextx]
        if dist!='#':
            if dist>ab[y][x]+1:
                ab[nexty][nextx]=ab[y][x]+1
                que.append([nexty,nextx])

if ab[gh+1][gw+1] ==math.inf:
    print(-1)
else:
    print(ab[gh+1][gw+1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
        
    s[y][x]='#'
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i:
                continue
            if x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]!='#':
                nxt.append([y+i,x+j,now+1])
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        rcl(y+yy,x+xx,now)


while nxt:
    i=nxt.pop(0)
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)

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 bfs(root):
    x, y = root
    dp[y, x] = 0
    queue = deque([root])
    while queue:
        x, y = queue.popleft()
        d = dp[y, x]
        for dx, dy in product(range(-2, 3), repeat=2):
            if dx == dy == 0:
                continue
            nx, ny = x+dx, y+dy
            if abs(dx) + abs(dy) == 1:
                if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                    dp[ny, nx] = d
                    queue.appendleft((nx, ny))          
            elif dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                queue.append((nx, ny))
bfs((cw-1, ch-1))
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Submission status: Time Limit Exceeded

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

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

from collections import  deque
seen = set()
queue = deque([(0, CH-1, CW-1)])

while queue:
    move, row, col = queue.popleft()

    if (row, col) in seen:
        continue
    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

print(-1)

Submission status: Time Limit Exceeded

Solution code:

def     RemoveDoublons(pile, elem):
    i = 0
    l = len(pile)
    while (i < l):
        val = pile[i]
        if (val[0] == elem[0] and val[1] == elem[1]):
            pile.pop(i)
            l -= 1
        i += 1
    return pile

def     findCloser(pile, distance, lastDist):
    pos = 0
    elem = pile[0]
    bestDist = distance[elem[0]][elem[1]]
    if (bestDist == lastDist):
        return 0
    for i in range(len(pile)):
        val = pile[i]
        if (distance[val[0]][val[1]] < bestDist):
            elem = val
            bestDist = distance[elem[0]][elem[1]]
            pos = i
            if (bestDist == lastDist):
                return pos
    return pos

def     isValidCase(i, j, size, mappy):
    if (i < 0 or  j < 0 or i >= size[0] or j >= size[1] or not mappy[i][j]):
        return False
    return True

def     Calculdist(i, j, elem):
    if ((i == elem[0] and  abs(j - elem[1]) == 1) or (j == elem[1] and  abs(i - elem[0]) == 1)):
        return 0
    return 1

def printMappy(distance):
    for i in range(len(distance)):
        print(distance[i])

def     parcour(mappy, distance, start, end, size):
    pile = [start]
    distance[start[0]][start[1]] = 0
    myDist = 0
    while(len(pile) > 0):
        pos = findCloser(pile, distance, myDist)
        elem = pile.pop(pos)
        pile = RemoveDoublons(pile, elem)
        myDist = distance[elem[0]][elem[1]]
        if (elem[0] == end[0] and elem[1] == end[1]):
            return myDist
        for i in range(elem[0] - 2, elem[0] + 3):
            for j in range(elem[1] - 2, elem[1] + 3 ):
                if (isValidCase(i, j, size, mappy) and not (i == elem[0] and j == elem[1])):
                    dist = Calculdist(i, j, elem)
                    if (myDist + dist < distance[i][j]):
                        distance[i][j] = myDist + dist
                        pile.append([i,j])
    return -1


data = input().split()
size = [int(data[0]) , int(data[1])]
data = input().split()
start = [int(data[0]) - 1, int(data[1]) - 1]
data = input().split()
end = [int(data[0]) - 1, int(data[1]) - 1]

LIM = 999999
mappy = []
distance = []
for i in range(size[0]):
    tmp = [False] * size[1]
    tmp2 = [LIM] * size[1]
    s = input()
    for j in range(size[1]):
        if (s[j] == '.'):
            tmp[j] = True
    mappy.append(tmp)
    distance.append(tmp2)
res = parcour(mappy, distance, start, end, size)
print(res)
#printMappy(distance)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = float('inf')


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


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


def LS(): return sys.stdin.readline().split()


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


def IR(n): return [I() for i in range(n)]


def LIR(n): return [LI() for i in range(n)]


def SR(n): return [S() for i in range(n)]


def LSR(n): return [LS() for i in range(n)]


def SRL(n): return [list(S()) for i in range(n)]


def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7


h, w = LI()
sy, sx = LI()
gy, gx = LI()
sy-=1; sx-=1; gy-=1; gx-= 1
grid = SR(h)
dp = [[INF]*w for _ in range(h)]
q1 = deque([(sy,sx)])
q2 = deque([(sy, sx)])
dp[sy][sx]=0
while q1 or q2:
    while q1:
        uy,ux=q1.popleft()
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
            ny=uy+i
            nx=ux+j
            if 0<=ny<h and 0<=nx<w and grid[ny][nx]=="." and dp[ny][nx]>dp[uy][ux]:
                dp[ny][nx]=dp[uy][ux]
                q1+=[(ny,nx)]
                q2+=[(ny,nx)]
    while q2:
        uy,ux=q2.popleft()
        for i in range(-2,3):
            for j in range(-2, 3):
                ny=uy+i
                nx=ux+j
                if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == "." and dp[ny][nx] > dp[uy][ux] + 1:
                    dp[ny][nx]=dp[uy][ux]+1
                    q1 += [(ny, nx)]
                    q2 += [(ny, nx)]


print(dp[gy][gx] if dp[gy][gx] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    gh, gw = map(int, input().split())
    gh -= 1
    gw -= 1
    S = [input().rstrip() for _ in range(H)]
    dist = [[INF] * W for _ in range(H)]
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(1, 1), (1, -1), (-1, 1), (-1, -1),
            (2, 0), (2, 1), (2, 2), (2, -1), (2, -2),
            (-2, 0), (-2, 1), (-2, 2), (-2, -1), (-2, -2),
            (0, 2), (1, 2), (-1, 2), (0, -2), (1, -2), (-1, -2)]
    Q = deque()
    Q.append((sh, sw))
    dist[sh][sw] = 0
    while Q:
        h, w = Q.popleft()
        if h == gh and w == gw:
            continue
        flag = 0
        d = dist[h][w]
        for dh, dw in walk:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.':
                    if dist[nh][nw] > d:
                        dist[nh][nw] = d
                        Q.append((nh, nw))
                else:
                    flag = 1
        if flag:
            for dh, dw in warp:
                nh = h + dh
                nw = w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if dist[nh][nw] > d + 1:
                        dist[nh][nw] = d + 1
                        Q.append((nh, nw))

    if dist[gh][gw] == INF:
        print(-1)
    else:
        print(dist[gh][gw])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
def label_borderd_4_neighborhoods(image, h, w, neg):
    labeled = [[0] * w for _ in range(h)]
    lut = [0]

    i = 1
    for y in range(1, h-1):
        for x in range(1, w - 1):
            if image[y][x] != neg:
                if labeled[y][x-1] == 0 and labeled[y-1][x] == 0:
                    labeled[y][x] = i
                    lut.append(i)
                    i+=1
                elif labeled[y-1][x] == 0 or labeled[y-1][x] == labeled[y][x-1]:
                    labeled[y][x] = labeled[y][x-1]
                elif labeled[y][x-1] == 0:
                    labeled[y][x] = labeled[y-1][x]
                else:
                    j, k = labeled[y-1][x], labeled[y][x-1]
                    while lut[j] != j:
                        j = lut[j]
                    while lut[k] != k:
                        k = lut[k]
                    l = min(j, k)
                    lut[j], lut[k] = l, l
                    j, k = labeled[y-1][x], labeled[y][x-1]
                    while lut[j] != l:
                        next_j = lut[j]
                        lut[j], j = l, next_j
                    while lut[k] != l:
                        next_k = lut[k]
                        lut[k], k = lut[k], next_k
                    labeled[y][x] = l
    for i in range(len(lut)):
        l = i
        while l != lut[l]:
            l = lut[l]
        j = i
        while j != lut[j]:
            next_j = lut[j]
            lut[j], j = l, next_j
    for y in range(1, h-1):
        for x in range(1, w - 1):
            labeled[y][x] = lut[labeled[y][x]]
    return labeled, len(set(lut)) - 1

h, w = map(int, input().split())
sy, sx = map(lambda x:int(x)+1, input().split())
gy, gx = map(lambda x:int(x)+1, input().split())
grid = [['#'] * (w + 4) for _ in range(2)]
for y in range(h):
    grid.append(['#', '#'] + [c for c in input()] + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

labeled, label_n = label_borderd_4_neighborhoods(grid, h + 4, w + 4, '#')

s = labeled[sy][sx]
g = labeled[gy][gx]
if s == g:
    print(0)
    quit()

q = [(0, sy, sx)]
visited = set()
ans = 0
while q:
    n, y, x = heappop(q)
    if (y, x) in visited:
        continue
    if labeled[y][x] == g:
        ans = n
        q.append((0, 0, 0)) # dummy
        break
    visited.add((y, x))
    for dy in range(-2, 3):
        yy = y + dy 
        for dx in range(-2, 3):
            xx = x + dx
            if labeled[yy][xx] != 0 and not (yy, xx) in visited:
                if abs(dx) + abs(dy) == 1:
                    heappush(q, (n, yy, xx))
                elif labeled[yy][xx] != labeled[y][x]:
                    heappush(q, (n+1, yy, xx))
print(ans if q else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([[ch-1, cw-1, 0]])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

d[(ch-1) * w + (cw-1)] = 0
while stack:
    curh, curw, cnt = stack_popleft()
    if d[curh * w + curw] < cnt: continue
    #print(curh, curw, cnt)
    d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt
            stack_append([nh, nw, cnt])
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            d[nh * w + nw] = cnt + 1
            stack_append([nh, nw, cnt+1])

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
S = [input().strip() for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in d:
        ny, nx = y+h, x+w
        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and worp < worps[ny][nx]:
            worps[ny][nx] = worp
            q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h < H and 0 <= w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.appendleft([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    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()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0, 0, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, c, d, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # 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 and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            q.appendleft((nx, ny, c+1, d, e))
    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] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, c+1, d, e+1))

print(-1 if ans == float("inf") else ans)