题目描述
你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。
给定一些游戏的初始状态,编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
样例
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
3
2
-1
看到题的第一眼肯定是搜索
但爆搜的复杂度是无法承受的
所以我们考虑剪枝
剪枝1
当前操作次数>min(6,f)时return,其中f为当前搜到的最少次数
剪枝2
令x为当前所搜索的行,则当x-2这一行中有灯未开时,return
加上这些剪枝就可以愉快地AC啦!
代码
#include<bits/stdc++.h>
using namespace std;
const int n=5;
int f=10;
int a[10][10];
void solve(int x,int y) {
a[x][y]^=1;
a[x+1][y]^=1;
a[x][y+1]^=1;
a[x-1][y]^=1;
a[x][y-1]^=1;
}
void dfs(int x,int y,int s) {
if(s>min(f,6)) {
return ;
}
if(x==n&&y==n+1) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(a[i][j]==0) {
return ;
}
}
}
f=min(f,s);
return ;
}
if(y==n+1) {
dfs(x+1,1,s);
return ;
}
if(y==1&&x>2) {
for(int j=1; j<=n; j++) {
if(a[x-2][j]==0) {
return ;
}
}
}
dfs(x,y+1,s);
solve(x,y);
dfs(x,y+1,s+1);
solve(x,y);
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
f=10;
for(int i=1; i<=n; i++) {
string s;
cin>>s;
for(int j=1; j<=n; j++) {
a[i][j]=s[j-1]-'0';
}
}
dfs(1,1,0);
if(f==10) {
printf("-1\n");
} else {
printf("%d\n",f);
}
}
}