蓝桥杯算法提高VIP-开灯游戏 （C++代码）

解题思路:

        模拟 + DFS。其中最巧妙的就是如何记录开关的某个组合出现过，当然是 Hash 值啦。

参考代码:

#include<bits/stdc++.h> /* 一共 112 个组合，5 ms 哟 */
using namespace std;
const int SIZE = 23277;         /*   随便开个数啦   >v<  */

bool Light[10]; 
bool Status[SIZE]; int Index;   /*   存储开关的某个状态  */

/*   用结构体存储开关组合，用作排序输出   */
struct Ans {
	char num[10];
} ans[144];

/*   模拟灯   */
void OPT(char button[], int num) {
	/*  改变灯  */
	if (num == 1)      Light[2] = !Light[2], Light[4] = !Light[4];
	else if (num == 2) Light[1] = !Light[1], Light[3] = !Light[3], Light[5] = !Light[5];
	else if (num == 3) Light[2] = !Light[2], Light[6] = !Light[6];
	else if (num == 4) Light[1] = !Light[1], Light[5] = !Light[5], Light[7] = !Light[7];
	else if (num == 5) Light[2] = !Light[2], Light[4] = !Light[4], Light[6] = !Light[6], 
	                   Light[8] = !Light[8];
	else if (num == 6) Light[3] = !Light[3], Light[5] = !Light[5], Light[9] = !Light[9];
	else if (num == 7) Light[4] = !Light[4], Light[8] = !Light[8];
	else if (num == 8) Light[5] = !Light[5], Light[7] = !Light[7], Light[9] = !Light[9];
	else if (num == 9) Light[6] = !Light[6], Light[8] = !Light[8];
	
	/* 改变开关 */
	if (button[num - 1] == '1')
		button[num - 1] = '0';
	else
		button[num - 1] = '1';
}

/*   Hash函数计算开关某个状态对应的一个值   */
int  Hash(char button[]) {
	int hash = 0;
	for (int i = 1; i < 10; i++)
		hash = hash * i + button[i - 1] + 7;
	return hash % 16529; /* 16529 是一个素数 */
}

/*     判断当前灯是否亮了 4 盏    */
bool Judge() {
	int total = 0;
	for (int i = 1; i < 10; i++)
		if (Light[i])
			total++;
	return total == 4;
}

void DFS(char now[]) {
	if (Judge()) {
		strcpy(ans[Index++].num, now); return;
	}
	/*   每个按钮都一遍   */
	for (int button = 1; button < 10; button++) {
		OPT(now, button);                   /*     按下去.jpg     */
		int StatusValue = Hash(now);        /*   计算开关状态值   */
		if (!Status[StatusValue]) {
			Status[StatusValue] = true;
			DFS(now);                       /*     继续到处按     */
		}
		OPT(now, button);                   /*  回溯  */
	}
}

bool cmp(Ans ans1, Ans ans2) {
	return strcmp(ans1.num, ans2.num) < 0;
}

int main() {
	/*clock_t Sta = clock();*/
	char init[] = "000000000";              /*  初始状态全关闭  */

	Status[Hash(init)] = true; DFS(init);

	sort(ans, ans + Index, cmp);

	for (int i = 0; i < Index; i++)
		printf("%s\n", ans[i].num);

	/*clock_t End = clock();
	cout << (double)(End - Sta) / CLOCKS_PER_SEC << endl;*/
}