题目：
给你一个大小为 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 == 30 <= grid[i][j] <= 9grid中元素之和为9。
错误思路
思路：
由于grid中元素之和为9，所以说明最终每个方格中元素都是1
换句话说，我们不必从0出发找到2,3这样的元素的位置，反而可以从2,3这样的元素出发找0，这样就是分配的最短的
由于要最短路径，所以是广度优先搜索
上述思路错误的原因在于， 大于1的元素分布是未知的，所以从他们出发，他们之间并不能协调好到0的路径。比较典型的例子就是 [[1,2,2],[1,1,0],[0,1,1]]。
相对于从大于1的元素出发而言，从0出发也有问题。
这个问题在于从0出发，我们枚举0元素的顺序必须有考究，不然还是会出现问题，典型例子就是 [[3,2,0],[0,1,0],[0,3,0]]
代码：
class Solution {
public:
int minimumMoves(vector<vector<int>>& grid) {
int dire[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int ans = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (grid[i][j] == 1 || grid[i][j] == 0) {
continue;
}
vector<vector<bool>> visit(3, vector<bool>(3, false));
visit[i][j] = true;
int need = grid[i][j] - 1, cur = 0;
queue<vector<int>> que;
que.push({i, j, 0});
while (cur < need) {
vector<int> top = que.front();
int rowIdx = top[0], colIdx = top[1], dis = top[2];
que.pop();
for (int k = 0; k < 4; k++) {
int nextRow = rowIdx + dire[k][0];
int nextCol = colIdx + dire[k][1];
if (nextRow >= 0 && nextRow < 3 && nextCol >= 0 && nextCol < 3) {
if (visit[nextRow][nextCol] == false) {
visit[nextRow][nextCol] = true;
if (grid[nextRow][nextCol] == 0) {
cur++;
ans += dis + 1;
grid[nextRow][nextCol] = 1;
}
que.push({nextRow, nextCol, dis + 1});
}
}
}
}
}
}
return ans;
}
};
正确思路
思路：
如果某个位置 (x,y) 恰好有一个石头，那么要想达到最少移动次数，移动 (x,y) 到别处 P 一定不会更优：这是因为如果我们这样做，就需要将另一个 Q 处的石头再移动到位置 (x,y)，那就不如直接将 Q 处的石头移动到 P 了。
因此，我们只需要考虑所有至少有两个石头的位置，以及没有石头的位置。在最少的移动次数的策略中，一定是对于每一个没有石头的位置，分配一个多出的石头，并将该石头使用最少的移动次数（曼哈顿距离）送达。这样一来，我们可以使用两个数组 more 和 less，分别存储上述的位置。如果一个位置有 k (k≥2) 个石头，那么其在 more 中出现 k−1 次；如果一个位置没有石头，那么其在 less 中出现 1 次。
例如对于「示例 2」，这两个数组分别为：
more = [(0,1),(0,1),(2,2),(2,2)]
less = [(0,2),(1,1),(1,2),(2,1)]
我们可以枚举 more 或者 less 的每一个排列，而另一个数组保持不变，这样就可以枚举所有可能的分配情况。
注意到这两个数组的长度相同，而 less 中没有重复元素但 more 中有，因此 more 的排列个数更少，枚举 more 的每一个排列可以使得时间复杂度更低。
代码：
class Solution {
public:
int minimumMoves(vector<vector<int>>& grid) {
vector<pair<int, int>> more, less;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (grid[i][j] > 1) {
for (int k = 2; k <= grid[i][j]; ++k) {
more.emplace_back(i, j);
}
}
else if (grid[i][j] == 0) {
less.emplace_back(i, j);
}
}
}
int ans = INT_MAX;
do {
int steps = 0;
for (int i = 0; i < more.size(); ++i) {
steps += abs(more[i].first - less[i].first) + abs(more[i].second - less[i].second);
}
ans = min(ans, steps);
} while (next_permutation(more.begin(), more.end()));
return ans;
}
};