搜索开关问题

学习
字数统计: 2.1k   |   阅读时长≈ 9 分钟

搜索开关问题

开关问题是RoysterCDD自己取的名字，表示一类用位运算解决的搜索变种问题

[例1]. 翻硬币

image-20240211111035470
  • 本题的思路是直接用两个字符数组$start$和$finish$来存储初始状态和结束状态，因为题目说一定有解，所以对比两个数组，出现状态不同，则翻转该硬币和相邻硬币即可，假设每两个硬币间存在一个开关，按下该开关即可翻转相邻两枚硬币的状态
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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 题目描述: 给你一个初始状态,一个目标状态,还有某种操作,最常用做法:BFS,同样的题目还有八数码
// 但是BFS时间复杂度比较高,局面很多的话应考虑其他做法,可以考虑和费解的开关相同的做法
// 假设每两个灯泡之间中间有一个开关,这个开关按下后可以翻转其两侧灯泡的亮灭状态
// 这样的话想从初始状态到最终状态(假设每个开关只摁一次)只有唯一的一组解

const int N=100+10;
int n;
char start[N],finish[N];

void turn(int i) {
	if(start[i]=='*') start[i]='o';
	else start[i]='*';
}

int main() {
	cin>>start>>finish;
	n=strlen(start); // 初始状态的长度,即硬币的总个数
	int res=0;
	for(int i=0;i<n-1;i++) {
        // 如果状态不相同,则翻转该硬币和相邻硬币的状态
		if(start[i]!=finish[i]) {
			turn(i),turn(i+1);
			res++;
		}
	}
	cout<<res;
	return 0;
}

[例2]. 费解的开关

image-20240211100922703

image-20240211104635922
  • 题目的思路：输入图的状态后，我们对第一行灯的操作，实际上就能够确定剩下四行我们应该对灯进行什么操作，所以枚举第一行的每种操作，从$00000$到$11111$，$1$表示翻转，$0$表示不翻转，$[0,31]$共$32$种情况，所以枚举$op=[0,31]$，用位运算的方式判断每一位是否为$1$
  • 当第一行的操作确定后，比如$g[0,2]==0$，那我们就要去点亮第二行的$g[1,2]$，用上下左右的上方向去点亮第一行未被点亮的灯，对于剩余行的操作都是一样的，遍历完后如果我们发现最后一行有未被点亮的灯或者操作数多于6次，那么就无法达到，输出$-1$即可
  • 对于每种第一行的操作，我们用$res=min(res,step)$来更新最小的答案，本题的技巧还有位运算的技巧、二进制状态表示、准备一个备份数组$backup[N][N]$用于状态复原等
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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
using namespace std;

const int N=6;
char g[N][N],backup[N][N]; // 图和备份
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0}; // 五个方位(0,0表示本身这个点)

void turn(int x,int y) {
	for(int i=0;i<5;i++) {
		int a=x+dx[i], b=y+dy[i];
		if(a<0 || a>=5 || b<0 || b>=5) continue; // 越界处理
		// 因为0和1的ASCII码表示分别为48(110000和49(110001)
		// 所以只需要亦或一个1,亦或0不变,亦或1反转,亦或一个1反转最后一位
		g[a][b]^=1; // 即可让48->49,49->48
	}
}

int main() {
	// 每一行开关的操作完全被前一行灯的亮灭状态所确定
	int T;
	cin>>T;
	while(T--) {
		for(int i=0;i<5;i++) cin>>g[i]; // 输入图
		int res=10;
		
		// 我们枚举第一行的操作
		// 0~31表示的是00000到11111(遍历每一种操作,1表示我们翻转,0表示不翻转)
		for(int op=0;op<32;op++) {
			memcpy(backup,g,sizeof g); // 复制g给backup,操作g
			int step=0;
			// 判断第一行中op共5位中哪一位是1
			for(int i=0;i<5;i++) {
				// op>>i&1:先右移i位,现在第i位变成最低位,再看是否为1
				if(op>>i&1) {
					step++; // 经过一次操作
					turn(0,i); // 翻转为1的这一位的状态
				}
			}
			
			// 所以第一行的状态影响了接下来所有行的状态
			// 遍历第一行到倒数第二行,如果为0的话就翻转
			for(int i=0;i<4;i++) {
				for(int j=0;j<5;j++) {
					if(g[i][j]=='0') {
						step++; // 如果为0那么需要翻转一次
						turn(i+1,j); // 下一行的第j个元素需要翻转
					}
				}
			}
			bool dark=false;
			for(int i=0;i<5;i++) {
				// 如果最后一行有没亮的,那就别无他法了
				if(g[4][i]=='0') {
					dark=true;
					break;
				}
			}
			if(!dark) res=min(res,step);
			memcpy(g,backup,sizeof g); // 恢复状态
		}
		if(res>6) res=-1; // 题目要求不能超过6步
		cout<<res<<endl;
	}
	return 0;
}

[例3]. 飞行员兄弟

image-20240211105824073

image-20240211105917746

image-20240211105930997
  • 本题的思路类似，一共$16$个开关，所以方案总数是$2^{16}=65535$种，故枚举$[0,2<<16]$来表示对于这$16$的开关的操作，所以这个$int$型的二进制表示中某一位的值是$1$表示我们要改变这个开关的状态，$0$则表示不改变，枚举每种操作，最后看是否能够使所有把手都打开，如果可以的话把方案加入到$vector$数组中，最后打印即可
  • 技巧：$get(x,y)$函数返回的值代表二维数组中对应位置在二进制表示中的第几个开关（下标）
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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 题目描述: 本题的难点在于每个灯泡可以被很多开关所控制
// 用暴力法来做,只有4*4=16个开关,所以每个开关嗯的方案数是2^16=65536
// 枚举所有方案→0~2^16-1,用二进制表示,某位为1是摁下,为0表示不摁
// 按照该方案对所有灯泡进行操作,判断灯泡是不是全亮,是的话则记录方案
// 现在要求:步数最小/字典序最小(从小到大排序就可以了)

const int N=5;
char g[N][N],backup[N][N];

// 返回的是(x,y)上的数是第几个开关,从上往下从左往右编号
int get(int x,int y) {
	return x*4+y; // 从0~15
}

// "+"和"-"翻转
void turn_one(int x,int y) {
	if(g[x][y]=='+') g[x][y]='-';
	else g[x][y]='+';
}

void turn_all(int x,int y) {
	for(int i=0;i<4;i++) {
		turn_one(x,i); // 这一行上的数翻转状态
		turn_one(i,y); // 这一列上的数翻转状态
	}
	turn_one(x,y); // 因为(x,y)在这一行和这一列交汇处,所以翻转两次相当于没有翻转,再单独翻转一次
}

int main() {
	for(int i=0;i<4;i++) {
		cin>>g[i];
	}
	vector<PII> res; // 存储所有的方案
	// 枚举每种操作情况,每个开关对应开和不开两种状态,方案数是2^16
	for(int op=0;op<1<<16;op++) {
		vector<PII> temp; // 每次新开一个,相当于清空了
		memcpy(backup,g,sizeof g); // 备份图
		for(int i=0;i<4;i++) {
			for(int j=0;j<4;j++) {
				// 如果op在这一位上的值为1
				if(op>>get(i,j)&1) {
					// 向temp中记录一下操作数
					temp.push_back({i,j});
					turn_all(i,j); // 进行一次反转操作
				}
			}
		}		
		// 判断所有灯泡是否全亮
		bool has_closed=false;
		for(int i=0;i<4;i++) {
			for(int j=0;j<4;j++) {
				if(g[i][j]=='+')
					has_closed=true;
			}
		}
		if(has_closed==false) {
			if(res.empty()||res.size()>temp.size()) res=temp;
		}
		memcpy(g,backup,sizeof g); // 还原
	}
	
	cout<<res.size()<<endl; // 方案总数
	// 打印每一种方案
	for(auto op:res) cout<<op.x+1<<' '<<op.y+1<<endl; // 坐标+1
	
	return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信