关灯问题II （状态压缩 BFS）

题目描述

现有n盏灯，以及m个按钮。每个按钮可以同时控制这n盏灯——按下了第i个按钮，对于所有的灯都有一个效果。按下i按钮对于第j盏灯，是下面3中效果之一：如果a[i][j]为1，那么当这盏灯开了的时候，把它关上，否则不管；如果为-1的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是0，无论这灯是否开，都不管。

现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。

输入格式

前两行两个数，n m

接下来m行，每行n个数,a[i][j]表示第i个开关对第j个灯的效果。

输出格式

一个整数，表示最少按按钮次数。如果没有任何办法使其全部关闭，输出-1

输入输出样例

输入

输出

说明/提示

对于20%数据，输出无解可以得分。

对于20%数据，n<=5

对于20%数据，m<=20

上面的数据点可能会重叠。

对于100%数据 n<=10,m<=100

我们用二进制的每一位代表一个灯，

对于n个灯，一共有 (1<<n)-1 个状态，而对于第i个灯进行操作的时候是 1<<(i-1) 。

我们把初始状态，用每个操作都试一遍，就产生了许多新的状态，把新状态入队，然后又可以产生新的新状态，我们逐一尝试，直到有目标状态为止。

 1 #include <bits/stdc++.h>
 2 #define pb push_back
 3 #define fi first
 4 #define se second
 5 typedef long long LL;
 6 const int INF=0x3f3f3f3f;
 7 const double eps =1e-8;
 8 const int mod=1e9+7;
 9 const int maxn=1e5+10;
10 using namespace std;
11 
12 int a[5005][5005];
13 int vis[5005];//记录每个状态是否出现过，防重复计算 
14 int n,m;
15 int ans;
16 
17 void BFS()
18 {
19     queue<pair<int,int> > qe;
20     qe.push({(1<<n)-1,0}); vis[(1<<n)-1]=1; //初始状态入队 
21     while(!qe.empty())
22     {
23         pair<int,int> now=qe.front(); qe.pop();
24         for(int i=1;i<=m;i++)//枚举每个操作
25         {
26             int to=now.first;
27             for(int j=1;j<=n;j++)
28             {
29                 if(a[i][j]==1 && 1<<(j-1)&to) to ^= 1<<(j-1);
30                 else if(a[i][j]==-1) to |= 1<<(j-1);
31             }
32             if(!vis[to])
33             {
34                 if(to==0)//达到目标状态
35                 {
36                     vis[0]=1; //相当于一个标记flag
37                     ans=now.second+1;
38                     return ;
39                 }
40                 qe.push({to,now.second+1}); //新状态入队
41                 vis[to]=1;
42             }
43         }
44     }
45 }
46 
47 int main()
48 {
49     #ifdef DEBUG
50     freopen("sample.txt","r",stdin);
51     #endif
52     
53     scanf("%d %d",&n,&m);
54     for(int i=1;i<=m;i++)
55     {
56         for(int j=1;j<=n;j++)
57             scanf("%d",&a[i][j]);
58     }
59     BFS();
60     if(vis[0]) printf("%d",ans);
61     else printf("-1
");
62     
63     return 0;
64 }