- 按两次同一个按钮,效果与不按等价,如果已按 4 次按钮,第 5 次必然按下的是前 4 次按过的按钮之一,相当于按 3 次按钮,由此可知,只需要遍历出按 1 到 4 次按钮的所有可能情况即可。而按 4 次按钮时,如果每个按钮都按了一次,按 1 号按钮与 23 按钮的功能等价,相当于只按了 4 号按钮,因此最后只需要遍历按 1 到 3 次按钮的所有可能情况
- 每次按下按钮,每 6 个灯泡的状态必然相同,因此只需要检查前 6 个灯泡即可。而前 6 个灯泡中,可以分前 3 个灯泡和后 3 个灯泡考虑。按 1 或 4 号按钮对前 3 个灯泡和后 3 个灯泡的影响相同。按 2 号按钮时,会改变前 3 个灯泡的中间灯泡状态,改变后 3 个灯泡的两侧灯泡状态,此时后 3 个灯泡的状态即与前 3 个灯泡互补。3 号按钮同理,因此前 3 个灯泡的状态即可确定后 3 个灯泡状态,因此只需要检查前 3 个灯泡状态即可
class Solution {
public:
int flipLights(int n, int m) {
bitset<3> b;
unordered_set<bitset<3>> s;
dfs(b, s, min(m, 3), min(n, 3));
return size(s);
}
void dfs(bitset<3>& b, unordered_set<bitset<3>>& s, int m, int n) {
if (!m) {
s.emplace(b);
return;
}
bitset<3> t = b;
flip_all(b, n);
dfs(b, s, m - 1, n);
flip_even(b, n);
dfs(b, s, m - 1, n);
flip_odd(b, n);
dfs(b, s, m - 1, n);
flip_3k_append_1(b, n);
dfs(b, s, m - 1, n);
b = t;
}
void flip_all(bitset<3>& b, int n) {
for (int i = 0; i < n; ++i) {
b.flip();
}
}
void flip_even(bitset<3>& b, int n) {
for (int i = 1; i < n; i += 2) {
b.flip(i);
}
}
void flip_odd(bitset<3>& b, int n) {
for (int i = 0; i < n; i += 2) {
b.flip(i);
}
}
void flip_3k_append_1(bitset<3>& b, int n) {
for (int i = 0; i < n; i += 3) {
b.flip(i);
}
}
};
class Solution {
public:
int flipLights(int n, int m) {
if (!n || !m) {
return 1;
}
if (n == 1) {
return 2;
}
if (n == 2) {
if (m == 1) {
return 3;
}
return 4;
}
if (m == 1) {
return 4;
}
if (m == 2) {
return 7;
}
return 8;
}
};