Problem: 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.

Submission attempts (in order):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline




#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from collections import deque

def main():
	h,w,k=MI()
	x1,y1,x2,y2=MI()
	G=["@"]*(w+2)
	for _ in range(h):
		G.append("@")
		G+=(list(map(str,input().rstrip())))
		G.append("@")
	G+=["@"]*(w+2)
	#print(G)


	G[x1*(w+2)+y1]=0
	#print(G)

	Q=deque()
	Q.append((x1*(w+2)+y1,0))

	while Q:
		#print(Q)
		now,d=Q.popleft()
		#print(Q)
		for i in range(1,k+1):
			if G[now+i]==d or G[now+i]=="@":
				break
			elif G[now+i]==".":
				G[now+i]=d+1
				Q.append([now+i,d+1])
			elif G[now+i]>d:
				G[now+i]=d+1
				Q.append([now+i,d+1])


		for i in range(1,k+1):
			if G[now-i]==d or G[now+i]=="@":
				break
			elif G[now-i]==".":
				G[now-i]=d+1
				Q.append([now-i,d+1])
			elif G[now-i]>d:
				G[now-i]=d+1
				Q.append([now-i,d+1])
			else:
				break

		for i in range(1,k+1):
			if G[now+(w+2)*i]==d or G[now+(w+2)*i]=="@":
				break
			elif G[now+(w+2)*i]==".":
				G[now+(w+2)*i]=d+1
				Q.append([now+(w+2)*i,d+1])
			elif G[now+(w+2)*i]>d:
				G[now+(w+2)*i]=d+1
				Q.append([now+(w+2)*i,d+1])
			else:
				break


		for i in range(1,k+1):
			if G[now-(w+2)*i]==d or G[now-(w+2)*i]=="@":
				break
			elif G[now-(w+2)*i]==".":
				G[now-(w+2)*i]=d+1
				Q.append([now-(w+2)*i,d+1])
			elif G[now-(w+2)*i]>d:
				G[now-(w+2)*i]=d+1
				Q.append([now-(w+2)*i,d+1])
			else:
				break
		#print(Q)
	#print(G)

	if G[x2*(w+2)+y2]==".":
		print(-1)
	else:
		print(G[x2*(w+2)+y2])


if __name__ == "__main__":
	main()


import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline




#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from collections import deque

def main():
	h,w,k=MI()
	x1,y1,x2,y2=MI()
	G=["@"]*(w+2)
	for _ in range(h):
		G.append("@")
		G+=(list(map(str,input().rstrip())))
		G.append("@")
	G+=["@"]*(w+2)
	#print(G)


	G[x1*(w+2)+y1]=0
	#print(G)

	Q=deque()
	Q.append((x1*(w+2)+y1,0))

	while Q:
		#print(Q)
		now,d=Q.popleft()
		#print(Q)
		for m in [1,-1,w+2,-w-2]:
			for i in range(1,k+1):
				if G[now+m*i]==d or G[now+m*i]=="@":
					break
				elif G[now+m*i]==".":
					G[now+m*i]=d+1
					Q.append([now+m*i,d+1])
				elif G[now+m*i]==d+1:
					continue
				else:
					break

		#print(Q)
	#print(G)

	if G[x2*(w+2)+y2]==".":
		print(-1)
	else:
		print(G[x2*(w+2)+y2])


if __name__ == "__main__":
	main()


Verdicts: Runtime Error

Accepted