目录

dfs训练蓝桥杯15a组

目录

dfs训练蓝桥杯15a组

https://i-blog.csdnimg.cn/direct/439509197c8d48629cac028feb51ed0d.png

#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每个位置利用坐标变换的技巧进行位置移动。