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代码(第一次提交)#includeiostream#includecstdio#includealgorithmusingnamespacestd;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;i5;i++){intsum=0;for(intj=0;j5;j++){sum+=g[i][j];}if(sum%5==0)returnfalse;}for(intj=0;j5;j++){intsum=0;for(inti=0;i5;i++){sum+=g[i][j];}if(sum%5==0)returnfalse;}returntrue;}voidprint(){for(inti=0;i=4;i++){for(intj=0;j=4;j++)coutg[i][j]' ';coutendl;}coutendl;}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;i24;i++){dfs(1,i);}coutans;return0;}(复写代码，发现斜着的连线也可以使用取模判断的方法来简化写法，即便是void类型的函数，也可以在结束时就写好return，这样可以避免因为某些分支忘记回溯导致出错)#includeiostream#includecstdio#includealgorithmusingnamespacestd;intg[28][28];longlongans=0;boolcheck(){for(inti=0;i5;i++){intsum=0;for(intj=0;j5;j++){sum+=g[i][j];}if(sum%5==0)returnfalse;}for(inti=0;i5;i++){intsum=0;for(intj=0;j5;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