2023编码大赛（2）

题目：

双方轮流放置5种门，尽可能点亮自己的灯，灭掉他人的灯。

思路：

建立打分系统，采用极大极小算法。

代码初稿：

struct Node {
	int id;
	char type;// P G L  power gate light  
	int in1, in2; //无效id设为-1
	int out1, out2; //无效id设为-1
	char gateType; //type=G时，gateType有意义，分别为  DAONMZ  Z表示未知
	bool isMine;  //type=G L时,isMine有意义
	int value[4]{ -1, - 1, - 1, - 1 }; //in1 in2 out1 out2的信号，-1未知0黄1红， 只需要把电源模块的out1初始化即可
};

int gatePower(char c) {
	if (c == 'D' || c == 'N')return 4;
	if (c == 'A' || c == 'M')return 2;
	return 6;
}


void refresh(map<int, Node>&m, int id) {
	if (m[id].type == 'P') {
		m[id].value[3] = m[id].value[2];
		return;
	}
	if (m[id].type == 'L') {
		return;
	}
	if (m[id].gateType == 'D') {
		m[id].value[2] = m[id].value[0];
		m[id].value[3] = m[id].value[1];
	}
	if (m[id].gateType == 'A') {
		if (m[id].value[0] == 1 && m[id].value[1] == 1) {
			m[id].value[2] = 1, m[id].value[3] = 1;
		}
		else if (m[id].value[0] == 0 || m[id].value[1] == 0) {
			m[id].value[2] = 0, m[id].value[3] = 0;
		}
	}
	if (m[id].gateType == 'O') {
		if (m[id].value[0] == 1 || m[id].value[1] == 1) {
			m[id].value[2] = 1, m[id].value[3] = 1;
		}
		else if (m[id].value[0] == 0 && m[id].value[1] == 0) {
			m[id].value[2] = 0, m[id].value[3] = 0;
		}
	}
	if (m[id].gateType == 'N') {
		m[id].value[2] = m[id].value[0]==-1 ? -1 : 1- m[id].value[0];
		m[id].value[3] = m[id].value[1]==-1 ? -1 : 1- m[id].value[1];
	}
	if (m[id].gateType == 'M') {
		if (m[id].value[0] == 0)m[id].value[2] = 0;
		if (m[id].value[0] == 1)m[id].value[2] = m[id].value[1];
		if (m[id].value[1] == 0)m[id].value[3] = m[id].value[0] == -1 ? -1 : 1 - m[id].value[0];
		if (m[id].value[1] == 1)m[id].value[3] = 0;
	}
}
void initValueFromOne(map<int, Node>&m, int firstid) //id的节点刷新后，调用此函数刷新后续节点   
{
	queue<int>q; //需要刷新状态的队列
	q.push(firstid);  
	refresh(m, firstid);  
	while (!q.empty()) {
		int id = q.front();
		q.pop();
		int idout1 = m[id].out1;

		if (idout1 > -1) {
			if (m[idout1].in1 == -1) { 
				m[idout1].in1 = id;
			}
			else if (m[idout1].in2 == -1) { 
				m[idout1].in2 = id;
			}
			int x = m[idout1].in1 == id ? 0 : 1;
			bool isFreshed = (m[idout1].value[x] != m[id].value[2]); 
			if (isFreshed) { 
				m[idout1].value[x] = m[id].value[2]; 
				q.push(idout1); 
			}
		}
		int idout2 = m[id].out2;
		
		if (idout2 > -1) {
			if (m[idout2].in1 == -1) { 
				m[idout2].in1 = id;
			}
			else if (m[idout2].in2 == -1) { 
				m[idout2].in2 = id;
			}
			int x = m[idout2].in1 == id ? 0 : 1;
			bool isFreshed = (m[idout2].value[x] != m[id].value[3]);
			if (isFreshed) {
				m[idout2].value[x] = m[id].value[3];
				q.push(idout2);
			}
		}
	}
}
void initValue(map<int, Node>&m, vector<int>powerNodes)
{
	for (auto id : powerNodes)initValueFromOne(m, id);
}

int point(map<int,Node>m, vector<int>powerNodes, vector<int>lightNodes){
	int s = 0;
	for (auto id : lightNodes) {
		if (m[id].value[0] == 1 && m[id].value[1] == 1) { //这个灯是否亮
			if(m[id].isMine)s += 1000;
			else s -= 1000;
		}
		else if (m[id].value[0] == 0 || m[id].value[1] == 0) { //这个灯不可能亮 
			continue;
		}
		else if (m[id].value[0] == 1 || m[id].value[1] == 1) { //这个灯可能亮
			if (m[id].isMine)s += 500;
			else s -= 500;
		}
		else {   //2个-1的未知信号
			if (m[id].isMine)s += 250;
			else s -= 250;
		}
	}
	for (auto mi : m) {
		if (mi.second.type == 'G') {
			if (mi.second.isMine)s -= gatePower(mi.second.gateType);
			else s+= gatePower(mi.second.gateType);
		}
	}
	return s;
}
void setMap(map<int, Node>&m, char t, int id) 
{
	m[id].gateType = t; 
	initValueFromOne(m, id); 
}

pair<int,char> choice(map<int, Node>m, vector<int>powerNodes, vector<int>lightNodes,vector<int>validNodes) {
	int maxPoint = -123456;
	int ansid = 0;
	char anst;
	initValue(m, powerNodes);
	for (auto id : validNodes) {
		for (char t : "DAONM") {
			auto m2 = m;
			setMap(m2, t, id);
			int p = point(m2, powerNodes, lightNodes);
			if (maxPoint < p) {
				maxPoint = p;
				ansid = id;
				anst = t;
			}
			//reback(m, id);  
		}
	}
	return make_pair(ansid, anst);
}