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
    from collections import deque
    def input(): return sys.stdin.readline().rstrip()

    def bfs():
        inf = 1e7

        dist = [[inf]*w for _ in range(h)]
        dist[xs][ys] = 0
        que = deque([(xs, ys)])
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            x, y = que.popleft()
            for i in range(4):
                nx, ny = x, y
                for _ in range(k):
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < h and 0 <= ny < w:
                        if 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((nx, ny))
        
        if dist[xg][yg] == inf:
            print(-1)
        else:
            print(dist[xg][yg])


               

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    bfs()


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    def bfs():
        inf = 1e18

        dist = [[inf]*w for _ in range(h)]
        dist[xs][ys] = 0
        que = deque([(xs, ys)])
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            x, y = que.popleft()

            if (x,y) == (xg, yg):
                return dist[x][y]

            for i in range(4):
                nx, ny = x, y
                for _ in range(k):
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < h and 0 <= ny < w:
                        if 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((nx, ny))
        if dist[xg][yg] == inf:
            return -1


               

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    ans = bfs()
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    
    def dijkstra():
        def toId(x, y, v): return (x*w+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h*w*4)
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//w
            y = Id//4%w
            v = Id%4

            if cost > dp[Id]:
                continue
            
            if x == xg and y == yg:
                return modCeil(cost)//k
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if 0 <= nx < h and 0 <= ny < w and field[nx][ny] == '.':
                push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:     
            return -1
        return modCeil(ans)//k

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    ans = dijkstra()
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    
    def dijkstra():
        def toId(x, y, v): return (x*w+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h*w*4)
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//w
            y = Id//4%w
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if 0 <= nx < h and 0 <= ny < w:
                if field[nx][ny] == '.':
                    push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:     
            return -1
        return modCeil(ans)//k

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = []
    for _ in range(h):
        field.append(input())
    
    ans = dijkstra()
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    
    def dijkstra():
        def toId(x, y, v): return (x*(w+2)+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h+2)*(w+2)*4
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//(w+2)
            y = Id//4%(w+2)
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if field[nx][ny] == '.':
                push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:     
            return -1
        return modCeil(ans)//k

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    
    def dijkstra():
        def toId(x, y, v): return (x*(w+2)+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h+2)*(w+2)*4
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//(w+2)
            y = Id//4%(w+2)
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if field[nx][ny]:
                push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:       
            return -1
        return modCeil(ans)//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()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    def toId(x, y, v): return (x*(w+2)+y)*4 + v

    def modCeil(x): return x + (-x)%k

    def dijkstra():
        inf = 1e18

        dp = [inf]*(h+2)*(w+2)*4
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//(w+2)
            y = Id//4%(w+2)
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                nId = toId(x, y, nv)
                if dp[nId] > cost:
                    dp[nId] = modCeil(cost)
                    heappush(que, (dp[nId], nId))
            
            nx, ny = x+dx[v], y+dy[v]
            nId = toId(nx, ny, v)
            if field[nx][ny]:
                if dp[nId] > cost + 1:
                    dp[nId] = cost + 1
                    heappush(que, (dp[nId], nId))

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:       
            return -1
        return modCeil(ans)//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()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    def dijkstra():
        inf = 10 ** 18

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

        que = [(0, xs, ys, 0)]
        direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        while que:
            cost, x, y, dirt = heappop(que)

            if cost > dp[x][y][dirt]:
                continue

            if (x, y) == (xg, yg):
                ans = (dp[x][y][dirt] + (-dp[x][y][dirt]) % k)//k
                return ans

            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][i] > dp[x][y][i] + 1:
                            dp[nx][ny][i] = dp[x][y][i] + 1
                            heappush(que, (dp[nx][ny][i], nx, ny, i))
                    else:
                        if dp[x][y][i] > dp[x][y][dirt] + (-dp[x][y][dirt])%k:
                            dp[x][y][i] = dp[x][y][dirt] + (-dp[x][y][dirt])%k
                            heappush(que, (dp[x][y][i], x, y, i))
        return -1


    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()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y = dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@" and depth[ny][nx] > depth[y][x]:
                    depth[ny][nx] = depth[y][x] +1
                    dq.append((nx,ny))
            else:
                break
            K -= 1
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for _ in range(h):
    maze.append(list(input()))
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y = dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@" and depth[ny][nx] > depth[y][x]:
                    depth[ny][nx] = depth[y][x] +1
                    dq.append((nx,ny))
            else:
                break
            K -= 1
print(depth[c][d] if depth[c][d] != float("inf") else -1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    R = set()
    L = set()
    U = set()
    D = set()
    dic = {}
    dic[(x1, y1)] = 0
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in D or np in st or pond[x-i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                U.add(np)
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x-i, y)])
            U.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in U or np in st or pond[x+i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                D.add(np)
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x+i, y)])
            D.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in R or np in st or pond[x][y-i] == 1:
                break
            if np in dic and dic[np] <= c:
                L.add(np)
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y-i)])
            L.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in L or np in st or pond[x][y+i] == 1:
                break
            if np in dic and dic[np] <= c:
                R.add(np)
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y+i)])
            R.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    R = set()
    L = set()
    U = set()
    D = set()
    dic = {}
    dic[(x1, y1)] = 0
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in D or np in st or pond[x-i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x-i, y)])
            U.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in U or np in st or pond[x+i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x+i, y)])
            D.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in R or np in st or pond[x][y-i] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y-i)])
            L.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in L or np in st or pond[x][y+i] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y+i)])
            R.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    R = set()
    L = set()
    U = set()
    D = set()
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in D or np in st or pond[x-i][y] == 1:
                break
            if np in U:
                continue
            heapq.heappush(hq, [c, (x-i, y)])
            U.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in U or np in st or pond[x+i][y] == 1:
                break
            if np in D:
                continue
            heapq.heappush(hq, [c, (x+i, y)])
            D.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in R or np in st or pond[x][y-i] == 1:
                break
            if np in L:
                continue
            heapq.heappush(hq, [c, (x, y-i)])
            L.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in L or np in st or pond[x][y+i] == 1:
                break
            if np in R:
                continue
            heapq.heappush(hq, [c, (x, y+i)])
            R.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    R = set()
    L = set()
    U = set()
    D = set()
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in D or np in st or pond[x-i][y] == 1:
                break
            heapq.heappush(hq, [c, (x-i, y)])
            U.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in U or np in st or pond[x+i][y] == 1:
                break
            heapq.heappush(hq, [c, (x+i, y)])
            D.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in R or np in st or pond[x][y-i] == 1:
                break
            heapq.heappush(hq, [c, (x, y-i)])
            L.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in L or np in st or pond[x][y+i] == 1:
                break
            heapq.heappush(hq, [c, (x, y+i)])
            R.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = ["@" for _ in range(h+2)]
    for i in range(w+1):
        pond[0] += "@"
        pond[h+1] += "@"
    for i in range(1, h+1):
        s = input()
        pond[i] += s + "@"
    hq = [[0, (x1, y1)]]
    st = set()
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in st or pond[x-i][y] == "@":
                break
            heapq.heappush(hq, [c, (x-i, y)])
        for i in range(1, k+1):
            np = (x+i, y)
            if np in st or pond[x+i][y] == "@":
                break
            heapq.heappush(hq, [c, (x+i, y)])
        for i in range(1, k+1):
            np = (x, y-i)
            if np in st or pond[x][y-i] == "@":
                break
            heapq.heappush(hq, [c, (x, y-i)])
        for i in range(1, k+1):
            np = (x, y+i)
            if np in st or pond[x][y+i] == "@":
                break
            heapq.heappush(hq, [c, (x, y+i)])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[] for _ in range(h)]
dp = [[-1]*w for _ in range(h)]
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  #p= heapq.heappop(que)
  p = que.popleft()
  p = p[1]
  if (p[0] == x2) & (p[1] == y2):exit(print(dp[x2][y2]))
  for i in range(4):
    for j in range(1,k+1):
      nx = p[0] + dx[i]*j
      ny = p[1] + dy[i]*j
      if not ((0 <= nx < h) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[p[0]][p[1]]:break
      dp[nx][ny] = dp[p[0]][p[1]] + 1
      #heapq.heappush(que, (dp[nx][ny], [nx,ny]))
      que.append((dp[nx][ny], [nx,ny]))

if dp[x2][y2] != 0:
  print(dp[x2][y2])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
#from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[] for _ in range(h)]
dp = [[-1]*w for _ in range(h)]
que = []
c = [input() for _ in range(h)]

dp[x1][y1] = 0
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) & (p[1] == y2):exit(print(dp[x2][y2]))
  for i in range(4):
    for j in range(1,k+1):
      nx = p[0] + dx[i]*j
      ny = p[1] + dy[i]*j
      if not ((0 <= nx < h) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[p[0]][p[1]]:break
      dp[nx][ny] = dp[p[0]][p[1]] + 1
      heapq.heappush(que, (dp[nx][ny], [nx,ny]))

if dp[x2][y2] != 0:
  print(dp[x2][y2])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[] for _ in range(h)]
dp = [[-1]*w for _ in range(h)]
que = []
for i in range(h):
  c[i] = input()

dp[x1][y1] = 0
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) & (p[1] == y2):exit(print(dp[x2][y2]))
  for i in range(4):
    for j in range(1,k+1):
      nx = p[0] + dx[i]*j
      ny = p[1] + dy[i]*j
      if not ((0 <= nx < h) & (0 <= ny < w)):break
      if c[nx][ny] == '@':break
      if 0 <= dp[nx][ny] <= dp[p[0]][p[1]]:break
      dp[nx][ny] = dp[p[0]][p[1]] + 1
      heapq.heappush(que, (dp[nx][ny], [nx,ny]))

if dp[x2][y2] != 0:
  print(dp[x2][y2])
else:
  print(-1)

Submission status: Time Limit Exceeded

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

dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):break
  for i in range(4):
    nx = p[0] + dx[i]
    ny = p[1] + dy[i]
    if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
      if c[nx][ny] != '@':
        cnt = 1
        while (0 <= dp[nx][ny] < dp[p[0]][p[1]]):
          dp[nx][ny] = dp[p[0]][p[1]] + 1
          heapq.heappush(que, (dp[nx][ny], [nx,ny]))
          cnt += 1
          nnx = nx + dx[i]
          nny = ny + dy[i]
          if (nnx<0) | (nnx>(h-1)) | (nny<0) | (nny>(w-1)) | (cnt > k):break
          if c[nnx][nny] == '@':break
          nx = nnx
          ny = nny

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = [int(_) for _ in input().split()]
x1, y1, x2, y2 = [int(_) - 1 for _ in input().split()]
C = [[10**6 if s == '.' else None for s in input()] for _ in range(H)]
C[x1][y1] = 0
Qx = [(x1, y1)]  #次にxが変化
Qy = [(x1, y1)]  #次にyが変化
while True:
    if not (Qx or Qy):
        break
    Qy2 = []
    while Qx:
        x, y = Qx.pop()
        for nx in range(x + 1, H):
            if C[nx][y] is None:
                break
            d = C[x][y] + 1 + (nx - x - 1) // K
            if C[nx][y] > d:
                Qy2 += [(nx, y)]
                C[nx][y] = d
        for nx in range(x - 1, -1, -1):
            if C[nx][y] is None:
                break
            d = C[x][y] + 1 + (x - nx - 1) // K
            if C[nx][y] > d:
                Qy2 += [(nx, y)]
                C[nx][y] = d
    Qx2 = []
    while Qy:
        x, y = Qy.pop()
        for ny in range(y + 1, W):
            if C[x][ny] is None:
                break
            d = C[x][y] + 1 + (ny - y - 1) // K
            if C[x][ny] > d:
                Qx2 += [(x, ny)]
                C[x][ny] = d
        for ny in range(y - 1, -1, -1):
            if C[x][ny] is None:
                break
            d = C[x][y] + 1 + (y - ny - 1) // K
            if C[x][ny] > d:
                Qx2 += [(x, ny)]
                C[x][ny] = d
    Qx = Qx2
    Qy = Qy2
ans = C[x2][y2]
print(ans if ans < 10**6 else -1)

Submission status: Time Limit Exceeded

Solution code:
import collections
H, W, K = [int(_) for _ in input().split()]
x1, y1, x2, y2 = [int(_) - 1 for _ in input().split()]
C = [[10**6 if s == '.' else None for s in input()] for _ in range(H)]
C[x1][y1] = 0
Qx = collections.deque([(x1, y1)])  #次にxが変化
Qy = collections.deque([(x1, y1)])  #次にyが変化
while True:
    if not (Qx or Qy):
        break
    Qy2 = collections.deque([])
    while Qx:
        x, y = Qx.popleft()
        for nx in range(x + 1, H):
            if C[nx][y] is None:
                break
            d = C[x][y] + 1 + (nx - x - 1) // K
            if C[nx][y] > d:
                Qy2 += [(nx, y)]
                C[nx][y] = d
        for nx in range(x - 1, -1, -1):
            if C[nx][y] is None:
                break
            d = C[x][y] + 1 + (x - nx - 1) // K
            if C[nx][y] > d:
                Qy2 += [(nx, y)]
                C[nx][y] = d
    Qx2 = collections.deque([])
    while Qy:
        x, y = Qy.popleft()
        for ny in range(y + 1, W):
            if C[x][ny] is None:
                break
            d = C[x][y] + 1 + (ny - y - 1) // K
            if C[x][ny] > d:
                Qx2 += [(x, ny)]
                C[x][ny] = d
        for ny in range(y - 1, -1, -1):
            if C[x][ny] is None:
                break
            d = C[x][y] + 1 + (y - ny - 1) // K
            if C[x][ny] > d:
                Qx2 += [(x, ny)]
                C[x][ny] = d
    Qx = Qx2
    Qy = Qy2
ans = C[x2][y2]
print(ans if ans < 10**6 else -1)