Yuzhen's Blog

Yuzhen Qin

题解:P10449 费解的开关

4
2024-06-17

使用 std::bitset 优化 DFS 爆搜解决。

首先预处理出按下每一个开关后改变的灯的 bitset

然后进行 DFS 搜索,每次选择一个灯按开关,使用 ^(按位异或)操作改变灯的状态。使用 bitset::count() 函数获得亮着的灯的个数,如果返回值为 25,就代表所有灯都已经变亮。

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

bool a[5][5], b[5][5];
bitset<25> status[25];

bitset<25> compress(bool* arr) {
	bitset<25> res;
	res.reset();
	for(int i = 0; i < 5; i++)
		for(int j = 0; j < 5; j++)
			res[i * 5 + j] = arr[i * 5 + j];
	return res;
}

int dfs(int dep, int lst, bitset<25> bs) {
	if(bs.count() == 25)
		return dep;
	if(dep == 6)
		return -1;
	
	int ans = 7;
	for(int i = lst + 1; i < 25; i++) {
		int tmp = dfs(dep + 1, i, bs ^ status[i]);
		if(tmp != -1)
			ans = min(ans, tmp);
	}
	
	return (ans == 7 ? -1 : ans);
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(/* nullptr */ 0);
	cout.tie(/* nullptr */ 0);
	
	int n;
	cin >> n;
	
	for(int i = 0; i < 5; i++)
		for(int j = 0; j < 5; j++) {
			b[i][j] = 1;
			if(i > 0) b[i - 1][j] = 1;
			if(i < 4) b[i + 1][j] = 1;
			if(j > 0) b[i][j - 1] = 1;
			if(j < 4) b[i][j + 1] = 1; 
			status[i * 5 + j] = compress((bool*)b); 
			b[i][j] = 0;
			if(i > 0) b[i - 1][j] = 0;
			if(i < 4) b[i + 1][j] = 0;
			if(j > 0) b[i][j - 1] = 0;
			if(j < 4) b[i][j + 1] = 0; 
		}
	
	while(n--) {
		for(int i = 0; i < 5; i++) {
			string str;
			cin >> str;
			for(int j = 0; j < 5; j++)
				a[i][j] = str[j] - '0';
		}

		cout << dfs(0, -1, compress((bool*)a)) << '\n';
	}
	
	return 0;
}