AcWing 116. 飞行员兄弟(无脑遍历)
原题链接
简单
作者:
西加加
,
2024-04-09 19:50:19
,
所有人可见
,
阅读 2
Intuition:最优解同一个地方不会按两次,并且先后顺序不影响,因此可以用16位二进制来表示所有解法(每一位对应那个开关是否操作);
不用vector用pq会好一些,但pq的初始化太麻烦了,我还没搞懂;
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cmath>
using namespace std;
bool bsComp(bitset<16> & bs1, bitset<16> & bs2) {
if (bs1.count() < bs2.count())
return true;
else
return false;
}
int toRow(int n) {
return n / 4 + 1;
}
int toCol(int n) {
return n % 4 + 1;
}
int toNum(int row, int col) {
return row * 4 + col;
}
void turn(bitset<16> & puzzle, int i, int j) {
for (int x = 0; x < 4; x ++)
puzzle[toNum(x, j)] = !puzzle[toNum(x, j)];
for (int y = 0; y < 4; y ++)
puzzle[toNum(i, y)] = !puzzle[toNum(i, y)];
puzzle[toNum(i, j)] = !puzzle[toNum(i, j)];
}
bool isSolution(bitset<16> puzzle, bitset<16> & bs) {
for (int i = 0; i < 4; i ++) {
for (int j = 0; j < 4; j ++) {
if (bs[toNum(i, j)])
turn(puzzle, i, j);
}
}
if (puzzle.count() == 16) return true;
else return false;
}
void showSteps(bitset<16> & sol) {
cout << sol.count() << '\n';
for (int i = 0; i < 16; i ++) {
if (sol[i]) {
cout << toRow(i) << ' ' << toCol(i) << '\n';
}
}
}
void No116Helper(bitset<16> puzzle) {
vector<bitset<16>> sol;
for (int op = pow(2, 16) - 1; op; op --) {
bitset<16> bs(op);
if (isSolution(puzzle, bs))
sol.push_back(bs);
}
sort(sol.begin(), sol.end(), bsComp);
showSteps(sol[0]);
}
void No116() {
bitset<16> puzzle(0);
string s;
for (int i = 0; i < 4; i ++) {
cin >> s;
for (int j = 0; j < 4; j ++) {
if (s[j] == '-')
puzzle[toNum(i, j)] = true;
}
}
No116Helper(puzzle);
}
int main() {
No116();
return 0;
}