题解 P2040 【打开所有的灯】
SIGSEGV
2018-04-29 19:51:55
此题甚水。首先要明确：同一盏灯操作一次就够了！！！因为灯的状态与开关灯的次序无关！
接着就好办了：用一个int记录下一个二进制数，代表对灯光的操作，如样例，最优操作是动第一与第五盏灯，操作码为000010001（2） 即17. 然后这个九位二进制数到范围在0～1023之间，慢慢去凑状态吧～
最后贴代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[5][5],b[5][5],dx[] = {0,1,0,-1},dy[] = {1,0,-1,0},ans = INT_MAX;
void chk(int num) //这是个检查的函数
{
int cnt = 0;
for (int i = 0;i < 3;i++)
for (int j = 0;j < 3;j++)
{
if (num % 2) //此灯要戳一下
{
++cnt;
b[i][j] = !b[i][j];
for (int k = 0;k < 4;k++)
{
int nx = i + dx[k],ny = j + dy[k];
if (nx >= 0 && ny >= 0 && nx < 3 && ny < 3)
b[nx][ny] = !b[nx][ny];
}
}
num /= 2;//向下一位进军
}
for (int i = 0;i < 3;i++)
for (int j = 0;j < 3;j++)
if (b[i][j] == 0) return;
ans = min(ans,cnt);
}
int main()
{
for (int i = 0;i < 3;i++)
for (int j = 0;j < 3;j++)
scanf("%d",&a[i][j]);
int mx = pow(2,10);
for (int i = 0;i < mx;i++)//凑状态码
{
for (int j = 0;j < 3;j++)
for (int k = 0;k < 3;k++) b[j][k] = a[j][k];//不想要用memcpy，反正时间差不多
chk(i);
}
printf("%d",ans);
return 0;
}
```