【洛谷P1225】黑白棋游戏【DFS】【状压】

分析

这题看到整个矩阵只有16个数，且都是0/1，所以考虑用一个16位二进制数来存整个状态。然后用一个数组就可以存所有的状态（判断是否曾经到达）

我们从（3,3）开始枚举每个点，从开始状态开始搜索。矩阵的坐标是这样设计的：

  3 2 1 0
3  
2 
1
0
1
2
3
4
5

每次都判断能否向下或者向右交换（数字不一样且状态没访问过），能访问就入队。记录前驱和坐标，后面递归输出。

关于二维与一维的转换和一些位运算解析：

1. pos=4*i+j;//在16位中的位置 
2. q[h]&(1<<pos)//取出第pos位
3. temp=q[h]^(3<<pos-1)//将自己和右边的交换
4. temp=q[h]^((1<<pos)+(1<<pos-4))//将自己和下面的交换
5. p1[q[t]]=(5-(i+1))*10+(5-(j+1));
   p2[q[t]]=(5-(i+1))*10+(5-(j+1)+1);//转为横纵坐标的记录
1
2
3
4
5
6

其实在存状态是否被访问的时候，还可以再压缩，现在是一个整数存一个“能或不能”，其实可以一位存一个，又压缩到1/32了，但是较难实现，我没有使用。

瞎扯淡：今天早上调了好久，下午睡一觉过来打了不到30min过了样例，很兴奋，小心翼翼又试了很多次，结果洛谷一次过，差点跳起来！

上代码

#include
#include
#include
using namespace std;

int v[1<<16],step[1<<17],p1[1<<17],p2[1<<17];
int q[1<<17],pre[1<<16],rec[1<<16],tot;//pre前驱,nxt后继 
int target,st;

void putchange(int now)
{
	if(now==st) return;
	rec[++tot]=p1[now]*100+p2[now];
    //cout<
    putchange(pre[now]);
}

void bfs()
{
	int h=0,t=1;
	q[t]=st;
	v[st]=1;
	step[st]=0;
	while(h<t)
	{
		h++;
		for(int i=3;i>=0;i--)
		{
			for(int j=3;j>=0;j--)
			{
				int pos=4*i+j;//在16位中的位置 
				if(j>0&&(q[h]&(1<<pos))!=((q[h]&(1<<pos-1))<<1))//向右 
	            {
	            	int temp=q[h]^(3<<pos-1);
	            	if(!v[temp])
	                {
	                	v[temp]=1;
						step[temp]=step[q[h]]+1;
						q[++t]=temp;
						pre[q[t]]=q[h]; 
						p1[q[t]]=(5-(i+1))*10+(5-(j+1));
						p2[q[t]]=(5-(i+1))*10+(5-(j+1)+1);
						if(q[t]==target)
						{
							putchange(target);
							return; 
						} 
					} 
				}
				if(pos>=4&&(q[h]&(1<<pos))!=((q[h]&(1<<pos-4))<<4))//下 
				{
					int temp=q[h]^((1<<pos)+(1<<pos-4));
					if(!v[temp])
					{
						v[temp]=1;
						step[temp]=step[q[h]]+1;
						q[++t]=temp;
						pre[q[t]]=q[h];
						p1[q[t]]=(5-(i+1))*10+(5-(j+1));
						p2[q[t]]=(5-(i+1)+1)*10+(5-(j+1));
						if(q[t]==target)
						{
							putchange(target);
							return; 
						} 
					}
				}
			}
		}
	} 
}

int main()
{
    for(int i=1;i<=4;i++)
    {
    	for(int j=1;j<=4;j++)
    	{
    		char c;
    		cin>>c;
    		st=(st<<1)+(c-48);
		}
	}
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			char c;
			cin>>c;
			target=(target<<1)+(c-48);
		}
	}
	bfs();
	cout<<step[target]<<endl;
	for(int i=tot;i>=1;i--)
	{
		cout<<rec[i]<<endl;
	}
	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
90
91
92
93
94
95
96
97
98
99
100