← 返回 microsoft 的题目列表Shortest Path in a Grid with at Most K Cells per Move
类型：online_judge
Problem: Shortest Path in a Grid with at Most K Cells per Move
Given an n x m grid:
. represents an empty cell that can be visited;
# represents an obstacle that cannot be entered or crossed.
You are given a start cell (sx, sy) and a target cell (tx, ty). Coordinates are 1-indexed.
In one move, you may choose one of the four directions and move from 1 to k cells in that direction. You cannot move out of bounds, enter an obstacle, or jump over an obstacle.
Return the minimum number of moves needed to reach the target. If it is impossible, return -1.
Input Format
n m k
grid_row_1
grid_row_2
...
grid_row_n
sx sy tx ty
Output Format
minimum_steps
Constraints
1 <= n, m <= 1000
1 <= k <= 1000
Grid cells contain only . and #
The start and target cells are inside the grid and are not obstacles
Example
Input:
3 3 2
...
...
...
1 1 3 3
Output:
2
Explanation: Move right from (1,1) to (1,3), then down to (3,3).
Example
Input
3 3 2
...
...
...
1 1 3 3
Output
2