Acwing 95難解なスイッチ(bfs+ビット演算)

難解なスイッチのテーマの入り口:https://www.acwing.com/problem/content/97/エンドステップ数が6ステップ以内に達する状態は限られているため、何度の問い合わせでもこれらの状態は増加や減少せず、ステップ数も変化しないので、エンドポイントから6ステップ以内に歩けるすべての状態を先に処理してステップ数を記録すれば、後のクエリでは主に前に記録した配列からステップ数を取り出すことができる.

#include
using namespace std;
int step[1<<25];
struct node {
	int nowstatus;
	int step;
};
queueq;
void pre_bfs(){
	memset(step,-1,sizeof(step));
	q.push((node){(1<<25)-1,0});
	step[(1<<25)-1] = 0;
	while(!q.empty()){
		node temp = q.front();
		q.pop();
		if(temp.step == 6) continue;
		//           。 
		for(int i = 1;i<= 25; i++){
			int tp = 1<< (i-1);
			if(i%5 != 1) tp += (1<< (i-2));//          
			if(i%5 != 0) tp += (1<< i); //          
			if(i > 5) tp += (1 << (i-6));//          
			if(i < 21) tp += (1<< (i+4));//           
			node news = (node){temp.nowstatus ^ tp,temp.step+1};
			if(step[news.nowstatus] == -1){
				q.push(news);
				step[news.nowstatus] = news.step;
			}			
		}
	}
}
int main(){
	int n;
	scanf("%d",&n);
	pre_bfs();
	for(int i = 1;i<= n; i++){
		int num = 0;
		char c;
		for(int i = 1;i<= 25;i++){
			cin >> c;
			num += ((c-'0') << (i-1)) ;
		}
		printf("%d
",step[num]);
	}
	return 0;
}