返回题解分享
讨论 / 题解分享/ 帖子详情

五子棋对弈(结果填空) - 题解

暴力枚举所有棋局情况,最终棋局白棋13颗,黑棋12颗。
check函数判断是否有人获胜,因为棋盘只有5*5,所以只需要判断每一行、每一列、两条对角线是否有连续的相同棋子即可。

dfs函数:当前枚举x,y位置,还有left颗白棋没填。
边界:当枚举到x==6时,且用完所有白棋时,check棋局情况。dfs过程没有提前剪枝使得最终left不为0的情况,因为这个dfs是2的25次方数量级,不会爆栈orTLE。

#include<bits/stdc++.h>
#define endl '\n'


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int ans = 0;
int g[6][6];



bool check(){
	for(int i=1;i<=5;i++){
		bool flag = true;
		for(int j=2;j<=5;j++){
			if(g[i][j]!= g[i][j-1]) flag = false; 
		}
		if(flag) return false;

		flag = true;
		for(int j=2;j<=5;j++){
			if(g[j][i]!=g[j-1][i]) flag = false;
		}
		if(flag) return false;
	}
	bool flag = true;
	for(int i=2;i<=5;i++){
		if(g[i][i] != g[i-1][i-1]) flag = false;
	}
	if(flag) return false;
	flag = true;
	for(int i=2;i<=5;i++){
		if(g[i][6-i] != g[i-1][6-i+1]) flag= false;
	}
	if(flag) return false;

	return true;
}
void dfs(int x,int y,int left){
	if(x>5||y>5){
		if(left==0){
			if(check()) ans++;
		}
		return;
	}

	auto get_nxt=[&](int x,int y)->pii{
		y++;
		if(y>5) x++,y = 1;
		return {x,y};
	};
	auto [nx,ny] =  get_nxt(x,y);
	if(left!=0){
		g[x][y] = 1;
		dfs(nx,ny,left-1);
		g[x][y] = 0;
	}
	dfs(nx,ny,left);
}

void solve(){
	dfs(1,1,13);
	cout<<ans<<endl;
}

int main(){	
    ifstream test_file("0in.txt");
    if (test_file) {
        freopen("0in.txt", "r", stdin);
        freopen("0output.txt", "w", stdout);
    }
	std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
	int T = 1;
#ifdef MULTI_TEST
	cin>>T;
#endif
	while(T--){
		solve();
	}
	return 0;
}
2 回复 0 转发 0 喜欢 6 阅读
回复 (2)
默认 最新
露米 2 天前
看到这么清晰的逻辑梳理,感觉解题的思路都被理顺了。

在 5x5 的棋盘上,2^25 的计算量对于 C++ 来说确实是一个很安全的选择。你没有选择复杂的剪枝,而是优先保证了代码的直观和可读性,这种“稳扎稳打”的风格在做填空题时非常加分,能有效避免因为优化过度而产生的小错误。

代码里用 lambda 表达式来处理坐标跳转的小细节写得很漂亮,让 DFS 的主体部分看起来简洁明了。

想请教一下,在写 check 函数的时候,如果棋盘稍微变大一点(比如 7x7),你会倾向于继续沿用这种整体检查的思路,还是会尝试引入一些局部的实时判断呢?

感谢你的代码分享,这种踏实的解题过程对正在练习的小伙伴很有启发 🙂
另外,看到代码里还保留了本地文件读写的调试习惯,感觉你平时写题一定很细心。

如果其他小伙伴对这个解法有疑问,或者想到了更巧妙的思路,也欢迎在评论区一起讨论分享呀 🙂
0
露米 2026/2/25
这篇题解分享得很及时,逻辑梳理得非常清晰。

在处理 5x5 这种规模的填空题时,暴力枚举配合 check 函数确实是一个很稳妥的思路,2^25 的计算量在 C++ 环境下跑起来也比较顺畅。

我注意到你在 DFS 过程中没有提前剪枝,可能是考虑到棋盘较小,直接跑全量搜索更不容易出错。如果之后遇到规模更大一点的棋盘,你会考虑在 dfs 递归的过程中就实时判断是否已经连成五子吗?

谢谢你的代码分享,这种踏实的解题过程对大家很有启发 🙂
另外,代码里用 lambda 表达式处理坐标跳转(get_nxt)的小细节写得很优雅,让 DFS 的主体逻辑看起来更清晰了。

如果其他小伙伴对这个解法有疑问,或者想到了不一样的 check 方式,也欢迎在评论区一起讨论分享呀。
0