题目描述
解题报告
一、题意理解
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
使用windows自带的画图，摁住shift拖动鼠标画出下列的图形进行演示。
样例演示：
二、每一行开关的操作完全由前一行灯的亮灭决定
- 假设第一行的所有状态用枚举来确定，每个开关要么摁，要么不摁，在这里就是2 5 2^52 5 次种选法。
- 依次依据前一行的亮灭状态，决定它的下一行可以怎么摁，才能保证这个前一行是亮的。
/
三、细节敲定
1.如何枚举第一行的32中操作。一个五位二进制正好可以表示这32种操作。比如
11010 => 对应第26个操作。那么0 ~ 2 5 2^52 5-1就可以逐一对应枚举第一行会有的32种方案
2.开关点亮函数
点击一个位置的开关以后，它上下左右四个位置的开关都会被改变状态。用四个i f ifif就显得太麻烦了。这里考虑的是通过添加偏移量实现。
3.时间复杂度
32 ∗ 25 ∗ 5 ∗ 500 = 2000000 32 * 25 * 5 * 500 = 200000032∗25∗5∗500=2000000,大概是两百万次的运算。是完全没有问题的
参考代码
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 6; char g[N][N],backup[N][N]; int dx[] = {-1,0,1,0,0} , dy[] = {0,-1,0,1,0}; //补全turn 函数 void turn(int x,int y) { for(int i = 0; i < 5;i++) { int a = x+dx[i] , b = y + dy[i]; //判断边界 if(a < 0 || a >= 5 || b < 0 || b>= 5) continue; //更新状态 g[a][b] ^= 1; } } int main() { int T; cin >> T; while(T--) { //构建地图 for(int i = 0; i < 5;i++) cin >> g[i]; int res = 10;//记录答案 //枚举第一行的32种选择 for(int op = 0; op < 32;op++) { memcpy(backup,g,sizeof g); int step = 0;//记录执行的步骤 //处理当前这个方案是否有可以摁亮的灯 for(int i = 0; i < 5; i++) { if(!(op >> i &1)) { step ++; turn(0,i); } } //根据第一行现在的情况，处理后面四行的处理情况 for(int i = 0; i < 4;i++) { for(int j = 0; j < 5;j++) if(g[i][j] == '0') { step ++; turn(i+1,j); } } //遍历最后一行，倘若有黑的灯，那么当前方案失败 bool dark = false;//标记 for(int i = 0; i < 5;i++) if(g[4][i] == '0') { dark = true; break; } if(!dark) res = min(res,step); memcpy(g,backup,sizeof g);//从备份中把数据拿回来 } if(res > 6) res = -1;//res = -1代表无解 cout << res << endl; } return 0; }
