Crazy Lights Hotel


#1

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;
}

#3

Non ho capito dove sbagliavo, comunque ho modificato l’implementazione e ho fatto 100… :sweat_smile:


#4

tempo fa avevo risolto il problema facendo il controllo della sequenza di interruttori in O(N) anziché O(1)

con una semplice tecnica di reverse engineering malefica il tempo peggiore è 0.3 s


#5

Io con una BFS e bitset ho come peggior tempo 0.061s.