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

先挂个链接 – 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; 
}

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

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

留个赞再走呗~

* 关灯问题 II（Luogu P2622）