刷题记录:牛客NC19975[HAOI2008]移动玩具

传送门:牛客

题目描述:

在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时
只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态
移动到某人心中的目标状态
输入:
1111
0000
1110
0010

1010
0101
1010
0101
输出:
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

emmm,假设你之前碰到过状压题,那么你应该会很容易的看出来,这道题应该是一道和状态压缩有关的题目(首先这道题的n很小,并且这道题的状态只有两种,符合二进制)

但是即使当时我一看就看出了状态压缩,我还是没有任何的头绪,感觉不知道从那个地方进行搜索,在研究过题解之后,我才逐渐搞懂了这道题的解决方案

主体思路:

1. 首先既然是状压,我们肯定是要储存我们刚开始的状态和结束是的状态.在这里我们直接开辟一个1<<16的数组即可.具体到代码中对于每一个输入的数字我们先左移一位我们的目前的状态再与当前数字进行一个亦或(为什么使用|呢,因为我们左移之后我们的当前的位置肯定是0,假设我们输入的数字是0的话,那么就是0,假设不是的就是1,恰好符合了我们亦或的性质)
2. 然后是我们的搜索部分(当时我是无论如何都想不到),竟然可以直接枚举每一个相邻的数字,然后记录换之后的状态,以此作为枚举方式

首先是如何选出我们的两个数字,我们采用下列循环的方式进行

为什么要使用下列方式进行枚举呢,因为假设我们直接使用0~3,0~3这样进行双循环的话,将会导致最后一个位置
是无法没枚举到的,下列这种巧妙的枚举方式很好的解决了这个问题,check(i,j,0)用来,枚举水平方向
check(j,i,0)来枚举竖直方向,这样还巧妙的避免了撞墙的问题
for(int i=0;i<4;i++) {
	for(int j=0;j<3;j++) {
		if(check(i,j,0)) {
			return ;
		}else if(check(j,i,1)) {
			return ;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

然后是根据我们的横纵坐标找出我们那个位置的数字

因为我们已经进行状压来存储了,所以我们当前的状态其实是一个数字

我们可以采用 且(&) 运算来进行选出

为了方便起见我们是用to_pos来快速获得我们的位置

	int now_state=f.state&(1<<to_pos[x][y]);
	//这是选出前一个位置的数字,显然一个数字与他本身就是他自己
	int next_state=f.state&(1<<to_pos[x+flag][y+!flag]);
1
2
3

然后我们进行交换操作

	int now=f.state&(~now_state)&(~next_state);
	//首先是上半部分,这里需要结合下部分一起结合理解
	now=now|(now_state>>to_pos[x][y]<<to_pos[x+flag][y+!flag])|(next_state>>to_pos[x+flag][y+!flag]<<to_pos[x][y]);
	//先右移相应的位置,再移回来,感觉这部分的移动还是挺好理解的
1
2
3
4

对于这一部分,我们假设我们的now_state和我们的next_state覆盖了0,1,这种情况还是比较好

理解的,首先我们这两个数字除了我们需要的那一位之外都是0,此时我们取反时候都变成了1,那么进

行与运算肯定是对我们的原状态是没有任何影响的.所以可以这么认为,我们只需要关注选出的两个

位置即可.所以此时我们的那一个位置假设是1的话,我们取一个反就变成了0,那么与一下之后就将原状
态变成了0(也就是这个数字交换了0),反之亦然.

但是当我们的两个数字都是一样时(比如都是0或者1时),此时我们的状态似乎变的有一点点的奇怪,

因为此时我们的状态应该是不应该进行改变的,但是此时将其改变了,这是为什么呢??此时我们应该

关注我们的下一行的代码,当我们加入下一行的代码时,我们发现下一行代码又重新将我们改变过的

值又重新赋值为我们的原本的值了,所以并没有进行一个改变

搞懂之前的一些细节之后我们的代码也就不难写出了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int st_state=0,end_state=0;
int to_pos[6][6]={{15,14,13,12},{11,10,9,8},{7,6,5,4},{3,2,1,0}};
struct Node{
	int step,state;
};
queue<Node>q;
int vis[1<<16+10];
int check(int x,int y,int flag) {
	Node f=q.front();
	int now_state=f.state&(1<<to_pos[x][y]);
	int next_state=f.state&(1<<to_pos[x+flag][y+!flag]);
	int now=f.state&(~now_state)&(~next_state);
	now=now|(now_state>>to_pos[x][y]<<to_pos[x+flag][y+!flag])|(next_state>>to_pos[x+flag][y+!flag]<<to_pos[x][y]);//交换两个数的值
	if(now==end_state) {
		printf("%d\n",f.step+1);
		return true;
	}
	if(vis[now]) return false;
	vis[now]=1;
	q.push({f.step+1,now});
	return false;
}
void BFS() {
	q.push({0,st_state});
	vis[st_state]=1;
	if(q.front().state==end_state) {//注意刚开始就是答案,可能不需要变换
		printf("0\n");
		return ;
	}
	while(!q.empty()) {
		for(int i=0;i<4;i++) {
			for(int j=0;j<3;j++) {
				if(check(i,j,0)) {
					return ;
				}else if(check(j,i,1)) {
					return ;
				}
			}
		}
		q.pop();
	};
}
int main() {
	char c;int num;
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=4;j++) {
			cin>>c;
			num=c-'0';
			st_state=((st_state<<1)|num);
		}
		scanf("%c",&c);
	}
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=4;j++) {
			cin>>c;
			num=c-'0';
			end_state=((end_state<<1)|num);
		}
		scanf("%c",&c);
	}	
	BFS();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89