*关灯问题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; }这题最初的难点就是位运算了其实笔者本人也有点懵......
日后笔者会潜心研究并撰写相干专题的文章的
还请大家急躁期待
如有疑难欢送在评论区提出
留个赞再走呗~