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:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n,m,k=map(int,input().split())
    x1,y1,x2,y2=map(int,input().split())
    ar=[]
    ans=[]
    #visited=[]
    for i in range(n):
        #visited.append([False]*m)
        ar.append(input())
        ans.append([0]*m)

    if(ar[x1-1][y1-1]=='@' or ar[x2-1][y2-1]=='@'):
        print(-1)
    q=[(x1-1,y1-1)]
    br=[(-1,0),(1,0),(0,1),(0,-1)]
    while(q):
        a,b=q.pop(0)
        #print(a,b)
        if(a==x2-1 and b==y2-1):
            print(ans[a][b])
            exit()
        for p,r in br:
            for i in range(1,k+1):
                x=a+i*p
                y=b+i*r
                if not (0<=x<n and 0<=y<m) or ar[x][y]=='@':
                    break
                if(0<ans[x][y]<=ans[a][b]):
                    break

                ans[x][y]=ans[a][b]+1
                q.append((x,y))
    print(-1)







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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # 池を蓮で囲む
    c = [['@'] * (w+2)]
    for _ in range(h):
        i = list('@' + input() + '@')
        c.append(i)
    c.append(['@'] * (w+2))

    # BFS
    # 直線を進めるだけ進む
    from collections import deque
    seen = [[0] * (w+2) for _ in range(h+2)]
    seen[x1][y1] = 1
    todo = deque([(x1, y1)])

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

    while len(todo) > 0:
        ix, iy = todo.popleft()
        s = seen[ix][iy] + 1

        for j in range(4):
            jx, jy = ix, iy
            dxj, dyj = dx[j], dy[j]

            for _ in [0] * k:
                jx, jy = jx + dxj, jy + dyj

                if c[jx][jy] == '@':
                    break

                if jx == x2 and jy == y2:
                    print(s - 1)
                    exit()
            
                if seen[jx][jy] == 0:
                    seen[jx][jy] = s
                    todo.append((jx, jy))

    print(-1)

main()

Submission status: Time Limit Exceeded

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

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # 池を蓮で囲む
    c = [['@'] * (w+2)]
    for _ in range(h):
        i = list('@' + input() + '@')
        c.append(i)
    c.append(['@'] * (w+2))

    # BFS
    # 直線を進めるだけ進む
    from collections import deque
    seen = [[0] * (w+2) for _ in range(h+2)]
    seen[x1][y1] = 1
    todo = deque([(x1, y1)])

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

    while len(todo) > 0:
        ix, iy = todo.popleft()
        s = seen[ix][iy] + 1

        for j in range(4):
            jx, jy = ix, iy
            dxj, dyj = dx[j], dy[j]

            for _ in range(k):
                jx, jy = jx + dxj, jy + dyj

                if c[jx][jy] == '@':
                    break

                if jx == x2 and jy == y2:
                    print(s - 1)
                    exit()
            
                if seen[jx][jy] == 0:
                    seen[jx][jy] = s
                    todo.append((jx, jy))

    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import *

# fast input
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")


def profile(f): return f


@profile
def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    mapdata = sys.stdin.buffer.read().splitlines()
    # print(data)
    start = (x1, y1)
    goal = (x2, y2)

    distances = defaultdict(lambda: INF)
    distances[start] = 0
    shortest_path = {}
    shortest_path[start] = None

    maxdist = max(H, W)

    leaf = ord("@")

    queue = [(0, start)]
    while queue:
        d, frm = heappop(queue)
        # print("from", frm)
        if distances[frm] < d:
            # already know shorter path
            continue
        if frm == goal:  # goal
            break

        x, y = frm
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x
            ny = y
            for dist in range(1, maxdist):
                nx += dx
                ny += dy
                if nx < 1 or H < nx or ny < 1 or W < ny:
                    # print("out of bounds")
                    break
                # print(nx, ny, data[nx - 1][ny - 1])
                if mapdata[nx - 1][ny - 1] == leaf:
                    # print("hit leaf")
                    break
                cost = (dist - 1) // K + 1
                to = (nx, ny)
                if distances[to] > distances[frm] + cost:
                    # found shorter path
                    distances[to] = distances[frm] + cost
                    heappush(queue, (distances[to], to))
                    shortest_path[to] = frm
        # print(distances)

    if distances[goal] == INF:
        # unreachable
        print(-1)
    else:
        path = []
        cur = goal
        print(distances[goal])

        # while True:
        #     frm = shortest_path[cur]
        #     path.append(frm)
        #     cur = frm
        #     if frm == start:
        #         break
        # path.reverse()
        # print(len(path))  # edge count
        # for (frm, to) in path:
        #     print(frm, to)


main()

Submission status: Time Limit Exceeded

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

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # 池を蓮で囲む
    c = [['@'] * (w+2)]
    for _ in range(h):
        i = list('@' + input() + '@')
        c.append(i)
    c.append(['@'] * (w+2))

    # BFS
    # 直線を進めるだけ進む
    from collections import deque
    seen = [[0] * (w+2) for _ in range(h+2)]
    seen[x1][y1] = 1
    todo = deque([(x1, y1)])

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

    while len(todo) > 0:
        ix, iy = todo.popleft()
        for j in range(4):
            jx, jy = ix, iy

            for _ in range(k):
                jx, jy = jx + dx[j], jy + dy[j]

                if c[jx][jy] == '@':
                    break

                if jx == x2 and jy == y2:
                    print(seen[ix][iy])
                    exit()
            
                if seen[jx][jy] == 0:
                    seen[jx][jy] = seen[ix][iy] + 1
                    todo.append((jx, jy))

    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import *

# fast input
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    mapdata = sys.stdin.buffer.read().splitlines()
    # print(data)
    start = (x1, y1)
    goal = (x2, y2)

    distances = defaultdict(lambda: INF)
    distances[start] = 0
    shortest_path = {}
    shortest_path[start] = None

    maxdist = max(H, W)

    leaf = ord("@")

    def neighbor(frm):
        "return (to, cost)"
        x, y = frm
        # print("frm", frm)
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x
            ny = y
            for dist in range(1, maxdist):
                nx += dx
                ny += dy
                if nx < 1 or H < nx or ny < 1 or W < ny:
                    # print("out of bounds")
                    break
                # print(nx, ny, data[nx - 1][ny - 1])
                if mapdata[nx - 1][ny - 1] == leaf:
                    # print("hit leaf")
                    break
                cost = (dist - 1) // K + 1
                yield ((nx, ny), cost)

    queue = [(0, start)]
    while queue:
        d, frm = heappop(queue)
        # print("from", frm)
        if distances[frm] < d:
            # already know shorter path
            continue
        if frm == goal:  # goal
            break
        for to, cost in neighbor(frm):
            if distances[to] > distances[frm] + cost:
                # found shorter path
                distances[to] = distances[frm] + cost
                heappush(queue, (distances[to], to))
                shortest_path[to] = frm
        # print(distances)

    if distances[goal] == INF:
        # unreachable
        print(-1)
    else:
        path = []
        cur = goal
        print(distances[goal])

        # while True:
        #     frm = shortest_path[cur]
        #     path.append(frm)
        #     cur = frm
        #     if frm == start:
        #         break
        # path.reverse()
        # print(len(path))  # edge count
        # for (frm, to) in path:
        #     print(frm, to)


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import *

# fast input
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
map = sys.stdin.buffer.read().splitlines()
# print(data)
start = (x1, y1)
goal = (x2, y2)

distances = defaultdict(lambda: INF)
distances[start] = 0
shortest_path = {}
shortest_path[start] = None

maxdist = max(H, W)

leaf = ord("@")


def neighbor(frm):
    "return (to, cost)"
    x, y = frm
    # print("frm", frm)
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx = x
        ny = y
        for dist in range(1, maxdist):
            nx += dx
            ny += dy
            if nx < 1 or H < nx or ny < 1 or W < ny:
                # print("out of bounds")
                break
            # print(nx, ny, data[nx - 1][ny - 1])
            if map[nx - 1][ny - 1] == leaf:
                # print("hit leaf")
                break
            cost = (dist - 1) // K + 1
            yield ((nx, ny), cost)


queue = [(0, start)]
while queue:
    d, frm = heappop(queue)
    # print("from", frm)
    if distances[frm] < d:
        # already know shorter path
        continue
    if frm == goal:  # goal
        break
    for to, cost in neighbor(frm):
        if distances[to] > distances[frm] + cost:
            # found shorter path
            distances[to] = distances[frm] + cost
            heappush(queue, (distances[to], to))
            shortest_path[to] = frm
    # print(distances)

if distances[goal] == INF:
    # unreachable
    print(-1)
else:
    path = []
    cur = goal
    print(distances[goal])

    # while True:
    #     frm = shortest_path[cur]
    #     path.append(frm)
    #     cur = frm
    #     if frm == start:
    #         break
    # path.reverse()
    # print(len(path))  # edge count
    # for (frm, to) in path:
    #     print(frm, to)

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

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


    
    H,W,K=MI()
    x1,y1,x2,y2=MI()
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    
    C=[[]for _ in range(H)]
    for i in range(H):
        C[i]=list(input())
    
    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=[]#どの列に何があるか
    square_h=int(W**0.5)+3
    square_w=int(H**0.5)+3
    
    for i in range(H):
        XL.append(SquareSkipList(square=square_h))    
    for i in range(W):
        YL.append(SquareSkipList(square=square_w))
    
    
    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:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, W, K = map(int, input().split())
    x1,y1, x2, y2 = map(int, input().split())
    MAP = []
    for i in range(H):
        MAP.append(input())

    queue = []
    heappush(queue, (0, (x1, y1)))
    checked = [[0] * W for _ in range(H)]

    goal = False
    while queue:
        time, (x,y) = heappop(queue)
        checked[x-1][y-1] = 1
        if x == x2 and y == y2:
            goal =True
            break
        for i, j in ((1,0), (-1,0), (0,1), (0,-1)):
            for k in range(1, K+1):
                n_x = x + i * k
                n_y = y + j * k
                if n_x > H or n_x < 1 or n_y < 1 or n_y > W or checked[n_x-1][n_y-1] or MAP[n_x-1][n_y-1] == '@':
                    break
                else:
                    heappush(queue, (time + 1, (n_x, n_y)))
    if not goal:
        print(-1)
    else:
        print(time)
if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
k+=1
y1,x1,y2,x2=map(lambda i:int(i)-1,input().split())
c=[]
for i in range(h):
    c.extend(list(i=="." for i in input()))
d=[-1]*(h*w)
d[x1+y1*w]=0

step=1
start=[(x1,y1)]
nextstart=[]
while len(start)!=0 and d[x2+y2*w]==-1:
    nextstart.clear()
    for x,y in start:
        U,D,L,R=True,True,True,True
        for i in range(1,k):
            if U:
                p=x+(y-i)*w
                if y-i>=0 and c[p]:
                    if d[p]<0:
                        nextstart.append((x,y-i))
                        d[p]=step
                else:
                    U=False
            if D:
                p=x+(y+i)*w
                if y+i!=h and c[p]:
                    if d[p]<0:
                        nextstart.append((x,y+i))
                        d[p]=step
                else:
                    D=False
            if L:
                p=x-i+y*w
                if x-i>=0 and c[p]:
                    if d[p]<0:
                        nextstart.append((x-i,y))
                        d[p]=step
                else:
                    L=False
            if R:
                p=x+i+y*w
                if x+i!=w and c[p]:
                    if d[p]<0:
                        nextstart.append((x+i,y))
                        d[p]=step
                else:
                    R=False
            if not (U or D or L or R):
                break
    start,nextstart=nextstart,start
    step+=1
print(d[x2+y2*w])

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
k+=1
y1,x1,y2,x2=map(lambda i:int(i)-1,input().split())
c=[]
for i in range(h):
    c.extend(list(i=="." for i in input()))
d=[-1]*(h*w)
d[x1+y1*w]=0

step=1
start=[(x1,y1)]
while len(start)!=0 and d[x2+y2*w]==-1:
    nextstart=[]
    for x,y in start:
        U,D,L,R=True,True,True,True
        for i in range(1,k):
            if U:
                p=x+(y-i)*w
                if y-i>=0 and c[p]:
                    if d[p]<0:
                        nextstart.append((x,y-i))
                        d[p]=step
                else:
                    U=False
            if D:
                p=x+(y+i)*w
                if y+i!=h and c[p]:
                    if d[p]<0:
                        nextstart.append((x,y+i))
                        d[p]=step
                else:
                    D=False
            if L:
                p=x-i+y*w
                if x-i>=0 and c[p]:
                    if d[p]<0:
                        nextstart.append((x-i,y))
                        d[p]=step
                else:
                    L=False
            if R:
                p=x+i+y*w
                if x+i!=w and c[p]:
                    if d[p]<0:
                        nextstart.append((x+i,y))
                        d[p]=step
                else:
                    R=False
            if not (U or D or L or R):
                break
    start=nextstart
    step+=1
print(d[x2+y2*w])

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
k+=1
y1,x1,y2,x2=map(lambda i:int(i)-1,input().split())
c=[]
for i in range(h):
    c.extend(list(i=="." for i in input()))
d=[-1]*(h*w)
d[x1+y1*w]=0

step=1
start=[(x1,y1)]
while len(start)!=0 and d[x2+y2*w]==-1:
    nextstart=[]
    for x,y in start:
        U,D,L,R=True,True,True,True
        for i in range(1,k):
            if U:
                p=x+(y-i)*w
                if y-i>=0 and c[p]:
                    if d[p]<0:
                        nextstart.append((x,y-i))
                        d[p]=step
                else:
                    U=False
            if D:
                p=x+(y+i)*w
                if y+i!=h and c[p]:
                    if d[p]<0:
                        nextstart.append((x,y+i))
                        d[p]=step
                else:
                    D=False
            if L:
                p=x-i+y*w
                if x-i>=0 and c[p]:
                    if d[p]<0:
                        nextstart.append((x-i,y))
                        d[p]=step
                else:
                    L=False
            if R:
                p=x+i+y*w
                if x+i!=w and c[p]:
                    if d[p]<0:
                        nextstart.append((x+i,y))
                        d[p]=step
                else:
                    R=False
    start=nextstart
    step+=1
print(d[x2+y2*w])

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
k+=1
y1,x1,y2,x2=map(lambda i:int(i)-1,input().split())
c=[]
for i in range(h):
    c.extend(list(i=="." for i in input()))
d=[-1]*(h*w)
d[x1+y1*w]=0

step=1
start=[(x1,y1)]
while len(start)!=0 and d[x2+y2*w]==-1:
    nextstart=[]
    for x,y in start:
        for i in range(1,k):
            p=x+(y-i)*w
            if y-i<0 or c[p]==False:
                break
            if d[p]<0:
                nextstart.append((x,y-i))
            d[p]=step
        for i in range(1,k):
            p=x+(y+i)*w
            if y+i==h or c[p]==False:
                break
            if d[p]<0:
                nextstart.append((x,y+i))
            d[p]=step
        for i in range(1,k):
            p=x-i+y*w
            if x-i<0 or c[p]==False:
                break
            if d[p]<0:
                nextstart.append((x-i,y))
            d[p]=step
        for i in range(1,k):
            p=x+i+y*w
            if x+i==w or c[p]==False:
                break
            if d[p]<0:
                nextstart.append((x+i,y))
            d[p]=step
    start=nextstart
    step+=1
print(d[x2+y2*w])

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))
            else:
                break
print(-1)