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

解题思路:这是一道模拟题，题目要求找出所有符合情况的答案，显而易见数据量很小，这是比较比较符合dfs解题的思路的。

用dfs来解题的话首先得想明白搜索树的构造：显然每个开关只有选或者不选的情况，也就是说每个节点的分支只有两个，就不需要用for循环来表示不同的分支了，直接把两种状态（开或不开）写在一起就好。搜索树的深度也很明显——九个开关，也就是深度为九，那么当第九个开关判断完毕时就要对这次遍历进行分析：若是满足只有四盏灯打开的状态，就要把这次的灯的开关情况记录一下。

注意事项:由于要满足字典序最小，所以把不开灯的情况写在前面。

回溯的时候开关的情况和灯的情况都要变回去。

参考代码:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int a[10];

int ans[10][1000];

int st[10];

int cnt = 0;

bool check()

{

int count = 0;

for(int i=1;i<=9;i++)

if(a[i]) count++;

if(count==4) return true;

else return false; 

} 

void dfs(int step)

{

if(step>9)

{

if(check())

{

cnt++;

for(int i=1;i<=9;i++)

ans[i][cnt] = st[i];

}

return;

}

if(step==1)

{

dfs(step+1);

a[2] = !a[2];

a[4] = !a[4];

st[1] = 1;

dfs(step+1);

a[2] = !a[2];

a[4] = !a[4];

st[1] = 0;

}

if(step==2)

{

dfs(step+1);

a[1] = !a[1];

a[3] = !a[3];

a[5] = !a[5];

st[2] = 1;

dfs(step+1);

st[2] = 0;

a[1] = !a[1];

a[3] = !a[3];

a[5] = !a[5];

}

if(step==3)

{

dfs(step+1);

a[2] = !a[2];

a[6] = !a[6];

st[3] = 1;

dfs(step+1);

st[3] = 0;

a[2] = !a[2];

a[6] = !a[6];

}

if(step==4)

{

dfs(step+1);

a[1] = !a[1];

a[5] = !a[5];

a[7] = !a[7];

st[4] = 1;

dfs(step+1);

st[4] = 0;

a[1] = !a[1];

a[5] = !a[5];

a[7] = !a[7];

}

if(step==5)

{

dfs(step+1);

a[2] = !a[2];

a[4] = !a[4];

a[6] = !a[6];

a[8] = !a[8];

st[5] = 1;

dfs(step+1);

st[5] = 0;

a[2] = !a[2];

a[4] = !a[4];

a[6] = !a[6];

a[8] = !a[8];

}

if(step==6)

{

dfs(step+1);

a[3] = !a[3];

a[5] = !a[5];

a[9] = !a[9];

st[6] = 1;

dfs(step+1);

st[6] = 0;

a[3] = !a[3];

a[5] = !a[5];

a[9] = !a[9];

}

if(step==7)

{

dfs(step+1);

a[4] = !a[4];

a[8] = !a[8];

st[7] = 1;

dfs(step+1);

st[7] = 0;

a[4] = !a[4];

a[8] = !a[8];

}

if(step==8)

{

dfs(step+1);

a[9] = !a[9];

a[7] = !a[7];

a[5] = !a[5];

st[8] = 1;

dfs(step+1);

st[8] = 0;

a[7] = !a[7];

a[9] = !a[9];

a[5] = !a[5];

}

if(step==9)

{

dfs(step+1);

a[6] = !a[6];

a[8] = !a[8];

st[9] = 1;

dfs(step+1);

st[9] = 0;

a[6] = !a[6];

a[8] = !a[8];

}

}

int main()

{

dfs(1);

for(int i=1;i<=cnt;i++)

{

for(int j=1;j<=9;j++)

printf("%d",ans[j][i]);

printf("\n");

}

return 0;

}