Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Minimum Moves to Spread Stones Over Grid

Explore how to solve the problem of spreading stones evenly across a 3x3 grid using backtracking. Understand how to identify cells with extra stones, track empty cells, and calculate the minimum moves needed by considering all combinations and using Manhattan distance to measure moves. This lesson helps you develop a systematic approach to combinatorial grid problems and improve recursive problem-solving skills.

We'll cover the following...

Statement

Given a 2D grid of integers of size (3×33 \times 3), where each value represents the number of stones in the given cell, return the minimum number of moves required to place exactly one stone in each grid cell.

Constraints:

  • Only one stone can be moved in one move.

  • Stone from a cell can only be moved to another cell if they are adjacent (share a side).

  • The sum of all stones in the grid must be equal to 99.

  • grid.length, grid[i].length =3 = 3

  • 0≤0 \le grid[i][j] ≤9 \le 9

Solution

This solution works by trying different combinations of moving extra stones around the grid until each empty cell has at least one stone. ...