116.飞行员兄弟
注释部分是调试中用的部分,忘了void change(int k, vector<PII> &res)
中的&导致答案一直为空
#include <iostream>
#include <vector>
#include <string>
#include <cstring>using namespace std;typedef pair<int, int> PII;
const int MAX_OP = 1 << 16;
int a[4][4], backup[4][4];void change(int k, vector<PII> &res)
{int x = k / 4, y = k % 4;for (int i = 0; i < 4; i ++ ){backup[x][i] ^= 1;backup[i][y] ^= 1;}backup[x][y] ^= 1;// for (int i = 0; i < 4; i ++ )// { // for (int j = 0; j < 4; j ++ )// cout << backup[i][j] << " ";// cout << endl;// }// cout << endl;res.push_back({x, y});// for (auto p : res)// {// cout << p.first << " " << p.second << endl;// }return;
}int main()
{// 读入for (int i = 0; i < 4; i ++ ){string line;cin >> line;for (int j = 0; j < 4; j ++ ){if (line[j] == '+') a[i][j] ^= 1;}}// for (int i = 0; i < 4; i ++ )// { // for (int j = 0; j < 4; j ++ )// cout << a[i][j] << " ";// cout << endl;// }// cout << endl;// memcpy(backup, a, sizeof a);// vector<PII> res;// change(0, res);// change(2, res);// change(3, res);// change(12, res);// change(14, res);// change(15, res);// 处理vector<PII> res;for (int op = 0; op < MAX_OP; op ++ ){memcpy(backup, a, sizeof a);// if (op == 13499) cout << "13499" << endl;// for (int i = 0; i < 4; i ++ )// { // for (int j = 0; j < 4; j ++ )// cout << backup[i][j] << " ";// cout << endl;// }// cout << endl;vector<PII> tmp;for (int k = 0; k < 16; k ++ ){if (op >> k & 1) change(k, tmp);}bool flag = true;for (int i = 0; i < 4; i ++ )for (int j = 0; j < 4; j ++ ){if (backup[i][j] == 1) flag = false;}// for (auto p : tmp)// {// cout << p.first << " " << p.second << endl;// }if (flag && (res.empty() || res.size() > tmp.size())) res = tmp;}// 输出cout << res.size() << endl;for (auto p : res){cout << p.first + 1 << " " << p.second + 1 << endl;}return 0;
}/*
1234
1234
1234
12342^16*/
y总代码
抄的时候把if (k >> i & 1)
抄成if (k >> 1 & 1)
导致答案为空
y总通过state变量的二进制记录了16个位置的开关情况,用change记录了如果改变(i,j)时,要改变的情况,比如
改变1,1
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
1,2,3,4,5,9,13都要改变
用0001000100011111记录,=1相当于取反,就是动一下开关,=0,就是不动
now记录了改变后的state也就是当前所有灯光开关情况,都为0,也就是now = 0,也就是达到了要求
#include <iostream>
#include <vector>
using namespace std;const int MAX_OP = 1 << 16;
int change[4][4];typedef pair<int, int> PII;int get(int x, int y)
{return x * 4 + y;
}int main()
{int state = 0;for (int i = 0; i < 4; i ++ ){string line;cin >> line;for (int j = 0; j < 4; j ++ )if (line[j] == '+') state += 1 << get(i, j);}for (int i = 0; i < 4; i ++ )for (int j = 0; j < 4; j ++ ){for (int k = 0; k < 4; k ++ ){change[i][j] += 1 << get(i, k);change[i][j] += 1 << get(k, j);}change[i][j] -= 1 << get(i, j);}vector<PII> res;for (int k = 0; k < MAX_OP; k ++ ){int now = state;vector<PII> path;for (int i = 0; i < 16; i ++ ){if (k >> i & 1){int x = i / 4, y = i % 4;now ^= change[x][y];path.push_back({x, y});}}// cout << path.size() << endl;if (!now && (res.empty() || res.size() > path.size())) res = path;}cout << res.size() << endl;for (auto p : res) cout << p.first + 1 << " " << p.second + 1 << endl;return 0;
}