洛谷-P2622 关灯问题II(BFS+状压)

╰半夏微凉° 2022-04-24 00:44 148阅读 0赞

# [P2622 关灯问题II][P2622 _II] #

### 题目描述 ###

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

### bfs+状压 ###

一些位运算说明:  
`n=n<<1`:n=2\*n  
`n=n>>1`:n=n/2  
`(1<<j)&n`:判断二进制下第j位是0还是1  
`n=n^(1<<j)`:n对应二进制下第j位取反  
`n=n|(1<<j)`:n对应二进制下第j位变为1  
广搜遍历所有状态，这些灯一共有1<<n种状态，每种状态用一个十进制数保存，比如3盏灯，状态是100，对应十进制下是4，所以这里的十进制数是一个状态。当最后状态为0时，就表示所有灯都熄灭了，初始状态是(1<<n)-1,二进制下对应的1111…1表示所有灯处于打开状态。

#include <iostream>
    #include <algorithm>
    #include <queue>
    #include <vector>
    using namespace std;
    const int MAXN = 3000;
    struct Node
    { 
        int steps; //步数
        int dp;    //目前的状态
        Node(int s, int d) : steps(s), dp(d) { }
    };
    int n, m; //n盏灯，m个开关
    int mp[MAXN][MAXN];
    bool vis[MAXN]; //标记被访问过的状态
    void bfs(int num)
    { 
        queue<Node> que;
        que.push(Node(0, num));
        while (!que.empty())
        { 
            Node u = que.front();
            que.pop();
            int pre = u.dp;             //取出当前状态,表示所有灯目前的状态，比如010，关开关
            for (int i = 0; i < m; i++) //遍历每个开关
            { 
                int fw = pre;
                for (int j = 0; j < n; j++)
                { 
                    if (mp[i][j] == 1) //开关是关
                    { 
                        if (1 << j & fw) //当前第j个灯是开还是关,1表示开
                        { 
                            fw = fw ^ (1 << j); //把该位变为0
                        }
                    }
                    else if (mp[i][j] == -1) //开关是开
                    { 
                        fw = fw | (1 << j); //把该位变为1
                    }
                }
                if (vis[fw]) //如果该状态被访问过，不再加入队列
                    continue;
                if (fw == 0) //表示所有灯都关掉了
                { 
                    vis[0] = true;
                    cout << u.steps + 1 << endl;
                }
                vis[fw] = true;
                que.push(Node(u.steps + 1, fw));
            }
        }
    }
    int main()
    { 
        //freopen("test.txt","r",stdin);
        cin >> n >> m;
        int num = (1 << n) - 1; //表示灯初始状态，全部打开
        for (int i = 0; i < m; i++)
        { 
            for (int j = 0; j < n; j++)
            { 
                cin >> mp[i][j]; //设置开关
            }
        }
        bfs(num);
        if (vis[0] == false)
            cout << -1 << endl;
        return 0;
    }

[P2622 _II]: https://www.luogu.org/problemnew/show/P2622