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: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W,K = IL()
y1,x1,y2,x2 = IL()
data = SLs(H)
for i in range(H):
  data[i] = list(data[i])
d = [[INF for i in range(W)] for j in range(H)]
flag = [[0 for i in range(W)] for j in range(H)]

dd = [i+1 for i in range(K)]

d[y1-1][x1-1] = 0
q = deque([(y1-1,x1-1)])
now = 0
temp = []
while q:
  y,x = q.popleft()
  if now < d[y][x]:
    for w,z in temp:
      data[w][z] = "@"
    now = d[y][x]
    temp = []
  for i in range(K):
    ny,nx = y+dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
          temp.append((ny,nx))
      else:
        break
  for i in range(K):
    ny,nx = y-dd[i],x
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
          temp.append((ny,nx))
      else:
        break
  for i in range(K):
    ny,nx = y,x+dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
          temp.append((ny,nx))
      else:
        break
  for i in range(K):
    ny,nx = y,x-dd[i]
    if 0<=ny<H and 0<=nx<W:
      if data[ny][nx] == ".":
        if d[ny][nx] > d[y][x]+1:
          d[ny][nx] = d[y][x]+1
          q.append((ny,nx))
          temp.append((ny,nx))
      else:
        break
        
if d[y2-1][x2-1]!=INF:
  print(d[y2-1][x2-1])
else:
  print(-1)

Submission status: Accepted

Solution code:
import math
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

# a = list(map(int, input().split()))

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


#11-


h,w,k = list(map(int, input().split()))

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

mapa = []
visited = [[[0,0] for j in range(w)] for i in range(h)]
visited[y1][x1] = [1,1]

for i in range(h):
    mapa.append( input() )

#
queue = [[y1,x1,0]]
done = 0

while(True):
    if(len(queue)==done):
        break
    now = queue[done]
    # move-y
    for i in range(1,min(k+1,h-now[0])):
        seey,seex = now[0]+i,now[1]
        if(seey == y2 and seex == x2):
            print(now[2]+1)
            exit()
        if(mapa[seey][seex]=='@'):
            break
        elif(visited[seey][seex][0]==0 and mapa[seey][seex]=='.'):
            queue.append([seey,seex,now[2]+1])
            visited[seey][seex][0]=now[2]+1
            if(visited[seey][seex][1]<=now[2] and visited[seey][seex][1]!=0):
                break
        else:
            break
    for i in range(1,min(k+1,now[0]+1)):
        seey,seex = now[0]-i,now[1]
        if(seey == y2 and seex == x2):
            print(now[2]+1)
            exit()
        if(mapa[seey][seex]=='@'):
            break
        elif(visited[seey][seex][0]==0 and mapa[seey][seex]=='.'):
            queue.append([seey,seex,now[2]+1])
            visited[seey][seex][0]=now[2]+1
            if(visited[seey][seex][1]<=now[2] and visited[seey][seex][1]!=0):
                break
        else:
            break
    # move-x
    for i in range(1,min(k+1,w-now[1])):
        seey,seex = now[0],now[1]+i
        if(seey == y2 and seex == x2):
            print(now[2]+1)
            exit()
        if(mapa[seey][seex]=='@'):
            break
        elif(visited[seey][seex][1]==0 and mapa[seey][seex]=='.'):
            queue.append([seey,seex,now[2]+1])
            visited[seey][seex][1]=now[2]+1
            if(visited[seey][seex][0]<=now[2] and visited[seey][seex][0]!=0):
                break
        else:
            break
    for i in range(1,min(k+1,now[1]+1)):
        seey,seex = now[0],now[1]-i
        if(seey == y2 and seex == x2):
            print(now[2]+1)
            exit()
        if(mapa[seey][seex]=='@'):
            break
        elif(visited[seey][seex][1]==0 and mapa[seey][seex]=='.'):
            queue.append([seey,seex,now[2]+1])
            visited[seey][seex][1]=now[2]+1
            if(visited[seey][seex][0]<=now[2] and visited[seey][seex][0]!=0):
                break
        else:
            break
    done+=1

print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    h, w, k = map(int, input().strip().split())
    x1, y1, x2, y2 = map(int, input().strip().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    m = []
    costs1 = [[None for j in range(w)] for i in range(h)]
    costs2 = [[None for j in range(w)] for i in range(h)]
    for _ in range(h):
        m.append(list(input().strip()))
    q1 = deque()
    q1.append((x1, y1, 0))
    costs1[x1][y1] = 0
    q2 = deque()
    q2.append((x2, y2, 0))
    costs2[x2][y2] = 0
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while q1 and q2:
        (x, y, cost) = q1.popleft()
        if not costs2[x][y] is None:
            print(cost + costs2[x][y])
            return
        for (add_x, add_y) in directions:
            for dist in range(1, k + 1):
                new_x = x + add_x * dist
                new_y = y + add_y * dist
                if new_x >= h or new_x < 0 or new_y >= w or new_y < 0 or m[new_x][new_y] == '@' or ((not costs1[new_x][new_y] is None) and costs1[new_x][new_y] < cost + 1):
                    break
                if costs1[new_x][new_y] is None:
                    costs1[new_x][new_y] = cost + 1
                    q1.append((new_x, new_y, cost + 1))
        (x, y, cost) = q2.popleft()
        if not costs1[x][y] is None:
            print(cost + costs1[x][y])
            return
        for (add_x, add_y) in directions:
            for dist in range(1, k + 1):
                new_x = x + add_x * dist
                new_y = y + add_y * dist
                if new_x >= h or new_x < 0 or new_y >= w or new_y < 0 or m[new_x][new_y] == '@' or ((not costs2[new_x][new_y] is None) and costs2[new_x][new_y] < cost + 1):
                    break
                if costs2[new_x][new_y] is None:
                    costs2[new_x][new_y] = cost + 1
                    q2.append((new_x, new_y, cost + 1))
    print("-1")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
X = [1] * (W + 2)
for _ in range(H):
    X += [1] + [1 if a == "@" else 0 for a in input()] + [1]
X += [1] * (W + 2)
H, W = H+2, W+2
s, t = x1 * W + y1, x2 * W + y2

def BFS(i0=0):
    Q = deque([(i0, 3)])
    D = [-1] * (H * W)
    D[i0] = 0
    while Q:
        x, t = Q.popleft()
        if t & 1:
            for d in (1, -1):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if 0 <= D[y] <= D[x]: break
                    D[y] = D[x] + 1
                    Q.append((y, 2))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
        if t & 2:
            for d in (W, -W):
                for y in range(x + d, x + d * K, d):
                    if X[y]: break
                    if 0 <= D[y] <= D[x]: break
                    D[y] = D[x] + 1
                    Q.append((y, 1))
                else:
                    y = x + d * K
                    if X[y] == 0:
                        if D[y] == -1:
                            D[y] = D[x] + 1
                            Q.append((y, 3))
                        
    return D

print(BFS(s)[t])

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
y1,x1,y2,x2 = map(int,input().split())
grid = []
grid.append(['@']*(w+2))
for i in range(h):
    grid.append(['@']+list(input())+['@'])
grid.append(['@']*(w+2))

q = set()
next_q = set()
next_q.add((y1,x1))
ans = 0
while True:
    if not next_q:
        print(-1)
        exit()
    for y,x in next_q:
        grid[y][x] = '@'
    q = next_q
    next_q = set()
    while q:
        y,x = q.pop()
        if (y,x) == (y2,x2):
            print(ans)
            exit()
        for i in range(1,k+1):
            if grid[y+i][x] == '@':
                break
            next_q.add((y+i,x))
        for i in range(1,k+1):
            if grid[y-i][x] == '@':
                break
            next_q.add((y-i,x))
        for i in range(1,k+1):
            if grid[y][x+i] == '@':
                break
            next_q.add((y,x+i))
        for i in range(1,k+1):
            if grid[y][x-i] == '@':
                break
            next_q.add((y,x-i))
    ans += 1

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    S = [[False]*W for _ in range(H)]
    for i in range(H):
        s = input()
        for j in range(W):
            if s[j] == ".":
                S[i][j] = True

    cost = [[-1]*W for _ in range(H)]

    # 深さ優先探索
    def bfs(x, y, gx, gy):
        stack = deque([[x, y]])
        cost[x][y] = 0
        while stack:
            x, y = stack[0]
            if x == gx and y == gy:
                return
            point = cost[x][y] + 1
            # up
            for i in range(1, K+1):
                if x-i >= 0:
                    if not S[x-i][y]:
                        break
                    elif cost[x-i][y] == -1:
                        cost[x-i][y] = point
                        stack.append([x-i, y])
                    elif cost[x-i][y] < point:
                        break
                else:
                    break
            # down
            for i in range(1, K+1):
                if x+i < H:
                    if not S[x+i][y]:
                        break
                    elif cost[x+i][y] == -1:
                        cost[x+i][y] = point
                        stack.append([x+i, y])
                    elif cost[x+i][y] < point:
                        break
                else:
                    break
            # left
            for i in range(1, K+1):
                if y-i >= 0:
                    if not S[x][y-i]:
                        break
                    elif cost[x][y-i] == -1:
                        cost[x][y-i] = point
                        stack.append([x, y-i])
                    elif cost[x][y-i] < point:
                        break
                else:
                    break
            # right
            for i in range(1, K+1):
                if y+i < W:
                    if not S[x][y+i]:
                        break
                    elif cost[x][y+i] == -1:
                        cost[x][y+i] = point
                        stack.append([x, y+i])
                    elif cost[x][y+i] < point:
                        break
                else:
                    break

            stack.popleft()        

    bfs(sx-1, sy-1, gx-1, gy-1)
    print(cost[gx-1][gy-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#

import sys
from collections import deque
input=sys.stdin.readline

def main():
    H,W,K=map(int,input().split())
    x1,y1,x2,y2=map(int,input().split())
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    mas=[list(input()) for i in range(H)]

    dist=[[-1]*W for i in range(H)]
    dist[x1][y1]=0
    
    qu=deque([(x1,y1)])
    qup=qu.popleft
    qua=qu.append
    
    d=((-1,0),(1,0),(0,-1),(0,1))
    
    while(len(qu)>0):
        v=qup()
        for di in d:
            for i in range(1,K+1):
                nvh=v[0]+i*di[0]
                nvw=v[1]+i*di[1]
                if nvh<0 or nvh>=H or nvw<0 or nvw>=W or mas[nvh][nvw]=="@":
                    break
                if dist[nvh][nvw]!=-1 and dist[nvh][nvw]<=dist[v[0]][v[1]]:
                    break
                if dist[nvh][nvw]==-1:
                    dist[nvh][nvw]=dist[v[0]][v[1]]+1
                    qua((nvh,nvw))
    print(dist[x2][y2])
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def reachable(field, h2, w2, k):
    # 各マスから上下左右にどこまで行けるか
    hw = h2 * w2
    up, dw, lf, rg = [-1] * hw, [-1] * hw, [-1] * hw, [-1] * hw
    lf_tmp = -1
    for i in range(w2, hw - w2):
        if field[i] == '.':
            if lf_tmp == -1:
                lf_tmp = i
            lf[i] = max(lf_tmp, i - k)
        else:
            lf_tmp = -1
    rg_tmp = -1
    for i in range(hw - w2, w2 - 1, -1):
        if field[i] == '.':
            if rg_tmp == -1:
                rg_tmp = i
            rg[i] = min(rg_tmp, i + k)
        else:
            rg_tmp = -1
    wk = w2 * k
    for j in range(1, w2):
        up_tmp = -1
        for i in range(j, hw, w2):
            if field[i] == '.':
                if up_tmp == -1:
                    up_tmp = i
                up[i] = max(up_tmp, i - wk)
            else:
                up_tmp = -1
        dw_tmp = 0
        for i in range(hw - w2 + j, w2 - 1, -w2):
            if field[i] == '.':
                if dw_tmp == -1:
                    dw_tmp = i
                dw[i] = min(dw_tmp, i + wk)
            else:
                dw_tmp = -1
    return up, dw, lf, rg


def solve(h2, w2, k, field, x1, y1, x2, y2):
    s = x1 * w2 + y1
    t = x2 * w2 + y2
    up, dw, lf, rg = reachable(field, h2, w2, k)
    # print(up)
    # print(dw)
    # print(lf)
    # print(rg)

    INF = 10 ** 18
    ans = [[INF, INF] for _ in field]
    ans[s][0] = ans[s][1] = 0

    q = deque([(0, s)])
    while q:
        cost, v = q.popleft()
        if v == t:
            return cost
        nc = cost + 1

        for u in range(up[v], v, w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            q.append((nc, u))

        for u in range(dw[v], v, -w2):
            if ans[u][0] <= nc:
                break
            ans[u][0] = nc
            q.append((nc, u))

        for u in range(lf[v], v, 1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            q.append((nc, u))

        for u in range(rg[v], v, -1):
            if ans[u][1] <= nc:
                break
            ans[u][1] = nc
            q.append((nc, u))

        # print(cost, divmod(v, w2), q)
        # print([divmod(lim[v], w2) for lim in (up, dw, lf, rg)])

    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('@' + row + '@')
field.append('@' * w2)
field = ''.join(field)
print(solve(h2, w2, k, field, x1, y1, x2, y2))

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
c = ["@" * (W+2)] + ["@" + input() + "@" for _ in range(H)] + ["@" * (W+2)]
INF = 10**6+5
dist = [[INF for _ in range(W+2)] for _ in range(H+2)]
dist[sh][sw] = 0
q = deque()
q.append(sh*(W+2)+sw)
DI = [1, 0, -1, 0]
DJ = [0, 1, 0, -1]
while q:
	l = q.popleft()
	i, j = l//(W+2), l%(W+2)
	for di, dj in zip(DI, DJ):
		for k in range(1, K+1):
			ii, jj = i+di*k, j+dj*k
			if c[ii][jj] == "@":
				break
			if dist[ii][jj] <= dist[i][j]:
				break
			if dist[ii][jj] > dist[i][j] + 1:
				dist[ii][jj] = dist[i][j] + 1
				if ii == gh and jj == gw:
					print(dist[ii][jj])
					sys.exit()
				q.append(ii*(W+2) + jj)
print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#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()

Submission status: Accepted

Solution code:
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

#46 . 64 @
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#print(L)
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])
#print(L)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)