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

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline






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


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)
	


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

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

	while Q:
		
		now,d=Q.popleft()
		
		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

		
	

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


if __name__ == "__main__":
	main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline






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


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)
	


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

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

	while Q:
		
		now,d=Q.popleft()
		
		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

		
	

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


if __name__ == "__main__":
	main()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.buffer.readline

h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1


c = [list(input()) for i in range(h)]

pq = [0]*(h*w)


dp = [10**7]*(h*w)


pq[x1*w + y1] = 3
dp[x1*w + y1] = 0
tank = deque([x1*w+y1])



while tank:

    
    now = tank.popleft()
    cost = dp[now]
    
    for i in range(1,k+1):
        if (now+i)%w != 0 and dp[now+i] > cost and c[(now+i)//w][(now+i)%w] == 46 and pq[now+i] < 5:
            pq[now+i] += 1 
            dp[now+i] = cost+1
            tank.append(now+i)
        else:
            break
    for i in range(1,k+1):
        if (now-i)%w != w-1 and dp[now-i] > cost and c[(now-i)//w][(now-i)%w] == 46 and pq[now-i] < 5:
            pq[now-i] += 1
            dp[now-i] = cost+1
            tank.append(now-i)
        else:
            break

    for i in range(1,k+1):
        if (now+i*w) < h*w and dp[now+i*w] > cost and c[(now+i*w)//w][(now+i*w)%w] == 46 and pq[now+i*w] < 5:
            pq[now+i*w] += 1
            dp[now+i*w] = cost+1
            tank.append(now+i*w)
        else:
            break
    for i in range(1,k+1):
        if (now-i*w) >= 0 and dp[now-i*w] > cost and c[(now-i*w)//w][(now-i*w)%w] == 46 and pq[now-i*w] < 5:
            pq[now-i*w] += 1
            dp[now-i*w] = cost+1
            tank.append(now-i*w)
        else:
            break


if dp[x2*w+y2] == 10**7:
    print(-1)
else:
    print(dp[x2*w+y2])

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10000000)
readline = sys.stdin.readline

def solve():
    H, W, K = map(int, readline().split())
    x1, y1, x2, y2 = map(int,readline().split())
    x1, y1, x2, y2 = (v - 1 for v in (x1, y1, x2, y2))
    C = [readline().rstrip() for i in range(H)]

    INF = 10 ** 10
    visited = [[INF] * W for i in range(H)]
    dist = [[0] * W for i in range(H)]

    dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    q = deque()

    q.append((x1, y1, 0))
    visited[x1][y1] = 0
    dist[x1][y1] = 0

    def aa(_i, _j, y, x, d):
        i, j = _i, _j
        for k in range(K):
            i += y
            j += x
            if not (0 <= i < H and 0 <= j < W):
                break
            if C[i][j] == '@':
                break
            if d > visited[i][j]:
                break
            if d == visited[i][j]:
                continue
            visited[i][j] = d
            dist[i][j] = d
            q.append((i, j, d))

    while q:
        i, j, d = q.popleft()
        for y,x in dirs:
            aa(i, j, y, x, d+1)
    
    if visited[x2][y2] == INF:
        print(-1)
    else:
        print(dist[x2][y2])
    
solve()

Solution (Python):
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
import sys
input=sys.stdin.readline
L=[]
l=["@" for i in range(W+2)]
L.append(l)
for i in range(H):
    c=["@"]+list(input().rstrip())+["@"]
    L.append(c)
L.append(l)
L[x1][y1]=0

Q=[[x1,y1]]
for i in range(10**7):
    if i>=len(Q):
        break
    for j in range(1,K+1):
        if L[Q[i][0]+j][Q[i][1]]==".":
            L[Q[i][0]+j][Q[i][1]]=L[Q[i][0]][Q[i][1]]+1
            Q.append([Q[i][0]+j,Q[i][1]])
        elif L[Q[i][0]+j][Q[i][1]]==L[Q[i][0]][Q[i][1]]+1:
            continue
        else:
            break
    for j in range(1,K+1):
        if L[Q[i][0]-j][Q[i][1]]==".":
            L[Q[i][0]-j][Q[i][1]]=L[Q[i][0]][Q[i][1]]+1
            Q.append([Q[i][0]-j,Q[i][1]])
        elif L[Q[i][0]-j][Q[i][1]]==L[Q[i][0]][Q[i][1]]+1:
            continue
        else:
            break
    for j in range(1,K+1):
        if L[Q[i][0]][Q[i][1]+j]==".":
            L[Q[i][0]][Q[i][1]+j]=L[Q[i][0]][Q[i][1]]+1
            Q.append([Q[i][0],Q[i][1]+j])
        elif L[Q[i][0]][Q[i][1]+j]==L[Q[i][0]][Q[i][1]]+1:
            continue
        else:
            break
    for j in range(1,K+1):
        if L[Q[i][0]][Q[i][1]-j]==".":
            L[Q[i][0]][Q[i][1]-j]=L[Q[i][0]][Q[i][1]]+1
            Q.append([Q[i][0],Q[i][1]-j])
        elif L[Q[i][0]][Q[i][1]-j]==L[Q[i][0]][Q[i][1]]+1:
            continue
        else:
            break
if L[x2][y2]==".":
    print(-1)
else:
    print(L[x2][y2])

Solution (Python):


H,W,K = map(int, input().split())
x1,y1,x2,y2 = map(int, input().split())

C = [input() for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
T[x1-1][y1-1] = 0

que = {(x1-1,y1-1):0}
step = 1

while len(que)>0:
  que_next = {}
  for q in que.keys():
    x,y = q[0],q[1]
    for i in range(1,K+1):
      if x-i<0:
        break
      if C[x-i][y]=='@' or T[x-i][y]==1:
        break
      if x-i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next[(x-i,y)] = 0
    for i in range(1,K+1):
      if x+i>H-1:
        break
      if C[x+i][y]=='@' or T[x+i][y]==1:
        break
      if x+i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next[(x+i,y)] = 0
    for i in range(1,K+1):
      if y-i<0:
        break
      if C[x][y-i]=='@' or T[x][y-i]==1:
        break
      if x==x2-1 and y-i==y2-1:
        print(step)
        exit()
      que_next[(x,y-i)] = 0
    for i in range(1,K+1):
      if y+i>W-1:
        break
      if C[x][y+i]=='@' or T[x][y+i]==1:
        break
      if x==x2-1 and y+i==y2-1:
        print(step)
        exit()
      que_next[(x,y+i)] = 0
  que = que_next
  for q in que.keys():
    T[q[0]][q[1]] = 1
  step += 1

print(-1)

Solution (Python):



H,W,K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
x1-=1
y1-=1
x2-=1
y2-=1



c = []
for i in range(H):
    c.append(input())

fresh = [True] * (H*W)
count = [-1] * (H*W)

queue = [x1*W+y1] 
count[x1*W+y1] = 0 
fresh[x1*W+y1] = False
n = [] 
for i in range(H):
    for j in range(W):
        if(c[i][j] == '@'):
            fresh[i*W+j] = False





step = 1
status = True
while status:
    if(len(queue) > 0):
        pivot = queue.pop()
        
        
        for g in range(1, K+1):
            if((pivot+g)%W != 0 and fresh[pivot+g]):
                n.append(pivot+g)
                count[pivot+g] = step
                
            else:
                break
        
        
        for g in range(1, K+1):
            if((pivot-g)%W != W-1 and fresh[pivot-g]):
                n.append(pivot-g)
                count[pivot-g] = step
                
            else:
                break   
        
        
        for g in range(1, K+1):
            if( (pivot+g*W)//W < H and fresh[pivot+g*W]):
                n.append(pivot+g*W)
                count[pivot+g*W] = step
                
            else:
                break    
        
        
        for g in range(1, K+1):
            if( (pivot-g*W)>= 0 and fresh[pivot-g*W] ):
                n.append(pivot-g*W)
                count[pivot-g*W] = step
                
            else:
                break
    elif(len(n)>0): 
        n = sorted(n)
        last = -1
        l = []
        for i in range(len(n)):
            if last != n[i]:
                l.append(n[i])
                last = n[i]
        for e in l:
            fresh[e] = False
        queue = l
        n = []
        
        step += 1
    else:
        status = False            


print(count[x2*W+y2])

Solution (Python):
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(int, input().split())
sx-=1
sy-=1
gx-=1
gy-=1

grid = ['' for _ in range(h)]

for i in range(h):
    grid[i] = input()
INF = 1001001001  
costgrid = [[INF]*w for _ in range(h)]

import heapq

q = []
q.append((0,sx,sy))

dx = (0,1,0,-1)
dy = (1,0,-1,0)
ans=INF
while q:
    cost,x,y = heapq.heappop(q)
    for i in range(4):
        for j in range(1,k+1):
            nx = x+dx[i]*j
            ny = y+dy[i]*j
            if(not 0<=nx<h):
                break
            if(not 0<=ny<w):
                break
            if(grid[nx][ny]=='@'):
                break
            if(costgrid[nx][ny]<=cost):
                break
            if(costgrid[nx][ny]>cost+1):
                costgrid[nx][ny]=cost+1
                heapq.heappush(q,(cost+1,nx,ny))
                if nx==gx and ny==gy:
                    ans=min(costgrid[nx][ny],ans)
                    q=[]

if ans!=INF:
    print(ans)
else:
    print(-1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline






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


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)
	


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

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

	while Q:
		
		now,d=Q.popleft()
		
		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+1:
				continue
			else:
				break


		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+1:
				continue
			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+1:
				continue
			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+1:
				continue
			else:
				break
		
	

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


if __name__ == "__main__":
	main()

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    H, W, K = map(int, input().split())
    sh, sw, gh, gw = map(int, input().split())
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    seen = [[1] * W for _ in range(H)]
    for h in range(H):
        line = input().rstrip('\n')
        for w in range(W):
            if line[w] == "@":
                seen[h][w] = 2

    
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    que = deque()
    que.append((sh, sw))
    seen_d = [[[0] * W for _ in range(H)] for _ in range(4)]
    seen[sh][sw] = 0
    while que:
        h, w = que.popleft()
        for id in range(4):
            dh, dw = d[id]
            h_new = h
            w_new = w
            for _ in range(K):
                flg = 1
                flggg = 0
                h_new += dh
                w_new += dw
                if 0 <= h_new < H and 0 <= w_new < W:
                    if seen[h_new][w_new] == 1:
                        seen[h_new][w_new] = seen[h][w] - 1
                        seen_d[id][h_new][w_new] = 1
                        que.append((h_new, w_new))
                        flg = 0
                    elif seen[h_new][w_new] <= 0:
                        if seen_d[id][h_new][w_new] == 0:
                            if seen[h_new][w_new] != seen[h][w]:
                                seen_d[id][h_new][w_new] = 1
                                flg = 0
                if flg:
                    break
    if seen[gh][gw] < 0:
        print(-seen[gh][gw])
    else:
        print(-1)
    


if __name__ == '__main__':
    main()

Solution (Python):
import heapq

H, W, K=map(int, input().split())
x1, y1, x2, y2=map(int, input().split())
c=['@'*(W+2)]+['@'+input()+'@' for _ in range(H)]+['@'*(W+2)]
l=[[-2]*(W+2) for _ in range(H+2)]
ll=[[-2]*(W+2) for _ in range(H+2)]
q=[[0, x1, y1]]

heapq.heapify(q)
ll[x1][y1]=0

while q:
  tmp=heapq.heappop(q)
  if ll[tmp[1]][tmp[2]]==tmp[0]:
    l[tmp[1]][tmp[2]]=tmp[0]
  else:
    continue
  
  j=1
  while j<=K and c[tmp[1]-j][tmp[2]]=='.':
    if l[tmp[1]-j][tmp[2]]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1]-j, tmp[2]])
      l[tmp[1]-j][tmp[2]]=-1
      ll[tmp[1]-j][tmp[2]]=tmp[0]+1
      j+=1
    elif ll[tmp[1]-j][tmp[2]]==tmp[0]+1:
      j+=1
    else:
      j=K+1
    
  j=1
  while j<=K and c[tmp[1]+j][tmp[2]]=='.':
    if l[tmp[1]+j][tmp[2]]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1]+j, tmp[2]])
      l[tmp[1]+j][tmp[2]]=-1
      ll[tmp[1]+j][tmp[2]]=tmp[0]+1
      j+=1
    elif ll[tmp[1]+j][tmp[2]]==tmp[0]+1:
      j+=1
    else:
      j=K+1
      
  j=1
  while j<=K and c[tmp[1]][tmp[2]-j]=='.':
    if l[tmp[1]][tmp[2]-j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]-j])
      l[tmp[1]][tmp[2]-j]=-1
      ll[tmp[1]][tmp[2]-j]=tmp[0]+1
      j+=1
    elif ll[tmp[1]][tmp[2]-j]==tmp[0]+1:
      j+=1
    else:
      j=K+1
      
  j=1
  while j<=K and c[tmp[1]][tmp[2]+j]=='.':
    if l[tmp[1]][tmp[2]+j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]+j])
      l[tmp[1]][tmp[2]+j]=-1
      ll[tmp[1]][tmp[2]+j]=tmp[0]+1
      j+=1
    elif ll[tmp[1]][tmp[2]+j]==tmp[0]+1:
      j+=1
    else:
      j=K+1

if l[x2][y2]<0:
  print(-1)
else:
  print(l[x2][y2])

Solution (Python):
import queue

INF = 10 ** 9

H, W, K = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())

sentinels = [-1] * (W+2)
MAP = [sentinels]
for _ in range(H):
    MAP.append( [-1] + list(map(lambda c: INF if c == '.' else -1, input())) + [-1] )
MAP.append(sentinels)

q = queue.Queue()
q.put((sx, sy))
MAP[sx][sy] = 0
while not q.empty():
    x, y = q.get()
    for d in range(1, K+1):
        if MAP[x+d][y] > MAP[x][y] + 1:
            MAP[x+d][y] = MAP[x][y] + 1
            q.put((x+d, y))
        elif MAP[x+d][y] < MAP[x][y] + 1:
            break
    for d in range(1, K+1):
        if MAP[x-d][y] > MAP[x][y] + 1:
            MAP[x-d][y] = MAP[x][y] + 1
            q.put((x-d, y))
        elif MAP[x-d][y] < MAP[x][y] + 1:
            break
    for d in range(1, K+1):
        if MAP[x][y+d] > MAP[x][y] + 1:
            MAP[x][y+d] = MAP[x][y] + 1
            q.put((x, y+d))
        elif MAP[x][y+d] < MAP[x][y] + 1:
            break
    for d in range(1, K+1):
        if MAP[x][y-d] > MAP[x][y] + 1:
            MAP[x][y-d] = MAP[x][y] + 1
            q.put((x, y-d))
        elif MAP[x][y-d] < MAP[x][y] + 1:
            break

if MAP[gx][gy] == INF:
    print(-1)
else:
    print(MAP[gx][gy])

Solution (Python):
import queue

H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

li = [list(input()) for _ in range(H)]
cnt = [[10**10 for _ in range(W)] for _ in range(H)]
cnt2 = [[10**10 for _ in range(W)] for _ in range(H)]



xy = [[1,0], [0,1], [-1,0], [0,-1]]

q = queue.Queue()
q.put([x1-1,y1-1,0])
cnt[x1-1][y1-1] = 0

while not(q.empty()):
    mm = q.get()
    x = mm[0]
    y = mm[1]
    cst = mm[2]

    for i in range(4):
        
        for j in range(1,K+1):
            nx = x+xy[i][0]*j
            ny = y+xy[i][1]*j
            
            
            if nx>=0 and nx<H and ny>=0 and ny<W and li[nx][ny]==".":
                if cnt[nx][ny]!=10**10 and cnt[nx][ny]<cst+1:
                    break
                elif cnt[nx][ny]!=10**10:
                    continue
                else:
                    cnt[nx][ny] = cst + 1
                    q.put([nx,ny,cst+1])
            else:
                break

if cnt[x2-1][y2-1]==10**10:
    print(-1)
else:
    print(cnt[x2-1][y2-1])

Solution (Python):



H,W,K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
x1-=1
y1-=1
x2-=1
y2-=1



c = []
for i in range(H):
    c.append(input())

fresh = [True] * (H*W)
count = [-1] * (H*W)

queue = [x1*W+y1] 
count[x1*W+y1] = 0 
fresh[x1*W+y1] = False
n = [] 
for i in range(H):
    for j in range(W):
        if(c[i][j] == '@'):
            fresh[i*W+j] = False





step = 1
status = True
while status:
    if(len(queue) > 0):
        pivot = queue.pop()
        
        
        for g in range(1, K+1):
            if((pivot+g)%W != 0 and fresh[pivot+g]):
                n.append(pivot+g)
                count[pivot+g] = step
                
            else:
                break
        
        
        for g in range(1, K+1):
            if((pivot-g)%W != W-1 and fresh[pivot-g]):
                n.append(pivot-g)
                count[pivot-g] = step
                
            else:
                break   
        
        
        for g in range(1, K+1):
            if( (pivot+g*W)//W < H and fresh[pivot+g*W]):
                n.append(pivot+g*W)
                count[pivot+g*W] = step
                
            else:
                break    
        
        
        for g in range(1, K+1):
            if( (pivot-g*W)>= 0 and fresh[pivot-g*W] ):
                n.append(pivot-g*W)
                count[pivot-g*W] = step
                
            else:
                break
    elif(len(n)>0): 
        n = sorted(n)
        last = -1
        l = []
        for i in range(len(n)):
            if last != n[i]:
                l.append(n[i])
                last = n[i]
        for e in l:
            fresh[e] = False
        queue = l
        n = []
        
        step += 1
    else:
        status = False            


print(count[x2*W+y2])

Solution (Python):
from collections import deque

H, W, K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = list(list(input())for _ in range(H))
cost = [[H*W+1]*W for _ in range(H)]
cost[x1-1][y1-1] = 0
queue = deque([[x1-1,y1-1]])
while queue:
    x,y = queue.popleft()
    for vecx,vecy in [[0,1],[1,0],[-1,0],[0,-1]]:
        for k in range(1,K+1):
            nx,ny = x+k*vecx, y+k*vecy
            if not(0<=nx<H) or not(0<=ny<W):
                break
            if c[nx][ny] == '@':
                break
            if cost[nx][ny] > cost[x][y]+1:
                cost[nx][ny] = cost[x][y]+1
                queue.append([nx,ny])
            elif cost[nx][ny] < cost[x][y]+1:
                break
if cost[x2-1][y2-1] == H*W+1:
    print(-1)
else:
    print(cost[x2-1][y2-1])

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    dist = list2d(H, W, INF)
    que = deque()
    for h, w in src:
        que.append((h, w))
        dist[h][w] = 0
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            for k in range(1, K+1):
                h2 = h + dh*k
                w2 = w + dw*k
                if grid[h2][w2] == '@':
                    break
                if dist[h2][w2] < dist[h][w] + 1:
                    break
                elif dist[h2][w2] != INF:
                    continue
                dist[h2][w2] = dist[h][w] + 1
                que.append((h2, w2))
    return dist

H, W, K = MAP()
x1, y1, x2, y2 = MAP()
grid = build_grid(H, W, '@', str, space=0, padding=1)

res = bfs(grid, [(x1, y1)])
ans = res[x2][y2]
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l 
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif visited[new_y][new_x] == -1:
                  visited[new_y][new_x] = visited[y][x] + 1
                  queue.append([new_y, new_x])
                elif visited[new_y][new_x] < visited[y][x] + 1:
                  p = 1
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

H, W, K = map(int, input().split())

x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)

print(visited[x2][y2])

Solution (Python):
from collections import deque
n, m, k = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
INF = float("inf")
d = [[INF] * m for _ in range(n)]
t = [[] for i in range(n)]
for i in range(n):
    a = list(input())
    t[i] = a
 

sx, sy, gx, gy = sx - 1, sy - 1, gx - 1, gy - 1
 
 
def bfs():
    que = deque()
    que.append((sx, sy))
    d[sx][sy] = 0
 
    while len(que):
        x, y = que.popleft()
        if x == gx and y == gy:
            break
        for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            for i in range(1, k + 1):
                nx, ny = x + i * dx, y + i * dy
                if not 0 <= nx < n or not 0 <= ny < m or t[nx][ny] != "." or d[nx][ny] <= d[x][y]:
                    break
                else:
                    if d[nx][ny] > d[x][y] + 1:
                        d[nx][ny] = d[x][y] + 1
                        que.append((nx, ny))
 
    return d[gx][gy]
 
 
ans = bfs()
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
from collections import deque


input = iter(sys.stdin.readlines()).__next__

R, C, K = [int(x) for x in input().split()]
X1, Y1, X2, Y2 = [int(x) - 1 for x in input().split()]  

grid = [input().rstrip() for r in range(R)]

source = (X1, Y1)
q = deque([source])
dist = {source: 0}


def getNbr(node, currDist):
    r, c = node
    ret = []
    for dr, dc in [(0, 0), (-1, 0), (0, -1), (0, 1), (1, 0)]:
        for k in range(1, K + 1):
            nr = r + dr * k
            nc = c + dc * k
            if not (0 <= nr < R and 0 <= nc < C):
                break
            if grid[nr][nc] == "@" or ((nr, nc) in dist and dist[(nr, nc)] <= d):
                break
            ret.append((nr, nc))
    return ret


while q:
    node = q.popleft()
    d = dist[node]
    for nbr in getNbr(node, d):
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = d + 1


if False:
    for row in grid:
        print(row)
    print()
    for r in range(R):
        for c in range(C):
            print(dist.get((r, c), "?"), end=" ")
        print()


if (X2, Y2) in dist:
    print(dist[(X2, Y2)])
else:
    print(-1)

Solution (Python):
from queue import Queue
INF = 10 ** 6 + 1
H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
D = [[INF for i in range(W)] for j in range(H)]
D[x1-1][y1-1] = 0
tx = [1,0,-1,0]
ty = [0,1,0,-1]

q = Queue()
q.put([x1-1,y1-1,0])

while not q.empty():
    x, y, k = q.get()
    if x == x2 - 1 and y == y2 - 1:
        break
    for i in range(4):
        nx = x
        ny = y
        for _ in range(K):
            nx += tx[i]
            ny += ty[i]
            if (not (0 <= nx <= H-1 and 0 <= ny <= W-1)) or MAP[nx][ny] == '@' or D[nx][ny] < k + 1:
                break
            if D[nx][ny] == k + 1:
                continue
            D[nx][ny] = k + 1
            q.put([nx, ny, k+1])

if D[x2-1][y2-1] == INF:
    print(-1)
else:
    print(D[x2-1][y2-1])

Solution (Python):
import sys
import numpy as np
from numba import njit
from heapq import heappop, heappush

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(b1[:],i8,i8,i8,i8,i8)', cache=True)
def main(C, H, W, S, T, K):
    INF = 10**18
    N = H * W
    q = [5 * S]
    dist = np.full((5 * N), INF, np.int64)
    dist[5 * S] = 0
    move = [0, 1, -1, W, -W]
    B = 5 * N + 10
    while q:
        x = heappop(q)
        dist_x, x = divmod(x, B)
        if dist_x > dist[x]:
            continue
        v, d = divmod(x, 5)
        if d == 0:
            
            for i in range(1, 5):
                w = v + move[i]
                y = 5 * w + i
                dist_y = dist_x + 1
                if C[w] and dist_y < dist[y]:
                    dist[y] = dist_y
                    heappush(q, B * dist_y + y)
        else:
            
            if dist_x % K != 0:
                w = v + move[d]
                y = 5 * w + d
                dist_y = dist_x + 1
                if C[w] and dist_y < dist[y]:
                    dist[y] = dist_y
                    heappush(q, B * dist_y + y)
            
            y = 5 * v
            dist_y = dist_x + (-dist_x) % K
            if dist_y < dist[y]:
                dist[y] = dist_y
                heappush(q, B * dist_y + y)
    x = dist[5 * T]
    if x == INF:
        return -1
    return dist[5 * T] // K

H, W, K = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())

C = np.zeros((H + 2, W + 2), np.bool_)
C[1:-1, 1:-1] = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'.'
C = C.ravel()
H += 2
W += 2

S = W * x1 + y1
T = W * x2 + y2

print(main(C, H, W, S, T, K))

Solution (Python):


H,W,K = map(int, input().split())
x1,y1,x2,y2 = map(int, input().split())

C = [input() for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
T[x1-1][y1-1] = 0

que = {(x1-1,y1-1):0}
step = 1

while len(que)>0:
  que_next = {}
  for q in que.keys():
    x,y = q[0],q[1]
    for i in range(1,K+1):
      if x-i<0:
        break
      if C[x-i][y]=='@' or T[x-i][y]==1:
        break
      if x-i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next[(x-i,y)] = 0
    for i in range(1,K+1):
      if x+i>H-1:
        break
      if C[x+i][y]=='@' or T[x+i][y]==1:
        break
      if x+i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next[(x+i,y)] = 0
    for i in range(1,K+1):
      if y-i<0:
        break
      if C[x][y-i]=='@' or T[x][y-i]==1:
        break
      if x==x2-1 and y-i==y2-1:
        print(step)
        exit()
      que_next[(x,y-i)] = 0
    for i in range(1,K+1):
      if y+i>W-1:
        break
      if C[x][y+i]=='@' or T[x][y+i]==1:
        break
      if x==x2-1 and y+i==y2-1:
        print(step)
        exit()
      que_next[(x,y+i)] = 0
  que = que_next
  for q in que.keys():
    T[q[0]][q[1]] = 1
  step += 1

print(-1)