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
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque([[x1-1,y1-1]])
dp[x1-1][y1-1]=0
def bfs(d):
    global dp,now
    l=len(now)
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub+=[[x,y+j,d]]
                cand.add((x,y+j))
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub+=[[x,y-j,d]]
                cand.add((x,y-j))
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub+=[[x+j,y,d]]
                cand.add((x+j,y))
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub+=[[x-j,y,d]]
                cand.add((x-j,y))
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now+=[i]
    if l!=0:bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

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 = [[-1] * 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 0 <= dist[xx][yy] <= dist[x][y]:
                        break
                    if dist[xx][yy] == -1:
                        d.append([xx, yy])
                    dist[xx][yy] = dist[x][y] + 1
                else:
                    break

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque([[x1-1,y1-1]])
dp[x1-1][y1-1]=0
def bfs(d):
    global dp,now
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                cand.add((x,y+j))
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                cand.add((x,y-j))
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                cand.add((x+j,y))
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                cand.add((x-j,y))
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

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():
    import sys
    read = sys.stdin.read
    readline = sys.stdin.readline
    readlines = sys.stdin.readlines
    from collections import deque

    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 = [[-1] * 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 0 <= dist[xx][yy] <= dist[x][y]:
                        break
                    if dist[xx][yy] == -1:
                        d.append([xx, yy])
                    dist[xx][yy] = dist[x][y] + 1
                else:
                    break

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
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 = [[-1]*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 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    h,w,k = map(int,input().split())
    x,y,gx,gy = map(int,input().split())
    x -= 1
    gx -= 1
    y -= 1
    gy -= 1
    c = [list(input()) for _ in range(h)]
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    que = deque()
    que.append((x,y))
    d[x][y] = 0
    while que:
        (qx,qy) = que.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            for K in range(1,k+1):
                nx = qx + dx[i]*K
                ny = qy + dy[i]*K
                if not(nx>=0 and h>nx and ny>=0 and w>ny) or c[nx][ny] == '@' or (d[nx][ny] != -1 and d[nx][ny] < d[qx][qy]+1):
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    que.append((nx,ny))
    print(d[gx][gy])
 
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    #maze=[]
    #for _ in range(h):
    #    maze.append(tuple(input()))

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        #pri(dis)
                    else:
                        break
                else:
                    break

    print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利

H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
mp = [input() for _ in range(H)]
INF = 10**10
dist = [[INF]*W for _ in range(H)]
dist[x1-1][y1-1] = 0
q = deque()
q.append((x1-1,y1-1)) # スタート地点をenqueue
while(q):
    x, y = q.popleft()
    if x==x2-1 and y==y2-1:
        print (dist[x2-1][y2-1])
        exit()
    else:
        for dx, dy in  dxdy:
            for i in range(1,K+1):
                nx = x + dx*i
                ny = y + dy*i
                if not (0<=nx<H and 0<=ny<W) or mp[nx][ny]=='@':
                    break
                if dist[nx][ny] <= dist[x][y]:
                    break 
                if dist[nx][ny] == INF:
                    q.append((nx,ny))
                    dist[nx][ny] = dist[x][y] + 1
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利

H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
mp = [input() for _ in range(H)]
INF = 10**10
dist = [[INF]*W for _ in range(H)]
dist[x1-1][y1-1] = 0
q = deque()
q.append((x1-1,y1-1)) # スタート地点をenqueue
while(q):
    x, y = q.popleft()
    if x==x2-1 and y==y2-1:
        print (dist[x2-1][y2-1])
        exit()
    else:
        for dx, dy in  dxdy:
            for i in range(1,K+1):
                nx = x + dx*i
                ny = y + dy*i
                if not (0<=nx<H and 0<=ny<W) or mp[nx][ny]=='@':
                    break
                #print(nx,ny,x,y)
                #print (dist[nx][ny] , dist[x][y])
                if dist[nx][ny] <= dist[x][y]:
                    break 
                #print(nx,ny,x,y)
                if dist[nx][ny] == INF:
                    q.append((nx,ny))
                dist[nx][ny] = dist[x][y] + 1
print(-1)

Submission status: Accepted

Solution code:
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  d=[]
  d.append((sx,sy))
  for ss in d:
    x,y=ss
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      if b[x+i][y]==0:d.append((x+i,y))
      b[x+i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      if b[x-i][y]==0:d.append((x-i,y))
      b[x-i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      if b[x][y+j]==0:d.append((x,y+j))
      b[x][y+j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      if b[x][y-j]==0:d.append((x,y-j))
      b[x][y-j]=b[x][y]+1
  print(-1)
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:
    exit(print(ans[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 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:
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:
    exit(print(ans[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 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:
from heapq import heappop, heappush

import numpy as np

from numba import njit


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


@njit('i8(i8,i8,i8,i1[:],i8,i8,i8,i8)', cache=True)
def solve(h2, w2, k, field, x1, y1, x2, y2):
    s = x1 * w2 + y1
    t = x2 * w2 + y2
    up, dw, lf, rg = reachable(field, h2, w2, k)

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

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

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

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

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

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

    return -1


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

field_tmp = [input() for _ in range(h)]
field = [0] * w2
for row in field_tmp:
    field.append(0)
    field.extend(map('@.'.index, row))
    field.append(0)
field.extend([0] * w2)
field = np.array(field, dtype=np.int8)
print(solve(h2, w2, k, field, x1, y1, x2, y2))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

import numpy as np

from numba import njit


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


@njit('i8(i8,i8,i8,i1[:],i8,i8,i8,i8)')
def solve(h2, w2, k, field, x1, y1, x2, y2):
    s = x1 * w2 + y1
    t = x2 * w2 + y2
    up, dw, lf, rg = reachable(field, h2, w2, k)

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

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

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

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

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

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

    return -1


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

field_tmp = [input() for _ in range(h)]
field = [0] * w2
for row in field_tmp:
    field.append(0)
    field.extend(map('@.'.index, row))
    field.append(0)
field.extend([0] * w2)
field = np.array(field, dtype=np.int8)
print(solve(h2, w2, k, field, x1, y1, x2, y2))

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappop, heappush

import numpy as np

from numba import njit


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


@njit('i8(i8,i8,i8,i1[:],i8,i8,i8,i8)')
def solve(h2, w2, k, field, x1, y1, x2, y2):
    s = x1 * w2 + y1
    t = x2 * w2 + y2
    up, dw, lf, rg = reachable(field, h2, w2, k)

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

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

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

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

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

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

    return -1


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

field_tmp = [input() for _ in range(h)]
field = [0] * w2
for row in field_tmp:
    field.append(0)
    field.extend(map('@.'.index, row))
    field.append(0)
field.extend([0] * w2)
field = np.array(field, dtype=np.int8)
print(solve(h2, w2, k, field, x1, y1, x2, y2))

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, w, K = na()
x1, y1, x2, y2 = na()
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1

bd = [ns() for _ in range(h)]

q = deque()
ds = [9999999999999999] * (h*w)

q.append((x1, y1))
ds[x1*w+y1] = 0
dr = (1, 0, -1, 0)
dc = (0, 1, 0, -1)
while len(q) > 0:
    r, c = q.popleft()
    for i in range(4):
        for j in range(1, K+1):
            nr, nc = r + dr[i] * j, c + dc[i] * j
            if 0 <= nr < h and 0 <= nc < w and bd[nr][nc] != "@":
                nd = ds[r*w+c] + 1
                if nd < ds[nr*w+nc]:
                    ds[nr*w+nc] = nd
                    q.append((nr, nc))
                elif nd <= ds[nr*w+nc]:
                    continue
                else:
                    break
            else:
                break
ans = ds[x2*w+y2]
if ans < 999999999999:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    X1, Y1, X2, Y2 = [int(x) for x in input().split()]
    C = [input().strip() for _ in range(H)]

    q = collections.deque()
    q.append((X1 - 1, Y1 - 1, 0))

    V = [[float("inf")] * W for j in range(H)]
    V[X1 - 1][Y1 - 1] = 0


    while q:
        c = q.popleft()
        x = c[0]
        y = c[1]
        d = c[2]

        if y == Y2 - 1 and x == X2 - 1:
            print(c[2])
            return

        e, w, n, s = True, True, True, True
        for k in range(1, K + 1):
            if not e and not w and not n and not s:
                break
            if e:
                if y + k >= W or C[x][y + k] == "@":
                    e = False
                else:
                    if V[x][y + k] == float("inf"):
                        V[x][y + k] = d + 1
                        q.append((x, y + k, d + 1))

                    if V[x][y + k] < d + 1:
                        e = False
            if w:
                if y - k < 0 or C[x][y - k] == "@":
                    w = False
                else:
                    if V[x][y - k] == float("inf"):
                        V[x][y - k] = d + 1
                        q.append((x, y - k, d + 1))
                    if V[x][y - k] < d + 1:
                        w = False

            if n:
                if x - k < 0 or C[x - k][y] == "@":
                    n = False
                else:
                    if V[x - k][y] == float("inf"):
                        V[x - k][y] = d + 1
                        q.append((x - k, y, d + 1))
                    if V[x - k][y] < d + 1:
                        n = False

            if s:
                if x + k >= H or C[x + k][y] == "@":
                    s = False
                else:
                    if V[x + k][y] == float("inf"):
                        V[x + k][y] = d + 1
                        q.append((x + k, y, d + 1))
                    if V[x + k][y] < d + 1:
                        s = False

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
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 = [[-1]*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 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

h,w,k = map(int,readline().split())
x1,y1,x2,y2 = map(int,readline().split())

c = read().split()
inf = 10**7
cost = [[inf] * (w+2) for _ in range(h+2)]
for i in range(h):
    for j in range(w):
        if(c[i][j] == '@'):
            cost[i+1][j+1] = -1

for i in range(h+2):
    cost[i][0] = -1
    cost[i][-1] = -1

for j in range(w+2):
    cost[0][j] = -1
    cost[-1][j] = -1

cost[x1][y1] = 0
stack = [(x1,y1)]

cnt = 0
while(stack):
    cnt += 1
    next = set()
    while(stack):
        x,y = stack.pop()
        for dx,dy in zip([-1,1,0,0],[0,0,-1,1]):
            for j in range(1,k+1):
                jx = x + dx*j
                jy = y + dy*j
                if(cost[jx][jy] < cnt):
                    break
                next.add((jx,jy))

    for jx,jy in next:
        cost[jx][jy] = cnt
        stack.append((jx,jy))

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

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


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, XY1XY2, C):
    q = deque()
    s = (XY1XY2[0]-1)*W + XY1XY2[1]-1
    go = (XY1XY2[2]-1)*W + XY1XY2[3]-1
    q.append(s)
    d = {s: 0}

    while q:
        u = q.popleft()
        i = u // W
        j = u % W
        e = list()
        for k in range(1, K+1):
            if i - k >= 0 and C[i-k][j] != '@':
                n = (i-k)*W + j
                if n not in d:
                    e.append(n)
                elif d[u] +1 > d[n]:
                    break
            else:
                break
        for k in range(1, K+1):
            if i + k < H and C[i+k][j] != '@':
                n = (i+k)*W + j
                if n not in d:
                    e.append(n)
                elif d[u] + 1 > d[n]:
                    break
            else:
                break
        for k in range(1, K+1):
            if j - k >= 0 and C[i][j-k] != '@':
                n = i*W + j-k
                if n not in d:
                    e.append(n)
                elif d[u] + 1 > d[n]:
                    break
            else:
                break
        for k in range(1, K+1):
            if j + k < W and C[i][j+k] != '@':
                n = i*W + j+k
                if n not in d:
                    e.append(n)
                elif d[u] + 1 > d[n]:
                    break
            else:
                break
        for v in e:
            q.append(v)
            d[v] = d[u] + 1
            if v == go:
                return d[v]

    return -1


def main():
    H, W, K = read_int_n()
    XY1XY2 = read_int_n()

    C = [read_str() for _ in range(H)]
    print(slv(H, W, K, XY1XY2, C))

    # H = 1000
    # W = 1000
    # K = 1000
    # XY1XY2 = [1, 1, H, W]
    # C = [['.'] * W for _ in range(H)]
    # for i in range(1, H, 2):
    #     if ((i + 1) // 2) % 2 == 1:
    #         for j in range(W-1):
    #             C[i][j] = '@'
    #     else:
    #         for j in range(1, W):
    #             C[i][j] = '@'

    # # for r in C:
    # #     print(r)
    # print(slv(H, W, K, XY1XY2, C))


if __name__ == '__main__':
    main()