当前位置:网站首页>P2622 light off problem II

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 .

about 20% data ,n<=5

about 20% data ,m<=20

The data points above may overlap .

about 100% data n<=10,m<=100

 

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]=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]=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;
}

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

版权声明
本文为[Weihe]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/05/20210520223457630M.html