洛谷题单指南-状态压缩动态规划-P2622 关灯问题 II

原题链接：https://www.luogu.com.cn/problem/P2622

题意解读：求将所有灯都关掉最少按钮次数。

解题思路：

典型的最小步数模型，灯的状态采用状态压缩，然后通过BFS即可求得最少步数。

初始状态所有灯都开：(1 << n) - 1

对于每一个状态，枚举所有的开关，转移到目标状态，直到为0。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 11, M = 105, INF = 0x3f3f3f3f;
int a[M][N];
int d[1 << N];
bool vis[1 << N];
int n, m, ans;

void bfs()
{
    int s = (1 << n) - 1; //初始状态
    queue<int> q;
    q.push(s);
    vis[s] = true;
    d[s] = 0;
    while(q.size())
    {
        int x = q.front(); 
        q.pop();
        for(int i = 0; i < m; i++) //枚举所有开关
        {
            int y = 0;
            for(int j = 0; j < n; j++) //计算目标状态
            {
                if(a[i][j] == -1 && !(x >> j & 1)) y |= 1 << j; 
                else if(a[i][j] == 1 && (x >> j & 1));
                else if(x >> j & 1) y |= 1 << j;
            }
            if(vis[y]) continue;
            d[y] = d[x] + 1; //步数加1
            if(y == 0) return; //找到结果状态
            q.push(y);
            vis[y] = true;
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            cin >> a[i][j];
    memset(d, 0x3f, sizeof(d));
    bfs();
    if(d[0] != INF) cout << d[0];
    else cout << -1;

    return 0;
}