PTA 2813：画家问题 （熄灯问题）

经典的熄灯问题，思路就不过多阐述，csdn都有

#include <bits/stdc++.h>
using namespace std;
int num[20];
int num2[20];
int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {string str;cin >> str;for (int j = 0; j < n; j++) {// 如果是开灯状态，标记上1，反之0num[i] |= str[j] == 'w' ? 1 << j : 0;}// 存原图num2[i] = num[i];}// 结果可不可行bool flag = false;// 最小操作次数int ans = -1;// 2 ==> 00, 01, 10, 11,// 2  0 1 2 3// 0 ~ 2^2 - 1 (1 << 2) -1// 枚举N个格子的状态for (int k = 0; k < (1 << n); k++) {// 第0层的状态为枚举的Knum[0] = k;// 这次枚举的开关灯次数int cnt = 0;// 还原图，因为上次实在num上修改的，所以要还原for (int i = 1; i <= n; i++) {num[i] = num2[i];}// 修改灯的状态for (int i = 1; i <= n; i++) {for (int j = 0; j < n; j++) {// 01 & 10 == 00 == 0// 如果上一层的第j个灯是开的，则这一层需要关闭if (num[i - 1] & (1 << j)) {// 次数++cnt++;// 修改当前灯的状态num[i] ^= (1 << j);// 左边灯的状态if (j > 0) num[i] ^= (1 << (j - 1));// 右边灯的状态if (j < n - 1) num[i] ^= (1 << (j + 1));// 下一层第j个灯的状态num[i + 1] ^= (1 << j);// 上一层第j个灯不用修改，因为最后我们只需要判断最后一层灯的状态}}}// 如果最后一层灯都关闭了，则二进制上都是0，所以结果为0if (num[n] == 0) {flag = true;// 更新答案if (ans == -1 || ans > cnt) ans = cnt;}}if(!flag) cout << "inf" << endl;else cout << ans << endl;return 0;
}