Problem:


Score : 600 points

Problem Statement

Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.

Some of the squares have a lotus leaf on it and cannot be entered.
The square (i,j) has a lotus leaf on it if c_{ij} is @, and it does not if c_{ij} is ..

In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west.
The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.

Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2).
If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Constraints

1 \leq H,W,K \leq 10^6

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

H W K
x_1 y_1 x_2 y_2
c_{1,1}c_{1,2} .. c_{1,W}
c_{2,1}c_{2,2} .. c_{2,W}
:
c_{H,1}c_{H,2} .. c_{H,W}

Output

Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2), or print -1 if the travel is impossible.

Sample Input 1

3 5 2
3 2 3 4
.....
.@..@
..@..

Sample Output 1

5

Initially, Snuke is at the square (3,2).
He can reach the square (3, 4) by making five strokes as follows:

From (3, 2), go west one square to (3, 1).

From (3, 1), go north two squares to (1, 1).

From (1, 1), go east two squares to (1, 3).

From (1, 3), go east one square to (1, 4).

From (1, 4), go south two squares to (3, 4).

Sample Input 2

1 6 4
1 1 1 6
......

Sample Output 2

2

Sample Input 3

3 3 1
2 1 2 3
.@.
.@.
.@.

Sample Output 3

-1



Sample input:
3 5 2
3 2 3 4
.....
.@..@
..@..


Sample output:
5

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, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        dy_, dx_ = dy[i], dx[i]
        ny, nx = y, x
        for _ in range(1, k+1):
            ny, nx = ny + dy_, nx + dx_ 
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))

print(-1)

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, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        for j in range(1, k+1):
            ny, nx = y + dy[i] * j, x + dx[i] * j
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque
INF = 10**18
 
h, w, k = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
 
field = []
dist = []
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))
for _ in range(h):
    line = "".join(["@", input().rstrip(), "@"])
    field.append(line)
    dist.append([-1] + [INF] * (w) + [-1])
field.append("@" * (w + 2))
dist.append([-1] * (w + 2))
 
# for line in field:
#     print(line)
dist[sx][sy] = 0
 
delta = ((0, 1), (0, -1), (-1, 0), (1, 0))
 
def bfs(x, y):
    dq = deque()
    dist[x][y] = 0
    for dx, dy in delta:
        if field[x+dx][y+dy] == ".":
            dq.append((x+dx, y+dy, (dx, dy), k))
    while dq:
        x, y, d, step = dq.popleft()
        dx = d[0]; dy = d[1]
        ncost = dist[x - dx][y - dy] + 1 - (step < k)
        if ncost > dist[x][y]:
            continue
        else:
            dist[x][y] = ncost
        if step > 1:
            if field[x+dx][y+dy] == "." and dist[x+dx][y+dy] >= dist[x][y]:
                dq.appendleft((x + dx, y + dy, d, step - 1))
            for nd in delta:
                nx = x + nd[0]; ny = y + nd[1]
                if nd == d or nd == (-dx, -dy):
                    continue
                if field[nx][ny] == "." and dist[nx][ny] >= dist[x][y] + 1:
                    dq.append((nx, ny, nd, k))
        else:
            for nd in delta:
                nx = x + nd[0]; ny = y + nd[1]
                if nd == (-dx, -dy):
                    continue
                if field[nx][ny] == "." and dist[nx][ny] >= dist[x][y] + 1:
                    dq.append((nx, ny, nd, k))
 
bfs(sx, sy)
# for line in dist:
#     print(" ".join([str(item) for item in line]))
if dist[gx][gy] == INF:
    print(-1)
else:
    print(dist[gx][gy])

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, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
h = []
heappush(h, (0, x1-1, y1-1))
dp[x1-1][y1-1] = 0
while h:
    dist_xy, y, x = heappop(h)
    if y == x2 - 1 and x == y2 - 1:
        print(dist_xy)
        quit()
    for i in range(4):
        for j in range(1, k+1):
            ny, nx = y + dy[i] * j, x + dx[i] * j
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist_xy + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist_xy + 1
                    heappush(h, (dist_xy + 1, ny, nx))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from heapq import heapify, heappush as hpush, heappop as hpop
H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "@" else 0 for a in input()] + [1]
X += [1] * (W + 2)
X += X[:]
H, W = H+2, W+2
HW = H * W
s, t = x1 * W + y1, x2 * W + y2
ss, tt = s + HW, t + HW
def dijkstra():
    n = 2 * H * W
    h = [[0, s], [0, ss]]
    D = [-1] * n
    done = [0] * n
    D[s] = 0
    D[ss] = 0
    while h:
        d, i = hpop(h)
        done[i] = 1
        if i < HW:
            for j in (i+1, i-1):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, [nd, j])
                        D[j] = nd
        else:
            for j in (i+W, i-W):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, [nd, j])
                        D[j] = nd
            
        j = i + HW if i < HW else i - HW
        nd = (d + K - 1) // K * K
        if X[j]: continue
        if D[j] < 0 or D[j] > nd:
            if done[j] == 0:
                hpush(h, [nd, j])
                D[j] = nd
    return [-(-a//K) for a in (D[t], D[tt]) if a >= 0]

di = dijkstra()
print(min(di) if di else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=deque([a:=~w+a*w+b])
d[a]=1
while q:
 s=q.popleft()
 for x in 0,1,2,3:
  for z in range(k):
   y=0,z+1,0,~z;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる
        
        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき
            
            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)
                
            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]
                
            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def print(self):
            print(self.layer1)
            print(self.layer0)
            
        def len(self):
            return self.cnt

    ##############################


    
    mod=10**9+7
    H,W,K=MI()
    x1,y1,x2,y2=MI()
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    
    C=[]
    for i in range(H):
        s=list(input())
        C.append(s)
    
    D=[[-1]*W for _ in range(H)]
    
    import queue
    
    q=queue.Queue()
    q.put((x1,y1,0))
    
    D[x1][y1]=0
    inf=10**7
    
    
    #各行と各列の未巡回リストを作る
    XL=[]#どの行に何があるか
    YL=[]#どの列に何があるか
    for i in range(H):
        XL.append(SquareSkipList(square=1200))    
    for i in range(W):
        YL.append(SquareSkipList(square=1200))
    
    
    for i in range(H):
        for j in range(W):
            XL[i].add(j)
            YL[j].add(i)
    
    #最初のところ
    XL[x1].remove(y1)
    YL[y1].remove(x1)
    
    #番兵
    for i in range(H):
        XL[i].add(inf)
        XL[i].add(-inf)
    for j in range(W):
        YL[j].add(inf)
        YL[j].add(-inf)
        
    # for i in range(H):
    #     XL[i].print()  
    # print("---")
    # for j in range(W):
    #     YL[j].print()
        
    
    while not q.empty():
        x,y,d=q.get()
        
        #xを固定してyを動かす，右側
        ceil=y+K
        floor=y
        while True:
            a=XL[x].search_higher_equal(floor)
            if a>ceil:
                break
            else:
                nx=x
                ny=a
                
                #壁なら激突して終わり，取り除きもしない
                if C[nx][ny]=="@":
                    break
                
                XL[x].remove(a)
                YL[a].remove(x)
                
                
                D[nx][ny]=d+1
                q.put((nx,ny,d+1))
                
        #xを固定してyを動かす，左側
        ceil=y
        floor=y-K
        while True:
            a=XL[x].search_lower(ceil+1)
            if a<floor:
                break
            else:
                nx=x
                ny=a
                
                #壁なら激突して終わり，取り除きもしない
                if C[nx][ny]=="@":
                    break
                
                XL[x].remove(a)
                YL[a].remove(x)
                
                
                D[nx][ny]=d+1
                q.put((nx,ny,d+1))
               
        #yを固定，右側 
        ceil=x+K
        floor=x
        while True:
            a=YL[y].search_higher_equal(floor)
            if a>ceil:
                break
            else:
                nx=a
                ny=y
                
                #壁なら激突して終わり，取り除きもしない
                if C[nx][ny]=="@":
                    break
                
                XL[a].remove(y)
                YL[y].remove(a)
                
                D[nx][ny]=d+1
                q.put((nx,ny,d+1))
                
        #yを固定，左
        ceil=x
        floor=x-K
        while True:
            a=YL[y].search_lower(ceil)
            if a<floor:
                break
            else:
                nx=a
                ny=y
                
                #壁なら激突して終わり，取り除きもしない
                if C[nx][ny]=="@":
                    break
                
                XL[a].remove(y)
                YL[y].remove(a)
                
                
                D[nx][ny]=d+1
                q.put((nx,ny,d+1))
                
    # for i in range(H):
    #     print(D[i])
                    
  
    print(D[x2][y2])
                    
            

main()

Submission status: Time Limit Exceeded

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

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x : int(x) - 1, input().split())
c = [input().rstrip() for _ in range(H)]
INF = 10**18
dist = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]
dist[x1][y1] = [(1, 0)] * 4
heap = []
for i in range(4):
    heappush(heap, (dist[x1][y1][i], x1, y1, i))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while heap:
    d, x, y, i = heappop(heap)

    if d > dist[x][y][i]:
        continue

    for j in range(4):
        nd = (d[0] + 1, 0)
        if dist[x][y][j] > nd:
            dist[x][y][j] = nd
            heappush(heap, (nd, x, y, j))

    nx = x + dx[i]
    ny = y + dy[i]
    if nx < 0 or H <= nx or ny < 0 or W <= ny or c[nx][ny] == '@':
        continue
    nd = (d[0], d[1] + 1) if d[1] < K else (d[0] + 1, 1)
    if dist[nx][ny][i] > nd:
        dist[nx][ny][i] = nd
        heappush(heap, (nd, nx, ny, i))
ans = min(dist[x2][y2])[0]
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      if cost[y+j*dy[i]][x+j*dx[i]]>c+1:
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

Submission status: Time Limit Exceeded

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

def calc():
  h,w,k=map(int,input().split())
  sy,sx,gy,gx=map(int,input().split())
  sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
  board=[input() for _ in range(h)]
  q=collections.deque()
  q.append((sx,sy))
  checked=[[[0,0,0,0] for _ in range(w)] for _ in range(h)]
  checked[sy][sx][0]=1
  checked[sy][sx][1]=1
  checked[sy][sx][2]=1
  checked[sy][sx][3]=1
  cost=[[10**18]*w for _ in range(h)]
  cost[sy][sx]=0
  while len(q)!=0:
    x,y=q.popleft()
    c=cost[y][x]
    for i in range(1,k+1):
      if x+i<w and checked[y][x+i][0]==0 and board[y][x+i]=='.' and c<cost[y][x+i]:
        checked[y][x+i][0]=1
        cost[y][x+i]=c+1
        q.append((x+i,y))
      else:
        break
    for i in range(1,k+1):
      if x-i>=0 and checked[y][x-i][1]==0 and board[y][x-i]=='.' and c<cost[y][x-i]:
        checked[y][x-i][1]=1
        cost[y][x-i]=c+1
        q.append((x-i,y))
      else:
        break
    for i in range(1,k+1):
      if y+i<h and checked[y+i][x][2]==0 and board[y+i][x]=='.' and c<cost[y+i][x]:
        checked[y+i][x][2]=1
        cost[y+i][x]=c+1
        q.append((x,y+i))
      else:
        break
    for i in range(1,k+1):
      if y-i>=0 and checked[y-i][x][3]==0 and board[y-i][x]=='.' and c<cost[y-i][x]:
        checked[y-i][x][3]=1
        cost[y-i][x]=c+1
        q.append((x,y-i))
      else:
        break
  if cost[gy][gx]==10**18:
    print(-1)
  else:
    print(cost[gy][gx])
calc()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
def main():
    direction = [(-1, 0), (0, -1), (1, 0), (0, 1)] 
    h,w,K = [int(j) for j in input().split()]
    stx, sty,endx, endy = [int(j)-1 for j in input().split()]
    l = []
    n = h
    for i in range(n):
        l.append(list(input()))
    q = []
    heappush(q, (0, (-1, stx, sty)))
    visited = [[-1 for i in range(w)] for j in range(h)]
    flag = True
    while(q):
        ele = heappop(q)
        x,y = ele[1][1],ele[1][2]
        prev_dir = ele[1][0]
        dist = ele[0] 
        # print(x,y,dist) 
        visited[x][y] = dist
        if x==endx and y==endy:
            print(dist)
            flag = False
            break
        for i in range(4):
            if i==prev_dir:
                continue
            if prev_dir!=-1 and i%2==prev_dir%2:
                continue
            for k in range(1,max(h, w)):
                nx = x+direction[i][0]*k
                ny = y+direction[i][1]*k
                if nx<0 or nx>=h or ny<0 or ny>=w:
                    break
                if l[nx][ny]=="@":
                    break
                cost = int((k+K-1)/K)+dist
                if visited[nx][ny]==-1 or visited[nx][ny]>cost:
                    visited[nx][ny] = cost
                    heappush(q, (cost, (i, nx, ny)))  
    if flag:
        print(-1)
# for #!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase




# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
direction = [(-1, 0), (0, -1), (1, 0), (0, 1)] 
h,w,K = [int(j) for j in input().split()]
stx, sty,endx, endy = [int(j)-1 for j in input().split()]
l = []
n = h
for i in range(n):
    l.append(list(input()))
q = []
heappush(q, (0, (-1, stx, sty)))
visited = [[-1 for i in range(w)] for j in range(h)]
flag = True
while(q):
    ele = heappop(q)
    x,y = ele[1][1],ele[1][2]
    prev_dir = ele[1][0]
    dist = ele[0] 
    # print(x,y,dist) 
    visited[x][y] = dist
    if x==endx and y==endy:
        print(dist)
        flag = False
        break
    for i in range(4):
        if i==prev_dir:
            continue
        if prev_dir!=-1 and i%2==prev_dir%2:
            continue
        for k in range(1,max(h, w)):
            nx = x+direction[i][0]*k
            ny = y+direction[i][1]*k
            if nx<0 or nx>=h or ny<0 or ny>=w:
                break
            if l[nx][ny]=="@":
                break
            cost = int((k+K-1)/K)+dist
            if visited[nx][ny]==-1 or visited[nx][ny]>cost:
                visited[nx][ny] = cost
                heappush(q, (cost, (i, nx, ny)))  
if flag:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=0,z+1,0,~z;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=z+1,0,~z,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=0,~z,0,z+1;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in range(4):
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[x^1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[x^1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0,~z;i,j=s//w+y[x],s%w+y[x+1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
y=1,0,-1,0,1
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in range(4):
  for z in range(k):
   if'.'!=m[(i:=s//w+y[x]*~z)][(j:=s%w+y[x+1]*~z)]or(p:=d[s]+1)>d[(t:=i*w+j)]:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
m+='@'*w,
d=[I:=h*w]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]:break
   if d[t]>=p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

q = [(1,x1-1,y1-1)]
c[x1-1][y1-1] = 0
while(q):
  qq = []
  for a,x,y in q:
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      for kk in range(1,k+1):
        xx = x+dx*kk
        yy = y+dy*kk
        if not (0 <= xx < h) or not (0 <= yy < w) or c[xx][yy] == '@' or (c[xx][yy] != '.' and c[xx][yy] < a):
            break
        c[xx][yy] = a
        qq.append((a+1,xx,yy))
  #print(qq)
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
#print(c)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Time Limit Exceeded

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)