状态压缩算法解决关灯问题2

 

• Step1 Problem

原题
现有n盏灯，以及m个按钮。每个按钮可以同时控制这n盏灯——按下了第i个按钮，对于所有的灯都有一个效果。按下i按钮对于第j盏灯，是下面3中效果之一：如果a[i][j]为1，那么当这盏灯开了的时候，把它关上，否则不管；如果为-1的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是0，无论这灯是否开，都不管。
现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。

• Step2 Ideas:

这题是一道比较经典的状态压缩题目（自己感觉就是用二进制代表某种状态，再以十进制表示二进制的数，枚举了全部的状态，DP起来复杂度岂不是很大？没错，状压其实是一种很暴力的算法，因为他需要遍历每个状态，所以将会出现2^n的情况数量，不过这并不代表这种方法不适用：一些题目可以依照题意，排除不合法的方案，使一行的总方案数大大减少从而减少枚举），这题需要对状压及位运算有一定的了解：首先要判断某一位的灯是开的还是关的，才能进行修改。对队首的某一状态，枚举每一个开关灯操作，记录到达这一新状态的步数（也就是老状态 + 1），若是最终答案，输出，若不是，压入队列。也就是说：我们把初始状态，用每个操作都试一遍，就产生了许多新的状态，再用所有操作一一操作新状态，就又产生了新的新状态，我们逐一尝试，直到有目标状态为止，这可以通过BFS实现。
前置技能：BFS， 位运算；
简单介绍一下位运算：
1.’&’符号，x&y，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。例如3(11)&2(10)=2(10)。
2.’|’符号，x|y，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。例如3(11)|2(10)=3(11)。
3.’ ^ ’符号，x ^ y，会将两个十进制数在二进制下进行异或运算，然后返回其十进制下的值。例如3(11)^2(10)=1(01)。
4.’<<’符号，左移操作，x<<2，将x在二进制下的每一位向左移动两位，最右边用0填充，x<<2相当于让x乘以4。相应的，’>>’是右移操作，x>>1相当于给x/2，去掉x二进制下的最有一位。
这四种运算在状压dp中有着广泛的应用，常见的应用如下：
1.判断一个数字x二进制下第i位是不是等于1。
方法：if ( ( ( 1 <<( i - 1 ) ) & x ) > 0)
将1左移i-1位，相当于制造了一个只有第i位上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0，说明x第i位上是1，反之则是0。
2.将一个数字x二进制下第i位更改成1。
方法：x = x | ( 1<<(i-1) )
证明方法与1类似，此处不再重复证明。
3.把一个数字二进制下最靠右的第一个1去掉。
方法：x=x&(x-1)

• Step3 Code:

#include 
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 2e3+5;
int n, m;
struct node
{
    int dp, st;
};
int ma[maxn][maxn];
bool vis[maxn];

void bfs(int x)
{
    queue<node> q;
    node now;
    now.dp = x;
    now.st = 0;
    q.push(now);
    while(!q.empty())
    {
        node u = q.front();
        q.pop();
        for(int i = 1; i <= m; i++)
        {
            int a = u.dp;
            for(int j = 1; j <= n; j++)
            {
                if(ma[i][j] == 1)
                {
                    if((1 << (j - 1)) & a)
                    {
                        a = a ^ (1 << (j - 1));
                    }
                }
                else if(ma[i][j] == -1) a = (1 << (j - 1) | a);
            }
            if(vis[a]) continue;
            node v;
            v.dp = a;
            v.st = u.st + 1;
            if(!a)
            {
                vis[0] = true;
                cout << v.st << endl;
                return ;
            }
            q.push(v);
            vis[a] = true;
        }
    }
}

int main()
{
    cin >> n >> m;
    int num = (1 << (n)) - 1;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> ma[i][j];
        }
    }
    bfs(num);
    if(!vis[0]) cout << -1 << endl;
    return 0;
}