提供一个正常思路的bfs的爆搜解法,如果不会找规律的,可以看一下这个正常思路的解法,也能过。发现操作都是6的倍数,所以取一下min即可,其他都是bfs标准模版
class Solution {
public:
int flipLights(int n, int presses) {
n=min(n,6);
unordered_set<int> st;
queue<int> q;
int start=(1<<n)-1;
q.push(start);
while (presses--){
int sz=q.size();
st.clear();
while (sz--){
int t=q.front();q.pop();
vector<int> next={f1(t,n),f2(t,n),f3(t,n),f4(t,n)};
for (int &ne:next){
if (st.count(ne)) continue;
q.push(ne);
st.insert(ne);
}
}
}
return q.size();
}
int f1(int state,int n){
int mask=(1<<n)-1;
return mask^state;
}
int f2(int state,int n){
for (int i=0;i<n;i+=2) state^=1<<i;
return state;
}
int f3(int state,int n){
for (int i=1;i<n;i+=2) state^=1<<i;
return state;
}
int f4(int state,int n){
for (int i=0;i<n;i+=3) state^=1<<i;
return state;
}
};
可以