将石头分散到网格图的最少移动次数

You are given a 0-indexed 2D integer matrix grid of size 3 * 3, representing the number of stones in each cell. The grid contains exactly 9 stones, and there can be multiple stones in a single cell.

In one move, you can move a single stone from its current cell to any other cell if the two cells share a side.

Return the minimum number of moves required to place one stone in each cell.

 

Example 1:

Input: grid = [[1,1,0],[1,1,1],[1,2,1]]
Output: 3
Explanation: One possible sequence of moves to place one stone in each cell is: 
1- Move one stone from cell (2,1) to cell (2,2).
2- Move one stone from cell (2,2) to cell (1,2).
3- Move one stone from cell (1,2) to cell (0,2).
In total, it takes 3 moves to place one stone in each cell of the grid.
It can be shown that 3 is the minimum number of moves required to place one stone in each cell.

Example 2:

Input: grid = [[1,3,0],[1,0,0],[1,0,3]]
Output: 4
Explanation: One possible sequence of moves to place one stone in each cell is:
1- Move one stone from cell (0,1) to cell (0,2).
2- Move one stone from cell (0,1) to cell (1,1).
3- Move one stone from cell (2,2) to cell (1,2).
4- Move one stone from cell (2,2) to cell (2,1).
In total, it takes 4 moves to place one stone in each cell of the grid.
It can be shown that 4 is the minimum number of moves required to place one stone in each cell.

 

Constraints:

• grid.length == grid[i].length == 3
• 0 <= grid[i][j] <= 9
• Sum of grid is equal to 9.

/*
 * Problem: Given a 3x3 grid where each cell contains a certain number of stones, find the minimum number of moves required to ensure each cell contains exactly one stone. A move involves transferring a stone to an adjacent cell with a common edge.
 * 
 * Approach (Java Stream):
 * 1. Identify cells with excess stones and cells lacking stones.
 * 2. Use streams to calculate the minimum distance to balance the stones.
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int minMoves(int[][] grid) {
        // List to store excess and deficit coordinates
        List<int[]> excess = new ArrayList<>();
        List<int[]> deficit = new ArrayList<>();
        
        // Populate excess and deficit lists using streams
        IntStream.range(0, 3).forEach(i ->
            IntStream.range(0, 3).forEach(j -> {
                if (grid[i][j] > 1) {
                    excess.add(new int[]{i, j, grid[i][j] - 1});
                } else if (grid[i][j] == 0) {
                    deficit.add(new int[]{i, j});
                }
            })
        );
        
        // Calculate minimum moves using excess and deficit
        return excess.stream().mapToInt(from ->
            deficit.stream().mapToInt(to ->
                (Math.abs(from[0] - to[0]) + Math.abs(from[1] - to[1])) * from[2]
            ).min().orElse(0)
        ).sum();
    }
}

题目的目标是通过最少的移动，将每个格子中的石头数量均匀为一个。这个题解采用了深度优先搜索（DFS）的策略来尝试所有可能的石头移动方式。首先，题解通过两次遍历找出所有需要石头（即空格子）和多余石头的格子。然后，使用DFS尝试所有可能的从多余石头格子到空格子的移动方式，每次移动都更新当前的移动总次数，并在所有格子都被填满后记录最小的移动次数。DFS过程中，每次尝试将一个石头从一个有多余石头的格子移动到一个空格子，然后递归处理下一个空格子，直到所有空格子都被处理完毕。

O((M*N)^2)

O(N)