关于c++:解题日志-关灯问题IIBFS状压

*关灯问题II（Luogu P2622）

先挂个链接 – https://www.luogu.com.cn/prob…

题面 – 现有N盏灯，M个按钮。每个按钮能够同时管制这n盏灯——按下某个按钮，对于所有的灯都有一个成果。给出所有开关对所有灯的管制成果，问起码要按几下按钮能将灯从全开变为全关

Now，进入正题

瞧下数据，N<=10，M<=100
数据规模不很大，果决BFS（广度优先搜寻）
然而……
BFS的判重又成了大问题
一一比对，看状态是否统一，显然超时
不判重，BFS就间接废了

这时候，新Get到的技能——状态压缩闪亮退场
状态压缩行将原来状态的数组寄存变为一个01形成的整数寄存
这样就这能够设置一个下标代表状态的vis[]数组来判重
判重霎时降到O(1)级别
状态的扭转则用位运算，也降到O(1)级别

就是这么容易……

上面挂上程序(C++)和精心设计的注解不便了解

//Luogu P2622 - 关灯问题II
//https://www.luogu.com.cn/problem/P2622
//BFS+状压 

#include <bits/stdc++.h> 
#define MAXN 2048 
using namespace std; 
 
int N, M; 

struct Node{ 
    int dp; //状压值,反馈灯状态 
    int step; //操作次数
}; 

int vis[MAXN]; //用于BFS的判重 
int a[MAXN][MAXN]; //灯的管制成果 

void BFS(int n){ 
    queue<Node> Q; 
    Node fir;
    fir.step = 0, fir.dp = n;
    Q.push(fir); 
    
    while(!Q.empty()){ 
       Node u=Q.front(); 
       Q.pop(); 
       int pre=u.dp; 
       //拿出队首 
       
       for(int i=1; i<=M; i++){ 
          int now=pre; //now即为状压值,灯的状态 
          
          for(int j=1; j<=N; j++){ 
             if(a[i][j]==1){  
                if((1<<(j-1))&now){ 
                   now = now^(1<<(j - 1));
                } 
             } 
             else if(a[i][j]==-1){ 
                now = ( (1<<(j-1))|now);
                 
             } 
          } 
          //应用位运算扭转状压值,反馈了开关对于灯状态的影响 
          
            fir.dp=now, fir.step=u.step+ 1;   
          
          if(vis[now]) continue; //BFS的判重 
          if(fir.dp==0){ 
             vis[0]=true;
             cout << fir.step << endl; 
             return ;
          }    
          //如果达到,输入并退出BFS 
           
          Q.push(fir); //新状态入队 
          vis[now] = true; //记录状态,用于判重 
       } 
    } 
} 

int main(){ 
   cin >> N >> M; 
   int temp=(1<<(N))-1; 

   for(int i=1; i<=M; i++){ 
     for(int j=1; j<=N; j++){ 
        cin >> a[i][j]; 
     } 
   } 

   BFS(temp); 

   if(!vis[0]) 
     cout << -1 << endl; //无奈达到,输入-1 

   return 0; 
}

这题最初的难点就是位运算了
其实笔者本人也有点懵……
日后笔者会潜心研究并撰写相干专题的文章的
还请大家急躁期待

如有疑难欢送在评论区提出

留个赞再走呗~