2024年蓝桥杯省赛C++大学A组试题整理

2024年蓝桥杯省赛A整理

1.五子棋对弈

五子棋博弈
本题题目中所描述的所求是不同的棋局情况,但是事实上要求的其实是棋面情况(即最后棋盘下满后的情况，并不会对固定棋盘下满情况下具体下棋的先后手进行要求)
对于本道题目我们直接考虑枚举，最后棋盘上是会存在13个白子和12个黑子。当我们将黑子的位置确定后，白子的位置也就随即确定。因此我们只需要枚举12个黑子的位置情况。
我们采用先枚举12个黑子在棋盘的25个格子中任意放置的所有情况，之后在检查没中情况是否符合平局的要求。
那么我们就需要设计一个用以枚举所有可能情况的函数(dfs)，以及一个可以判断是否满足平局条件的函数(check)。
check函数的构造是容易的，我们下面考虑函数dfs的构造。
我们设dfs(int i,int x)
其中i表示当前枚举到了第i个黑子，x表示当前黑子所在第x个格子中，我们对x计算x/5和x%5便可以得到x对应的横纵坐标。
在我们已经确定第i个黑子落于位置x处后，若i==12，则我们已经枚举完所有的黑子，可以进行check()
若i!=12,则我们第i+1个黑子可能落在所有x+1,…24中的任意一个格子中.我们在此处需要用循环进行枚举。
在最后完成枚举之后，用于回溯，我们需要再将棋盘中的黑子变为白子。
AC代码(第一次提交)

#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;intans=0;intg[10][10];boolcheck(){if(g[0][0]==g[1][1]&&g[0][0]==g[2][2]&&g[0][0]==g[3][3]&&g[0][0]==g[4][4])returnfalse;if(g[0][4]==g[1][3]&&g[0][4]==g[2][2]&&g[0][4]==g[3][1]&&g[0][4]==g[4][0])returnfalse;for(inti=0;i<5;i++){intsum=0;for(intj=0;j<5;j++){sum+=g[i][j];}if(sum%5==0)returnfalse;}for(intj=0;j<5;j++){intsum=0;for(inti=0;i<5;i++){sum+=g[i][j];}if(sum%5==0)returnfalse;}returntrue;}voidprint(){for(inti=0;i<=4;i++){for(intj=0;j<=4;j++)cout<<g[i][j]<<' ';cout<<endl;}cout<<endl;}voiddfs(inti,intx){g[x/5][x%5]=1;if(i==12){if(check()){ans++;}else{g[x/5][x%5]=0;return;}}for(intj=x+1;j<=24;j++){dfs(i+1,j);}g[x/5][x%5]=0;}intmain(){for(inti=0;i<24;i++){dfs(1,i);}cout<<ans;return0;}

(复写代码，发现斜着的连线也可以使用取模判断的方法来简化写法，即便是void类型的函数，也可以在结束时就写好return，这样可以避免因为某些分支忘记回溯导致出错)

#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;intg[28][28];longlongans=0;boolcheck(){for(inti=0;i<5;i++){intsum=0;for(intj=0;j<5;j++){sum+=g[i][j];}if(sum%5==0)returnfalse;}for(inti=0;i<5;i++){intsum=0;for(intj=0;j<5;j++){sum+=g[j][i];}if(sum%5==0)returnfalse;}intsum=g[0][0]+g[1][1]+g[2][2]+g[3][3]+g[4][4];if(sum%5==0)returnfalse;sum=g[4][0]+g[3][1]+g[2][2]+g[1][3]+g[0][4];if(sum%5==0)returnfalse;returntrue;}voiddfs(inti,intx){g[x/5][x%5]=1;if(i==12){if(check()){ans++;g[x/5][x%5]=0;return;}}for(intj=x+1;j<=24;j++){dfs(i+1,j);}g[x/5][x%5