【题解】关灯问题Ⅱ

题目描述

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