Problem: 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.

Submission attempts (in order):
from heapq import heappop, heappush 
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    
    que = [(0, xs, ys)]
    inf = 10 ** 6
    dp = [[inf for _ in range(w+1)] for _ in range(h+1)]
    visited = [[False for _ in range(w+1)] for _ in range(h+1)]
    dp[xs][ys] = 0
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while que:
        cost, x, y= heappop(que)
        
        # if cost > dp[x][y]:
        #     continue
        if x == xg and y == yg:
            print(cost)
            exit(0)
        if visited[x][y]
            for i in range(4):
                for j in range(1, k+1):
                    x_, y_ = x+j*dx[i], y+j*dy[i]
                    if not field[x_][y_]:
                        break
                    if dp[x_][y_] > dp[x][y] + 1:
                        dp[x_][y_] = dp[x][y] + 1
                        heappush(que, (dp[x_][y_], x_, y_))
        visited[x][y] = True
    print(-1)
        

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):
        
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    dijkstra(xs, ys, xg, yg, h, w, k, field)

if __name__ == '__main__':
    main()

import sys

def main(lines):
    n, m, s = map(int,lines[0].split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        a,b,d = map(int,lines[i+1].split())
        adj[a].append((b,d))
    from heapq import heappush, heappop
    inf = 10**9
    node = []
    dist = [inf]*n
    done = [False]*n
    dist[s] = 0
    heappush(node,(0,s))
    while node:
        cost, v = heappop(node)
        if not done[v]:
            for e in adj[v]:
                if dist[e[0]] > dist[v]+e[1]:
                    dist[e[0]] = dist[v] + e[1]
                    heappush(node, (dist[e[0]],e[0]))
        done[v] = True
    for el in dist:
        if el == inf:
            print('INF') 
        else:
            print(el)       


if __name__ == '__main__':
    lines = []
    for l in sys.stdin:
        lines.append(l.rstrip('\r\n'))
    main(lines)


from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    def dijkstra():
        inf = 10 ** 9
        visited = [[False]*(w+2) for _ in range(h+2)]

        dp = [[inf]*(w+2) for _ in range(h+2)]
        dp[xs][ys] = 0

        que = [(0, xs, ys, 0)]
        direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        while que:
            cost, x, y, dirt = heappop(que)
            # if (x, y) == (xg, yg):
            #     ans = (dp[x][y] + k - 1)//k
            #     return ans

            if not visited[x][y]:
                for i in range(4):
                    nx, ny = x + direction[i][0], y + direction[i][1]
                    if field[nx][ny]:
                        if i == dirt:
                            if dp[nx][ny] > dp[x][y] + 1:
                                dp[nx][ny] = dp[x][y] + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                        else:
                            if dp[nx][ny] > (dp[x][y] + k-1)//k*k + 1:
                                dp[nx][ny] = (dp[x][y] + k-1)//k*k + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                visited[x][y] = True
        if dp[xg][yg] == inf
            return -1
        else:
            return (dp[xg][yg] + k - 1)//k


    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()

from heapq import heappop, heappush 
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    
    que = [(0, xs, ys)]
    inf = 10 ** 6
    dp = [[inf for _ in range(w+1)] for _ in range(h+1)]
    visited = [[False for _ in range(w+1)] for _ in range(h+1)]
    dp[xs][ys] = 0
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while que:
        cost, x, y= heappop(que)
        
        # if cost > dp[x][y]:
        #     continue
        if x == xg and y == yg:
            print(cost)
            exit(0)
        if visited[x][y]:
            for i in range(4):
                for j in range(1, k+1):
                    x_, y_ = x+j*dx[i], y+j*dy[i]
                    if not field[x_][y_]:
                        break
                    if dp[x_][y_] > dp[x][y] + 1:
                        dp[x_][y_] = dp[x][y] + 1
                        heappush(que, (dp[x_][y_], x_, y_))
        visited[x][y] = True
    print(-1)
        

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):
        
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    dijkstra(xs, ys, xg, yg, h, w, k, field)

if __name__ == '__main__':
    main()

from heapq import heappop, heappush 
from collections import deque
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    
    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):
        
        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()

Verdicts: Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Accepted