新手题解

聪聪
聪聪数学满分，我一个100分只考16的比不上他😭😭😭
但是，即使数学不好，就不能模拟吗？
理论存在😡😡😡😡😡实践开始😈😈😈😈😈

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
bool vis[2][2][2][2][2][2][2][2];//定义八维数组记录有没有过翻到这种情况
struct node{
	int a[9];//记录当前硬币状态
	int step;//记录步数
};
bool check(node x){//检查正面是不是占一半
	int ct = 0;
	for(int i = 1; i <= 8; i++){
		ct += x.a[i];
	}return ct == 4;//哈哈哈8/2=4我知道
}
int bfs(node n){//是个人都会的广搜
	queue <node> q;
	q.push(n);
	while(!q.empty()){
		node head = q.front();
		q.pop();
		if(check(head)) return head.step;//如果占一半直接return好吧
		for(int i = 1; i <= 8; i++){
			for(int j = 1; j <= 8; j++){
				if(i != j){//不能翻同样的硬币
					node xx = head;
					xx.a[i] ^= 1, xx.a[j] ^= 1, xx.step++;//翻硬币，加步数
					if(!vis[xx.a[1]][xx.a[2]][xx.a[3]][xx.a[4]][xx.a[5]][xx.a[6]][xx.a[7]][xx.a[8]]){//如果之前没有这种情况
						vis[xx.a[1]][xx.a[2]][xx.a[3]][xx.a[4]][xx.a[5]][xx.a[6]][xx.a[7]][xx.a[8]] = 1;
						q.push(xx);//加入队列
					}
				}
			}
		}
	}
}
int main(){
	node n;
	n.step = 0;
	for(int i = 1; i <= 8; i++){
		cin >> n.a[i];
	}cout << bfs(n);

	return 0;
}

时间复杂度：$O(2^n×n)$