费解的开关(Vijos 1197)思路

[原题链接](https://www.vijos.org/p/1197) ## 思路 先分析，按开关的顺序不影响结果。因此，这个按开关操作满足：①交换律；②每个元素的逆元都是它本身，因为按两次就相当于不按。于是可知，一个开关不可能重复按下，在一种方案中每个开关只有按和不按两种状态。 于是就有了思路。最朴素的算法当然就是暴力枚举+判断了。一共25个开关，最多按6个，因此最多枚举（搜索）量是C(25,0)+C(25,1)+C(25,2)+C(25,3)+C(25,4)+C(25,5)+C(25,6)。这个思路时间复杂度较大，只能通过n<6的数据点，即只能得30分。 而我们会发现很多枚举出来的方案都是不可能打开所有灯的。当我们按从左到右、从上到下的顺序枚举时，我们会发现，枚举到某一盏灯的时候，它左上角的灯的开关状态已经确定了（因为我们已经枚举过了所有可能改变它的状态的开关）。那么，如果此时左上角的这盏灯还没有打开，这种方案就永远不可能把所有灯的灯打开，我们就应该把它从搜索树上剪掉。进行这样的可行性剪枝，可以大大降低算法的时间复杂度。优化后的代码可在20ms之内通过单个测试点。 ## 代码 下面是优化后的代码。相比优化前，这份代码只增加了2行，但是时间却大大减少，由此我们认识到优化剪枝的重要性。 ```cpp #include <iostream> #define MAXN 9 using namespace std; void solve(void); void change(int x,int y); bool get(void); bool judge(void); void dfs(int pos,int k); bool a[MAXN][MAXN]; int ans; int main(void){ //主函数 int i,j,k,n; cin >> n; for (i=0;i<n;i++){ for (j=1;j<=5;j++) for (k=1;k<=5;k++) a[j][k]=get(); solve(); } return 0; } void solve(void){ //每组数据的独立解函数 ans=7; dfs(1,0); ans=(ans>=7)?-1:ans; cout << ans << endl; } void change(int x,int y){ //按一下第x行第y列的开关 a[x][y]=!a[x][y]; a[x-1][y]=!a[x-1][y]; a[x+1][y]=!a[x+1][y]; a[x][y-1]=!a[x][y-1]; a[x][y+1]=!a[x][y+1]; } bool get(void){ //输入函数 char ch; while (1){ cin >> ch; if (ch=='0') return 0; if (ch=='1') return 1; } } void dfs(int pos,int k){ //搜索函数 int x,y; x=(pos-1)/5+1; y=pos%5; y=y?y:5; //Turn 0 to 5 if (x>1&&y>1&&(!a[x-1][y-1])) return; //以上两行是优化的关键代码 if (k>=ans) //保证只操作6次（并进行最优化剪枝） return; if (pos==26){ if (judge()) ans=k; return; } dfs(pos+1,k); change(x,y); dfs(pos+1,k+1); change(x,y);//Change back } bool judge(void){ //判断是否所有灯都打开 bool ok=1; int i,j; for (i=1;i<=5;i++) for (j=1;j<=5;j++) ok=ok&a[i][j]; return ok; } ```