【C++组合数学】2850. 将石头分散到网格图的最少移动次数|2001

本文涉及知识点

组合数学汇总
C++图论 本题可以通过最小费用最大流做，我不会

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

给你一个大小为 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 。

组合数学

如果grid[r][c] > 1，需要移出grid[r][c]-1个石子。
如果grid[r][c] < 1，需要移入一个石子。
from记录需要移出的行列号，to记录需要移入的行列号。n是需要移出的石子数。
cur = {0,2,3…n-1} 用系统函数枚举cur的全排列
from[cur[i]] 移到to[i]。
时间复杂度：O(rc(rc)!) r是行数，c是列数。

代码

核心代码

class Solution {
		public:
			int minimumMoves(vector<vector<int>>& grid) {
				const int R = grid.size();
				const int C = grid.size();
				vector<pair<int, int>> from, to;
				for (int r = 0; r < R; r++) {
					for (int c = 0; c < C; c++) {
						if (grid[r][c] < 1) {
							to.emplace_back(r, c);
						}
						else if (grid[r][c] > 1) {
							for (int i = 0; i + 1 < grid[r][c]; i++) {
								from.emplace_back(r, c);
							}
						}
					}
				}
				const int n = from.size();
				vector<int> inx(n);
				iota(inx.begin(), inx.end(), 0);
				int ans = INT_MAX;
				do {
					int cur = 0;
					for (int i = 0; i < n; i++) {
						const int j = inx[i];
						cur += abs(from[j].first - to[i].first) + abs(from[j].second - to[i].second);
					}
					ans = min(ans, cur);
				} while (next_permutation(inx.begin(), inx.end()));
				return ans;
			}
		};

单元测试

vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {1,1,0},{1,1,1},{1,2,1} };
			auto res = Solution().minimumMoves(grid);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {1,3,0},{1,0,0},{1,0,3} };
			auto res = Solution().minimumMoves(grid);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid = { {1,2,2},{1,1,0},{0,1,1} };
			auto res = Solution().minimumMoves(grid);
			AssertEx(4, res);
		}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。