实现了一个六边形棋盘游戏的模拟系统，主要解决以下问题：

1. 棋盘建模：将六边形棋盘转换为图结构，每个顶点表示一个棋盘位置。

2. 邻接关系建立：通过insert_edge函数建立顶点之间的邻接关系。

3. 连通分量检测：使用BFS算法识别相同数字的连通区域（群体）。

4. 得分计算：评估玩家在每个可放置位置的操作收益，包括： • 移除对手群体的得分（正收益）

   • 移除己方群体的损失（负收益）

5. 最优策略选择：遍历所有空位，选择收益最大的操作。

代码实现

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <climits>

using namespace std;
#define MAXNODE 60
#define MAXN 12
int chess[MAXNODE];
struct Comp
{
	int node_num;
	int empty_nbr_num;
	Comp(int n0, int e0) : node_num(n0), empty_nbr_num(e0) {}
};
void insert_edge(map<int, vector<int> >& nbrs, map<int, vector<int> >& empty_enbrs, int node_id, int l)
{
	nbrs[node_id].push_back(l);
	nbrs[l].push_back(node_id);
	if (chess[node_id] == 0 && chess[l] == 0) {
		empty_enbrs[node_id].push_back(l);
		empty_enbrs[l].push_back(node_id);
	}
}
int main()
{
	int N, C;
	int node_id;
	while (cin >> N >> C && (N || C)) {
		node_id = 0;
		vector<int> empty_node;
		int c;
		map<int, vector<int> > nbrs;
		map<int, vector<int> > empty_enbrs;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j <= i; ++j) {
				cin >> c;
				if (c == 0) {
					empty_node.push_back(node_id);
				}
				chess[node_id++] = c;
			}
		}
		int tmp = 0;
		for (int i = 0; i < N - 1; ++i) {
			for (int j = 0; j <= i; ++j) {
				// triangle: tmp tmp+i+1 tmp+i+2
				int l = tmp + i + 1;
				int r = tmp + i + 2;
				insert_edge(nbrs, empty_enbrs, tmp, l);
				insert_edge(nbrs, empty_enbrs, tmp, r);
				insert_edge(nbrs, empty_enbrs, r, l);
				++tmp;
			}
		}
		
		map<int, vector<Comp> > empty2comps, empty2Ccomps;
		int comp_sz;
		set<int> empty_nbrs;
		
		int visited[MAXNODE] = {0}; // mark when pushing into queue(one node might be the same neighbor of different nodes)
		for (int i = 0; i < node_id; ++i) {
			if (visited[i] == 0 && chess[i]) {
				comp_sz = 0;
				empty_nbrs.clear();
				
				c = chess[i];
				queue<int> q;
				q.push(i);
				visited[i] = 1;
				int curr;
				while (q.empty() == 0) {
					curr = q.front();
					q.pop();
					++comp_sz;
					for (size_t k = 0; k < nbrs[curr].size(); ++k) {
						int nbr = nbrs[curr][k];
						if (chess[nbr] == 0) {
							empty_nbrs.insert(nbr);
						}
						if (chess[nbr] == c && visited[nbr] == 0) {
							q.push(nbr);
							visited[nbr] = 1;
						}
					}
				}
				int empty_nbrs_sz = empty_nbrs.size();
				if (c == C) {
					for (set<int>::iterator it = empty_nbrs.begin(); it != empty_nbrs.end(); ++it) {
						int e = *it;
						empty2Ccomps[e].push_back(Comp(comp_sz, empty_nbrs_sz));
					}
				} else {
					if (empty_nbrs_sz <= 1) {
						for (set<int>::iterator it = empty_nbrs.begin(); it != empty_nbrs.end(); ++it) {
							int e = *it;
							empty2comps[e].push_back(Comp(comp_sz, empty_nbrs_sz));
						}
					}
				}
			}
		}
		
		int max_score = INT_MIN;
		for (size_t i = 0; i < empty_node.size(); ++i) {
			int e = empty_node[i];
			int score = 0;
			
			for (size_t j = 0; j < empty2comps[e].size(); ++j) {
				Comp cp = empty2comps[e][j];
				score += cp.node_num;
			}
			
			int del_score = 0;
			bool has_other_nbr = (empty_enbrs[e].size() > 0);
			for (size_t j = 0; j < empty2Ccomps[e].size(); ++j) {
				Comp cp = empty2Ccomps[e][j];
				del_score += cp.node_num;
				if (cp.empty_nbr_num > 1) {
					has_other_nbr = 1;
				}
			}
			if (has_other_nbr == 0) { // after connect, no empty nbr
				score -= del_score;
				--score;
			}
			if (score > max_score) {
				max_score = score;
			}
		}
		cout << max_score << endl;
	}
	return 0;
}