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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import deque
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    # 0123: 上下左右
    stack = deque([((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
                   ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3])
    append, popleft = stack.append, stack.popleft
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        b = popleft()
        d = b % 4
        x, y = divmod(b >> 2, KETA)
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            append(((xx * KETA + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import deque
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    # 0123: 上下左右
    stack = deque([((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
                   ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3])
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while stack:
        b = stack.popleft()
        head += 1
        d = b % 4
        x, y = divmod(b >> 2, KETA)
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                stack.append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                stack.append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            stack.append(((xx * KETA + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6
KETA = 10**7


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    c = [[-1] + [0 if c == "." else -1 for c in input()] + [-1]
         for i in range(H)]
    c = [[-1] * (W + 2)] + c + [[-1] * (W + 2)]
    c[x1][y1] = 0

    # 0123: 上下左右
    stack = [((x1 * KETA + y1) << 2) + 0, ((x1 * KETA + y1) << 2) + 1,
             ((x1 * KETA + y1) << 2) + 2, ((x1 * KETA + y1) << 2) + 3]
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    head = 0
    while head < len(stack):
        b = stack[head]
        head += 1
        d = b % 4
        x, y = divmod(b >> 2, KETA)
        flag = True
        a = c[x][y] + 1
        for k in range(1, K + 1):
            xx, yy = x + k * DX[d], y + k * DY[d]
            if c[xx][yy] == 0:
                stack.append(((xx * KETA + yy) << 2) + (d - 1) % 4)
                stack.append(((xx * KETA + yy) << 2) + (d + 1) % 4)
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            stack.append(((xx * KETA + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
from math import ceil
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7
EPS = 1e-6


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = LIST()
    x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
    c = [[c for c in input()] for i in range(H)]
    dist = [[INF] * W for i in range(H)]
    dist[x1][y1] = 0

    # 0123: 上下左右
    stack = [(0, x1, y1, 0), (0, x1, y1, 1),
             (0, x1, y1, 2), (0, x1, y1, 3)]
    head = 0
    while head < len(stack):
        curr, x, y, d = stack[head]
        head += 1
        c[x][y] = "@"
        # print(curr, x, y, d, head)
        # print(stack)
        if d == 0:
            dx, dy = 1, 0
        elif d == 1:
            dx, dy = 0, 1
        elif d == 2:
            dx, dy = -1, 0
        else:
            dx, dy = 0, -1
        flag = True
        for i in range(1, K + 1):
            xx = x + i * dx
            yy = y + i * dy
            if not(0 <= xx < H) or not(0 <= yy < W) or c[xx][yy] == "@":
                flag = False
                break
            if (xx, yy) == (x2, y2):
                print(int(ceil(curr + 1 / K - EPS)))
                return
            if dist[xx][yy] > curr + 1:
                dist[xx][yy] = curr + 1
                stack.append((curr + 1, xx, yy, (d - 1) % 4))
                stack.append((curr + 1, xx, yy, (d + 1) % 4))
        if flag:
            if dist[xx][yy] >= curr + 1:
                stack.append((curr + 1, xx, yy, d))
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF=float('inf')
from collections import deque
def mbfs(G,sh,sw,H,W):
    dist=[[INF]*W for i in range(H)]
    dist[sh][sw]=0
    d=deque()
    d.append([sh,sw])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        d.popleft()
        for dir in range(4):
            for k in range(1,K+1):
                nh=h+dx[dir]*k
                nw=w+dy[dir]*k
                if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                    break
                if(G[nh][nw]=='@'):
                    break
                if(dist[nh][nw]<=dist[h][w]):
                    break
                if dist[nh][nw]==dist[h][w]+1:
                    continue
                else:
                    dist[nh][nw]=dist[h][w]+1
                    d.append([nh,nw])
    return dist
H,W,K=map(int,input().split())
sx,sy,gx,gy=map(lambda x:int(x)-1,input().split())
c=[list(input()) for i in range(H)]
dist=mbfs(c,sx,sy,H,W)
ans=dist[gx][gy]
print(ans if ans!=INF else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(h)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
                    if ny == gy and nx == gx:
                        print(G[y][x] + 1)
                        return
    print(-1)
    return

solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


def solve():
    h, w, k = nm()
    sy, sx, gy, gx = nm()
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    sx -= 1; sy -= 1
    gx -= 1; gy -= 1
    C = [ns() for _ in range(h)]
    G = [[10**7]*w for _ in range(h)]
    G[sy][sx] = 0
    q = deque([(sy, sx)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            dy, dx = d[i]
            ny, nx = y, x
            for _ in range(k):
                ny += dy; nx += dx
                if ny < 0 or h <= ny or nx < 0 or w <= nx:
                    break
                if C[ny][nx] == '@' or G[ny][nx] <= G[y][x]:
                    break
                if G[ny][nx] > G[y][x] + 1:
                    G[ny][nx] = G[y][x] + 1
                    q.append((ny, nx))
    ans = G[gy][gx]
    print(ans if ans < 10**7 else -1)
    return

solve()

Submission status: Accepted

Solution code:
from queue import Queue


def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(lambda z: int(z) - 1, input().split())
    c = [list(input().replace('\n', '')) for _ in range(h)]
    c[sx][sy] = 0
    q = Queue()
    q.put((sx, sy))
    while not q.empty():
        x, y = q.get()
        d = c[x][y]
        # 南へ移動
        for i in range(1, k + 1):
            if x + i >= h:
                break
            if c[x + i][y] == '@':
                break
            elif isinstance(c[x + i][y], int) and c[x + i][y] < d + 1:
                break
            elif isinstance(c[x + i][y], int) and c[x + i][y] == d + 1:
                continue
            else:
                c[x + i][y] = d + 1
                q.put((x + i, y))
        # 北へ移動
        for i in range(1, k + 1):
            if x - i < 0:
                break
            if c[x - i][y] == '@':
                break
            elif isinstance(c[x - i][y], int) and c[x - i][y] < d + 1:
                break
            elif isinstance(c[x - i][y], int) and c[x - i][y] == d + 1:
                continue
            else:
                c[x - i][y] = d + 1
                q.put((x - i, y))
        # 東へ移動
        for i in range(1, k + 1):
            if y + i >= w:
                break
            if c[x][y + i] == '@':
                break
            elif isinstance(c[x][y + i], int) and c[x][y + i] < d + 1:
                break
            elif isinstance(c[x][y + i], int) and c[x][y + i] == d + 1:
                continue
            else:
                c[x][y + i] = d + 1
                q.put((x, y + i))
        # 西へ移動
        for i in range(1, k + 1):
            if y - i < 0:
                break
            if c[x][y - i] == '@':
                break
            elif isinstance(c[x][y - i], int) and c[x][y - i] < d + 1:
                break
            elif isinstance(c[x][y - i], int) and c[x][y - i] < d + 1:
                continue
            else:
                c[x][y - i] = d + 1
                q.put((x, y - i))
    print(-1 if c[gx][gy] == '.' else c[gx][gy])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
c_ = [tuple(input()) for _ in range(h)]
c = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if c_[i][j] == '@':
            c[i][j] = True
# print(x1, y1)
# print(x2, y2)

dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
MAX = 10**7


def convert(x, y, d):
    return (x * w + y) * 4 + d


# dp = [[[(MAX, MAX)] * 4 for _ in range(w)] for _ in range(h)]
dp = [MAX * (k + 1) + k] * (h * w * 4)

# q = [((1, 0, x1, y1, i)) for i in range(4)]
q = [((k + 1, convert(x1, y1, i))) for i in range(4)]

while q:
    c0, xyd = heappop(q)
    c1 = c0 // (k + 1)
    c2 = c0 % (k + 1)
    # print(x, y, d, c1, c2)
    d = xyd % 4
    y = (xyd // 4) % w
    x = (xyd // 4) // w
    if c1 > dp[xyd] // (k + 1):
        continue
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        nxyi = convert(nx, ny, i)
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if c[nx][ny]:
            continue
        if i == d and c2 < k:
            if dp[nxyi] > c1 * (k + 1) + c2 + 1:
                dp[nxyi] = c1 * (k + 1) + c2 + 1
                heappush(q, (dp[nxyi], nxyi))
        else:
            if dp[nxyi] > (c1 + 1) * (k + 1) + 1:
                dp[nxyi] = (c1 + 1) * (k + 1) + 1
                heappush(q, (dp[nxyi], nxyi))

ans = min(dp[convert(x2, y2, i)] // (k + 1) for i in range(4))
if ans == MAX:
    ans = -1
print(ans)

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:
#関数リスト
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    h, w, k = MI()
    x1, y1, x2, y2 = MI()
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1

    mylist = [0] * h

    #tableの読み込み
    for i in range(h):
        temp = input().rstrip()
        temp = [temp[j] for j in range(w)]
        mylist[i] = temp
    #初期化
    distance = [[-1 for i in range(w)] for j in range(h)]
    distance[x1][y1] = 0
    d = deque()
    start = (x1, y1)
    goal = [x2, y2]
    d.append(start)
    move = ([-1,0],[1,0],[0,1],[0,-1])

    while d:
        pos = d.popleft()
        x = pos[0]
        y = pos[1]
        if x == x2 and y == y2:
            print(distance[x2][y2])
            exit()
        dist = distance[x][y]
        for i in move:
            #tempxの初期化
            tempx = x
            tempy = y
            for l in range(k):
                tempx += i[0]
                tempy += i[1]
                if not ((tempx >= 0 and tempx <= h-1) and (tempy >= 0 and tempy <= w - 1)):
                    break
                elif mylist[tempx][tempy] == "." and distance[tempx][tempy] == -1:
                    distance[tempx][tempy] = dist + 1
                    d.append((tempx, tempy))
                elif dist + 1 <= distance[tempx][tempy] and mylist[tempx][tempy] == ".":
                    distance[tempx][tempy] = dist + 1
                else:
                    break
    print(-1)            
        
main()

Submission status: Accepted

Solution code:
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
inf=float('inf')
seen=[[[(inf,inf)]*4 for _ in range(w)] for _ in range(h)]
D=[(-1,0),(0,1),(1,0),(0,-1)]# 上:0, 右:1, 下:2, 左:3
q=deque()
for d in range(4):
  seen[x1][y1][d]=(1,0)
  q.append((x1, y1, d, 1, 0)) # (x, y, 進行方向[d], 移動回数[c], 進行済マス数[k])
while q:
  x,y,d,c,k_=q.popleft()
  # nx, ny: 次の座標
  # nd: 次の進行方向
  # nc: 次の移動回数
  # nk: 次の進行済マス数
  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 cmap[nx][ny]!='@' and seen[nx][ny][nd]>(nc,nk):
      seen[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,seen[x2][y2][d][0])
ans=-1 if ans==inf else ans
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())

pond=[list(input()) for _ in range(H)]

inf=float("inf")
cost=[[inf]*W for _ in range(H)]
cost[x1][y1]=0
from heapq import heappop,heappush
hq=[(0,x1,y1)]

while hq:
    t,x,y=heappop(hq)
    if x==x2 and y==y2:
      print(t)
      exit()
    #北へ
    for i in range(1,K+1):
        if x-i<0 or pond[x-i][y]=="@" or cost[x-i][y]<t+1:
            break
        if cost[x-i][y]>t+1:
            cost[x-i][y]=t+1
            heappush(hq,(t+1,x-i,y))
    #東へ
    for i in range(1,K+1):
        if y+i>W-1 or pond[x][y+i]=="@" or cost[x][y+i]<t+1:
            break
        if cost[x][y+i]>t+1:
            cost[x][y+i]=t+1
            heappush(hq,(t+1,x,y+i))
    #南へ
    for i in range(1,K+1):
        if x+i>H-1 or pond[x+i][y]=="@" or cost[x+i][y]<t+1:
            break
        if cost[x+i][y]>t+1:
            cost[x+i][y]=t+1
            heappush(hq,(t+1,x+i,y))
    #西へ
    for i in range(1,K+1):
        if y-i<0 or pond[x][y-i]=="@" or cost[x][y-i]<t+1:
            break
        if cost[x][y-i]>t+1:
            cost[x][y-i]=t+1
            heappush(hq,(t+1,x,y-i))

print(-1)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())

pond=[]
for _ in range(H):
    pond.append(list(input()))

inf=10**7
cost=[[inf]*W for _ in range(H)]
cost[x1][y1]=0
from heapq import heapify,heappop,heappush
hq=[(0,x1,y1)]

while hq:
    t,x,y=heappop(hq)
    if x==x2 and y==y2:
      print(t)
      exit()
    #北へ
    for i in range(1,K+1):
        if x-i<0 or pond[x-i][y]=="@" or cost[x-i][y]<t+1:
            break
        if cost[x-i][y]>t+1:
            cost[x-i][y]=t+1
            heappush(hq,(t+1,x-i,y))
    #東へ
    for i in range(1,K+1):
        if y+i>W-1 or pond[x][y+i]=="@" or cost[x][y+i]<t+1:
            break
        if cost[x][y+i]>t+1:
            cost[x][y+i]=t+1
            heappush(hq,(t+1,x,y+i))
    #南へ
    for i in range(1,K+1):
        if x+i>H-1 or pond[x+i][y]=="@" or cost[x+i][y]<t+1:
            break
        if cost[x+i][y]>t+1:
            cost[x+i][y]=t+1
            heappush(hq,(t+1,x+i,y))
    #西へ
    for i in range(1,K+1):
        if y-i<0 or pond[x][y-i]=="@" or cost[x][y-i]<t+1:
            break
        if cost[x][y-i]>t+1:
            cost[x][y-i]=t+1
            heappush(hq,(t+1,x,y-i))

print(-1)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())

pond=[]
for _ in range(H):
    pond.append(list(input()))

inf=10**7
cost=[[inf]*W for _ in range(H)]
cost[x1][y1]=0
from heapq import heapify,heappop,heappush
hq=[(0,x1,y1)]

while hq:
    t,x,y=heappop(hq)
    #北へ
    for i in range(1,K+1):
        if x-i<0 or pond[x-i][y]=="@" or cost[x-i][y]<t+1:
            break
        if cost[x-i][y]>t+1:
            cost[x-i][y]=t+1
            heappush(hq,(t+1,x-i,y))
    #東へ
    for i in range(1,K+1):
        if y+i>W-1 or pond[x][y+i]=="@" or cost[x][y+i]<t+1:
            break
        if cost[x][y+i]>t+1:
            cost[x][y+i]=t+1
            heappush(hq,(t+1,x,y+i))
    #南へ
    for i in range(1,K+1):
        if x+i>H-1 or pond[x+i][y]=="@" or cost[x+i][y]<t+1:
            break
        if cost[x+i][y]>t+1:
            cost[x+i][y]=t+1
            heappush(hq,(t+1,x+i,y))
    #西へ
    for i in range(1,K+1):
        if y-i<0 or pond[x][y-i]=="@" or cost[x][y-i]<t+1:
            break
        if cost[x][y-i]>t+1:
            cost[x][y-i]=t+1
            heappush(hq,(t+1,x,y-i))

if cost[x2][y2]==inf:
    print(-1)
    exit()  
print(cost[x2][y2])

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())

pond=[]
for _ in range(H):
    pond.append(list(input()))

inf=10**7
cost=[[inf]*W for _ in range(H)]
cost[x1][y1]=0
from heapq import heapify,heappop,heappush
hq=[(0,x1,y1)]

while hq:
    t,x,y=heappop(hq)
    #北へ
    for i in range(1,K+1):
        if x-i<0 or pond[x-i][y]=="@" or cost[x-i][y]<t+1:
            break
        if cost[x-i][y]>t+1:
            cost[x-i][y]=t+1
            heappush(hq,(t+1,x-i,y))
    #東へ
    for i in range(1,K+1):
        if y+i>W-1 or pond[x][y+i]=="@" or cost[x][y+i]<t+1:
            break
        if cost[x][y+i]>t+1:
            cost[x][y+i]=t+1
            heappush(hq,(t+1,x,y+i))
    #南へ
    for i in range(1,K+1):
        if x+i>H-1 or pond[x+i][y]=="@" or cost[x+i][y]<t+1:
            break
        if cost[x+i][y]>t+1:
            cost[x+i][y]=t+1
            heappush(hq,(t+1,x+i,y))
    #西へ
    for i in range(1,K+1):
        if y-i<0 or pond[x][y-i]=="@" or cost[x][y-i]<t+1:
            break
        if cost[x][y-i]>t+1:
            cost[x][y-i]=t+1
            heappush(hq,(t+1,x,y-i))

if cost[x2][y2]==inf:
    print(-1)
    exit()  
print(cost[x2][y2])

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
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())
S = [input()[:-1] for _ in [0]*H]

def geth(x, y, z):
    return (x*W+y)*4+z

def push(x, y, z, d):
    h = geth(x, y, z)
    if D[h] <= d:
        return
    D[h] = d
    heappush(q, (d, h))

INF = 10**10
MAX = H*W*4
D = [INF]*MAX
dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]

q = []
for z in range(4):
    heappush(q, (0, geth(x1, y1, z)))

while q:
    d, h = heappop(q)
    z = h % 4
    x, y = divmod((h//4), W)

    if d > D[h]:
        continue
    D[h] = d

    for _z, (dx, dy) in enumerate(dirs):
        if _z == z:
            _x, _y = x+dx, y+dy
            if 0 <= _x < H and 0 <= _y < W and S[_x][_y] == '.':
                push(_x, _y, z, d+1)
        else:
            _h = geth(x, y, _z)
            _d = (d+K-1)//K*K
            push(x, y, _z, _d)

g = geth(x2, y2, 0)
ans = min(D[g:g+4])
if ans == INF:
    print(-1)
else:
    ans = (ans-1+K)//K
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

import heapq

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # surround the square with '@'
    c = [['@'] * (w+2)]
    for _ in range(h):
        i = input()
        l = ['@']
        for j in i:
            l.append(j)
        l.append('@')
        c.append(l)
    c.append(['@'] * (w+2))

    # Dijkstra
    # seen[x][y] = the minimum cost of (x, y)
    # if seen[x][y] == -1, (x, y) is unresearched
    seen = [[-1] * (w+2) for _ in range(h+2)]

    # todo[i] == (cost, x, y, direction)
    todo = [(0, x1, y1, 0)]
    heapq.heapify(todo)

    # direction
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    while len(todo) > 0:
        cost, xi, yi, direction = heapq.heappop(todo)

        # only straight
        if seen[xi][yi] != -1:
            if (seen[xi][yi]+k-1)//k * k > cost:
                xj, yj = xi + dx[direction], yi + dy[direction]
                if c[xj][yj] == '.':
                    heapq.heappush(todo, (cost+1, xj, yj, direction))
            continue
        seen[xi][yi] = cost

        # goal
        if xi == x2 and yi == y2:
            print((cost+k-1)//k)
            exit()
        
        # 4 directions
        for j in range(4):
            xj, yj = xi + dx[j], yi + dy[j]
            if c[xj][yj] == '.':
                if j == direction:
                    if seen[xj][yj] == -1 or (seen[xj][yj]+k-1)//k * k > cost:
                        heapq.heappush(todo, (cost+1, xj, yj, j))
                elif seen[xj][yj] == -1:
                    heapq.heappush(todo, ((cost+k-1)//k * k + 1, xj, yj, j))

    print(-1)

main()

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

import heapq

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # surround the square with '@'
    c = [['@'] * (w+2)]
    for _ in range(h):
        i = list('@' + input() + '@')
        c.append(i)
    c.append(['@'] * (w+2))

    # Dijkstra
    # seen[x][y] = the minimum cost of (x, y)
    # if seen[x][y] == -1, (x, y) is unresearched
    seen = [[-1] * (w+2) for _ in range(h+2)]

    # todo[i] == (cost, x, y, direction)
    todo = [(0, x1, y1, 0)]
    heapq.heapify(todo)

    # direction
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    while len(todo) > 0:
        cost, xi, yi, direction = heapq.heappop(todo)

        # only straight
        if seen[xi][yi] != -1:
            if (seen[xi][yi]+k-1)//k * k > cost:
                xj, yj = xi + dx[direction], yi + dy[direction]
                if c[xj][yj] == '.':
                    heapq.heappush(todo, (cost+1, xj, yj, direction))
            continue
        seen[xi][yi] = cost

        # goal
        if xi == x2 and yi == y2:
            print((cost+k-1)//k)
            exit()
        
        # 4 directions
        for j in range(4):
            xj, yj = xi + dx[j], yi + dy[j]
            if c[xj][yj] == '.':
                if j == direction:
                    if seen[xj][yj] == -1 or (seen[xj][yj]+k-1)//k * k > cost:
                        heapq.heappush(todo, (cost+1, xj, yj, j))
                elif seen[xj][yj] == -1:
                    heapq.heappush(todo, ((cost+k-1)//k * k + 1, xj, yj, j))

    print(-1)

main()

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

import heapq

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # surround the square with '@'
    c = [['@'] * (w+2)]
    for _ in range(h):
        i = list('@' + input() + '@')
        c.append(i)
    c.append(['@'] * (w+2))

    # Dijkstra
    # seen[x][y] = the minimum cost of (x, y)
    # if seen[x][y] == -1, (x, y) is unresearched
    seen = [[-1] * (w+2) for _ in range(h+2)]

    # todo[i] == (cost, x, y, direction)
    todo = [(0, x1, y1, 0)]
    heapq.heapify(todo)

    # direction
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    while len(todo) > 0:
        cost, xi, yi, direction = heapq.heappop(todo)

        # special case
        if seen[xi][yi] != -1:
            if (seen[xi][yi]+k-1)//k * k >= cost:
                xj, yj = xi + dx[direction], yi + dy[direction]
                if c[xj][yj] == '.':
                    heapq.heappush(todo, (cost+1, xj, yj, direction))
            continue
        seen[xi][yi] = cost

        # goal
        if xi == x2 and yi == y2:
            print((cost+k-1)//k)
            exit()
        
        # add
        for j in range(4):
            xj, yj = xi + dx[j], yi + dy[j]
            if c[xj][yj] == '.':
                if j == direction:
                    if seen[xj][yj] == -1 or (seen[xj][yj]+k-1)//k * k > cost:
                        heapq.heappush(todo, (cost+1, xj, yj, j))
                elif seen[xj][yj] == -1:
                    heapq.heappush(todo, ((cost+k-1)//k * k + 1, xj, yj, j))

    print(-1)

main()