我对状态空间的理解:https://www.cnblogs.com/AKMer/p/9622590.html
题目传送门:http://www.joyoi.cn/problem/tyvj-1266
这道题的状态空间就是经过若干次开关灯之后每盏灯的状态。
然后我们可以一行一行的来开关灯。首先我们得了解两个性质:
1、每一盏灯要么不动它的开关,要么只动一次。(显然)
2、第\(i\)行我们需要按下开关的灯的位置,在第\(i-1\)行必然是关着的。(因为前\(i-1\)行不会再动了,所以我们必须要关这些位置使得前面\(i-1\)行全亮)
所以、我们可以用一个\(5\)位二进制串来枚举第一行的操作,后面就都跟着性质2做就好了。做完最后一排判断是否全亮,如果全亮就更新答案,否则反之。
时间复杂度:\(O(2^n*n^2)\)
空间复杂度:\(O(n^2)\)
代码如下:
#include <cstdio>
#include <algorithm>
using namespace std;
const int inf=2e9;
int ans;
char s[6];
int mp[6][6];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
void change(int x,int y) {
for(int k=0;k<4;k++) {
int nx=x+dx[k],ny=y+dy[k];
if(nx<0||nx>4||ny<0||ny>4)continue;
mp[nx][ny]^=1;
}mp[x][y]^=1;
}//开一次开关影响五盏灯
bool check() {
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
if(!mp[i][j])return 0;
return 1;
}//判断是否全部亮起
void dfs(int layer,int tot) {
if(tot>6)return;//步数大于6不要
if(layer==5) {if(check())ans=min(ans,tot);return;}//更新答案
int sta=0,sum=tot;
for(int i=0;i<5;i++)
if(!mp[layer-1][i])sta|=1<<i,change(layer,i),sum++;//将上一行是0的位置全部按下开关,使得前layer-1行全部都是1,
dfs(layer+1,sum);
for(int i=0;i<5;i++)
if(sta&(1<<i))change(layer,i);//还原现场
}
int main() {
int T=read();
while(T--) {
for(int i=0;i<5;i++) {
scanf("%s",s);
for(int j=0;j<5;j++)
mp[i][j]=s[j]-'0';
}ans=inf;
for(int s=0;s<1<<5;s++) {//枚举第一行操作
int tot=0;
for(int i=0;i<5;i++)
if(s&(1<<i))change(0,i),tot++;//按下第一行开关
dfs(1,tot);
for(int i=0;i<5;i++)
if(s&(1<<i))change(0,i);//还原现场
}
if(ans==inf)puts("-1");
else printf("%d\n",ans);
}
return 0;
}