题解 | 黑白棋

通过枚举验证寻找答案

在本地运行以下程序即可, 实测需要约两分钟

#include <bits/stdc++.h>
int n1[26]{ 2,4,5,6,7,8,10,11,12,13,14,15,18,19,20,
	21,22,23,24,25,27,28,30,32,33,35 }, dp[10];
//  ^ 建立从[0-25]至题目中空位的映射关系       ^ 计算相同子序列的长度
int pop_ct(int t) {
	int res = 0;
	while (t) {
		++res;
		t &= t - 1;
	}
	return res;
}
int main() {
	string s1 = "10.0.."+
		(string)"...0.."+
		(string)"....00"+
		(string)"......"+
		(string)"..1..1"+
		(string)".0..1.";
		// ^  构造题目中的初始棋盘
	for (int i = (1 << 26) - 1;i > 0;--i)if(pop_ct(i) == 14) {
										//   ^  限制状压产生的结果中存在14个1,
	  									//		以满足题目黑白棋子数目相同的要求
		for (int j = 0;j < 26;++j) {// 由状压结果构造棋盘, 以便下文验证
			if (i & (1 << j))
				s1[n1[j]] = '1';
			else s1[n1[j]] = '0';
		}
		bool bd = 0;
	  //     ^ 即bad
		set<string> r1, r2;
	  
		for (int j = 0;j < 6;++j) {// ==============进行行检验
			int ml = 1, 		tl = s1[6*j] == '1';
			//   ^ 最大连续长度   ^ 统计该行中1的数目
			dp[0] = 1;
			for (int k = 1;k < 6;++k) {
			  dp[k] = ((s1[6 * j + k] == s1[6 * j + k - 1]) ? dp[k - 1] + 1 : 1);
			  tl += s1[6 * j + k] == '1';
			  ml = max(ml, dp[k]);
			}
			bd |= (tl != 3) | (ml >= 3);
			//     ^ 判断每行1的数量是否为3，或者是否有连续3个以上的1或0
			r1.insert(s1.substr(6 * j, 6));
			//    ^ 将每行的字符串插入集合r1中，确保每行的字符串唯一
		}

		if(bd)
			continue;
		// ^ 若行验证不符合条件就进入下轮枚举
		for (int j = 0;j < 6;++j) {// =============进行列检验
			int ml = 1, 		tl = s1[j] == '1';
			//   ^ 最大连续长度   ^ 统计该列中1的数目
			dp[0] = 1;
			string ts;ts.push_back(s1[j]);
			for (int k = 1;k < 6;++k) {
			  ts.push_back(s1[j + 6 * k]);
			  dp[k] = ((s1[6 * k + j] == s1[6 * k + j - 6]) ? dp[k - 1] + 1 : 1);
			  tl += s1[6 * k + j] == '1';
			  ml = max(ml, dp[k]);
			}
			bd |= (tl != 3) | (ml >= 3);
			//     ^ 判断每列1的数量是否为3，或者是否有连续3个以上的1或0

			r2.insert(ts);
			//    ^ 将每列的字符串插入集合r1中，确保每列的字符串唯一
		}

		if (!bd && r1.size() == 6 && r2.size() == 6) {// 找到解就结束
			cout << s1;
			return 0;
		}
	}
	return 0;
}
//最后附上答案 : 101001010011101100010110011001100110

}