给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。
网格图中总共恰好有 9 个石头，一个格子里可能会有多个石头。
每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。
请你返回每个格子恰好有一个石头的最少移动次数
1. 回溯法
贪心置换最大的
class Solution {
public:
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int minimumMoves(vector<vector<int>>& grid) {
string cur = "";
string target = "111111111";
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
cur.push_back(grid[i][j]+'0');
cout<<cur;
unordered_map<string,int> dp; //记录对应状态的次数，防止重复遍历
function<int(int)> f = [&](int depth)->int{
if(cur==target) return depth;
if(dp.count(cur)&&dp[cur]<=depth) return INT_MAX/2;//无效,剪枝
dp[cur] = depth;//记录该状态操作次数，剪枝
int res = INT_MAX/2;
int i = 0;
for(int k = 0; k < 9; k++) //贪心置换最大的
if(cur[k]>cur[i]) i = k;
//if(cur[i]=='0'||cur[i]=='1') continue;
int x = i/3; int y = i%3;
for(int j=0;j<4;j++){
int nx = x + dir[j][0]; int ny = y + dir[j][1];
if(nx<0||nx>2||ny<0||ny>2) continue;
int npos = nx*3 + ny;
cur[i]--; cur[npos]++;
res = min(res,f(depth+1));
cur[i]++; cur[npos]--;
}
return res;
};
return f(0);
}
};
2. 移入移出全排列匹配
class Solution {
public:
int minimumMoves(vector<vector<int>>& grid) {
vector<int> from,to;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++){
if(grid[i][j])
for(int k=1;k<grid[i][j];k++)
from.push_back(i*3+j);
else to.push_back(i*3+j);
}
int res = INT_MAX;
do{
int cur = 0;
for(int i=0;i<from.size();i++)//计算当前全部曼哈顿距离
cur+=cal(from[i],to[i]);
res = min(res,cur);
}
while(next_permutation(from.begin(),from.end()));
return res;
}
int cal(int from,int to){
int fx = from/3; int fy = from%3;
int tx = to/3; int ty = to%3;
return abs(fx-tx)+abs(fy-ty);
}
};