暴力枚举所有棋局情况,最终棋局白棋13颗,黑棋12颗。
check函数判断是否有人获胜,因为棋盘只有5*5,所以只需要判断每一行、每一列、两条对角线是否有连续的相同棋子即可。
dfs函数:当前枚举x,y位置,还有left颗白棋没填。
边界:当枚举到x==6时,且用完所有白棋时,check棋局情况。dfs过程没有提前剪枝使得最终left不为0的情况,因为这个dfs是2的25次方数量级,不会爆栈orTLE。
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 阅读



