# P2622 light off problem II

2021-06-27 15:00:24 Weihe

## Title Description

existing n Lights , as well as m Button . Each button can control this at the same time n Lights —— Press the second button i Button , There is an effect for all lights . Press down i Button for the second j Lights , It's below 3 One of the effects ： If a[i][j] by 1, So when this light is on , Turn it off , Otherwise it doesn't matter ; If -1 Words , If this light is off , So turn it on , Otherwise it doesn't matter ; If it is 0, Whether the light is on or not , It doesn't matter .

Now these lights are on , Give the control effect of all switches on all lights , It takes at least a few buttons to turn it off .

## I / O format

Input format ：

The first two lines are two numbers ,n m

Next m That's ok , Each row n Number ,a[i][j] It means the first one i The first switch is right j The effect of a light .

Output format ：

An integer , It means to press the button at least . If there's no way to shut it all down , Output -1

## I/o sample

sample input #1：
```3
2
1 0 1
-1 1 0```
sample output #1：
`2`

## explain

about 20% data , Output no solution can score .

The data points above may overlap .

Solution：

This topic is about dp Water problem .

Definition \$f[j]\$ Indicates that the current light status is \$j\$ Minimum cost of , The initial state \$f=0\$, Target state \$f[(1<<n)-1]\$（\$0\$ To open ,\$1\$ Weiguan ）.

use \$a_i,b_i\$ Record the switching effect of each button , Then run the shortest path , When you transfer, do something about it .

say concretely , if \$(i,j)\$ Input \$x==1\$ be \$a_i|=1<<j-1\$, If you type \$x==-1\$ be \$b_i|=1<<j-1\$.

Current state of transfer \$sta\$ Transfer to \$(sta|a_i)\&(～b_i)\$ You can switch the lights on and off .

Code ：

```/*Code by 520 -- 10.16*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=105;
int n,m,a[N],b[N],f[1<<21];
bool vis[1<<21];
queue<int>q;

int main(){
ios::sync_with_stdio(0);
cin>>n>>m; int x,lim=(1<<n)-1;
For(i,1,m) For(j,1,n) {
cin>>x;
if(x==1) a[i]|=(1<<j-1);
if(x==-1) b[i]|=(1<<j-1);
}
memset(f,0x3f,sizeof(f));
f=0;q.push(0);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
For(i,1,m) {
int sta=(u|a[i])&(~b[i]);
if(f[sta]>f[u]+1) {
f[sta]=f[u]+1;
if(!vis[sta]) vis[sta]=1,q.push(sta);
}
}
}
cout<<(f[lim]==0x3f3f3f3f?-1:f[lim]);
return 0;
}```

https://chowdera.com/2021/05/20210520223457630M.html