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
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

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

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Solution (Python):



H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}

from collections import deque

def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0

    while len(next_q)!=0:
        
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque




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


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



grid = [input() for _ in range(H)]


INF = float('inf')
path = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]


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


q = deque()
for d in range(4):
	path[x1][y1][d] = (1, 0)
	
	q.append((x1, y1, d, 1, 0))
	

while q:
	x, y, d, c, k = q.popleft()
	
	
	
	
	
	
	
	for nd in range(4):
		if nd == d:
			dx, dy = D[nd]
			nk = 1 if k == K else k + 1
			nc = c + 1 if k == K else c
		else:
			dx, dy = 0, 0
			nk = 0
			nc = c + 1
		nx = x + dx; ny = y + dy
		if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (nc, nk):
			path[nx][ny][nd] = (nc), (nk)
			if nc == c:
				q.appendleft((nx, ny, nd, nc, nk))
			else:
				q.append((nx, ny, nd, nc, nk))
				

ans = INF
for d in range(4):
	ans = min(ans, path[x2][y2][d][0])
ans = -1 if ans == INF else ans

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
inf = 10**18
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

checked = [[-1]*W for _ in range(H)]
checked[y1-1][x1-1] = 0

queue = deque([(y1-1, x1-1)])
def bfs(queue):
    while len(queue):
        y, x = queue.popleft()
        if y==y2-1 and x==x2-1:
            return checked[y][x]
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    break
                if query[ny][nx]=='@':
                    break
                if checked[ny][nx]<0:
                    checked[ny][nx] = checked[y][x]+1
                    queue.append((ny, nx))
                elif checked[ny][nx]<=checked[y][x]:
                    break
    return -1

print(bfs(queue))

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
inf = 10**18
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

checked = [[-1]*W for _ in range(H)]
checked[y1-1][x1-1] = 0

queue = deque([(y1-1, x1-1)])
def bfs(queue):
    while queue:
        y, x = queue.popleft()
        if y==y2-1 and x==x2-1:
            return checked[y][x]
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    continue
                if query[ny][nx]=='@':
                    break
                if checked[ny][nx]<0:
                    checked[ny][nx] = checked[y][x]+1
                    queue.append((ny, nx))
                elif checked[ny][nx]<=checked[y][x]:
                    break
    return -1

print(bfs(queue))

Solution (Python):

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

lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])
 
field.append(lastraw)
 

 
goal_point=(y2,x2)
 
[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]
 
field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0
 
while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.':
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            
          elif field[tx][ty] ==moves:
            k=0
          else:
            break
      elif field[tx][ty] ==moves:
        
        
        
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            
          elif field[tx][ty] ==moves:
            k=0
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break

print(moves)

Solution (Python):

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

lastraw=["@"]*(W+2)
field=[["@"]*(W+2)]
for i in range(H):
  field.append(["@"]+list(input())+["@"])

field.append(lastraw)



goal_point=(y2,x2)

[sy,sx]=[y1,x1]
[gy,gx]=[y2,x2]

field[x1][y1]=0
queue=[[sy,sx]]
tests = ((-1,0),(0, 1),(1, 0),(0, -1))
moves=0

while True:
  if len(queue)==0:
    moves=-1
    break
  queue_next = []
  moves += 1
  
  for y, x in queue:
    for ny, nx in tests:
      ty, tx = y + ny, x + nx
      if field[tx][ty] == '.':
        field[tx][ty] = moves
        queue_next.append((ty, tx))
        
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            
          elif field[tx][ty] ==moves:
            pass
          else:
            break
      elif field[tx][ty] ==moves:
        
        
        
        for i in range(K-1):
          ty, tx = ty + ny, tx + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
            
          elif field[tx][ty] ==moves:
            pass
          else:
            break
  queue = queue_next
  if goal_point in queue:
    break

print(moves)

Solution (Python):
from heapq import heappop, heappush


def solve(field, s, t, k):
    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0
    MOVE = [(-w2, 0), (-1, 1), (1, 1), (w2, 0)]

    q = [(0, s, 0)]
    while q:
        cost, v, direction = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = -1
        for di, ax in MOVE:
            u = v + di
            if field[u] == '@':
                continue
            nc = cost + 1 if di == direction else ceiling
            if nc == -1:
                nc = ceiling = ((cost - 1) // k + 1) * k + 1
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, u, di))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Solution (Python):
from heapq import heappop, heappush


def solve(field, s, t, k):
    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0
    MOVE = [(-w2, 0), (-1, 1), (1, 1), (w2, 0)]

    q = [(0, s, 0)]
    while q:
        cost, v, direction = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = ((cost - 1) // k + 1) * k + 1
        for di, ax in MOVE:
            u = v + di
            if field[u] == '@':
                continue
            nc = cost + 1 if di == direction else ceiling
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, u, di))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Solution (Python):
from heapq import heappop, heappush


def solve(field, s, t, k):
    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0
    MOVE = [(-w2, 0), (-1, 1), (1, 1), (w2, 0)]

    q = [(0, 0, s, 0)]
    while q:
        cost, straight, v, direction = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = ((cost - 1) // k + 1) * k + 1
        for di, ax in MOVE:
            u = v + di
            if field[u] == '@':
                continue
            if di == direction:
                nc = cost + 1
                ns = straight + 1
                if ns > k:
                    ns -= k
            else:
                nc = ceiling
                ns = 1
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, ns, u, di))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Solution (Python):
from heapq import heappop, heappush


def solve(field, s, t, k):
    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0
    MOVE = [(-w2, 0), (-1, 1), (1, 1), (w2, 0)]

    q = [(0, 0, s, 0)]
    while q:
        cost, straight, v, direction = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = ((cost - 1) // k + 1) * k + 1
        for di, ax in MOVE:
            u = v + di
            if field[u] == '@':
                continue
            if di == direction:
                nc = cost + 1
                ns = straight + 1
                if ns > k:
                    ns -= k
            else:
                nc = ceiling
                ns = 1
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, ns, u, di))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Solution (Python):
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))
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 board[y][x+i]=='.' and c<cost[y][x+i]:
      if cost[y][x+i]>c+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 board[y][x-i]=='.' and c<cost[y][x-i]:
      if cost[y][x-i]>c+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 board[y+i][x]=='.' and c<cost[y+i][x]:
      if cost[y+i][x]>c+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 board[y-i][x]=='.' and c<cost[y-i][x]:
      if cost[y-i][x]>c+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])

Solution (Python):
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))
  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 board[y][x+i]=='.' and c<cost[y][x+i]:
        if cost[y][x+i]>c+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 board[y][x-i]=='.' and c<cost[y][x-i]:
        if cost[y][x-i]>c+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 board[y+i][x]=='.' and c<cost[y+i][x]:
        if cost[y+i][x]>c+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 board[y-i][x]=='.' and c<cost[y-i][x]:
        if cost[y-i][x]>c+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()

Solution (Python):
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])

Solution (Python):
from heapq import heappop, heappush


def solve(field, s, t, k):
    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0
    MOVE = [(-w2, 0), (-1, 1), (1, 1), (w2, 0)]

    q = [(0, s, 0, k)]
    while q:
        cost, v, direction, remaining = heappop(q)
        if v == t:
            return (cost - 1) // k + 1

        ceiling = ((cost - 1) // k + 1) * k + 1
        for di, ax in MOVE:
            u = v + di
            if field[u] == '@':
                continue
            if di == direction and remaining > 0:
                nc = cost + 1
                nr = remaining - 1
            else:
                nc = ceiling
                nr = k - 1
            if ans[u][ax] <= nc:
                continue
            ans[u][ax] = nc
            heappush(q, (nc, u, di, nr))

    return -1


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
h2 = h + 2
w2 = w + 2

field_tmp = [input() for _ in range(h)]
field = ['@' * w2]
for row in field_tmp:
    field.append('@')
    field.append(row)
    field.append('@')
field.append('@' * w2)
field = ''.join(field)
s = x1 * w2 + y1
t = x2 * w2 + y2
print(solve(field, s, t, k))

Solution (Python):
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]
nx=set([])

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,k):
    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            if (x,y+i) not in nx:
                nx.add((x,y+i))
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            if (x,y-i) not in nx:
                nx.add((x,y-i))
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            if (x+i,y) not in nx:
                nx.add((x+i,y))
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            if (x-i,y) not in nx:
                nx.add((x-i,y))
            i+=1

    return 0

C[x1-1][y1-1]=0
keiro(x1-1,y1-1,K)
taisho=nx.copy()
result=1
for j in nx:
    C[j[0]][j[1]]=result

while C[x2-1][y2-1]=='.':
    nx=set([])
    if len(taisho)==0 or result>10**6:
        result=-1
        break
    for l in taisho:
        keiro(l[0],l[1],K)
    result+=1
    for j in nx:
        C[j[0]][j[1]]=result
    taisho=nx.copy()

print(result)

Solution (Python):
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
C=[]
nx=set([])

for _ in range(H):
    C.append(list(input()))

def keiro(x,y,k):
    i=1
    while True:
        if y+i>W-1 or C[x][y+i]!='.' or i>k:
            break
        else:
            if (x,y+i) not in nx:
                nx.add((x,y+i))
            i+=1
    
    i=1
    while True:
        if y-i<0 or C[x][y-i]!='.' or i>k:
            break
        else:
            if (x,y-i) not in nx:
                nx.add((x,y-i))
            i+=1
    
    i=1
    while True:
        if x+i>H-1 or C[x+i][y]!='.' or i>k:
            break
        else:
            if (x+i,y) not in nx:
                nx.add((x+i,y))
            i+=1
    
    i=1
    while True:
        if x-i<0 or C[x-i][y]!='.' or i>k:
            break
        else:
            if (x-i,y) not in nx:
                nx.add((x-i,y))
            i+=1

    return 0

C[x1-1][y1-1]=0
keiro(x1-1,y1-1,K)
taisho=nx.copy()
result=1
for j in nx:
    C[j[0]][j[1]]=result

while C[x2-1][y2-1]=='.':
    nx=set([])
    if len(taisho)==0 or result>10**6:
        result=-1
        break
    for l in taisho:
        keiro(l[0],l[1],K)
    result+=1
    for j in nx:
        C[j[0]][j[1]]=result
    taisho=nx.copy()

print(result)

Solution (Python):
from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = (i-1 for i in map(int,input().split()))
grid = []
inf = 1<<30
reach = [[inf for _ in range(W)] for _ in range(H)]
reach[sx][sy]=0
dif = [(1,0),(-1,0),(0,1),(0,-1)] 

for i in range(H):
    grid.append(list(input()))

que = deque([(sx,sy)])
while que:
    x,y = que.popleft()
    for i in range(4): 
        for k in range(1,K+1):
            nx = x+k*dif[i][0]
            ny = y+k*dif[i][1]
            if nx<0 or nx>=H or ny<0 or ny>= W or grid[nx][ny] == "@":
                break
            if reach[x][y]+1 > reach[nx][ny]:
                break
            if reach[x][y]+1 < reach[nx][ny]:
                reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
                que.append((nx,ny))
            if nx == gx and ny == gy:
                print(reach[nx][ny])
                exit()
print(-1)

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
SX, SY, GX, GY = lr()
SX -= 1; SY -= 1; GX -= 1; GY -= 1
pond = [sr() for _ in range(H)]
INF = 10 ** 10

def to_ID(x, y, con):
    return (x*W + y) * 4 + con

def mod_ceil_K(x):
    return (x+K-1) // K * K

def push(d, id):
    if dist[id] < d:
        return
    dist[id] = d
    heappush(que, (d, id))    

dist = [INF] * (H*W*4)
start = to_ID(SX, SY, 0)
dist[start] = 0
que = [(0, start)]
UDLR = [(0, -1), (1, 0), (0, 1), (-1, 0)]
goal = to_ID(GX, GY, 0)
while que:
    d, id = heappop(que)
    if id == goal:
        answer = mod_ceil_K(d) // K
        print(answer); exit()
    if dist[id] < d:
        continue
    x = id // 4 // W
    y = id // 4 % W
    con = id % 4
    for i in range(4):
        next_id = to_ID(x, y, i)
        if dist[next_id] > mod_ceil_K(d):
            push(mod_ceil_K(d), next_id)
    dx = UDLR[con][0]; dy = UDLR[con][1]
    nx = x + dx; ny = y + dy
    if not (0 <= nx < H and 0 <= ny < W) or pond[nx][ny] == '@':
        continue
    next_id = to_ID(nx, ny, con)
    if dist[next_id] > d + 1:
        dist[next_id] = d + 1
        push(d+1, next_id)
    
print(-1)

Solution (Python):

import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
SX, SY, GX, GY = lr()
SX -= 1; SY -= 1; GX -= 1; GY -= 1
pond = [sr() for _ in range(H)]
INF = 10 ** 10
dist = [[INF] * W for _ in range(H)]
dist[SX][SY] = 0
que = deque([(0, SX, SY)])
UDLR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while que:
    d, px, py = que.popleft()
    if px == GX and py == GY:
        print(d); exit()
    if dist[px][py] < d:
        continue
    nd = d + 1
    for dx, dy in UDLR:
        nx = px + dx; ny = py + dy
        for _ in range(K):
            if not (0 <= nx < H) or not (0 <= ny < W) \
                    or dist[nx][ny] < nd or pond[nx][ny] == '@':
                break
            if dist[nx][ny] > nd:
                que.append((nd, nx, ny))
                dist[nx][ny] = nd
            nx += dx; ny += dy

print(-1)

Solution (Python):
import sys
import math
from collections import defaultdict, deque
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

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 = rm()
x1, y1, x2, y2 = rm()
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

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

INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[INF]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                break
                
            if maze[nx][ny]=="@":
                break
                
            if cost[nx][ny]<=cost[x][y]:
                break
                
            if cost[nx][ny]==INF:
                cost[nx][ny]=cost[x][y]+1
                todo.append((nx,ny))
                



ans=cost[x2][y2]
if ans==INF:ans=-1
print(ans)

Solution (Python):



from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint
INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[INF]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                break
                
            if maze[nx][ny]=="@":
                break
                
            if cost[nx][ny]<=cost[x][y]:
                break
                
            if cost[nx][ny]==INF:
                cost[nx][ny]=cost[x][y]+1
                todo.append((nx,ny))



ans=cost[x2][y2]
if ans==INF:ans=-1
print(ans)

Solution (Python):



from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint


h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                break
                
            if maze[nx][ny]=="@":
                break
                
            if cost[nx][ny]!=-1 and cost[nx][ny]<=cost[x][y]:
                
                break
            if cost[nx][ny]==-1:
                cost[nx][ny]=cost[x][y]+1
                todo.append((nx,ny))



ans=cost[x2][y2]
print(ans)

Solution (Python):



from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint


h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                continue
            if maze[nx][ny]=="@":
                break
            if cost[nx][ny]!=-1 and cost[nx][ny]<=cost[x][y]:
                break
            if cost[nx][ny]!=-1:
                continue
            cost[nx][ny]=cost[x][y]+1
            todo.append((nx,ny))



ans=cost[x2][y2]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
Dy = (-1,0,1,0)
Dx = (0,1,0,-1)

from collections import deque,defaultdict,Counter
def main():
    H,W,K = map(int,input().split())
    sy,sx,gy,gx = map(int,input().split())
    sy -= 1; sx -= 1; gy -= 1;gx -= 1
    pond = [list(input()) for _ in range(H)]
    
    q = deque([(sy,sx)])
    dist = [[-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    while q:
        ny,nx = q.popleft()
        for dy,dx in zip(Dy,Dx):
            y,x = ny,nx
            for _ in range(K):
                y += dy
                x += dx
                if y < 0 or y >= H:
                    break
                if x < 0 or x >= W:
                    break
                if pond[y][x] == '@':
                    break
                if dist[y][x] >= 0 and dist[y][x] <= dist[ny][nx]:
                    break
                if dist[y][x] < 0:
                    dist[y][x] = dist[ny][nx] + 1
                    q.append((y,x))
                if (y,x) == (gy,gx):
                    break
    print(dist[gy][gx] if dist[gy][gx] >= 0 else -1) 
if __name__ == '__main__':
    main()