Vorrei un aiuto per risolvere questo problema, l’idea è quella di utilizzare una BFS e una bitmask che mi rappresenta lo stato delle luci ma totalizzo solo 30 punti
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
queue<pair<int,int>> q;
vector<bool> visitato;
int N, K, result;
int bfs(int bitmask, long long dist){
if(bitmask == result)
return dist;
visitato[bitmask]=true;
/*cout<<endl<<"bitmask: ";
for(int k=1; k<=N; k++){
int zeros=N-k;
int mask=(1<<zeros);
cout<<((bitmask&mask)>>zeros);
}
cout<<" dist:"<<dist<<endl<<endl;
*/
for(int i=1; i<=N; i++){
int zeros=N-i;
int bit=( (bitmask & (1<<zeros)) >> zeros);
if(bit==0){
int newmask=0;
int bits=1;
for(int j=0; j<v[i].size(); j++){
while(bits<v[i][j]){
zeros=N-bits;
int mask=(1<<zeros);
newmask+=mask;
bits++;
}
bits++;
}
while(bits<=N){
zeros=N-bits;
int mask=(1<<zeros);
newmask+=mask;
bits++;
}
newmask&=bitmask;
int zeros=N-i;
newmask|=(1<<zeros);
/*cout<<"newmask: ";
for(int k=1; k<=N; k++){
int zeros=N-k;
int mask=(1<<zeros);
cout<<((newmask&mask)>>zeros);
}
cout<<endl;
*/
if(!visitato[newmask])
q.push(make_pair(newmask, dist+1));
}
}
while(!q.empty()){
pair<int,int> x=q.front();
q.pop();
if(!visitato[x.first])
return bfs(x.first, x.second);
}
}
int main(){
ifstream in("input.txt");
ofstream out("output.txt");
in>>N>>K;
int zeros=N-K;
result=(1<<zeros);
visitato.assign((1<<(N)),false);
v.assign(N+1, vector<int>());
int bitmask=0;
for(int i=1; i<=N; i++){
int num;
in>>num;
if(num == 1){
zeros=N-i;
int mask=(1<<zeros);
bitmask+=mask;
}
}
for(int i=1; i<=N; i++){
int n;
in>>n;
for(int j=0; j<n; j++){
int light;
in>>light;
v[i].push_back(light);
}
}
out<<bfs(bitmask, 0);
return 0;
}
