五子棋对弈

问题描述

"在五子棋的对弈中，友谊的小船说翻就翻？" 不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友秉承着"友谊第一，比赛第二"的宗旨，决定在一块 5×55×5 的棋盘上，用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落，于是决定用一场和棋（平局）作为彼此友谊的见证。

比赛遵循以下规则：

1. 棋盘规模：比赛在一个 5×55×5 的方格棋盘上进行，共有 2525 个格子供下棋使用。
2. 棋子类型：两种棋子，黑棋与白棋，代表双方。小蓝持白棋，小桥持黑棋。
3. 先手规则：白棋（小蓝）具有先手优势，即在棋盘空白时率先落子（下棋）。
4. 轮流落子：玩家们交替在棋盘上放置各自的棋子，每次仅放置一枚。
5. 胜利条件：率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。
6. 平局条件：当所有 2525 个棋盘格都被下满棋子，而未决出胜负时，游戏以平局告终。

在这一设定下，小蓝和小桥想知道，有多少种不同的棋局情况，既确保棋盘下满又保证比赛结果为平局。

答案提交

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	3s	512M
Python3	10s	512M
PyPy3	3s	512M
Go	5s	512M
JavaScript	5s	512M

总通过次数: 721 |总提交次数: 1521 |通过率： 47.4%c茶

超时代码

#include <bits/stdc++.h>
using namespace std;
int mp[6][6];
int cnt;
bool check()
{int cnt1  = 0, cnt2 = 0;for(int i = 1; i <= 5; i++){for(int j = 1; j <= 5; j++){if(mp[i][j] == 1)cnt1++;if(mp[i][j] == 2)cnt2++;}}if(cnt1 != 12 || cnt2 != 13)    return false;for(int i = 1; i <= 5; i++){int flag = true;for(int j = 1; j <= 5; j++){if(mp[i][j] != mp[i][1]){flag = false;break;}}if(flag)    return false;}for(int i = 1; i <= 5; i++){int flag = true;for(int j = 1; j <= 5; j++){if(mp[j][i] != mp[1][i]){flag = false;break;} }if(flag)    return false;}int flag = true;for(int i = 1; i <= 5; i++){int  j = i;if(mp[i][j] != mp[1][1]){flag = false;break;}}if(flag)    return false;flag = true;for(int i = 1; i <= 5; i++){int j = 6 - i;if(mp[i][j] != mp[5][1]){flag = false;break;}}if(flag)    return false;return true;}
void dfs(int a, int b)
{if(b == 6){dfs(a + 1, 1); return;}if(a == 6){if(check())cnt++;return;}mp[a][b] = 1;dfs(a, b + 1);mp[a][b] = 0;mp[a][b] = 2;dfs(a, b + 1);mp[a][b] = 0;
}
int main()
{dfs(1, 1);cout << cnt << endl;
}

ac代码

#include<iostream>
using namespace std;
int mp[5][5];
long long sum=0;
void check(){int a=0;for(int i=0;i<5;i++){for(int j=0;j<5;j++){if(mp[i][j]==1) a++;}}if(a!=13) return;//此时满足13-12 int count=0;count+=mp[0][0]+mp[1][1]+mp[2][2]+mp[3][3]+mp[4][4];if(count%5==0) return; count=0;count+=mp[0][4]+mp[1][3]+mp[2][2]+mp[3][1]+mp[4][0];if(count%5==0) return; count=0;for(int i=0;i<5;i++){count+=mp[i][0]+mp[i][1]+mp[i][2]+mp[i][3]+mp[i][4];if(count%5==0) return; count=0;count+=mp[0][i]+mp[1][i]+mp[2][i]+mp[3][i]+mp[4][i];if(count%5==0) return; count=0;}//满足平局 sum++;
}
void dfs(int num){//依次由从左往右，再到从上往下的顺序遍历if(num==25){//棋盘下满 check();return;}int x=num/5,y=num%5;//换算成坐标mp[x][y]=0;dfs(num+1);mp[x][y]=1;dfs(num+1);
}
int main(){dfs(0);//从0开始，遍历所有结果cout<<sum;//3126376return 0;
}

#include <bits/stdc++.h>
using namespace std;
int mp[5][5];
int u=0;
void dfs(int sum,int h,int b)
{//地图满了；判断if(sum==25){if(h==13&&b==12){for(int i=0;i<5;i++){int s=mp[i][0]+mp[i][1]+mp[i][2]+mp[i][3]+mp[i][4];if(s==5||s==0) return;}for(int i=0;i<5;i++){int m=mp[0][i]+mp[1][i]+mp[2][i]+mp[3][i]+mp[4][i];if(m==5||m==0) return;}int p=mp[0][0]+mp[1][1]+mp[2][2]+mp[3][3]+mp[4][4];int l=mp[0][4]+mp[1][3]+mp[2][2]+mp[3][1]+mp[4][0];if(p==0||p==5||l==0||l==5) return;u++;}return;}int x=sum/5;int y=sum%5;//计算坐标mp[x][y]=1;//选择白棋dfs(sum+1,h+1,b);mp[x][y]=0;选择黑棋dfs(sum+1,h,b+1);
}
int main()
{dfs(0,0,0);cout<<u;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int ans, upp = (1 << 5) - 1;
bitset<5>area[6];
bool check(int y)
{if (area[y].count() == 5 || area[y].count() == 0)return false;if (y == 5){int sum = 0;int _sum = 0;for (int i = 0; i < 5; i++){sum = 0;for (int j = 1; j <= 5; j++)sum += area[j][i], _sum += area[j][i];if (sum == 0 || sum == 5)return false;}if (_sum != 13)return false;int suml = 0, sumr = 0;for (int i = 1; i <= 5; i++){suml += area[i][i-1];sumr += area[i][5-i];}if (suml == 5 || suml == 0 || sumr == 5 || sumr == 0)return false;}return true;
}
void dfs(int y)
{if (y == 6){ans++;return;}for (int i = 1; i <= upp; i++){bitset<5>temp(i);area[y] = temp;if (check(y))dfs(y + 1);}
}
int main()
{dfs(1);cout << ans;return 0;
}