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
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    vx = [0, 1, 0, -1]
    vy = [-1, 0, 1, 0]

    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    table = [[] for _ in range(H)]
    for i in range(H):
        table[i] = list(input().strip())
    q = deque()
    q.append((x1-1, y1-1, 0))
    table[x1-1][y1-1] = 0
    while len(q) > 0:
        x, y, cnt = q.popleft()
        for i in range(4):
            for k in range(1, K+1):
                nx = x + vx[i] * k
                ny = y + vy[i] * k
                if nx < 0 or ny < 0 or nx >= H or ny >= W:
                    break
                if table[nx][ny] == '@':
                    break
                if table[nx][ny] != '.':
                    if table[nx][ny] < cnt + 1:
                        break
                    else:
                        continue
                table[nx][ny] = cnt+1
                q.append((nx, ny, cnt+1))
    if table[x2-1][y2-1] == '.':
        print(-1)
    else:
        print(table[x2-1][y2-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

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

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
state = [list(input().rstrip()) for _ in range(H)]

q = [(x1-1, y1-1)]
checked = [[-1]*W for _ in range(H)]
checked[x1-1][y1-1] = 0
while q:
    qq = []
    for x, y in q:
        d = checked[x][y]
        dx = 1
        while x+dx < H and state[x+dx][y] == ord(".") and dx <= K:
            if checked[x+dx][y] == -1:
                checked[x+dx][y] = d + 1
                qq.append((x+dx, y))
            elif checked[x+dx][y] >= d + 1:
                checked[x+dx][y] = d + 1
            else:
                break
            dx += 1
        dx = -1
        while x+dx >= 0 and state[x+dx][y] == ord(".") and dx >= -K:
            if checked[x+dx][y] == -1:
                checked[x+dx][y] = d + 1
                qq.append((x+dx, y))
            elif checked[x+dx][y] >= d+1:
                checked[x+dx][y] = d + 1
            else:
                break
            dx -= 1
        dy = 1
        while y+dy < W and state[x][y+dy] == ord(".") and dy <= K:
            if checked[x][y+dy] == -1:
                checked[x][y+dy] = d + 1
                qq.append((x, y+dy))
            elif checked[x][y+dy] >= d+1:
                checked[x][y+dy] = d+1
            else:
                break
            dy += 1
        dy = -1
        while y+dy >= 0 and state[x][y+dy] == ord(".") and dy >= -K:
            if checked[x][y+dy] == -1:
                checked[x][y+dy] = d + 1
                qq.append((x, y+dy))
            elif checked[x][y+dy] >= d+1:
                checked[x][y+dy] = d+1
            else:
                break
            dy -= 1
    q = qq

print(checked[x2-1][y2-1])

Submission status: Accepted

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y = dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            K -= 1
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@" and depth[ny][nx] > depth[y][x]:
                if depth[ny][nx] == depth[y][x]+1:
                    continue
                depth[ny][nx] = depth[y][x] +1
                dq.append((nx,ny))
            else:
                break
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
st=sx+sy*(W+2)
gl=gx+gy*(W+2)
c=['@']*(W+2)
for i in range(H):
    c.extend(['@']+list(input())+['@'])
c.extend(['@']*(W+2))
que=deque()
dist=[INF]*(W+2)*(H+2)
que.append(st)
dist[st]=0
d=(-1,1,W+2,-(W+2))
while que:
    v=que.popleft()
    for k in range(4):
        nv=v
        for _ in range(K):
            nv+=+d[k]
            if c[nv]=='.' and dist[nv]>dist[v]:
                if dist[nv]==INF:
                    dist[nv]=dist[v]+1
                    que.append(nv)
            else:
                break
print(dist[gl] if dist[gl]!=INF else -1)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush 
from collections import deque
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    # que->(cost, x, y, direction)
    inf = 1e18
    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(0, xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        cost, x, y = que.popleft()
        if cost > dist[x][y]:
            continue
        for v in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[v]
                ny += dy[v]
                if not field[nx][ny]:
                    break
                if dist[nx][ny]<=dist[x][y]:
                    break
                if dist[nx][ny] > dist[x][y]+1:
                    dist[nx][ny] = dist[x][y]+1
                    que.append((dist[nx][ny], nx, ny))

    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])

        

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2) for _ in range(h+2)]
    for i in range(h):
        # False で覆うことでx,yの制限をなくす。
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    h += 2
    w += 2
    dijkstra(xs, ys, xg, yg, h, w, k, field)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
Dy = [0,1,0,-1]
Dx = [1,0,-1,0]
H, W, K = map(int, input().split())
y1,x1,y2,x2 = map(int, input().split())
C = ["@" + input() + "@" for _ in range(H)]
C = ["@"*(W+2)] + C + ["@"*(W+2)]
L = [[1]*(W+2) for _ in range(H+2)]
R = [[1]*(W+2) for _ in range(H+2)]
U = [[1]*(W+2) for _ in range(H+2)]
D = [[1]*(W+2) for _ in range(H+2)]
q = [(y1, x1)]
ans = 0
while q:
    q_new = []
    for y0, x0 in q:
        if (y0, x0) == (y2, x2):
            print(ans)
            exit()
        for dy, dx, Next in zip(Dy, Dx, [L, R, U, D]):
            y, x = y0, x0
            sum_next = 0
            Path = [(y, x)]
            while True:
                sum_next += Next[y][x]
                y = y0 + dy * sum_next
                x = x0 + dx * sum_next
                if sum_next > K:
                    break
                if C[y][x] == "@":
                    break
                Path.append((y, x))
                q_new.append((y, x))
            for path_y, path_x in Path:
                Next[path_y][path_x] = abs(path_y-y) + abs(path_x-x)
    q = q_new
    ans += 1

print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    def bfs():
        

        inf = 1e7

        dist = [[inf]*w for _ in range(h)]
        dist[xs][ys] = 0
        que = deque([(xs, ys)])
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            x, y = que.popleft()
            for i in range(4):
                nx, ny = x, y
                for _ in range(k):
                    nx += dx[i]
                    ny += dy[i]
                    if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                    if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                    if dist[nx][ny] > dist[x][y] + 1:
                        dist[nx][ny] = dist[x][y] + 1
                        que.append((nx, ny))
            
        if dist[xg][yg] == inf:
            print(-1)
        else:
            print(dist[xg][yg])

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    bfs()
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

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()
c = [input() for _ in range(h)]

que = deque()
que.append((y1-1, x1-1))
dp = [[inf] * w for _ in range(h)]
dp[x1-1][y1-1] = 0
while que:
    x, y = que.popleft()
    for i in range(4):
        if i == 0:
            for ki in range(k):
                nx = x + (ki + 1)
                if 0 <= nx < w:
                    if c[y][nx] == '.':
                        if dp[y][nx] < dp[y][x] + 1:
                            break
                        elif dp[y][nx] == dp[y][x] + 1:
                            continue
                        dp[y][nx] = dp[y][x] + 1
                        que.append((nx, y))
                    else:
                        break
                else:
                    break
        elif i == 1:
            for ki in range(k):
                ny = y + (ki + 1)
                if 0 <= ny < h:
                    if c[ny][x] == '.':
                        if dp[ny][x] < dp[y][x] + 1:
                            break
                        elif dp[ny][x] == dp[y][x] + 1:
                            continue
                        dp[ny][x] = dp[y][x] + 1
                        que.append((x, ny))
                    else:
                        break
                else:
                    break
        elif i == 2:
            for ki in range(k):
                nx = x - (ki + 1)
                if 0 <= nx < w:
                    if c[y][nx] == '.':
                        if dp[y][nx] < dp[y][x] + 1:
                            break
                        elif dp[y][nx] == dp[y][x] + 1:
                            continue 
                        dp[y][nx] = dp[y][x] + 1
                        que.append((nx, y))
                    else:
                        break
                else:
                    break
        else:
            for ki in range(k):
                ny = y - (ki + 1)
                if 0 <= ny < h:
                    if c[ny][x] == '.':
                        if dp[ny][x] < dp[y][x] + 1:
                            break
                        elif dp[ny][x] == dp[y][x] + 1:
                            continue
                        dp[ny][x] = dp[y][x] + 1
                        que.append((x, ny))
                    else:
                        break
                else:
                    break
ans = dp[x2-1][y2-1]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w,k = LI()
    y1,x1,y2,x2 = LI_()
    ca = [S() for _ in range(h)]

    aa = [[-1 if c == '@' else inf for c in s] for s in ca]
    aa[y1][x1] = 0
    q = [(y1,x1)]
    v = collections.defaultdict(bool)
    t = 0
    while q:
        t += 1
        nq = []
        for y,x in q:
            for dy, dx in dd:
                for i in range(1, k+1):
                    ty = y + dy * i
                    tx = x + dx * i
                    if ty < 0 or ty >= h or tx < 0 or tx >= w or aa[ty][tx] < t:
                        break

                    if aa[ty][tx] == t:
                        continue

                    aa[ty][tx] = t
                    nq.append((ty,tx))

        q = nq

    if aa[y2][x2] == inf:
        return -1

    return aa[y2][x2]


print(main())

Submission status: Accepted

Solution code:
#import heapq
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
#que = []
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  #p= heapq.heappop(que)[1]
  #x,y= p[0],p[1]
  p = que.popleft()
  if (p[0] == x2) & (p[1] == y2):exit(print(dp[x2][y2]))
  for i in range(4):
    for j in range(1,k+1):
      nx = p[0] + dx[i]*j
      ny = p[1] + dy[i]*j
      if not ((0 <= nx < h) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[p[0]][p[1]]:break
      if dp[nx][ny] == -1:
        #heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        que.append((nx,ny))
      dp[nx][ny] = dp[p[0]][p[1]] + 1

print(-1)

Submission status: Accepted

Solution code:
#import heapq
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
#que = []
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  #p= heapq.heappop(que)[1]
  #x,y= p[0],p[1]
  x,y = que.popleft()
  if (x == x2) & (y == y2):exit(print(dp[x2][y2]))
  for i in range(4):
    for j in range(1,k+1):
      nx = x + dx[i]*j
      ny = y + dy[i]*j
      if not ((0 <= nx < h) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[x][y]:break
      if dp[nx][ny] == -1:
        #heapq.heappush(que, (dp[nx][ny], [nx,ny]))
        que.append((nx,ny))
      dp[nx][ny] = dp[x][y] + 1

print(-1)

Submission status: Accepted

Solution code:
#import heapq
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
#que = []
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  x,y=que.popleft()
  if x==x2 and y==y2:
    exit(print(dp[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[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 c[xx][yy]=="@":break
      if 0<=dp[xx][yy]<=dp[x][y]:break
      if dp[xx][yy]==-1:que.append((xx,yy))
      dp[xx][yy]=dp[x][y]+1
print(-1)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from heapq import heappush, heappop
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = [(0, x1, y1)]
    dist[x1][y1] = 0
    while q:
        d, i, j = heappop(q)
        if dist[i][j] < d: continue
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                heappush(q, (d + 1, ni, nj))
                dist[ni][nj] = d + 1
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    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)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import collections
import sys
INF = 10**10
def main(H, W, K, x1, y1, x2, y2, C):
    dist = [[INF] * W for _ in range(H)]
    q = collections.deque([(x1, y1)])
    dist[x1][y1] = 0
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            for dt in range(1, K + 1):
                ni, nj = i + di * dt, j + dj * dt
                if not (0 <= ni < H and 0 <= nj < W): break
                if C[ni][nj] == '@': break
                if dist[ni][nj] == d + 1: continue
                if dist[ni][nj] < d + 1: break
                dist[ni][nj] = d + 1
                q.append((ni, nj))
    ans = dist[x2][y2]
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    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)]
    main(H, W, K, x1, y1, x2, y2, C)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
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

def array(*args, initial=0):
    pre = "[" * len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range(" + str(a) + ")]"
    S = pre + "{}".format(initial) + post
    return eval(S)


def main():
    H, W, K = MAP()
    x1, y1, x2, y2 = MAP()
    # 空間はINF,壁は-1, →↑←↓
    pond = array(H + 2, W + 2, 4, initial=-1)
    for h in range(1, H + 1):
        for w, c in enumerate(input(), start=1):
            if c == ".":
                for i in range(4):
                    pond[h][w][i] = INF
    # 距離(), x, y, 方向
    q = deque()
    q.append(((0, 0), x1, y1, 0))
    q.append(((0, 0), x1, y1, 1))
    q.append(((0, 0), x1, y1, 2))
    q.append(((0, 0), x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while q:
        new_q = deque()
        while q:
            (a0, a1), x, y, d = q.popleft()
            # 順方向へ進む
            nx = x + DX[d]
            ny = y + DY[d]
            # print((a0, a1), x, y, d, nx, ny)
            if pond[nx][ny][0] == -1:     # 行き止まりなら何もせず
                continue
            if pond[nx][ny][(d + 1) % 4] > a0 + 1:
                pond[nx][ny][(d + 1) % 4] = a0 + 1
                new_q.append(((a0 + 1, 0), nx, ny, (d + 1) % 4))
            if pond[nx][ny][(d - 1) % 4] > a0 + 1:
                pond[nx][ny][(d - 1) % 4] = a0 + 1
                new_q.append(((a0 + 1, 0), nx, ny, (d - 1) % 4))
            if pond[nx][ny][d] >= a0 + 1:
                pond[nx][ny][d] = a0 + 1
                if a1 + 1 < K:
                    q.append(((a0, a1 + 1), nx, ny, d))
                else:
                    new_q.append(((a0 + 1, 0), nx, ny, d))
            if (nx, ny) == (x2, y2):
                print(a0 + 1)
                return
        q = new_q
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')
 
 
def main():
    H, W, K = map(int, readline().split())
    x1, y1, x2, y2 = map(int, readline().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    C = read().split()
 
    dist = [[INF] * W for i in range(H)]
    dist[x1][y1] = 0
    d = deque([[x1, y1]])
    dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    while d:
        x, y = d.popleft()
        if (x, y) == (x2, y2):
            print(dist[x][y])
            quit()
        for dx, dy in dxy:
            xx = x
            yy = y
            for i in range(K):
                xx += dx;
                yy += dy
                if 0 <= xx < H and 0 <= yy < W and C[xx][yy] != '@':
                    if dist[xx][yy] <= dist[x][y]:
                        break
                    if dist[xx][yy] == INF:
                        d.append([xx, yy])
                    dist[xx][yy] = dist[x][y] + 1
                else:
                    break
 
    print(-1)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
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)]

def main():
    from heapq import heappush, heappop, heapify
    H, W, K = MAP()
    HH = max(H, W) + 2
    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)]

    # 0123: 上下左右
    stack = []
    heappush(stack, (0, x1, y1, 0))
    heappush(stack, (0, x1, y1, 1))
    heappush(stack, (0, x1, y1, 2))
    heappush(stack, (0, x1, y1, 3))
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        new_stack = []
        while stack:
            curr, x, y, d = heappop(stack)
            dx, dy = DX[d], DY[d]
            flag = True
            a = curr + 1
            for k in range(1, K + 1):
                xx, yy = x + k * dx, y + k * dy
                if c[xx][yy] == 0:
                    b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d - 1) % 4))
                    b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                    if b == 0 or b == a + 1:
                        heappush(new_stack, (a, xx, yy, (d + 1) % 4))
                    c[xx][yy] = a
                elif c[xx][yy] != a:
                    flag = False
                    break
            if flag:
                heappush(new_stack, (a, xx, yy, d))
            if c[x2][y2] > 0:
                print(c[x2][y2], flush=True)
                exit(0)
        stack = new_stack

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop, heapify
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)]

def main():
    H, W, K = MAP()
    HH = max(H, W) + 2
    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)]

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

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
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)]

def main():
    H, W, K = MAP()
    HH = max(H, W) + 2
    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)]

    # 0123: 上下左右
    stack = deque([(x1, y1, 0), (x1, y1, 1),
                   (x1, y1, 2), (x1, y1, 3)])
    append, popleft = stack.append, stack.popleft
    DX = (1, 0, -1, 0)
    DY = (0, 1, 0, -1)
    while stack:
        x, y, d = popleft()
        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:
                b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                if b == 0 or b == a + 1:
                    append((xx, yy, (d - 1) % 4))
                b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                if b == 0 or b == a + 1:
                    append((xx, yy, (d + 1) % 4))
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            append((xx, yy, 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 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)]

def main():
    H, W, K = MAP()
    HH = max(H, W) + 2
    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)]

    # 0123: 上下左右
    stack = deque([((x1 * HH + y1) << 2) | 0, ((x1 * HH + y1) << 2) | 1,
                   ((x1 * HH + y1) << 2) | 2, ((x1 * HH + 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, HH)
        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:
                b = c[xx + DX[(d - 1) % 4]][yy + DY[(d - 1) % 4]]
                if b == 0 or b == a + 1:
                    append(((xx * HH + yy) << 2) + (d - 1) % 4)
                b = c[xx + DX[(d + 1) % 4]][yy + DY[(d + 1) % 4]]
                if b == 0 or b == a + 1:
                    append(((xx * HH + yy) << 2) + (d + 1) % 4)
                c[xx][yy] = a
            elif c[xx][yy] != a:
                flag = False
                break
        if flag:
            append(((xx * HH + yy) << 2) + d)
        if c[x2][y2] > 0:
            print(c[x2][y2])
            return

    print(-1)
    return


if __name__ == '__main__':
    main()