题目描述
现有 n 盏灯, 以及 m 个按钮. 每个按钮可以同时控制这 n 盏灯 -- 按下了第 i 个按钮, 对于所有的灯都有一个效果. 按下 i 按钮对于第 j 盏灯, 是下面 3 中效果之一: 如果 a[i][j] 为 1, 那么当这盏灯开了的时候, 把它关上, 否则不管; 如果为 - 1 的话, 如果这盏灯是关的, 那么把它打开, 否则也不管; 如果是 0, 无论这灯是否开, 都不管.
现在这些灯都是开的, 给出所有开关对所有灯的控制效果, 求问最少要按几下按钮才能全部关掉.
输入格式
前两行两个数, n m
接下来 m 行, 每行 n 个数, a[i][j] 表示第 i 个开关对第 j 个灯的效果.
输出格式
一个整数, 表示最少按按钮次数. 如果没有任何办法使其全部关闭, 输出 - 1
输入输出样例
输入 #1 复制 3 2 1 0 1 -1 1 0
输出 #1 复制 2
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 150;
- bool vis[N];
- int mmp[N][N],m,n,num;
- struct qwq{
- int now,step;
- };
- void bfs(int n ){
- queue<qwq>Q;qwq f;
- f.now = n;f.step = 0;Q.push(f);
- while(!Q.empty()){
- qwq orz = Q.front();Q.pop();
- for(int i = 0;i <m;++i){
- int now = orz.now;
- for(int j = 0;j <num;++j){
- if(mmp[i][j]==1){
- if(now&(1<<j))now = now^(1<<j);
- }
- else if(mmp[i][j]==-1){
- now = ((1<<j)|now);
- }
- }
- f.now = now,f.step = orz.step+1;
- if(vis[now])continue;
- if(f.now == 0){
- vis[0] = true;
- cout<<f.step<<endl;
- return ;
- }
- Q.push(f);vis[now] = true;
- }
- }
- }
- int main()
- {
- cin>>n>>m;num = n;
- for(int i = 0;i <m;++i)
- for(int j = 0;j < n;++j)
- cin>>mmp[i][j] ;
- bfs((1<<n)-1);
- if(!vis[0])cout<<"-1"<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3279766.html