P4289 [HAOI2008] 移动玩具 - 洛谷

我一开始写了个贪心，就是从目标状态找初始状态能与之匹配的点距离，建一个小根堆放进去。

因为我发现：如果点 a 要去目标点时被点 b 挡了，那就先让点 b 去，点 a 到点 b 的位置。

这样就没有什么占位不占位之说了，距离都是曼哈顿距离。

看似十分正确（可以拿到 90 分），但有这样一组数据：

0000
0001
0100
0001

1000
0000
0011
0000
输出：6

而我的程序会输出 8，因为目标状态第三排第四列的 1 找了初始状态第二排第四列的 1，

导致总距离增加。

与其大费周章的判断能不能贪心，不如计算下总的可能状态数 。

小的可怜，直接宽搜，将 4 * 4 的方格转写成 16 个二进制 0 / 1，状态压缩。

进去队列每一次都移动一个现有状态的玩具，再用一个 bool 数组判重状态。

第一次到达目标状态时的代价就是最小代价。

（对二进制状态压缩位移上下左右还不太懂的同学，直接看代码就能懂！！我写了很详细的注释）

关于更细节的证明：

为什么宽搜是最小代价：

（1）BFS 从初始状态开始，按 “距离”（即步数）逐层向外扩展：

• 第 0 层：初始状态（0 步）
• 第 1 层：所有 1 步可达的状态
• 第 2 层：所有 2 步可达、且未在第 0 / 1 层出现的状态
• …
• 第 k 层：所有首次在第 k 步到达的状态

因此，第一次访问到目标状态时，所用的步数一定是最小的。

（2）状态不重复访问

（3）每一步代价相同（不相同得用最短路。

为什么不能使用贪心 or 贪心什么时候不能使用：

（1）贪心只能关注到局部最优，比如每个点都选择与自己最近的点。

         但没有关注到这个最近的点可能会重合，或者不选最近反而有利于大局观。

（2）贪心的本质：

         在每一步决策中，都做出当前看起来最优（局部最优）的选择，

         期望通过一系列这样的选择最终得到全局最优解。

         所以每次看到问题先判断子问题最优能不能达成全局最优，再选择贪心。

         像本题这种，有时候反而需要某个玩具 “牺牲” 下自己的利益，就不能用贪心。

详细注释代码：

/*
将：
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

压缩成：
 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
的二进制数 

对应着 2 的：
15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
次方位的 1 

那么 6号位 想要往上移动，对应的 2 次方 10 就得 +4 变成 14，对应 2 号位
		   想要往下移动，对应的 2 次方 10 就得 -4 变成 6，对应 10 号位
		   想要往左移动，对应的 2 次方 10 就得 +1 变成 11，对应 5 号位
		   想要往右移动，对应的 2 次方 10 就得 -1 变成 9，对应 7 号位
		   
当然移动前还要看看这些位置有没有玩具，是不是边界 
*/
#include<bits/stdc++.h>
using namespace std;

int st, ed;
map<int, bool> mp;

struct State {
	int s;   // 二进制状态 
	int k;   // 当前移动次数 
}; 

int get_ans() {
	queue<State> Q;
	Q.push({st, 0});   // 初始移动次数为 0 
	mp.clear();
	 
	while (!Q.empty()) {
		State x = Q.front(); Q.pop();
		if (mp[x.s]) {
			continue;
		}
		mp[x.s] = 1;
		if (x.s == ed) {
			return x.k;
		}
		
		for (int i = 0; i < 16; i ++) if ( (1 << i) & x.s ){
			// 找 x.s 状态上有的 1 
			// ***注意，当前 i 是二进制位上有的 1，也就是上面说的 0 ~ 15
			// 要把 0 ~ 15 映射回去，再移动和判断边界 
			 
			if (i + 4 < 16 && !( (1 << (i + 4)) & x.s ) && i / 4  != 3) {
				// 当前 1 的正上方有空位（0） 并且 i 代表的位置不在最上面一行 
				// ***这里的意思是，最上面一行映射的二进制次方 / 4 都为 3 
				
				int new_s = x.s ^ (1 << i) ^ (1 << (i + 4));
				// 将当前第 i 位的 1 转移到正上方 
				Q.push({new_s, x.k + 1}); 
			} 
			
			if (i - 4 >= 0 && !( (1 << (i - 4)) & x.s ) && i / 4 != 0) {
				// 当前 1 的正下方有空位（0） 并且 i 代表的位置不在最下面一行 
				// ***这里的意思是，最下面一行映射的二进制次方 / 4 都为 0
				
				int new_s = x.s ^ (1 << i) ^ (1 << (i - 4));
				// 将当前第 i 位的 1 转移到正下方 
				Q.push({new_s, x.k + 1}); 
			} 
			
			if (i + 1 < 16 && !( (1 << (i + 1)) & x.s ) && i % 4 != 3) {
				// 当前 1 的左边有空位（0） 并且 i 代表的位置不在最左边一列 
				// ***这里的意思是，最左边一列映射的二进制次方 % 4 都为 3 
				
				int new_s = x.s ^ (1 << i) ^ (1 << (i + 1));
				// 将当前第 i 位的 1 转移到左边 
				Q.push({new_s, x.k + 1}); 
			} 
			
			if (i - 1 >= 0 && !( (1 << (i - 1)) & x.s ) && i % 4!= 0) {
				// 当前 1 的右边有空位（0） 并且 i 代表的位置不在最右边一列 
				// ***这里的意思是，最右边一列映射的二进制次方 % 4 都为 0
				
				int new_s = x.s ^ (1 << i) ^ (1 << (i - 1));
				// 将当前第 i 位的 1 转移到右边 
				Q.push({new_s, x.k + 1}); 
			} 
		}
	}
	
	return 0;   // 不可能到这，但还是写一个 
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	st = 0;   // 一定要记得初始化！！ 
	for (int i = 1; i <= 4; i ++) {
		char s[10];   // 需要开大点，不然会有奇怪的错误 
		cin >> (s + 1);
		for (int j = 1; j <= 4; j ++) {
			st = (st << 1) + (s[j] - '0');   
			// 相当于把现有的都往前移一位，给当前 0 / 1 空出位置 
		}
	}
	
	ed = 0;   // 这里也是 
	for (int i = 1; i <= 4; i ++) {
		char s[10];
		cin >> (s + 1);
		for (int j = 1; j <= 4; j ++) {
			ed = (ed << 1) + (s[j] - '0');
		}
	}
	
	cout << get_ans() << "\n";
	
	return 0;
}

附，90 分贪心代码：

（史山没有任何参考价值！！！大家如果好奇贪心长啥样可以看）

#include<bits/stdc++.h>
using namespace std;

const int N = 5;
int a[10][10], b[10][10];

struct node {
	int x, y;
};

struct node2 {
	int x, y;
	int d;
};

int get_close(node no) {
	int dis = 20;
	node res = {no.x, no.y};
	for (int i = 1; i <= 4; i ++) {
		for (int j = 1; j <= 4; j ++) if (a[i][j] == 1) {
			if (abs(no.x - i) + abs(no.y - j) < dis) {
				dis = abs(no.x - i) + abs(no.y - j);
				res = {i, j};
			}
		}
	}
	return dis;
}
node get_close2(node no) {
	int dis = 20;
	node res = {no.x, no.y};
	for (int i = 1; i <= 4; i ++) {
		for (int j = 1; j <= 4; j ++) if (a[i][j] == 1) {
			if (abs(no.x - i) + abs(no.y - j) < dis) {
				dis = abs(no.x - i) + abs(no.y - j);
				res = {i, j};
			}
		}
	}
	return res;
}

bool operator < (node2 na, node2 nb) {
	return get_close({na.x, na.y}) > get_close({nb.x, nb.y});
}

int ans;

void print() {
	cout << "\n";
	cout << ans << "\n";
	for (int i = 1; i <= 4; i ++) {
		for (int j = 1; j <= 4; j ++) {
			cout << a[i][j];
		}
		cout << "\n";
	}
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	for (int i = 1; i <= 4; i ++) {
		char s[10];
		cin >> (s + 1);
		for (int j = 1; j <= 4; j ++) {
			a[i][j] = s[j] - '0';
		}
	}
	for (int i = 1; i <= 4; i ++) {
		char s[10];
		cin >> (s + 1);
		for (int j = 1; j <= 4; j ++) {
			b[i][j] = s[j] - '0';
		}
	}
	
	priority_queue<node2> Q;
	for (int i = 1; i <= 4; i ++) {
		for (int j = 1; j <= 4; j ++) if (b[i][j] == 1) {
			node no = {i, j};
			node2 no2;
			no2 = {i, j, get_close(no)};
			Q.push(no2);
		}
	}
	
	ans = 0;
	while (!Q.empty()) {
		node2 no = Q.top(); Q.pop();
		node t = get_close2({no.x, no.y});
		ans += get_close({no.x, no.y});
		a[t.x][t.y] = 0;
		a[no.x][no.y] = 2;
		//print();
	}
	cout << ans << "\n";
	
	return 0;
}