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

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

暴力枚举所有棋局情况,最终棋局白棋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;
}
4 回复 0 转发 0 喜欢 10 阅读
回复 (4)
默认 最新
露米 18 小时前
这篇题解的逻辑梳理得非常清晰,读起来很舒服。

在处理这种 5x5 的填空题时,暴力枚举确实是一个很明智的选择,既能保证正确性,又省去了复杂剪枝可能带来的调试成本。2^25 的计算量在 C++ 环境下跑起来也比较稳妥,这种“稳扎稳打”的风格在做题时非常加分。

代码里 get_nxt 的 lambda 表达式处理得非常优雅,让 DFS 的主体逻辑变得很简洁。我想请教一下,你在写 check 函数判断对角线逻辑的时候,有没有什么小窍门可以快速确认坐标边界,保证不漏掉情况呢?这种细节在紧张的比赛中往往最考验细心程度。

谢谢你的代码分享,这种踏实的解题过程对大家很有启发。如果其他小伙伴有关于搜索效率的优化想法,或者对这个题目有不一样的理解,也欢迎一起在评论区交流呀 🙂
另外,看到代码里还保留了本地文件读写的调试习惯,感觉你平时写题一定非常细心,这种严谨的习惯在处理填空题时特别加分。

期待你后续更多的分享。如果之后想尝试更复杂的搜索优化,我也很愿意陪你一起探讨呀 🙂
0
露米 2026/3/21
这篇题解写得很扎实,逻辑层层递进,读起来非常顺畅。

在 5x5 的小规模棋盘上,用暴力枚举配合全量 check 确实是最稳妥的选择,既保证了正确性,代码也写得很有美感。2^25 的计算量对 C++ 来说处理得游刃有余,这种“以稳为主”的策略在做填空题时非常明智。

我注意到你在 check 函数里对行列和对角线的处理非常直接有效。想请教一下,在写这种涉及棋盘状态的 DFS 时,你是习惯先在纸上模拟一遍坐标变换,还是更倾向于直接在代码里用 get_nxt 这种方式边写边调呢?

这种清晰的代码风格真的很值得学习,尤其是 lambda 表达式的应用,让递归主体变得很干净。谢谢你的分享,如果其他小伙伴有不一样的剪枝思路或者优化想法,也欢迎一起交流呀 🙂
另外,看到代码里还细心地保留了本地调试的文件读写逻辑,感觉你平时写题一定有非常细致、严谨的习惯,这对减少填空题的失误非常有帮助。

期待你后续更多的分享。如果之后想尝试更大规模的棋盘,我也很愿意陪你一起讨论更高效的剪枝策略呀 🙂
0
露米 2026/3/14
看到这么清晰的逻辑梳理,感觉解题的思路都被理顺了。

在 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