Problem:


Score : 600 points

Problem Statement

Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.

Some of the squares have a lotus leaf on it and cannot be entered.
The square (i,j) has a lotus leaf on it if c_{ij} is @, and it does not if c_{ij} is ..

In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west.
The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.

Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2).
If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Constraints

1 \leq H,W,K \leq 10^6

H \times W \leq 10^6

1 \leq x_1,x_2 \leq H

1 \leq y_1,y_2 \leq W

x_1 \neq x_2 or y_1 \neq y_2.

c_{i,j} is . or @.

c_{x_1,y_1} = .

c_{x_2,y_2} = .

All numbers in input are integers.

Input

Input is given from Standard Input in the following format:

H W K
x_1 y_1 x_2 y_2
c_{1,1}c_{1,2} .. c_{1,W}
c_{2,1}c_{2,2} .. c_{2,W}
:
c_{H,1}c_{H,2} .. c_{H,W}

Output

Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2), or print -1 if the travel is impossible.

Sample Input 1

3 5 2
3 2 3 4
.....
.@..@
..@..

Sample Output 1

5

Initially, Snuke is at the square (3,2).
He can reach the square (3, 4) by making five strokes as follows:

From (3, 2), go west one square to (3, 1).

From (3, 1), go north two squares to (1, 1).

From (1, 1), go east two squares to (1, 3).

From (1, 3), go east one square to (1, 4).

From (1, 4), go south two squares to (3, 4).

Sample Input 2

1 6 4
1 1 1 6
......

Sample Output 2

2

Sample Input 3

3 3 1
2 1 2 3
.@.
.@.
.@.

Sample Output 3

-1



Sample input:
3 5 2
3 2 3 4
.....
.@..@
..@..


Sample output:
5

Submission status: Accepted

Solution code:
## coding: UTF-8


H,W,K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
x1-=1
y1-=1
x2-=1
y2-=1
#1-index to 0-index


c = []
for i in range(H):
    c.append(input())

fresh = [True] * (H*W)
count = [-1] * (H*W)

queue = [x1*W+y1] #now <- start
count[x1*W+y1] = 0 #start -> step = 0
fresh[x1*W+y1] = False
n = [] #next
for i in range(H):
    for j in range(W):
        if(c[i][j] == '@'):
            fresh[i*W+j] = False

#print(fresh)
#print(count)
#print(queue)

step = 1
status = True
while status:
    if(len(queue) > 0):
        pivot = queue.pop()
        #右へ移動
        #if(pivot%W != W-1):#and fresh[pivot+1]):
        for g in range(1, K+1):
            if((pivot+g)%W != 0 and fresh[pivot+g]):
                n.append(pivot+g)
                count[pivot+g] = step
                #fresh[pivot+g] = False false後回し
            else:
                break
        #左へ移動
        #if(pivot%W != 0): #and fresh[pivot-1]):
        for g in range(1, K+1):
            if((pivot-g)%W != W-1 and fresh[pivot-g]):
                n.append(pivot-g)
                count[pivot-g] = step
                #fresh[pivot-g] = False false後回し 
            else:
                break   
        #下へ移動
        #if( int(pivot/W)<(H-1) and fresh[pivot+W]):
        for g in range(1, K+1):
            if( (pivot+g*W)//W < H and fresh[pivot+g*W]):
                n.append(pivot+g*W)
                count[pivot+g*W] = step
                #fresh[pivot+g * W] = False false後回し
            else:
                break    
        #上へ移動
        #if( int(pivot/W)>0 and fresh[pivot-W] ):
        for g in range(1, K+1):
            if( (pivot-g*W)>= 0 and fresh[pivot-g*W] ):
                n.append(pivot-g*W)
                count[pivot-g*W] = step
                #fresh[pivot-g*W] = False
            else:
                break
    elif(len(n)>0): 
        n = sorted(n)
        last = -1
        l = []
        for i in range(len(n)):
            if last != n[i]:
                l.append(n[i])
                last = n[i]
        for e in l:
            fresh[e] = False
        queue = l
        n = []
        #print('step{}end, queue:{}, n:{}, fresh:{}, count:{}'.format(step, queue, n, fresh, count))
        step += 1
    else:
        status = False            


print(count[x2*W+y2])

Submission status: Accepted

Solution code:
h,w,k = map(int, input().split())
sx,sy,gx,gy = map(int, input().split())
sx-=1
sy-=1
gx-=1
gy-=1

grid = ['' for _ in range(h)]

for i in range(h):
    grid[i] = input()
INF = 1001001001  
costgrid = [[INF]*w for _ in range(h)]

import heapq

q = []
q.append((0,sx,sy))

dx = (0,1,0,-1)
dy = (1,0,-1,0)
ans=INF
while q:
    cost,x,y = heapq.heappop(q)
    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):
                break
            if(not 0<=ny<w):
                break
            if(grid[nx][ny]=='@'):
                break
            if(costgrid[nx][ny]<=cost):
                break
            if(costgrid[nx][ny]>cost+1):
                costgrid[nx][ny]=cost+1
                heapq.heappush(q,(cost+1,nx,ny))
                if nx==gx and ny==gy:
                    ans=min(costgrid[nx][ny],ans)
                    q=[]

if ans!=INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from collections import deque

def main():
	h,w,k=MI()
	x1,y1,x2,y2=MI()
	G=["@"]*(w+2)
	for _ in range(h):
		G.append("@")
		G+=(list(map(str,input().rstrip())))
		G.append("@")
	G+=["@"]*(w+2)
	#print(G)


	G[x1*(w+2)+y1]=0
	#print(G)

	Q=deque()
	Q.append((x1*(w+2)+y1,0))

	while Q:
		#print(Q)
		now,d=Q.popleft()
		#print(Q)
		for i in range(1,k+1):
			if G[now+i]==d or G[now+i]=="@":
				break
			elif G[now+i]==".":
				G[now+i]=d+1
				Q.append([now+i,d+1])
			elif G[now+i]==d+1:
				continue
			else:
				break


		for i in range(1,k+1):
			if G[now-i]==d or G[now-i]=="@":
				break
			elif G[now-i]==".":
				G[now-i]=d+1
				Q.append([now-i,d+1])
			elif G[now-i]==d+1:
				continue
			else:
				break

		for i in range(1,k+1):
			if G[now+(w+2)*i]==d or G[now+(w+2)*i]=="@":
				break
			elif G[now+(w+2)*i]==".":
				G[now+(w+2)*i]=d+1
				Q.append([now+(w+2)*i,d+1])
			elif G[now+(w+2)*i]==d+1:
				continue
			else:
				break


		for i in range(1,k+1):
			if G[now-(w+2)*i]==d or G[now-(w+2)*i]=="@":
				break
			elif G[now-(w+2)*i]==".":
				G[now-(w+2)*i]=d+1
				Q.append([now-(w+2)*i,d+1])
			elif G[now-(w+2)*i]==d+1:
				continue
			else:
				break
		#print(Q)
	#print(G)

	if G[x2*(w+2)+y2]==".":
		print(-1)
	else:
		print(G[x2*(w+2)+y2])


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


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

    H, W, K = map(int, input().split())
    sh, sw, gh, gw = map(int, input().split())
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    seen = [[1] * W for _ in range(H)]
    for h in range(H):
        line = input().rstrip('\n')
        for w in range(W):
            if line[w] == "@":
                seen[h][w] = 2

    #d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    que = deque()
    que.append((sh, sw))
    seen_d = [[[0] * W for _ in range(H)] for _ in range(4)]
    seen[sh][sw] = 0
    while que:
        h, w = que.popleft()
        for id in range(4):
            dh, dw = d[id]
            h_new = h
            w_new = w
            for _ in range(K):
                flg = 1
                flggg = 0
                h_new += dh
                w_new += dw
                if 0 <= h_new < H and 0 <= w_new < W:
                    if seen[h_new][w_new] == 1:
                        seen[h_new][w_new] = seen[h][w] - 1
                        seen_d[id][h_new][w_new] = 1
                        que.append((h_new, w_new))
                        flg = 0
                    elif seen[h_new][w_new] <= 0:
                        if seen_d[id][h_new][w_new] == 0:
                            if seen[h_new][w_new] != seen[h][w]:
                                seen_d[id][h_new][w_new] = 1
                                flg = 0
                if flg:
                    break
    if seen[gh][gw] < 0:
        print(-seen[gh][gw])
    else:
        print(-1)
    #[print(seen[h]) for h in range(H)]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

H, W, K=map(int, input().split())
x1, y1, x2, y2=map(int, input().split())
c=['@'*(W+2)]+['@'+input()+'@' for _ in range(H)]+['@'*(W+2)]
l=[[-2]*(W+2) for _ in range(H+2)]
ll=[[-2]*(W+2) for _ in range(H+2)]
q=[[0, x1, y1]]

heapq.heapify(q)
ll[x1][y1]=0

while q:
  tmp=heapq.heappop(q)
  if ll[tmp[1]][tmp[2]]==tmp[0]:
    l[tmp[1]][tmp[2]]=tmp[0]
  else:
    continue
  
  j=1
  while j<=K and c[tmp[1]-j][tmp[2]]=='.':
    if l[tmp[1]-j][tmp[2]]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1]-j, tmp[2]])
      l[tmp[1]-j][tmp[2]]=-1
      ll[tmp[1]-j][tmp[2]]=tmp[0]+1
      j+=1
    elif ll[tmp[1]-j][tmp[2]]==tmp[0]+1:
      j+=1
    else:
      j=K+1
    
  j=1
  while j<=K and c[tmp[1]+j][tmp[2]]=='.':
    if l[tmp[1]+j][tmp[2]]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1]+j, tmp[2]])
      l[tmp[1]+j][tmp[2]]=-1
      ll[tmp[1]+j][tmp[2]]=tmp[0]+1
      j+=1
    elif ll[tmp[1]+j][tmp[2]]==tmp[0]+1:
      j+=1
    else:
      j=K+1
      
  j=1
  while j<=K and c[tmp[1]][tmp[2]-j]=='.':
    if l[tmp[1]][tmp[2]-j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]-j])
      l[tmp[1]][tmp[2]-j]=-1
      ll[tmp[1]][tmp[2]-j]=tmp[0]+1
      j+=1
    elif ll[tmp[1]][tmp[2]-j]==tmp[0]+1:
      j+=1
    else:
      j=K+1
      
  j=1
  while j<=K and c[tmp[1]][tmp[2]+j]=='.':
    if l[tmp[1]][tmp[2]+j]==-2:
      heapq.heappush(q, [tmp[0]+1, tmp[1], tmp[2]+j])
      l[tmp[1]][tmp[2]+j]=-1
      ll[tmp[1]][tmp[2]+j]=tmp[0]+1
      j+=1
    elif ll[tmp[1]][tmp[2]+j]==tmp[0]+1:
      j+=1
    else:
      j=K+1

if l[x2][y2]<0:
  print(-1)
else:
  print(l[x2][y2])

Submission status: Accepted

Solution code:
import queue

H,W,K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())

li = [list(input()) for _ in range(H)]
cnt = [[10**10 for _ in range(W)] for _ in range(H)]
cnt2 = [[10**10 for _ in range(W)] for _ in range(H)]



xy = [[1,0], [0,1], [-1,0], [0,-1]]

q = queue.Queue()
q.put([x1-1,y1-1,0])
cnt[x1-1][y1-1] = 0

while not(q.empty()):
    mm = q.get()
    x = mm[0]
    y = mm[1]
    cst = mm[2]

    for i in range(4):
        # print(x,y)
        for j in range(1,K+1):
            nx = x+xy[i][0]*j
            ny = y+xy[i][1]*j
            # print(nx,ny)
            
            if nx>=0 and nx<H and ny>=0 and ny<W and li[nx][ny]==".":
                if cnt[nx][ny]!=10**10 and cnt[nx][ny]<cst+1:
                    break
                elif cnt[nx][ny]!=10**10:
                    continue
                else:
                    cnt[nx][ny] = cst + 1
                    q.put([nx,ny,cst+1])
            else:
                break

if cnt[x2-1][y2-1]==10**10:
    print(-1)
else:
    print(cnt[x2-1][y2-1])

# for i in range(H):
#     for j in range(W):
#         print("{:>10}".format(cnt[i][j]),end="")
#     print()

Submission status: Accepted

Solution code:
from collections import deque

H, W, K = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
c = list(list(input())for _ in range(H))
cost = [[H*W+1]*W for _ in range(H)]
cost[x1-1][y1-1] = 0
queue = deque([[x1-1,y1-1]])
while queue:
    x,y = queue.popleft()
    for vecx,vecy in [[0,1],[1,0],[-1,0],[0,-1]]:
        for k in range(1,K+1):
            nx,ny = x+k*vecx, y+k*vecy
            if not(0<=nx<H) or not(0<=ny<W):
                break
            if c[nx][ny] == '@':
                break
            if cost[nx][ny] > cost[x][y]+1:
                cost[nx][ny] = cost[x][y]+1
                queue.append([nx,ny])
            elif cost[nx][ny] < cost[x][y]+1:
                break
if cost[x2-1][y2-1] == H*W+1:
    print(-1)
else:
    print(cost[x2-1][y2-1])

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    H, W = len(grid), len(grid[0])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    dist = list2d(H, W, INF)
    que = deque()
    for h, w in src:
        que.append((h, w))
        dist[h][w] = 0
    while que:
        h, w = que.popleft()
        for dh, dw in directions:
            for k in range(1, K+1):
                h2 = h + dh*k
                w2 = w + dw*k
                if grid[h2][w2] == '@':
                    break
                if dist[h2][w2] < dist[h][w] + 1:
                    break
                elif dist[h2][w2] != INF:
                    continue
                dist[h2][w2] = dist[h][w] + 1
                que.append((h2, w2))
    return dist

H, W, K = MAP()
x1, y1, x2, y2 = MAP()
grid = build_grid(H, W, '@', str, space=0, padding=1)

res = bfs(grid, [(x1, y1)])
ans = res[x2][y2]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
      #queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()#queueに入っていたものを消す。
        if [y, x] == [gy, gx]:#もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
          p = 0
          l = 1
          while p == 0:
              new_y, new_x = y + j * l, x + k * l 
              if (0 <= new_y < H) and (0 <= new_x < W): 
                if maze[new_y][new_x] == "@":
                  p = 1
                elif visited[new_y][new_x] == -1:#まだ来たことない点だったという条件
                  visited[new_y][new_x] = visited[y][x] + 1
                  queue.append([new_y, new_x])#新しい点を足す。
                elif visited[new_y][new_x] < visited[y][x] + 1:
                  p = 1
              else:
                p = 1
              l += 1
              if l == K + 1:
                p = 1

H, W, K = map(int, input().split())
#K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
C = [0] * H
for i in range(H):
  C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
#print(visited)
print(visited[x2][y2])

Submission status: Accepted

Solution code:
from collections import deque
n, m, k = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
INF = float("inf")
d = [[INF] * m for _ in range(n)]
t = [[] for i in range(n)]
for i in range(n):
    a = list(input())
    t[i] = a
 

sx, sy, gx, gy = sx - 1, sy - 1, gx - 1, gy - 1
 
 
def bfs():
    que = deque()
    que.append((sx, sy))
    d[sx][sy] = 0
 
    while len(que):
        x, y = que.popleft()
        if x == gx and y == gy:
            break
        for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            for i in range(1, k + 1):
                nx, ny = x + i * dx, y + i * dy
                if not 0 <= nx < n or not 0 <= ny < m or t[nx][ny] != "." or d[nx][ny] <= d[x][y]:
                    break
                else:
                    if d[nx][ny] > d[x][y] + 1:
                        d[nx][ny] = d[x][y] + 1
                        que.append((nx, ny))
 
    return d[gx][gy]
 
 
ans = bfs()
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


input = iter(sys.stdin.readlines()).__next__

R, C, K = [int(x) for x in input().split()]
X1, Y1, X2, Y2 = [int(x) - 1 for x in input().split()]  # 0 indexed

grid = [input().rstrip() for r in range(R)]

source = (X1, Y1)
q = deque([source])
dist = {source: 0}


def getNbr(node, currDist):
    r, c = node
    ret = []
    for dr, dc in [(0, 0), (-1, 0), (0, -1), (0, 1), (1, 0)]:
        for k in range(1, K + 1):
            nr = r + dr * k
            nc = c + dc * k
            if not (0 <= nr < R and 0 <= nc < C):
                break
            if grid[nr][nc] == "@" or ((nr, nc) in dist and dist[(nr, nc)] <= d):
                break
            ret.append((nr, nc))
    return ret


while q:
    node = q.popleft()
    d = dist[node]
    for nbr in getNbr(node, d):
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = d + 1


if False:
    for row in grid:
        print(row)
    print()
    for r in range(R):
        for c in range(C):
            print(dist.get((r, c), "?"), end=" ")
        print()


if (X2, Y2) in dist:
    print(dist[(X2, Y2)])
else:
    print(-1)

Submission status: Accepted

Solution code:
from queue import Queue
INF = 10 ** 6 + 1
H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
D = [[INF for i in range(W)] for j in range(H)]
D[x1-1][y1-1] = 0
tx = [1,0,-1,0]
ty = [0,1,0,-1]

q = Queue()
q.put([x1-1,y1-1,0])

while not q.empty():
    x, y, k = q.get()
    if x == x2 - 1 and y == y2 - 1:
        break
    for i in range(4):
        nx = x
        ny = y
        for _ in range(K):
            nx += tx[i]
            ny += ty[i]
            if (not (0 <= nx <= H-1 and 0 <= ny <= W-1)) or MAP[nx][ny] == '@' or D[nx][ny] < k + 1:
                break
            if D[nx][ny] == k + 1:
                continue
            D[nx][ny] = k + 1
            q.put([nx, ny, k+1])

if D[x2-1][y2-1] == INF:
    print(-1)
else:
    print(D[x2-1][y2-1])

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit
from heapq import heappop, heappush

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(b1[:],i8,i8,i8,i8,i8)', cache=True)
def main(C, H, W, S, T, K):
    INF = 10**18
    N = H * W
    q = [5 * S]
    dist = np.full((5 * N), INF, np.int64)
    dist[5 * S] = 0
    move = [0, 1, -1, W, -W]
    B = 5 * N + 10
    while q:
        x = heappop(q)
        dist_x, x = divmod(x, B)
        if dist_x > dist[x]:
            continue
        v, d = divmod(x, 5)
        if d == 0:
            # どちらかに進む
            for i in range(1, 5):
                w = v + move[i]
                y = 5 * w + i
                dist_y = dist_x + 1
                if C[w] and dist_y < dist[y]:
                    dist[y] = dist_y
                    heappush(q, B * dist_y + y)
        else:
            # 直進する
            if dist_x % K != 0:
                w = v + move[d]
                y = 5 * w + d
                dist_y = dist_x + 1
                if C[w] and dist_y < dist[y]:
                    dist[y] = dist_y
                    heappush(q, B * dist_y + y)
            # 止まって向きを変える権利を得る
            y = 5 * v
            dist_y = dist_x + (-dist_x) % K
            if dist_y < dist[y]:
                dist[y] = dist_y
                heappush(q, B * dist_y + y)
    x = dist[5 * T]
    if x == INF:
        return -1
    return dist[5 * T] // K

H, W, K = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())

C = np.zeros((H + 2, W + 2), np.bool_)
C[1:-1, 1:-1] = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'.'
C = C.ravel()
H += 2
W += 2

S = W * x1 + y1
T = W * x2 + y2

print(main(C, H, W, S, T, K))

Submission status: Accepted

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

H,W,K = map(int, input().split())
x1,y1,x2,y2 = map(int, input().split())

C = [input() for _ in range(H)]
T = [[-1 for _ in range(W)] for _ in range(H)]
T[x1-1][y1-1] = 0

que = {(x1-1,y1-1):0}
step = 1

while len(que)>0:
  que_next = {}
  for q in que.keys():
    x,y = q[0],q[1]
    for i in range(1,K+1):
      if x-i<0:
        break
      if C[x-i][y]=='@' or T[x-i][y]==1:
        break
      if x-i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next[(x-i,y)] = 0
    for i in range(1,K+1):
      if x+i>H-1:
        break
      if C[x+i][y]=='@' or T[x+i][y]==1:
        break
      if x+i==x2-1 and y==y2-1:
        print(step)
        exit()
      que_next[(x+i,y)] = 0
    for i in range(1,K+1):
      if y-i<0:
        break
      if C[x][y-i]=='@' or T[x][y-i]==1:
        break
      if x==x2-1 and y-i==y2-1:
        print(step)
        exit()
      que_next[(x,y-i)] = 0
    for i in range(1,K+1):
      if y+i>W-1:
        break
      if C[x][y+i]=='@' or T[x][y+i]==1:
        break
      if x==x2-1 and y+i==y2-1:
        print(step)
        exit()
      que_next[(x,y+i)] = 0
  que = que_next
  for q in que.keys():
    T[q[0]][q[1]] = 1
  step += 1

print(-1)

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

def rights(bd):
    n = len(bd)
    m = len(bd[0])
    rs = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m-1, -1, -1):
            if bd[i][j] == "@":
                rs[i][j] = 0
            elif j == m-1:
                rs[i][j] = 1
            else:
                rs[i][j] = rs[i][j+1] + 1
    return rs

def rotc(bd):
    n = len(bd)
    m = len(bd[0])
    rs = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            rs[j][n-1-i] = bd[i][j]
    return rs


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

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

right = rights(bd)
bd = rotc(bd)
up = rotc(rotc(rotc(rights(bd))))
bd = rotc(bd)
left = rotc(rotc(rights(bd)))
bd = rotc(bd)
down = rotc(rights(bd))
bd = rotc(bd)


q = deque()
rh = 1
while rh < w:
    rh *= 2
ch = 1
while ch < h:
    ch *= 2
ds = [9999999999] * (h*w+h*2*rh+w*2*ch)
q.append(x1*w+y1)
ds[x1*w+y1] = 0

# dr = (1, 0, -1, 0)
# dc = (0, 1, 0, -1)

# h*w
# h*2*rh
# w*2*ch
o0 = h*w
o1 = h*w + h*2*rh
while len(q) > 0:
    cur = q.popleft()
    curd = ds[cur]
    if cur < o0:
        r = cur // w
        c = cur % w

        rr = min(c + right[r][c] - 1, c + k) + 1
        ll = max(c - left[r][c] + 1, c - k)
        while ll != 0:
            f = ll & -ll
            if ll + f > rr:
                break
            tar = o0 + r*2*rh + (rh+ll)//f
            if ds[tar] > ds[cur] + 1:
                ds[tar] = ds[cur] + 1
                q.append(tar)
            ll += f
        while ll < rr:
            f = rr & -rr
            tar = o0 + r*2*rh + (rh+rr)//f-1
            if ds[tar] > ds[cur] + 1:
                ds[tar] = ds[cur] + 1
                q.append(tar)
            rr -= f

        rr = min(r + down[r][c] - 1, r + k) + 1
        ll = max(r - up[r][c] + 1, r - k)
        while ll != 0:
            f = ll & -ll
            if ll + f > rr:
                break
            tar = o1 + c * 2*ch + (ch + ll) // f
            if ds[tar] > ds[cur] + 1:
                ds[tar] = ds[cur] + 1
                q.append(tar)
            ll += f
        while ll < rr:
            f = rr & -rr
            tar = o1 + c * 2*ch + (ch + rr) // f - 1
            if ds[tar] > ds[cur] + 1:
                ds[tar] = ds[cur] + 1
                q.append(tar)
            rr -= f
    elif cur < o1:
        cur -= o0
        r = cur // (2*rh)
        v = cur % (2*rh)
        if v >= rh:
            tar = r*w + v-rh
            if ds[tar] > curd and bd[r][v-rh] == ".":
                ds[tar] = curd
                q.appendleft(tar)
        else:
            for j in range(2*v, 2*v+2):
                tar = o0 + r*2*rh + j
                if ds[tar] > curd:
                    ds[tar] = curd
                    q.appendleft(tar)
    else:
        cur -= o1
        c = cur // (2 * ch)
        v = cur % (2 * ch)
        if v >= ch:
            tar = (v-ch) * w + c
            if ds[tar] > curd and bd[v-ch][c] == ".":
                ds[tar] = curd
                q.appendleft(tar)
        else:
            for j in range(2 * v, 2 * v + 2):
                tar = o1 + c * 2 * ch + j
                if ds[tar] > curd:
                    ds[tar] = curd
                    q.appendleft(tar)

if ds[x2*w+y2] > 9999999:
    print(-1)
else:
    print(ds[x2*w+y2])

Submission status: Accepted

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

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

print(BFS(s)[t])

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(i)-1 for i in input().split()]
ans = [[-1] * w for _ in range(h)]
ans[x1][y1] = 0
c = [input() for _ in range(h)]
qu = [(x1, y1)]


for x, y in qu:
    if x == x2 and y == y2:
        print(ans[x2][y2])
        break

    for i in range(x + 1, min(x + k + 1, h)):
        if c[i][y] == "@":
            break
        if ans[i][y] == -1:
            ans[i][y] = ans[x][y] + 1
            qu.append((i, y))
        elif ans[i][y] <= ans[x][y]:
            break
    for i in reversed(range(max(0, x - k), x)):
        if c[i][y] == "@":
            break
        if ans[i][y] == -1:
            ans[i][y] = ans[x][y] + 1
            qu.append((i, y))
        elif ans[i][y] <= ans[x][y]:
            break

    for i in range(y + 1, min(y + k + 1, w)):
        if c[x][i] == "@":
            break
        if ans[x][i] == -1:
            ans[x][i] = ans[x][y] + 1
            qu.append((x, i))
        elif ans[x][i] <= ans[x][y]:
            break
    for i in reversed(range(max(0, y - k), y)):
        if c[x][i] == "@":
            break
        if ans[x][i] == -1:
            ans[x][i] = ans[x][y] + 1
            qu.append((x, i))
        elif ans[x][i] <= ans[x][y]:
            break
else:
    print(-1)