Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
check[ch][cw] = 0
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic1 = [[1, 1], [1, -1], [2, 2], [2, 1], [2, 0], [2, -1], [2, -1]]
magic2 = [[-1, 1], [-1, -1], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -1]]
magic3 = [[1, 1], [-1, 1], [2, 2], [1, 2], [0, 2], [-1, 2], [-2, 2]]
magic4 = [[1, -1], [-1, -1], [2, -2], [1, -2], [0, -2], [-1, -2], [-2, -2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    flg = [False, False, False, False]
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            if dy == 1:
                flg[0] = True
            elif dy == -1:
                flg[1] = True
            elif dx == 1:
                flg[2] = True
            else:
                flg[3] = True
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)
        
    if flg[0]:
        for dy, dx in magic1:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[1]:
        for dy, dx in magic2:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[2]:
        for dy, dx in magic3:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[3]:
        for dy, dx in magic4:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)

if check[dh][dw] == inf:
    print(-1)
else:
    print(check[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [list(input()) for _ in range(h)]

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

que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    if x == dw -1 and y == dh - 1:
        print(0)
        quit()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append((nx, ny))

d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
H = []
heappush(H, (0, cw-1, ch-1))
while H:
    D, x, y = heappop(H)
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > D:
                d[ny][nx] = D
                heappush(H, (D, nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > D + 1:
                    d[ny][nx] = D + 1
                    heappush(H, (D + 1, nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def cin():  return list(map(int,input().split()))

H, W = cin()
ch, cw = cin()
dh, dw = cin()
S = [list(input()) for i in range(H)]
           
def bfs():
    q = deque([])
    dp = [[INF for _ in range(W)] for _ in range(H)]
    dp[ch - 1][cw - 1] = 0
    q.append([ch - 1, cw - 1])
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        for i in range(-2, 3):
            for j in range(-2, 3):
                nx = x + i
                ny = y + j
                if 0 <= nx and nx < H and ny >= 0 and ny < W:
                    if S[nx][ny] == ".":
                        if (i == 0 and (j == 1 or j == -1)) or (j == 0 and (i == 1 or i == -1)):
                            if dp[nx][ny] > dp[x][y]:
                                dp[nx][ny] = dp[x][y]
                                q.append([nx, ny])
                        else:
                            if dp[nx][ny] > dp[x][y] + 1:
                                dp[nx][ny] = dp[x][y] + 1
                                q.append([nx, ny])
              
    return dp[dh - 1][dw - 1]

INF = 10 ** 9 + 7
ans = bfs()
if ans == INF:  print(-1)
else:  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
slist = [input() for i in range(h)]

que = deque()
que.append([ch - 1, cw - 1, 0])
memo = {}
memo[(ch - 1, cw - 1)] = 0
ans = float("inf")
while len(que) != 0:
    sh, sw, count = que.popleft()
    #print(sh, sw, count)
    if sh == dh - 1 and sw == dw - 1:
        if ans > count:
            memo[(sh, sw)] = count
            ans = count
        continue
    for ph, pw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
        if 0 <= sh + ph < h and 0 <= sw + pw < w:
            if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count:
                continue
            if slist[sh + ph][sw + pw] == ".":
                que.append([sh + ph, sw + pw, count])
                memo[(sh + ph, sw + pw)] = count

    for ph in range(-2, 3):
        for pw in range(-2, 3):
            if [ph, pw] not in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
                if 0 <= sh + ph < h and 0 <= sw + pw < w:
                    if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count + 1:
                        continue
                    if slist[sh + ph][sw + pw] == ".":
                        que.append([sh + ph, sw + pw, count + 1])
                        memo[(sh + ph, sw + pw)] = count + 1

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

Submission status: Time Limit Exceeded

Solution code:

import heapq
h,w = map(int, raw_input().split())
s = tuple(map(lambda x:int(x)-1 , raw_input().split()))
t = tuple(map(lambda x:int(x)-1 , raw_input().split()))

heap = [(0,tuple(s))]
r = {}
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = []
	for i in [-2,-1,0,+1,+2]:
		for j in [-2,-1,0,+1,+2]:
			v= (u[0]+i,u[1]+j)
			if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.':
				ret.append(v)
	return ret


while(heap):
	d,u = heapq.heappop(heap)

	r[u] = min(r[u] if u in r else +float('inf'), d)
	if u == t:
		break

	for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
		if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
			if (v not in r) or r[v] > d:
				heapq.heappush(heap,(d,v))
				r[v] = d
	for v in neighbors(u,mat):
		
		if 0 <= v[0] < h and 0 <= v[1] < w:
			if (v not in r) or r[v] > d:
				heapq.heappush(heap,(d+1,v))
				r[v] = d + 1

print (r[t] if t in r else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

H, W = MAP()
Ch, Cw = MAP()
Dh, Dw = MAP()
S = [input() for _ in range(H)]

cnt = [[INF]*W for _ in range(H)]
cnt[Ch-1][Cw-1] = 0

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

def wizard_cnt(start_y, start_x):
	q = deque([(start_y, start_x)])
	while q:
		y, x = q.pop()
		flg = True
		for i in range(24):
			if i == 4 and flg:
				break
			ny = y + dy[i]
			nx = x + dx[i]
			if i < 4:
				if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and cnt[y][x] < cnt[ny][nx]:
					cnt[ny][nx] = cnt[y][x]
					q.append((ny, nx))
				else:
					flg = False
			if 4 <= i and 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and cnt[y][x]+1 < cnt[ny][nx]:
				cnt[ny][nx] = cnt[y][x]+1
				q.append((ny, nx))

wizard_cnt(Ch-1, Cw-1)

if cnt[Dh-1][Dw-1] == INF:
	print(-1)
else:
	print(cnt[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
S = [input() for _ in range(H)]
d = [[0]*W for _ in range(H)]
d[ch][cw] = -1

que = deque([[cw, ch]])
count = 0
while que:
    while que:
        x, y = que.popleft()
        for i in range(-2, 3):
            for j in range(-2, 3):
                nnx, nny = x+i, y+j
                if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                    d[nny][nnx] = 1
        
        for dx, dy in [1, 0], [0, 1], [-1, 0], [0, -1]:
            nx, ny = x+dx, y+dy
            if 0<=nx<W and 0<=ny<H and S[ny][nx]!='#' and d[ny][nx]!=-1:
                if nx == dw and ny == dh:
                    print(count)
                    sys.exit()
                
                d[ny][nx] = -1
                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]]:
                        nnx, nny = nx+i, ny+j
                        if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                            d[nny][nnx] = 1
                que.append([nx, ny])
                
    for i in range(W):
        for j in range(H):
            if d[j][i] == 1:
                d[j][i] == -1
                if i==dw and j==dh:
                    print(count+1)
                    sys.exit()
                que.append([i, j])
                
    count += 1
    
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
inf = 10**20

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

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = input()
    for j in range(w):
        li[i][j] = s[j]

dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
bomb_count = 0

mx = []
my = []

for i in range(-2,3):
    for j in range(-2,3):
        if i == 0 and j == 0:
            continue
        mx.append(i)
        my.append(j)

lin = [[inf for i in range(w)]for j in range(h)]
lin[ch][cw] = 0#ここをスタートの座標に変えること
que.append([ch,cw])#ここもスタートの座標に変えること

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]

    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#" :
            continue
        #elif lin[nx][ny] == inf:
        else:
            if lin[nx][ny] > lin[x][y]:
                if [nx,ny] not in que:
                    que.append([nx,ny])
                lin[nx][ny] =lin[x][y]# 直接行ける
        
    # 魔法の力をもってすれば行ける
    for i,j in zip(mx,my):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#" :
            continue
        else:
            if lin[nx][ny] > lin[x][y]+1:
                if [nx,ny] not in que:
                    que.append([nx,ny])
                lin[nx][ny] = lin[x][y]+1

if lin[dh][dw] == inf:
    print(-1)
else:
    print(lin[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w = m()

c = l()

d = l()

s = [list(input()[:-1]) for i in range(h)]

data = [[-1 for j in range(w)]for i in range(h)]

po = [cl.deque([]) for i in range(h*w+1)]

now = 0
po[0] = cl.deque([[c[0]-1,c[1]-1]])
d[0] -= 1
d[1] -= 1
dire = [[1,0],[0,1],[-1,0],[0,-1]]

#data[c[0]-1][c[1]-1] = 0
while True:
    if now >= h*w+1:
        break
    if len(po[now]) == 0:
        now += 1
        continue
    else:
        popo = po[now].popleft()
        if data[popo[0]][popo[1]] != -1 and data[popo[0]][popo[1]] < now:
            continue
        else:
            data[popo[0]][popo[1]] = now
            for kkk in dire:
                if (popo[0] + kkk[0] >= 0 and popo[0] + kkk[0] < h) and (popo[1] + kkk[1] >= 0 and popo[1] + kkk[1] < w):
                    if s[popo[0] + kkk[0]][popo[1] + kkk[1]] == "#":
                        continue
                    if data[popo[0] + kkk[0]][popo[1] + kkk[1]] == -1 or data[popo[0] + kkk[0]][popo[1] + kkk[1]] > now:
                        data[popo[0] + kkk[0]][popo[1] + kkk[1]] = now
                        po[now].append([popo[0]+ kkk[0],popo[1] + kkk[1]])

            for i in range(5):
                i -= 2
                if i + popo[0] < 0 or i + popo[0] >= h:
                    continue
                for j in range(5):
                    j -= 2
                    if j + popo[1] < 0 or j + popo[1] >= w:
                        continue
                    elif s[popo[0]+ i][popo[1] + j] == ".":
                        if data[popo[0]+ i][popo[1] + j] > now+1 or data[popo[0]+ i][popo[1] + j] == -1:
                            if now + 1 <= h*w:
                                data[popo[0]+ i][popo[1] + j] = now+1
                                po[now+1].append([popo[0]+ i,popo[1] + j])


print(data[d[0]][d[1]])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush, heappushpop

INF = 1e10


class PriorityQueue:
    """
    優先度付きキューの
    """
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self, item):
        heappush(self.heap, item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self, item):
        return heappushpop(self.heap, item)
    
    def __call__(self):
        return self.heap
    
    def __len__(self):
        return len(self.heap)
    

def dijkstra(adj, sx, sy):
    Color = [[0]*(W+2) for _ in range(H+2)] # 0: 未訪問 1: Seen 2: Visited
    D = [[INF]*(W+2) for _ in range(H+2)] #始点からの距離(重み)
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。

    while PQ: # PQに候補がある限り

        min_cost, ux, uy = PQ.pop() # 最小コストなノードu

        Color[ux][uy] = 2 # uをVisitedに。

        if D[ux][uy] < min_cost:
            # 更新の必要なし.
            continue

        for adj_element in adj[(ux, uy)]:
            adj_x, adj_y, adj_w = adj_element
            if Color[adj_x][adj_y] != 2: #訪問済みでないなら
                if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                    D[adj_x][adj_y] = D[ux][uy] + adj_w
                    # P[adj_idx] = u
                    # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                    PQ.push((D[adj_x][adj_y], adj_x, adj_y))
                    Color[adj_x][adj_y] = 1
    
    return D


from collections import deque
import sys
input = sys.stdin.readline

H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [["#"]*(W+2) for _ in range(H+2)]
for i in range(1,1+H):
    tmp=list(input())
    for j in range(1,1+W):
        S[i][j]=tmp[j-1]

idxs = []
for row in range(1, H+1):
    for col in range(1, W+1):
        if S[row][col] == ".":
            idxs.append((row, col))

dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
graph = {idx: deque() for idx in idxs}
for idx in idxs:
    x = idx[0]
    y = idx[1]
    for dx, dy in dxdy:
        if S[x+dx][y+dy] == ".":
            graph[idx].append((x+dx, y+dy, 0))

for idx in idxs:
    x = idx[0]
    y = idx[1]
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if x+dx < 1 or x+dx>H or y+dy<1 or y+dy>W:
                continue
            if S[x+dx][y+dy] == ".":
                graph[idx].append((x+dx, y+dy, 1))

D = dijkstra(graph, ch, cw)
if D[dh][dw] == INF:
    print(-1)
else:
    print(D[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())
S = [input() for _ in range(H)]


move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[10**8] * W for _ in range(H)]


def bfs(i, j, d):
    visited[i][j] = d
    que = deque([(i, j, d)])

    while que:
        ci, cj, d = que.popleft()

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] <= d:
                continue
            if S[ni][nj] == '.':
                visited[ni][nj] = d
                que.append((ni, nj, d))

        for di in range(-2, 3):
            for dj in range(-2, 3):
                ni, nj = ci+di, cj+dj
                if not (0 <= ni < H and 0 <= nj < W)  \
                        or visited[ni][nj] <= d+1 or abs(ni)+abs(nj) <= 1:
                    continue
                if S[ni][nj] == '.':
                    visited[ni][nj] = d+1
                    que.append((ni, nj, d+1))


bfs(Ch-1, Cw-1, 0)
# print(visited)
if visited[Dh-1][Dw-1] == 10**8:
    print(-1)
else:
    print(visited[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:

import heapq
h,w = map(int, raw_input().split())
s = tuple(map(lambda x:int(x)-1 , raw_input().split()))
t = tuple(map(lambda x:int(x)-1 , raw_input().split()))

heap = [(0,tuple(s))]
r = {}
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = []
	for i in [-2,-1,0,+1,+2]:
		for j in [-2,-1,0,+1,+2]:
			v= (u[0]+i,u[1]+j)
			if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.':
				ret.append(v)
	return ret


while(heap):
	d,u = heapq.heappop(heap)

	r[u] = min(r[u] if u in r else +float('inf'), d)
	for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
		if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
			if (v not in r) or r[v] > d:
				heapq.heappush(heap,(d,v))
				r[v] = d
	for v in neighbors(u,mat):
		
		if 0 <= v[0] < h and 0 <= v[1] < w:
			if (v not in r) or r[v] > d:
				heapq.heappush(heap,(d+1,v))
				r[v] = d + 1

print (r[t] if t in r else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self, start, goal):
        grid = self.grid
        cy, cx = start
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        warp = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                warp.append((i, j))
        h = []
        self.set(start[1], start[0], 0)
        heappush(h, (cx, cy))
        while h:
            cx, cy = heappop(h)
            cc = self.get(cx, cy)
            for dx, dy in move:

                nx, ny = dx + cx, dy + cy
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc:
                    self.set(nx, ny, cc)
                    heappush(h, (nx, ny))

            for dx, dy in warp:
                nx, ny = dx + cx, dy + cy
                if nx < 0 or nx > self.w + 1 or ny < 0 or ny > self.h + 1:
                    continue
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc + 1:
                    self.set(nx, ny, cc + 1)
                    heappush(h, (nx, ny))
        # print(warp)
        # self.show()
        # self.showsomejoin(self.grid)
        ans = self.get(goal[1], goal[0])
        if ans == INF:
            print(-1)
            return
        else:
            print(ans)
            return





def solve():
    h, w = getList()
    start = getList()
    goal = getList()
    G = TwoDimGrid(h, w)
    G.search(start, goal)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

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

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()
visited[sh][sw] = 0
d.append(sh*(W+4)+sw)

while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[h][w]
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        visited[h1][w1]=cnt
        d.append((h1*(W+4)+w1))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        visited[h2][w2]=cnt+1
        d.append((h2*(W+4)+w2))
ans = visited[gh][gw] if visited[gh][gw]<float('inf') else -1
print(ans)

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())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
dy=[-1,1,0,0,2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dx=[0,0,1,-1,0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    
    for i in range(24):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if abs(ny-y)+abs(nx-x)==1:
          if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
            q.append((ny,nx))
            D[ny][nx]=D[y][x]
        else:
          if A[ny][nx]=='.':
            if D[ny][nx]==10**8:
              q.append((ny,nx))
              D[ny][nx]=D[y][x]+1
            elif D[ny][nx]>D[y][x]+1:
              q.append((ny,nx))
              D[ny][nx]=D[y][x]+1
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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
g = ['#' * (w + 4)] * 2 
for _ in range(h):
    g.append('##' + input() + '##')
g.append('#' * (w + 4))
g.append('#' * (w + 4))

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

import heapq
# Dijkstra
d = [-2, -1, 0, 1, 2]
seen = [[-1] * (w+2) for _ in range(h+2)]
todo = [(0, ch, cw)]
heapq.heapify(todo)
while len(todo) > 0:
    cost, x, y = heapq.heappop(todo)
    if seen[x][y] == -1:
        if x == dh and y == dw:
            print(cost)
            exit()
        seen[x][y] = cost

    for i in range(4):
        dx, dy = d1[i]
        if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
            heapq.heappush(todo, (cost, x+dx, y+dy))
    for i in range(20):
        dx, dy = d2[i]
        if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
            heapq.heappush(todo, (cost+1, x+dx, y+dy))

print(-1)