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:
import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**6 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1))
while q:
  px,py = q.popleft()
  d = dp[px][py]
  for j in range(1,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= d:
      break
    if dp[px+j][py] == 10**6:
      dp[px+j][py] = d+1
      q.append((px+j,py))
  for j in range(1,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= d:
      break
    if dp[px-j][py] == 10**6:
      dp[px-j][py] = d+1
      q.append((px-j,py))
  for j in range(1,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= d:
      break 
    if dp[px][py+j] == 10**6:
      dp[px][py+j] = d+1
      q.append((px,py+j))
  for j in range(1,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= d:
      break
    if dp[px][py-j] == 10**6:
      dp[px][py-j] = d+1
      q.append((px,py-j))
if dp[gx-1][gy-1] == 10**6:
  print(-1)
else:
  print(dp[gx-1][gy-1])

Submission status: Accepted

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict, deque
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n,m,k=map(int,input().split())
    x1,y1,x2,y2=map(int,input().split())
    ar=[]
    ans=[]
    visited=[]
    for i in range(n):
        visited.append([False]*m)
        ar.append(input())
        ans.append([0]*m)

    if(ar[x1-1][y1-1]=='@' or ar[x2-1][y2-1]=='@'):
        print(-1)
    q=deque()
    q.append((x1-1,y1-1))
    br=[(-1,0),(1,0),(0,1),(0,-1)]
    #ar[x1-1][y1-1]=1000000000
    while(q):
        a,b=q.popleft()
        #print(a,b)
        if(a==x2-1 and b==y2-1):
            print(ans[a][b])
            exit()
        for p,r in br:
            for i in range(1,k+1):
                x=a+i*p
                y=b+i*r
                if not (0<=x<n and 0<=y<m) or ar[x][y]=='@' or (x==x1-1 and y==y1-1):
                    break
                if(0<ans[x][y]<=ans[a][b]):
                    break
                #print('>>>', x, y, ans[x][y])
                ans[x][y]=ans[a][b]+1
                #print('>>>', x, y, ans[x][y])
                if(not visited[x][y]):
                    q.append([x,y])
                    visited[x][y]=True
    print(-1)







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def resolve():
    H,W,K = map(int,input().split())
    ys, xs, yg, xg = map(int,input().split())

    board = [['@']*(W+2)]
    for i in range(H):
        board.append(['@'] + list(input())+['@'])
    board.append(['@']*(W+2))
    board[ys][xs] = '#'

    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,K+1):
            if f1:
                if board[y][x+i] == '.':
                    l.append((x+i,y))
                elif board[y][x+i] == '@' or board[y][x+i] != dep+1:
                    f1 = False 
            if f2:
                if board[y][x-i] == '.':
                    l.append((x-i,y))
                elif board[y][x-i] == '@' or board[y][x-i] != dep+1:
                    f2 = False 
            if f3:
                if board[y+i][x] == '.':
                    l.append((x,y+i))
                elif board[y+i][x] == '@' or board[y+i][x] != dep+1:
                    f3 = False 
            if f4:
                if board[y-i][x] == '.':
                    l.append((x,y-i))
                elif board[y-i][x] == '@' or board[y-i][x] != dep+1:
                    f4 = False 
            if not(f1 or f2 or f3 or f4):
                break
        for nx,ny in l:
            if board[ny][nx] == '.':
                board[ny][nx] = dep + 1
                if (nx,ny) == (xg,yg):
                    print(dep+1)
                    return 
                else:
                    queue.append((nx,ny,dep+1))
    print(-1)
    return 
resolve()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

H,W,K = LI()
x1,y1,x2,y2 = LI()
c = [list(map(str,input())) for _ in range(H)]

def grid_bfs(S,s,default=-1):
    dist = [[default]*W for _ in range(H)]
    can_visit_mark = ['.']
    d = [(0,1),(0,-1),(1,0),(-1,0)]
    dist[s[0]][s[1]] = 0
    q = [s]
    counter = 1
    while q:
        q1 = []
        for now in q:
            for delta in d:
                for i in range(1,K+1):
                    new = (now[0]+i*delta[0], now[1]+i*delta[1])
                    if 0 <= new[0] <= H-1 and 0 <= new[1] <= W-1:
                        if S[new[0]][new[1]] in can_visit_mark:  
                            if dist[new[0]][new[1]] == default:
                                dist[new[0]][new[1]] = counter
                                q1.append(new)
                            elif dist[now[0]][now[1]] < dist[new[0]][new[1]]:
                                continue
                            else:
                                break
                        else:
                            break
                    else:
                        break
        if dist[x2-1][y2-1] != default:
            return dist[x2-1][y2-1]
        q = q1
        counter += 1
    return -1

print(grid_bfs(c,(x1-1,y1-1)))

Submission status: Accepted

Solution code:
from collections import deque
h, w, k = map(int, input().split())
n = h*w
x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])


def bfs(init_v):
    next_v = deque([init_v])
    dist = [-1]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = divmod(v, w)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            for a in range(1, k+1):
                x, y = i+di*a, j+dj*a
                if x < 0 or h <= x or y < 0 or w <= y:
                    break
                v2 = x*w+y
                if fld[v2] == '@':
                    break
                if dist[v2] != -1 and dist[v2] <= dist[v]:
                    break
                if dist[v2] != -1:
                    continue
                dist[v2] = dist[v]+1
                next_v.append(v2)
    return dist


dist = bfs(x1*w+y1)
print(dist[x2*w+y2])

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()
INF = 10**18
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

def main():
    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 = [input() for _ in range(H)]

    """
    まずはKの制約がない時を考える。単純なBFSでは明らかに間に合わないが、
    「位置」と「向き」の直積を頂点として扱うのがポイント。
    隣の頂点に同じ向きで移動するのにコスト0、同じ頂点で向きを変えるのにコスト1かかるとして
    辺を張れば、ダイクストラにより計算量O((4HW + 4HW) * log(4HW))で解ける。

    ではKの制約がある時はどうするかというと、コストを(従来のコスト, 直線移動距離)のペアに変更する。
    直線移動距離がKを超えたら従来のコストを１つ繰り上げる。
    このペアによるコストは辞書式順序により全順序構造を持つので同様にダイクストラで扱える。

    さらに実はこのコストはペアで扱わないにすることもでき、
        直線移動のコスト＝1/K
        方向転換のコスト＝切り上げ
    と定めると整数部分が本問で求めるコストになっている。
    少数は少し怖いので実際にはK倍して扱う。
    """

    # 向き付き2次元配列を１次元に押し込める補助関数を用意
    def toId(i, j, v):
        return (i * W + j) * 4 + v

    dist = [INF] * (H * W * 4)
    q = []

    # ダイクストラ更新１回分の補助関数
    def push(i, j, v, x):
        id = toId(i, j, v)
        if dist[id] <= x: return
        dist[id] = x
        heappush(q, (x, id))

    # ダイクストラ
    for v in range(4): push(x1, y1, v, 0)
    while q:
        x, id = heappop(q)
        if dist[id] != x: continue # 途中で値が書き換わっていたら伝搬は無効化する！
        i, j, v = (id // 4) // W, (id // 4) % W, id % 4
        # 方向転換
        push(i, j, (v + 1) % 4, (x + K - 1) // K * K)
        push(i, j, (v + 2) % 4, (x + K - 1) // K * K)
        push(i, j, (v + 3) % 4, (x + K - 1) // K * K)
        # 直進
        ni, nj = i + di[v], j + dj[v]
        if 0 <= ni < H and 0 <= nj < W and C[ni][nj] == '.':
            push(ni, nj, v, x + 1)
    ans = min(dist[toId(x2, y2, v)] for v in range(4))
    if ans == INF: print(-1)
    else: print((ans + K - 1) // K)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
si, sj, ti, tj = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1
b = [input() for _ in range(h)]
ans = [[-1]* w for _ in range(h)]
ans[si][sj] = 0
from collections import deque
d = deque()
d.append((si, sj))
while d:
  x, y = d.popleft()
  if x == ti and y == tj:
    print(ans[x][y])
    exit()
  for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
    for i in range(1, k+1):
      xx = x+dx*i
      yy = y+dy*i
      if not(0<= xx < h and 0<= yy < w) or b[xx][yy] == '@':
        break
      if 0 <= ans[xx][yy] <= ans[x][y]:
        break
      if ans[xx][yy] == -1:
        d.append((xx, yy))
      ans[xx][yy] = ans[x][y] + 1
print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

H, W, k = LI()
x1, y1, x2, y2 = LI()
maze = [input() for _ in range(H)]
dp = [[10**10] * W for _ in range(H)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
que = deque()
que.append((x1-1, y1-1))
dp[x1-1][y1-1] = 0
while que:
    y, x = que.popleft()
    dist = dp[y][x]
    if y == x2 - 1 and x == y2 - 1:
        print(dist)
        quit()
    for i in range(4):
        dy_, dx_ = dy[i], dx[i]
        ny, nx = y, x
        for _ in range(1, k+1):
            ny, nx = ny + dy_, nx + dx_ 
            if 0 <= ny < H and 0 <= nx < W:
                if maze[ny][nx] == '@':
                    break
                if dist + 1 < dp[ny][nx]:
                    dp[ny][nx] = dist + 1
                    que.append((ny, nx))
                if dist + 1 > dp[ny][nx]:
                    break
            else:
                break
print(-1)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from heapq import heapify, heappush as hpush, heappop as hpop
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)
X += X[:]
H, W = H+2, W+2
HW = H * W
s, t = x1 * W + y1, x2 * W + y2
ss, tt = s + HW, t + HW
def dijkstra():
    n = 2 * H * W
    h = [(0, s), (0, ss)]
    D = [-1] * n
    done = [0] * n
    D[s] = 0
    D[ss] = 0
    while h:
        d, i = hpop(h)
        done[i] = 1
        if i < HW:
            for j in (i+1, i-1):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, (nd, j))
                        D[j] = nd
        else:
            for j in (i+W, i-W):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, (nd, j))
                        D[j] = nd
            
        j = i + HW if i < HW else i - HW
        nd = (d + K - 1) // K * K
        if X[j]: continue
        if D[j] < 0 or D[j] > nd:
            if done[j] == 0:
                hpush(h, (nd, j))
                D[j] = nd
    return [-(-a//K) for a in (D[t], D[tt]) if a >= 0]

di = dijkstra()
print(min(di) if di else -1)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from heapq import heapify, heappush as hpush, heappop as hpop
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)
X += X[:]
H, W = H+2, W+2
HW = H * W
s, t = x1 * W + y1, x2 * W + y2
ss, tt = s + HW, t + HW
def dijkstra():
    n = 2 * H * W
    h = [s, ss]
    D = [-1] * n
    done = [0] * n
    D[s] = 0
    D[ss] = 0
    kk = 21
    m = (1 << kk) - 1
    while h:
        x = hpop(h)
        d, i = x >> kk, x & m
        done[i] = 1
        if i < HW:
            for j in (i+1, i-1):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, (nd << kk) + j)
                        D[j] = nd
        else:
            for j in (i+W, i-W):
                nd = d + 1
                if X[j]: continue
                if D[j] < 0 or D[j] > nd:
                    if done[j] == 0:
                        hpush(h, (nd << kk) + j)
                        D[j] = nd
            
        j = i + HW if i < HW else i - HW
        nd = (d + K - 1) // K * K
        if X[j]: continue
        if D[j] < 0 or D[j] > nd:
            if done[j] == 0:
                hpush(h, (nd << kk) + j)
                D[j] = nd
    return [-(-a//K) for a in (D[t], D[tt]) if a >= 0]

di = dijkstra()
print(min(di) if di else -1)

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque

    h, w, k = map(int, readline().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, readline().split())
    dict = [[-1] * w for _ in range(h)]
    move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    for i in range(h):
        c = readline().rstrip().decode()
        for j, cc in enumerate(c):
            if cc == '@':
                dict[i][j] = 0
    q = deque()
    q.append((x1, y1))
    dict[x1][y1] = 0
    while q:
        x, y = q.popleft()
        if x == x2 and y == y2:
            exit(print(dict[x][y]))
        for dx, dy in move:
            for i in range(1, k + 1):
                xx = x + dx * i
                yy = y + dy * i
                if 0 > xx or xx >= h or 0 > yy or yy >= w:
                    break
                if 0 <= dict[xx][yy] <= dict[x][y]:
                    break
                if dict[xx][yy] == -1:
                    q.append((xx, yy))
                dict[xx][yy] = dict[x][y] + 1
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import deque

    h, w, k = map(int, readline().split())
    x1, y1, x2, y2 = map(lambda x: int(x) - 1, readline().split())
    c = [readline().rstrip().decode() for _ in range(h)]
    dict = [[-1] * w for _ in range(h)]
    move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    q.append((x1, y1))
    dict[x1][y1] = 0
    while q:
        x, y = q.popleft()
        if x == x2 and y == y2:
            exit(print(dict[x][y]))
        for dx, dy in move:
            for i in range(1, k + 1):
                xx = x + dx * i
                yy = y + dy * i
                if 0 > xx or xx >= h or 0 > yy or yy >= w:
                    break
                if 0 <= dict[xx][yy] <= dict[x][y] or c[xx][yy] == '@':
                    break
                if dict[xx][yy] == -1:
                    q.append((xx, yy))
                dict[xx][yy] = dict[x][y] + 1
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x : int(x) - 1, input().split())
c = [input().rstrip() for _ in range(H)]
INF = 10**18
dist = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]
dist[x1][y1] = [(1, 0)] * 4
dq = deque()
for i in range(4):
    dq.append((dist[x1][y1][i], x1, y1, i))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while dq:
    d, x, y, i = dq.popleft()

    if d > dist[x][y][i]:
        continue

    for j in range(4):
        nd = (d[0] + 1, 0)
        if dist[x][y][j] > nd:
            dist[x][y][j] = nd
            dq.append((nd, x, y, j))

    nx = x + dx[i]
    ny = y + dy[i]
    if nx < 0 or H <= nx or ny < 0 or W <= ny or c[nx][ny] == '@':
        continue
    if d[1] < K:
        nd = (d[0], d[1] + 1)
        if dist[nx][ny][i] > nd:
            dist[nx][ny][i] = nd
            dq.appendleft((nd, nx, ny, i))
    else:
        nd = (d[0] + 1, 1)
        if dist[nx][ny][i] > nd:
            dist[nx][ny][i] = nd
            dq.append((nd, nx, ny, i))
ans = min(dist[x2][y2])[0]
print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[x^1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
q=[a]
d[a]=1
for s in q:
 for x in range(4):
  for z in range(k):
   y=~z,0,z+1,0,~z;i,j=s//w+y[x],s%w+y[x+1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   if'.'!=m[(i:=s//w+y*~z)][(j:=s%w+x*~z)]or d[s]>=d[(t:=i*w+j)]:break
   if-~d[s]<d[t]:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   if'.'!=m[(i:=s//w+y*~z)][(j:=s%w+x*~z)]or(p:=d[s]+1)>d[(t:=i*w+j)]:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
m+='@'*w,
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = []
for i in range(h):
  c.append(list(input()))

q = [(1,x1-1,y1-1)]
c[x1-1][y1-1] = 0
while(q):
  qq = []
  for a,x,y in q:
    for dx,dy in ((0,-1),(0,1),(-1,0),(1,0)):
      for kk in range(1,k+1):
        xx = x+dx*kk
        yy = y+dy*kk
        if not (0 <= xx < h) or not (0 <= yy < w) or c[xx][yy] == '@' or (c[xx][yy] != '.' and c[xx][yy] < a):
          break
        if c[xx][yy] == '.' or (c[xx][yy] != '.' and c[xx][yy] > a):
          c[xx][yy] = a
          qq.append((a+1,xx,yy))
  #print(qq)
  q = qq[:]

print(-1 if c[x2-1][y2-1] == '.' else c[x2-1][y2-1])
#print(c)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
from collections import deque

H, W, K = map(int, input().split())
x1, y1, x2, y2 = (int(i) - 1 for i in input().split())
C = [input() for _ in range(H)]

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

Q = deque([(x1, y1)])
while Q:
    x, y = Q.popleft()
    if (x, y) == (x2, y2):
        print(ans[x][y])
        quit()

    for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for a in range(1, K + 1):
            nx = x + a * di
            ny = y + a * dj

            if not (0 <= nx < H and 0 <= ny < W) or C[nx][ny] == "@" or 0 <= ans[nx][ny] <= ans[x][y]:
                break

            if ans[nx][ny] == -1:
                Q.append((nx, ny))

            ans[nx][ny] = 1 + ans[x][y]

print(-1)

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        for xx,yy in [(1,0),(0,1),(-1,0),(0,-1)]:
            for i in range(1,k+1):
                nx,ny = x+xx*i,y+yy*i
                if cord[ny][nx] == '.':
                    l.append((nx,ny))
                elif type(cord[ny][nx]) != int or cord[ny][nx] < dep+1:
                    break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'

print(bfs(xg,yg))

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        for xx,yy in [(1,0),(0,1),(-1,0),(0,-1)]:
            for i in range(1,k+1):
                nx,ny = x+xx*i,y+yy*i
                if cord[ny][nx] == '.':
                    l.append((nx,ny))
                elif cord[ny][nx] == dep+1:
                    continue
                else:
                    break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
#print(len(cord),len(cord[0]))

print(bfs(xg,yg))

Submission status: Accepted

Solution code:
# F - Pond Skater

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 = []
for _ in range(H):
    grid.append(list(str(input())))

dist = [[-1] * W for _ in range(H)]
dist[x1][y1] = 0
q = deque()
q.append((x1, y1))

while q:
    (x, y) = q.popleft()
    if (x, y) == (x2, y2):
        break
    for vx, vy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        for k in range(1, K+1):
            nx = x + vx*k
            ny = y + vy*k
            if nx < 0 or nx >= H or ny < 0 or ny >= W or grid[nx][ny] == '@':
                break
            if dist[nx][ny] != -1 and dist[nx][ny] != dist[x][y] + 1:
                break
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

print(dist[x2][y2])

Submission status: Accepted

Solution code:
def main():
    h,a,*m=open(0)
    h,w,k,a,b,f,g=map(int,(h+a).split())
    I=h*w
    d=[I]*I
    a=~w+a*w+b
    d[a]=1
    q=[a]
    for s in q:
        for y,x in(1,0),(-1,0),(0,1),(0,-1):
            for z in range(k):
                i,j=s//w+y*~z,s%w+x*~z
                t=i*w+j
                if not h>i>-1<j<w or'.'<m[i][j]or d[t]<=d[s]:break
                if d[t]==I:
                    q+=t,
                    d[t]=d[s]+1
    print(d[~w+f*w+g]%I-1)
main()

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
from collections import deque


def bfs(xg,yg):
    queue = deque([(xs,ys,0)])
    while queue:
        x,y,dep = queue.popleft()
        l = []
        f1 = True
        f2 = True
        f3 = True
        f4 = True
        for i in range(1,k+1):
            if f1:
                if cord[y][x+i] == '.':
                    l.append((x+i,y))
                elif cord[y][x+i] == '@' or cord[y][x+i] != dep+1:
                    f1 = False
            if f2:
                if cord[y][x-i] == '.':
                    l.append((x-i,y))
                elif cord[y][x-i] == '@' or cord[y][x-i] != dep+1:
                    f2 = False
            if f3:
                if cord[y+i][x] == '.':
                    l.append((x,y+i))
                elif cord[y+i][x] == '@' or cord[y+i][x] != dep+1:
                    f3 = False
            if f4:
                if cord[y-i][x] == '.':
                    l.append((x,y-i))
                elif cord[y-i][x] == '@' or cord[y-i][x] != dep+1:
                    f4 = False
            if not (f1 or f2 or f3 or f4):
                break
        for nx, ny in l:
            if cord[ny][nx] == '.':
                cord[ny][nx] = dep+1
                if (nx,ny) == (xg,yg):
                    return dep+1
                else:
                    queue.append((nx,ny,dep+1))
    return -1

h,w,k = iim()
ys,xs,yg,xg = iim()

cord = [['@']*(w+2)]
for i in range(h):
    cord.append(['@']+list(input())+['@'])
cord.append(['@']*(w+2))
cord[ys][xs] = '#'
#for i in cord:
#    print(*i)
#print(len(cord),len(cord[0]))

print(bfs(xg,yg))

Submission status: Accepted

Solution code:
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
d[~w+a*w+b]=1
q=[(a-1,b-1)]
for s,t in q:
 p=d[s*w+t]+1
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s+y*~z,t+x*~z;l=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[l]<p:break
   if d[l]==I:q+=(i,j),;d[l]=p
print(d[~w+f*w+g]%I-1)