关键词：
题目背景
pmshz在玩一个益(ruo)智(zhi)的小游戏，目的是打开九盏灯所有的灯，这样的游戏难倒了pmshz。。。
题目描述
这个灯很奇(fan)怪(ren)，点一下就会将这个灯和其周围四盏灯的开关状态全部改变。现在你的任务就是就是告诉pmshz要全部打开这些灯。
例如：
0 1 1
1 0 0
1 0 1
点一下最中间的灯 ([2,2]) 就变成了
0 0 1
0 1 1
1 1 1
再点一下左上角的灯 ([1,1]) 就变成了
1 1 1
1 1 1
1 1 1
达成目标。最少需要 (2) 步。
输出 (2) 即可。
输入格式
九个数字，(3*3) 的格式输入，每两个数字中间只有一个空格，表示灯初始的开关状态。（ (0) 表示关，(1) 表示开）
输出格式
一个整数，表示最少打开所有灯所需要的步数。
输入输出样例
输入 #1
0 1 1
1 0 0
1 0 1
输出 #1
2
——————————————————————————————————————
想了一会没有什么特别好的方法，所以直接搜索了，时间很充裕~
用二进制数表示九盏灯的开关状态，(2^9 = 512) 状态数允许完全被记录。
用 (way) 数组储存按下某栈灯时候会发生变化的灯的编号。
之后就是常规的广搜，(vis) 数组记录压缩后的每种状态实现需要的最少操作数。
代码如下：
#include <bits/stdc++.h>
#define MAX 666
using namespace std;
int init,vis[MAX];
int way[9][9]=1,3,-1,0,2,4,-1,1,5,-1,
0,4,6,-1,1,3,5,7,-1,2,4,8,-1,
3,7,-1,4,6,8,-1,5,7,-1;
queue<int> Q;
inline int read()
int X=0,w=0; char ch=0;
while (!isdigit(ch)) w|=ch=='-',ch=getchar();
while (isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
inline int open(int x,int opt)
int pos=0;
while (way[opt][pos]!=-1) x^=(1<<way[opt][pos++]);
return x^=(1<<opt);
int main()
memset(vis,-1,sizeof(vis));
for (int i=1;i<=9;i++) init<<=1,init+=read();
Q.push(init),vis[init]=0;
while (!Q.empty())
int now=Q.front(); Q.pop();
for (int i=0;i<9;i++)
int tmp=open(now,i);
if (vis[tmp]==-1) vis[tmp]=vis[now]+1,Q.push(tmp);
printf("%d",vis[(1<<9)-1]);
return 0;
洛谷p2040打开所有的灯
P2040打开所有的灯题目背景pmshz在玩一个益(ruo)智(zhi)的小游戏，目的是打开九盏灯所有的灯，这样的游戏难倒了pmshz。。。题目描述这个灯很奇(fan)怪(ren)，点一下就会将这个灯和其周围四盏灯的开关状态全部改变。现在你的任务... 查看详情
p2040打开所有的灯(代码片段)
...示关，1表示开） 输出格式： 1个整数，表示最少打开所有灯所需要的步数。 输入输出样例输入样例#1： 复制011100101输出样例#1： 复制21#include<bits/stdc++.h>2usingnamespacestd;3inta[3][3];4intb[3][3];5intans=999999;6intmain()... 查看详情
[luogu2622]关灯问题$||$（状压$dp$）(代码片段)
...按钮可以同时控制这(n)盏灯——按下了第i个按钮，对于所有的灯都有一个效果。按下(i)按钮对于第(j)盏灯，是下面(3)中效果之一：如果(a[i][j])为1，那么当这盏灯开了的时候，把它关上，否则不管；如果为(-1)的话，如果这盏灯是 查看详情
leetcode0864.获取所有钥匙的最短路径：广搜+状压(代码片段)
【LetMeFly】864.获取所有钥匙的最短路径：广搜+状压力扣题目链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys/给定一个二维网格 grid ，其中：'.'代表一个空房间'#'代表一堵'@' 是起点小 查看详情
题解$luogup2962$-双向广搜-异或高斯消元(代码片段)
...都是被关着的,问需要至少按下多少开关,才可以把所有灯打开。(N≤36)（你谷的翻译好像有点问题，就搬的另一个翻译，按照这个写就是对的）(\)(\ 查看详情
uvalive-6912primeswitch（状压dp）
...关同时控制编号为这个质数的倍数的灯，问最多有多少灯打开。【分析】发现小于根号1000的质数有10个左右，然后大于根号1000的质数所控制的灯是不会重叠的，所以我们状压枚举小于31的质数，然后贪心后面的。#include<cstdio>... 查看详情
usaco2.2partylamps高能等效+规律枚举
...luogu.org/problem/show?pid=1468#sub按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。按钮2：当按下此按钮，将改变所有奇数号的灯。按钮3：当按下此按钮，将改变所有偶数号的灯。按钮4：当按下... 查看详情
[luogu3959noip2017]宝藏(状压dp)(代码片段)
DescriptionInput第一行两个用空格分离的正整数n,m，代表宝藏屋的个数和道路数。接下来m行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为1?n），和这条道路的长度v。Output一个正整数，表示最... 查看详情
luogu2157状压dp(代码片段)
f[i][j][k]分别代表1-i-1个人全部打完饭时i及其后7个人的状态为j时最后一个打饭的人为i+k的状态下所用的最小时间当i已经打过饭时即j&1那么f[i][j>>1][k+1]=min(~,f[i][j][k]);如果没有那么枚举其后的打饭的人同时注意要保证忍耐度... 查看详情
luogu3943星空(代码片段)
...里将$^$记为异或。那么$a_i=b_0^b_1^b_2^...^b_i$，如果我们将所有一开始没有点亮的灯记为$1$，而将所有点亮的 查看详情
开灯问题-----00004
描述有n盏灯，编号为1~n，第1个人把所有灯打开，第2个人按下所有编号为2 的倍数的开关（这些灯将被关掉），第3 个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），依此类推。一共有k... 查看详情
开灯和蛇形
...。开灯问题，有n盏灯，编号为1-n,第一个人把所有的灯都打开，第二个人按下所有编号为2的倍数的开关（这些灯将被关掉），第三个人按下所有编号为3倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），以此类推，一... 查看详情
luogu2435染色状压qwq轮廓线dp(代码片段)
LINK题目大意有一个n行m列的格点图，你需要给每个点上染上k种颜色中的一种，要求没有两个相邻点颜色相同。给定第一行与最后一行的染色，试求总染色方案数。思路暴力预处理状态暴力转移可以得到80分的高分这个时候司来了... 查看详情
开灯问题
...nbsp;开灯问题，有n盏灯，编号为1~n。第一个人把所有灯都打开，第二个人按下所有编号为2的倍数的开关（这些灯将被关掉），第三个人按下所有编号为3的倍数的开关（其中关掉的灯将被打开，开着的灯将被关闭），以此类推。... 查看详情
万圣节后的早晨&&九数码游戏——双向广搜(代码片段)
....org/problemnew/show/P1778https://www.luogu.org/problemnew/show/P2578双向广搜。有固定起点终点，过程可逆。有时用于A*估价函数不好用的时候。万圣节后的早晨（由于鬼可以同时移动，估价函数不好设计）优化：1.预处理。预处理每个可以到... 查看详情
179竞赛
...都是关着的。在k 时刻（k的取值范围是0到n-1），我们打开light[k]这个灯。灯的颜色要想变成蓝色就必须同时满足下面两个条件：灯处于打开状态。排在它之前（左侧）的所有灯也都处于打开状态。请返回能够让所有开着的灯... 查看详情
[luogu1357]花园[dp+矩阵快速幂](代码片段)
...quo;长出”m个花圃来，消除这种影响具体做法是：枚举所有合法 查看详情
luogu4221wc2018州区划分（状压dp+fwt）(代码片段)
合法条件为所有划分出的子图均不存在欧拉回路或不连通，也即至少存在一个度数为奇数的点或不连通。显然可以对每个点集预处理是否合法，然后就不用管这个奇怪的条件了。 考虑状压dp。设f[S]为S集合所有划分方案... 查看详情