Solution: Minimum Moves to Spread Stones Over Grid
Let's solve the Minimum Moves to Spread Stones Over Grid problem using the Backtracking pattern.
We'll cover the following
Statement
Given a 2D grid of integers of size (
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
. grid.length
,grid[i].length
grid[i][j]
Solution
This solution works by trying different combinations of moving extra stones around the grid until each empty cell has at least one stone.
First, we check if there are exactly
If a cell is empty, we mark down its position.
If a cell has more than one stone, we note its position and the number of extra stones.
Once we know the locations of the empty cells and the cells with extra stones, we start exploring possible moves. We try placing each extra stone into each empty cell, one by one, and calculate the moves needed for each trial. The number of moves to transfer a stone from the extra cell at position
              
During the process, we keep track of the minimum number of moves to distribute all the stones, considering different combinations. After each trial, if the number of moves for that specific trial is less than the current minimum, we update the minimum number of moves. Additionally, after trying out one possible way to spread the stones, we backtrack and try other possible combinations. Once we have tried all possible combinations and calculated the number of moves for each possible combination of stone moves, we return the minimum number of moves.
Here are the detailed steps of this approach:
Populate the
zeros
array with the coordinates of the empty cells.Populate the
extras
array with the coordinates of the cells with more than one stone and the count of the extra stones. Also, initialize theminMoves
variable with a high value.Call the solution function to start with the first empty cell in
zeros
with the initial number of moves as zero. Iterate over each cell inextras
and move a stone from the cell inextras
to the cell inzeros
.Calculate the number of moves by computing the Manhattan distance between the current cell in
extras
and the current empty cell.Recursively call the solution function with the index of the next empty cell in
zeros
, and the sum of the number of moves calculated in the previous and current function call to fill the next empty cells inzeros
with the remaining cells inextras
.After all the empty cells are filled, update the value of the
minMoves
variable by calculating the minimum of the current total number of moves and the previous value ofminMoves
.Then, backtrack to the previous recursive function call, placing back the stone removed from the previous cell in
extras
, and iterate to the next stone inextras
to fill the current empty cell inzeros
.Finally, return the value of
minMoves
once all possible choices of moving stones from theextras
to the cells inzeros
have been explored.
The following illustration shows these steps in detail:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.