LoopCoach
Microsoft questions

Minimum Moves with k-Cell Jumps

MicrosoftOnsiteMedium

You are given a grid of 0 and 1 values. A cell with 0 is open; a cell with 1 is blocked. Rows are indexed 0 through m - 1 top to bottom and columns 0 through n - 1 left to right, where m and n are the grid's dimensions.

Part 1: Minimum moves with k-cell jumps

A piece starts at the open cell (sr, sc) and must reach the open cell (tr, tc).

In one move, the piece travels between 1 and k cells in a straight line — up, down, left or right. Every cell it passes, including the cell it lands on, must be inside the grid and open.

Return the fewest moves needed to reach (tr, tc), or -1 if the target cannot be reached.

  1. Example 1
    k
    2
    sc
    0
    sr
    0
    tc
    2
    tr
    2
    grid
    [[0,0,0],[0,1,0],[0,0,0]]
    Output
    2

    Why: Jump right two cells from (0, 0) to (0, 2), passing the open cell (0, 1), then jump down two cells to (2, 2), passing the open cell (1, 2). Two moves suffice, and no one-move jump reaches the target.

Constraints

  • 1 <= len(grid) <= 1000
  • 1 <= len(grid[i]) <= 1000
  • 0 <= sr < len(grid)
  • 0 <= sc < len(grid[0])
  • 0 <= tr < len(grid)
  • 0 <= tc < len(grid[0])
  • 1 <= k <= max(len(grid), len(grid[0]))
  • grid[i][j] is 0 or 1
  • grid[sr][sc] == 0
  • grid[tr][tc] == 0
Practice this question
Import your own questions
Paste a question you were asked and get a full problem: statement, tests and a checked solution.
Import a question