dfs训练蓝桥杯15a组
目录
dfs训练蓝桥杯15a组
#include<bits/stdc++.h>
using namespace std;
int mp[5][5];
int sum;
void DFS(int s,int b,int h)
{
if(s==25)
{
if(b==13&&h==12)
{
for(int i=0;i<5;i++)
{
int q=mp[i][0]+mp[i][2]+mp[i][3]+mp[i][1]+mp[i][4];
if(q==0||q==5) return;
int p=mp[0][i]+mp[1][i]+mp[2][i]+mp[3][i]+mp[4][i];
if(p==0||p==5) return;
}
int m=mp[0][0]+mp[1][1]+mp[2][2]+mp[3][3]+mp[4][4];
if(m==0||m==5) return;
int mm=mp[0][4]+mp[1][3]+mp[2][2]+mp[3][1]+mp[4][0];
if(mm==0||mm==5) return;
sum++;
}
return;
}
int x=s/5;
int y=s%5;
mp[x][y]=1;
DFS(s+1,b+1,h);
mp[x][y]=0;
DFS(s+1,b,h+1);
}
int main()
{
DFS(0,0,0);
cout<<sum;
}
简单的dfs搜索,每个位置选择白棋代码中用h。或者选择黑棋用l,步数一直++sum,根据五子棋规则,白棋只有13.黑棋只有12,总共下25,所以当sum==25的时候判断整个棋盘,如果满足白棋13黑棋12进行平局判断,不满足在retuen掉(我绝的是重点因为我在这里错了想了一会),不加27行retuen报错,然后进行平局判断,我们只要不是平局的,其他return掉,最后u++。
我们要填满棋盘白棋就要13黑就要12,dfs每个位置利用坐标变换的技巧进行位置移动。