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: Time Limit Exceeded

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())
  sx-=1
  sy-=1
  tx-=1
  ty-=1
  calc=lambda x,y:x*1000000+y
  b=[]
  for i in range(h):
    s=input()
    bb=[]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    b.append(bb)
  from collections import deque
  d=deque()
  d.append(calc(sx,sy))
  s=set()
  while d:
    x,y=divmod(d.popleft(),1000000)
    if calc(x,y)in s:
      s.discard(calc(x,y))
      continue
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if x-i<0:break
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append(calc(x-i,y))
      if b[x-i][y]!=0:
        s.add(calc(x-i,y))
      b[x-i][y]=b[x][y]+1
    for i in range(1,k+1):
      if x+i==h:break
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append(calc(x+i,y))
      if b[x+i][y]!=0:
        s.add(calc(x+i,y))
      b[x+i][y]=b[x][y]+1
    for j in range(1,k+1):
      if y-j<0:break
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append(calc(x,y-j))
      if b[x][y-j]!=0:
        s.add(calc(x,y-j))
      b[x][y-j]=b[x][y]+1
    for j in range(1,k+1):
      if y+j==w:break
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append(calc(x,y+j))
      if b[x][y+j]!=0:
        s.add(calc(x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

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 = []

    dd = [[-1 for _ in range(w)] for _ in range(h)]
    que1 = deque()
    que1.append((x,y))
    dd[x][y] = 0
    while que1:
        (qx,qy) = que1.popleft()
        if qx == gx and qy == gy:
            break
        for i in range(4):
            nx = qx + dx[i]
            ny = qy + dy[i]
            if not(nx>=0 and h>nx and ny>=0 and w>ny):
                continue
            if c[nx][ny] != "@" and dd[nx][ny] == -1:
                dd[nx][ny] = dd[qx][qy] + 1
                que1.append((nx,ny))
    if dd[gx][gy] == -1:
        print(-1)
        return


    heappush(que,(0,(x,y)))
    d[x][y] = 0
    while que:
        [num,(qx,qy)] = heappop(que)
        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] == '@':
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    heappush(que,[d[nx][ny],(nx,ny)])
    print(d[gx][gy])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import os
from collections import deque

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W, K = list(map(int, sys.stdin.buffer.readline().split()))
sx, sy, gx, gy = list(map(int, sys.stdin.buffer.readline().split()))
C = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(H)]

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

u_hist = [[(INF, INF, INF)] * W for _ in range(H)]
d_hist = [[(INF, INF, INF)] * W for _ in range(H)]
l_hist = [[(INF, INF, INF)] * W for _ in range(H)]
r_hist = [[(INF, INF, INF)] * W for _ in range(H)]
u_hist[sx][sy] = (0, 0, 0)
d_hist[sx][sy] = (0, 0, 0)
l_hist[sx][sy] = (0, 0, 0)
r_hist[sx][sy] = (0, 0, 0)
hist = (u_hist, d_hist, l_hist, r_hist)
D = ((0, 1), (1, 0), (0, -1), (-1, 0))

ans = INF
que = deque([(0, 0, sx, sy, 0), (0, 0, sx, sy, 1), (0, 0, sx, sy, 2), (0, 0, sx, sy, 3)])
while que:
    s, cnt, x, y, d = que.popleft()
    p = s + cnt / K
    if (p, s, cnt) > hist[d][x][y]:
        continue
    if x == gx and y == gy:
        ans = min(ans, s + (cnt + K - 1) // K)
    for i in range(4):
        nd = (d + i) % 4
        dx, dy = D[nd]
        nx = x + dx
        ny = y + dy
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if C[nx][ny] == '@':
            continue
        if nd == d:
            np = s + (cnt + 1) / K
            if hist[nd][nx][ny] < (np, s, cnt + 1):
                continue
            hist[nd][nx][ny] = (np, s, cnt + 1)
            que.append((s, cnt + 1, nx, ny, nd))
        else:
            ns = s + (cnt + K - 1) // K
            ncnt = 1
            np = ns + 1 / K
            if hist[nd][nx][ny] < (np, ns, ncnt):
                continue
            hist[nd][nx][ny] = (np, ns, ncnt)
            que.append((ns, ncnt, nx, ny, nd))

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

Submission status: Time Limit Exceeded

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]:
                break
if cost[x2-1][y2-1] == H*W+1:
    print(-1)
else:
    print(cost[x2-1][y2-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from functools import lru_cache
h,w,k = map(int,input().split())
k = min(k,10**4)
sy,sx,gy,gx = map(int,input().split())
sy,sx,gy,gx = sy-1,sx-1,gy-1,gx-1
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = deque()
now.append((sy,sx,-1))
gone[sy][sx] = 1
if map[gy][gx] == "@":
    print(-1)
    exit()
for ans in range(10 ** 6+1):
    next = deque()
    while now:
        y,x,status = now.popleft()
        if y == gy and x == gx:
            print(ans)
            exit()
        if status != 0 or (y>0 and map[y-1][x] != "@"):
            for i in range(1,k+1):
                if y-i < 0 or map[y-i][x] == "@":
                    break
                else:
                    if gone[y-i][x] == 0:
                        gone[y-i][x] = 1
                        next.append((y-i,x,0))
        if status != 1 or (y<h-1 and map[y+1][x] != "@"):
            for i in range(1,k+1):
                if y +i >= h or map[y+i][x] == "@":
                    break
                else:
                    if gone[y + i][x] == 0:
                        gone[y + i][x] = 1
                        next.append((y+i,x,1))
        if status != 2 or (x>0 and map[y][x-1] != "@"):
            for i in range(1,k+1):
                if x - i < 0 or map[y][x-i] == "@":
                    break
                else:
                    if gone[y][x-i] == 0:
                        gone[y][x-i] = 1
                        next.append((y,x-i,2))
        if status != 3 or (x<w-1 and map[y][x+1] != "@"):
            for i in range(1, k + 1):
                if x+i >= w or map[y][x+i] == "@":
                    break
                else:
                    if gone[y][x+i] == 0:
                        gone[y][x+i] = 1
                        next.append((y,x+i,3))
    if next == deque():
        print(-1)
        exit()
    now = next

Submission status: Time Limit Exceeded

Solution code:
import heapq

h, w, k = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
c = [input() for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

def is_in_range(x, y):
    return 0 <= x < h and 0 <= y < w

def calc_cost(x, y):
    return 0 if gy == y and gx == x else (1 if gy == y or gx == x else 2)

pq = [(0, 0, (sx, sy))]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
visited[sx][sy] = True
heapq.heapify(pq)

def search():
    while len(pq) != 0:
        _, cost, (cx, cy) = heapq.heappop(pq)
        # print(cost, (cx, cy))
        for dx, dy in d:
            for kk in range(1, k + 1):
                nx, ny = cx + dx * kk, cy + dy * kk
                if not is_in_range(nx, ny):
                    continue
                if c[nx][ny] == '@':
                    break
                # print((nx, ny))
                if not visited[nx][ny]:
                    visited[nx][ny] = True
                    if c[nx][ny] == '.':
                        if ny == gy and nx == gx:
                            return cost + 1
                        heapq.heappush(pq, (calc_cost(nx, ny) + cost + 1, cost + 1, (nx, ny)))

    return -1

print(search())

Submission status: Time Limit Exceeded

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
                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: Time Limit Exceeded

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]==".":
				G[now+i]=d+1
				Q.append([now+i,d+1])
			elif G[now+i]=="@":
				break
			elif G[now+i]>d:
				G[now+i]=d+1
				Q.append([now+i,d+1])
			else:
				break

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

		for i in range(1,k+1):
			if 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]=="@":
				break
			elif G[now+(w+2)*i]>d:
				G[now+(w+2)*i]=d+1
				Q.append([now+(w+2)*i,d+1])
			else:
				break

		for i in range(1,k+1):
			if 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]=="@":
				break
			elif G[now-(w+2)*i]>d:
				G[now-(w+2)*i]=d+1
				Q.append([now-(w+2)*i,d+1])
			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: Time Limit Exceeded

Solution code:
from collections import deque
from functools import lru_cache
h,w,k = map(int,input().split())
sy,sx,gy,gx = map(int,input().split())
sy,sx,gy,gx = sy-1,sx-1,gy-1,gx-1
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = deque()
now.append((sy,sx,-1))
gone[sy][sx] = 1
if map[gy][gx] == "@":
    print(-1)
    exit()
for ans in range(10 ** 6):
    next = deque()
    while now:
        y,x,status = now.popleft()
        if y == gy and x == gx:
            print(ans)
            exit()
        if status != 0 or (y>0 and map[y-1][x] != "@"):
            for i in range(1,k+1):
                if y-i < 0 or map[y-i][x] == "@":
                    break
                else:
                    if gone[y-i][x] == 0:
                        gone[y-i][x] = 1
                        next.append((y-i,x,0))
        if status != 1 or (y<h-1 and map[y+1][x] != "@"):
            for i in range(1,k+1):
                if y +i >= h or map[y+i][x] == "@":
                    break
                else:
                    if gone[y + i][x] == 0:
                        gone[y + i][x] = 1
                        next.append((y+i,x,1))
        if status != 2 or (x>0 and map[y][x-1] != "@"):
            for i in range(1,k+1):
                if x - i < 0 or map[y][x-i] == "@":
                    break
                else:
                    if gone[y][x-i] == 0:
                        gone[y][x-i] = 1
                        next.append((y,x-i,2))
        if status != 3 or (x<w-1 and map[y][x+1] != "@"):
            for i in range(1, k + 1):
                if x+i >= w or map[y][x+i] == "@":
                    break
                else:
                    if gone[y][x+i] == 0:
                        gone[y][x+i] = 1
                        next.append((y,x+i,3))
    if next == deque():
        print(-1)
        exit()
    now = next
print(-1)

Submission status: Time Limit Exceeded

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

H,W,K=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j]==".":
            MAP[i][j]=1<<30
        else:
            MAP[i][j]=-1

Q=[]
b=10**6+1
bb=b*b
Q.append(0+(x1-1)*b+(y1-1)*bb)
MAP[x1-1][y1-1]=0

while Q:
    P=heapq.heappop(Q)
    y=P//bb
    x=(P%bb)//b
    c=P%b

    if MAP[x][y]<c:
        continue

    for i in range(1,K+1):
        if 0<=x+i<H and 0<=y<W and (MAP[x+i][y]==1<<30 or MAP[x+i][y]>MAP[x][y]):
            MAP[x+i][y]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+(x+i)*b+y*bb))
        else:
            break

    for i in range(1,K+1):
        if 0<=x-i<H and 0<=y<W and (MAP[x-i][y]==1<<30 or MAP[x-i][y]>MAP[x][y]):
            MAP[x-i][y]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+(x-i)*b+y*bb))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y+i<W and (MAP[x][y+i]==1<<30 or MAP[x][y+i]>MAP[x][y]):
            MAP[x][y+i]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+x*b+(y+i)*bb))
        else:
            break

    for i in range(1,K+1):
        if 0<=x<H and 0<=y-i<W and (MAP[x][y-i]==1<<30 or MAP[x][y-i]>MAP[x][y]):
            MAP[x][y-i]=MAP[x][y]+1
            heapq.heappush(Q,(MAP[x][y]+1+x*b+(y-i)*bb))
        else:
            break
if MAP[x2-1][y2-1]==1<<30:
    print(-1)
else:
    print(MAP[x2-1][y2-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from functools import lru_cache

@lru_cache
def solve():
    H, W, K = map(int, input().split(" "))
    i1, j1, i2, j2 = map(lambda x: int(x)-1, input().split(" "))
    board = []
    for _ in range(H):
        board.append( list(input()))
    visited = [ [-1]*W for _ in range(H) ]

    directions = [ (-1,0),(1,0),(0,-1),(0,1) ]
    q = deque()
    visited[i1][j1] = 0
    q.append( (i1, j1, 0) )
    while q:
        i, j, v  = q.popleft()
        if (i,j)==(i2,j2) :
            return visited[i][j]
        if v > visited[i][j] :
            continue

        for di, dj in directions:
            for k in range(1, K+1):
                ni = di*k+i
                nj = dj*k+j
                if ni < 0 or ni >= H or nj < 0 or nj >= W or board[ni][nj] == '@' :
                    break 
                if visited[ni][nj] > visited[i][j] + 1 :
                    break 

                if visited[ni][nj] == -1 :
                    visited[ni][nj] = visited[i][j] + 1
                    q.append( (ni, nj, visited[ni][nj]) )

    return visited[i2][j2]

print(solve())

Submission status: Time Limit Exceeded

Solution code:
r, c, k = map(int, input().split())
sx, sy, gx, gy = map(int, input().split())
C = [input() for _ in range(r)]

from collections import deque

q = deque()
D = [[0]*c for _ in range(r)]
q.append((sx-1, sy-1))
D[sx-1][sy-1] = 1

dxy = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    x, y = q.popleft()
    for dx, dy in dxy:
        i = 0
        for _ in range(k):
            i += 1
            _x, _y = x + dx*i, y + dy*i
            if 0<=_x<r and 0<=_y<c and D[_x][_y] in [0, D[x][y] + 1] and C[_x][_y] == '.':
                D[_x][_y] = D[x][y] + 1
                q.append((_x, _y))
                if _x == gx-1 and _y == gy-1:
                    print(D[gx-1][gy-1]-1)
                    exit()
            else:
                break

print(D[gx-1][gy-1]-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from functools import lru_cache
h,w,k = map(int,input().split())
k = min(k,10**5)
sy,sx,gy,gx = map(int,input().split())
sy,sx,gy,gx = sy-1,sx-1,gy-1,gx-1
map = [str(input()) for i in range(h)]
gone = [[0] * w for i in range(h)]
now = deque()
now.append((sy,sx,-1))
gone[sy][sx] = 1
if map[gy][gx] == "@":
    print(-1)
    exit()
for ans in range(10 ** 6):
    next = deque()
    while now:
        y,x,status = now.popleft()
        if y == gy and x == gx:
            print(ans)
            exit()
        if status != 0 or (y>0 and map[y-1][x] != "@"):
            for i in range(1,k+1):
                if y-i < 0 or map[y-i][x] == "@":
                    break
                else:
                    if gone[y-i][x] == 0:
                        gone[y-i][x] = 1
                        next.append((y-i,x,0))
        if status != 1 or (y<h-1 and map[y+1][x] != "@"):
            for i in range(1,k+1):
                if y +i >= h or map[y+i][x] == "@":
                    break
                else:
                    if gone[y + i][x] == 0:
                        gone[y + i][x] = 1
                        next.append((y+i,x,1))
        if status != 2 or (x>0 and map[y][x-1] != "@"):
            for i in range(1,k+1):
                if x - i < 0 or map[y][x-i] == "@":
                    break
                else:
                    if gone[y][x-i] == 0:
                        gone[y][x-i] = 1
                        next.append((y,x-i,2))
        if status != 3 or (x<w-1 and map[y][x+1] != "@"):
            for i in range(1, k + 1):
                if x+i >= w or map[y][x+i] == "@":
                    break
                else:
                    if gone[y][x+i] == 0:
                        gone[y][x+i] = 1
                        next.append((y,x+i,3))
    if next == deque():
        print(-1)
        exit()
    now = next
print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  import sys
  input=sys.stdin.readline
  calc=lambda x,y:x*1000007+y
  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=deque()
  d.append(calc(sx,sy))
  s=set()
  while d:
    x,y=divmod(d.popleft(),1000007)
    if calc(x,y)in s:
      s.discard((x,y))
      continue
    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
      d.append(calc(x-i,y))
      if b[x-i][y]!=0:
        s.add((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
      d.append(calc(x+i,y))
      if b[x+i][y]!=0:
        s.add((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
      d.append(calc(x,y-j))
      if b[x][y-j]!=0:
        s.add((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
      d.append(calc(x,y+j))
      if b[x][y+j]!=0:
        s.add((x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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):
        for e in n:
            fresh[e] = False
        queue = n
        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: Time Limit Exceeded

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

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

grid = [None] * H
for i in range(H):
  grid[i] = readline().rstrip()
  
# 操作としてあり得るのは、
# ・1かきでKマス進む or @の直前まで進む
# ・1かきでKマス未満進んで方向転換する
# 
# ・前回水をかいてから何マス進んでいるか
# ・前回水をかいて、どのむき(U,D,L,R)に進んでいるか
#  (来たところに戻ることはあり得ないので)
# ・今までに何回水をかいたか
# ・今どこにいるか
# 水かき回数でダイクストラ
# たとえ泳ぐ向きが違っても同じ場所を2回通ることはあり得ない。

import numpy as np
# from numba import njit,i8
from collections import defaultdict

import heapq
# 今まで何回水をかいたか,i,j,前回水をかいてから何マス進んでいるか,どのむきに進んでいるか
def solve():
  def get_turn(d):
    if d in ("U","D"): # 縦方向に進んでいた場合の次の進み先
      return ((0,1,"R"),(0,-1,"L"))
    else:
      return ((1,0,"D"),(-1,0,"U"))
  
  def get_straight(d):
    if d == "U":
      return (-1,0,"U")
    if d == "D":
      return (1,0,"D")
    if d == "L":
      return (0,-1,"L")
    if d == "R":
      return (0,1,"R")
  q = []
  heapq.heapify(q)
  # 最初に進む4方向を入れておく
  seen = defaultdict(int)
  for first in "UDLR":
    c = get_straight(first)
    if 0 <= x1 + c[0] < H and 0 <= y1 + c[1] < W:
      if grid[x1 + c[0]][y1 + c[1]] != "@":
        heapq.heappush(q,(1,x1 + c[0],y1 + c[1],1,c[2]))
  seen[(x1,y1)] 
  while q:
    cost,i,j,swim,dire = heapq.heappop(q)
    #print("cost",cost,"i",i,"j",j,"swim",swim,"dire",dire)
    #print(q)
    if (i,j) in seen and seen[(i,j)] <= cost:
      continue
#    if i == x2 and j == y2:
#      return cost
    seen[(i,j)] = cost
    # 曲がる場合
    cases = get_turn(dire)
    for c in cases:
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          heapq.heappush(q,(cost + 1,i + c[0],j + c[1],1,c[2]))
    # 直進する場合
    c = get_straight(dire)
    if swim < K: # まだKマス進んでいない
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          # コストは増えず、swim距離は増える
          heapq.heappush(q,(cost,i + c[0],j + c[1],swim + 1,c[2]))
    elif swim == K: # すでにKマス進んでいる場合
      # 直進する場合
      if 0 <= i + c[0] < H and 0 <= j + c[1] < W:
        if grid[i + c[0]][j + c[1]] != "@":
          # コストは増えて、swim距離は1に
          heapq.heappush(q,(cost + 1,i + c[0],j + c[1],1,c[2]))
  if (x2,y2) in seen:
    return seen[(x2,y2)]
  else:
    return -1

print(solve())

Submission status: Time Limit Exceeded

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

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 = []
    heappush(que,(0,(x,y)))
    d[x][y] = 0
    while que:
        [num,(qx,qy)] = heappop(que)
        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] == '@':
                    break
                if d[nx][ny] == -1 or d[nx][ny] > d[qx][qy]+1:
                    d[nx][ny] = d[qx][qy] + 1
                    heappush(que,[d[nx][ny],(nx,ny)])
    print(d[gx][gy])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
calc=lambda x,y:x*1000007+y
def main():
  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=deque()
  d.append(calc(sx,sy))
  s=set()
  while d:
    x,y=divmod(d.popleft(),1000007)
    if calc(x,y)in s:
      s.discard((x,y))
      continue
    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
      d.append(calc(x-i,y))
      if b[x-i][y]!=0:
        s.add((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
      d.append(calc(x+i,y))
      if b[x+i][y]!=0:
        s.add((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
      d.append(calc(x,y-j))
      if b[x][y-j]!=0:
        s.add((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
      d.append(calc(x,y+j))
      if b[x][y+j]!=0:
        s.add((x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()