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

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

暴力枚举所有棋局情况,最终棋局白棋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;
}
0 回复 0 转发 0 喜欢 3 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!