Buggy python submission (verdict: Time Limit Exceeded):


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


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

def main():
    from collections import deque
    
    H,W,K=MI()
    x1,y1,x2,y2=MI()
    
    C=[]
    C.append(["@"]*(W+2))
    for _ in range(H):
        c=["@"] + list(input()) + ["@"]
        C.append(c)
    C.append(["@"]*(W+2))
    
    # 各ますにつき4方向分のデータを持つ，コストは（移動回数，今直線で動いた数）でもつ，移動回数がより重要視される
    inf=10**10
    D=[[[(inf,inf)]*4 for _ in range(W+2)]for _ in range(H+2)]#下上右左の4方向
    # D[i][j][k]はi行j列k向き
    
    
    dq=deque()
    for k in range(4):
        D[x1][y1][k]=(0,0)
        dq.append((x1,y1,k,0,0))
    
    dx=[1,-1,0,0]
    dy=[0,0,-1,1]
    
    
    #01BFSでいけそう
    
    while len(dq):
        x,y,d,cnt,k=dq.popleft()
        
        for nd in range(4):
            #方向そのまま
            if nd==d:
                nx=x+dx[nd]
                ny=y+dy[nd]
                nk=(k+1)%K
                ncnt=cnt
                if k+1>=K:
                    ncnt+=1
            #方向転換
            else:
                nk=0
                ncnt=cnt
                if k!=0:
                    ncnt+=1
                nx=x
                ny=y
            if C[nx][ny]==".":
                if D[nx][ny][nd] > (ncnt,nk):#更新する場合だけ
                    D[nx][ny][nd]=(ncnt,nk)
                    if ncnt==cnt:
                        dq.appendleft((nx,ny,nd,ncnt,nk))
                    else:
                        dq.append((nx,ny,nd,ncnt,nk))
                    
    ans=inf
    for d in range(4):
        temp=D[x2][y2][d][0]
        if D[x2][y2][d][1]:
            temp+=1
        ans=min(ans,temp)
        
    if ans>=inf:
        ans=-1
    print(ans)
    
    
    
    # for i in range(1,H+1):
    #     for j in range(1,W+1):
    #         print(D[i][j])
    
    
    
    
    
        
    
                    
            

main()

Buggy python submission (verdict: Time Limit Exceeded):


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


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

def main():
    from collections import deque
    
    H,W,K=MI()
    x1,y1,x2,y2=MI()
    
    C=[]
    C.append(["@"]*(W+2))
    for _ in range(H):
        c=["@"] + list(input()) + ["@"]
        C.append(c)
    C.append(["@"]*(W+2))
    
    # 各ますにつき4方向分のデータを持つ，コストは（移動回数，今直線で動いた数）でもつ，移動回数がより重要視される
    inf=10**10
    D=[[[(inf,inf)]*4 for _ in range(W+2)]for _ in range(H+2)]#下上右左の4方向
    # D[i][j][k]はi行j列k向き
    
    
    dq=deque()
    for k in range(4):
        D[x1][y1][k]=(0,0)
        dq.append((x1,y1,k,0,0))
    
    dx=[1,-1,0,0]
    dy=[0,0,-1,1]
    
    
    #01BFSでいけそう
    
    while len(dq):
        x,y,d,cnt,k=dq.popleft()
        
        for nd in range(4):
            #方向そのまま
            if nd==d:
                nx=x+dx[nd]
                ny=y+dy[nd]
                nk=(k+1)%K
                ncnt=cnt
                if k+1>=K:
                    ncnt+=1
            #方向転換
            else:
                nk=0
                ncnt=cnt
                if k!=0:
                    ncnt+=1
                nx=x
                ny=y
            if C[nx][ny]==".":
                if D[nx][ny][nd] > (ncnt,nk):#更新する場合だけ
                    D[nx][ny][nd]=(ncnt,nk)
                    if ncnt==cnt:
                        dq.appendleft((nx,ny,nd,ncnt,nk))
                    else:
                        dq.append((nx,ny,nd,ncnt,nk))
                    
    ans=inf
    for d in range(4):
        temp=D[x2][y2][d][0]
        if D[x2][y2][d][1]:
            temp+=1
        ans=min(ans,temp)
        
    if ans>=inf:
        ans=-1
    print(ans)
    
    
    
    # for i in range(1,H+1):
    #     for j in range(1,W+1):
    #         print(D[i][j])
    
    
    
    
    
        
    
                    
            

main()