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):
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1

xxx = set()
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '@':
            xxx.add((hh, ww))

from heapq import heappush, heappop
q = []
heappush(q, (0, x1, y1))
d = {}
d[(x1, y1)] = 0
while q:
    s, x, y = heappop(q)
    print(s,x,y)

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        d[(xx, yy)] = s+1
        heappush(q, (s+1, xx, yy))

print(-1)


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1

xxx = set()
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '@':
            xxx.add((hh, ww))

from heapq import heappush, heappop
q = []
heappush(q, (0, x1, y1))
d = {}
while q:
    s, x, y = heappop(q)
    d[(x, y)] = s
    if x == x2 and y == y2:
        exit(0)

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        heappush(q, (s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or (xx, yy) in xxx:
            break
        if (xx, yy) in d and d[(xx, yy)] <= s+1:
            continue
        heappush(q, (s+1, xx, yy))

print(-1)


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1

m = [[-1] * w for _ in range(h)]
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '.':
            m[hh][ww] = h*w

from collections import deque
q = deque()

q.append((0, x1, y1))
while q:
    s, x, y = q.popleft()
    s1 = s + 1

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

print(-1)


Verdicts: Wrong Answer

Wrong Answer

Accepted