题目描述

现有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

说明/提示

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

对于20%数据,n<=5

对于20%数据,m<=20

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

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

分析

本题采用BFS算法。

​ 阅读题目可发现题目最终目的:求问最少要按几下按钮才能全部关掉。是最小步数/路径问题。此类问题若状态与状态的之间的变化步骤为1,或将状态看作图中的结点,结点与结点之间的权值为1。该问题就可抽象为求最短路径问题,权值为1的最短路径问题可用BFS进行求解。

​ 对于本题需要搞清楚从当前状态到下一个状态的“方法“。从题目中可发现,三种执行的可能。若将灯的状态设定为:开为0,关为1。当a[i][j]为1,将对应的位置为0的替换成1,其他不管;当a[i][j]为-1,将对应位置的1的替换成0,其他不管。当a[i][j]为0,则什么也不用管。

​ 可发现,能实际对状态发生改变的也就两种情况,a[i][j]为1或者a[i][j]为-1。而这两种情况,分解为动作也就是开关灯处理。

​ 当我们将开设为0,关设为1,我们可以压缩状态使用n位的二进制来描述当前n盏灯的状态,最终所有灯关掉的状态可用 (1<<n)-1 描述。

仔细分析开关效果。

​ 设按下开关的编号为i,灯的编号为j,设当前压缩后的状态为x。

a[i][j] 为1时,j号灯无论开关与否都会变成关的状态,等同于我们要达成这样的效果:将二进制的第j位替换为1。即x|=(1<<j)

a[i][j]为-1时,j号灯无论开关与否都会变成开的状态,等同于我们要达成这样的效果:将二进制的第j位替换为0。即x&=(~(1<<j))

了解清楚后,套用BFS模板即可实现。

参考代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int a[105][105];//记录开关-灯的状态
int ans[1030];//ans[x] 到状态x的最短步数
bool vis[1030];//vis[x] true/false x状态是否到达过
int n,m;
struct node{
	int state,s;
	//当前状态 步数
};

int work(int sta,int x){// 按下x号按钮
	for(int j=0;j<n;j++){
		if(a[x][j]==-1){
			if(sta>>j&1){
				sta&=(~(1<<j));
			}
		}else if(a[x][j]==1){
			sta|=(1<<j);
		}
	}
	return sta;//返回按下按钮后的状态
}

void bfs(){
	queue <node> q;
	q.push(node{0,0});
	while(!q.empty()){
		node cur=q.front();//取出队首元素
		q.pop();
		ans[cur.state]=cur.s;//记录到队首状态的最短步数
		for(int i=0;i<m;i++){//探索下一个按下的按钮
			int t=work(cur.state,i);
			if(!vis[t]){
				vis[t]=true;
				q.push(node{t,cur.s+1});				
			}
		}
	}
}
int main(){
	memset(ans,-1,sizeof(ans));
	cin>>n>>m;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cin>>a[i][j];
		}
	}
	bfs();
	cout<<ans[(1<<n)-1];//注意符号优先级,减号优先级比位移高,所以加上括号
	return 0;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)