题目描述
解题报告
题意理解
首先看到开关二字，可能有小伙伴会想到能不能用递推中的开关模型来解决了。回想之前可以使用递推的开关习题的特点：它们开关的状态是开还是关都是由一些条件导致它们必须这么摁。
但是对于这道题而言，就不能这么，因为涉及的开关太多，就不存在这种使得开关摁法可以唯一确定的情况。
此时观察数据范围，发现它只有4个，那么可以估计一下可爱的暴力枚举能不能行了，通过算运算次数来大致确定时间复杂度。
16个开关，只有开或者不开两种情况，那么总共就是从0枚举到2 16 − 1 2^{16}-12
16
−1，也就是65536种情况。记住这每种情况，咱们都看成一个16位的二进制的数，以此模仿棋盘。如果某个位置上对应的二进制数是0就摁一下，是1就不摁
内层第一个枚举：
在这65536种情况中，每次还是需要去枚举16个位置是要打开还是关闭，每个开关最多会操作周围的七个灯泡。
内层第二个枚举：
以及枚举检查每个灯泡的状态是不是全部打开了，以及最后的记录方案，那么大致的运算次数就是65536 ∗ ( 16 ∗ 7 + 16 + 16 ) 65536*(16*7+16+16)65536∗(16∗7+16+16)
大概是一千万次的运算。C++一秒大约能算1亿次，没有问题。
关于字典序
题目中的从上到下，从左到右打开的顺序其实就是字典序。
解决这个还是比较简单的，只要我们在枚举的时候就是按照字典序枚举的，也就是按照从小到大的枚举顺序进行，最后得到的结果也一定是按照字典序的。
实现流程
第一步：枚举65536种方案。
第二步：按照该方案对16个灯泡进行操作。
第三步：判断操作以后是不是所有灯泡都亮了，假如都亮了，记录方案。因为要求最小步数，那么每次找到一个方案都要和之前方案进行比较。
细节
一、备份与还原备份
二、输出的答案中，起点是(1,1)。终点是(4,4)。因为咱们创建地图是从0开始的，所以要输出结果都+1
参考代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #define x first #define y second using namespace std; typedef pair<int,int> PII; const int N = 5; int n; char g[N][N],backup[N][N]; int get(int x,int y) { return 4 * x+ y; } 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); } //（x,y）多摁了一次，摁回来 turn_one(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++) if(!(op >> get(i,j)&1)) //get(i,j)这个函数是通过坐标确定当前到底是地图中0~15中的哪个数 { temp.push_back({i,j}); turn_all(i,j);//改变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) //如果用于存放答案的数组为空，或者存放的步数比现在新测试出来的大，就更新res if(res.empty() || res.size() > temp.size()) res = temp; //还原备份 memcpy(g,backup,sizeof backup); } cout << res.size() << endl; //注意题目中是从1开始的 for(auto r:res) cout << r.x+1 << ' ' << r.y+1<<endl; }
总结
至此为止，由递推作为背景的开关问题就告一段落啦。
