Luogu P2622 Turn-off Problem II [Shaped Pressure dp+bfs]

P2622 Turn-off Problem II
Title Description
Existing n lights and m buttons. Each button controls the N lights at the same time - pressing the second button has an effect on all lights. Pressing the I button is one of the following three effects for the J lamp: if a[i][j] is 1, turn it off when the lamp is turned on, otherwise it doesn't matter; if - 1, if the lamp is turned off, turn it on, otherwise it doesn't matter; if 0, whether the lamp is turned on or not, it doesn't matter.

Now these lights are on. Given the control effect of all switches on all lights, it is necessary to press at least a few buttons to turn them off.

Input format
The first two rows and two numbers, n m

Next m lines, n in each line, a[i][j] denotes the effect of the first switch on the jth lamp.

Output format
An integer representing the minimum number of button presses. If there is no way to turn it off, output - 1

Input and Output Samples
Input #1 replication
3
2
1 0 1
-1 1 0
Output #1 replication
2
Note/hint
For 20% of the data, the output can be scored without solution.

For 20% data, n<=5

For 20% data, m<=20

The data points above may overlap.

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

Ideas for solving problems:
Since there are only 10 lights at most, we can use a number of dpdpdp to directly indicate the state of the lamp, and then put the initial state into the queue, each time take the first state of the queue, traverse the switches, put the new state after operation into the queue, and keep the bfs paper to find the results.

Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int a[120][12];
struct node
{
	int dp;
	int step;
};
int n,m;
bool vis[3000];
int change(int x,int id,int wei) {
	int nape=x&(1<<(wei-1));
	if(nape==(1<<(wei-1))&&id==1) {
		return x^(1<<(wei-1));
	}
	if(nape==0&&id==-1) {
		return x|(1<<(wei-1));
	}
	return x;
}
int bfs()
{
	queue<node> q;
	while(!q.empty()) {
		q.pop();
	}
	node s;
	s.dp=(1<<m)-1;
	s.step=0;
	memset(vis,false,sizeof vis);
	vis[s.dp]=true;
	q.push(s);
	node nape;
	while(!q.empty()) {
		node fro=q.front();
		q.pop();
		if(fro.dp==0) {
			return fro.step;
		}
		for(int i=1;i<=n;i++) {
			nape.dp=fro.dp;
			for(int j=1;j<=m;j++) {
				nape.dp=change(nape.dp,a[i][j],j);
				//cout<<j<<" "<<(nape.dp&(1<<(j-1)))<<" "<<nape.dp<<endl;
			}
			nape.step=fro.step+1;
			if(vis[nape.dp]==false) {
				vis[nape.dp]=true;
				q.push(nape);
			}
		}
	}
	return -1;
}
int main() 
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    #endif
    //freopen("out.txt", "w", stdout);
    //ios::sync_with_stdio(0),cin.tie(0);
    scanf("%d %d",&m,&n);
    rep(i,1,n) {
    	rep(j,1,m) {
    		scanf("%d",&a[i][j]);
    	}
    }
    int ans=bfs();
    printf("%d\n",ans);
    return 0;
}

Tags: iOS

Posted on Tue, 08 Oct 2019 17:46:35 -0700 by priya_cks