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

题目描述：

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。

示例 1：

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]
输出：3
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。
2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。
总共需要 3 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 3 。

示例 2：

输入：grid = [[1,3,0],[1,0,0],[1,0,3]]
输出：4
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (0,1) 移动到 (0,2) 。
2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。
3 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。
总共需要 4 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 4 。

提示：

• grid.length == grid[i].length == 3
• 0 <= grid[i][j] <= 9
• grid 中元素之和为 9 。

---

解题分析及思路：

方法：深度优先搜索

思路：

首先找到所有不符合规则的格子，即找到不为1的格子，分为两组：

• 一组为所有石头数大于1的格子
• 一组为所有石头数等于0的格子

那么，要做的是，将所有石头数大于1的格子，都移动到所有石头数等于0的格子中，使得每个格子都有石头且都为1。

利用深度优先搜索的思想，所有石头数为0的格子都可以从石头数大于1的格子中选择一个格子，并将其移动到石头数等于0的格子中，使得每个格子都有石头且都为1。

从所有的方案中，选择最小的移动次数。

import "math"

func minimumMoves(grid [][]int) int {
	var num1 [][]int
	var num2 [][]int
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] > 1 {
				num1 = append(num1, []int{i, j, grid[i][j]})
			} else if grid[i][j] == 0 {
				num2 = append(num2, []int{i, j, grid[i][j]})
			}
		}
	}
	var minCount = math.MaxInt
	var dfs func(count, zeroCount int)
	dfs = func(count, zeroCount int) {
		if zeroCount == 0 {
			minCount = min(minCount, count)
			return
		}
		for index1 := 0; index1 < len(num1); index1++ {
			for index2 := 0; index2 < len(num2); index2++ {
				if num1[index1][2] > 1 && num2[index2][2] == 0 {
					num1[index1][2]--
					num2[index2][2]++
					dfs(count+abs(num1[index1][0]-num2[index2][0])+abs(num1[index1][1]-num2[index2][1]), zeroCount-1)
					num1[index1][2]++
					num2[index2][2]--
				}
			}
		}
		return
	}
	dfs(0, len(num2))
	if minCount == math.MaxInt {
		return 0
	}
	return minCount
}

func min(num1, num2 int) int {
	if num1 < num2 {
		return num1
	}
	return num2
}

func abs(num int) int {
	if num > 0 {
		return num
	}
	return -num
}

复杂度：

• 时间复杂度：O(2ⁿ), 其中 n 为网格矩阵的元素个数。
• 空间复杂度：O(n)

执行结果：

• 执行耗时:108 ms,击败了16.67% 的Go用户
• 内存消耗:2.7 MB,击败了50.00% 的Go用户