codevs1044四子连棋（Dfs）

/*

数据范围太小 暴力暴力 Dfs直接

终止条件嘛 就是4中目标棋局 挨着枚举一遍就好了

搜索的起点一定是空格 当然 空格周围有黑有白 黑先走或者白先走答案可能不一样

所以 维护一个b 表示这一步走那种颜色  b=1先走白棋 b=2先走黑棋

*/

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

int xx[]={,,,,-};//枚举四个方向

int yy[]={,,-,,};

int g[][],minn=;//最小步数

char s;

void Dfs(int x,int y,int num,int b)//b表示 先走那种颜色

{

    int m=,i,j,k;

    if(num>=minn) return; //剪枝 如果已经比目前的最优解大了 就不用再Dfs了

    for(i=;i<=;i++)//4种目标棋局一一列举 如果有符合的 更新m的值

      {

          if(g[i][]==g[i][]&&g[i][]==g[i][]&&g[i][]==g[i][]&&(g[i][]==||g[i][]==))m=num;

          if(g[][i]==g[][i]&&g[][i]==g[][i]&&g[][i]==g[][i]&&(g[][i]==||g[][i]==))m=num;

      }

    if(g[][]==g[][]&&g[][]==g[][]&&g[][]==g[][]&&(g[][]==||g[][]==))m=num;

    if(g[][]==g[][]&&g[][]==g[][]&&g[][]==g[][]&&(g[][]==||g[][]==))m=num;

    if(m<minn)//用m更新minn

      {

          minn=m;

          return;//不用往后Dfs了 因为后面不如现在优

      }

    for(i=;i<=;i++)

      {

          int ox=x+xx[i];

          int oy=y+yy[i];

          if(ox>&&ox<=&&oy>&&oy<=&&g[ox][oy]==b)

            {

                g[x][y]=g[ox][oy];

                g[ox][oy]=;//走完之后g[ox][oy]变空  g[x][y]变g[ox][oy]

            if(b==)b=;//黑白交替走 上次走黑 下次走白

                else b=;

                for(j=;j<=;j++)//因为空格又不止一个 所以 找空格0.0

                  for(k=;k<=;k++)

                    if(!g[j][k])//空

                      Dfs(j,k,num+,b);

                g[ox][oy]=g[x][y];//回溯

                g[x][y]=;

                if(b==)b=;

                else b=;

          }

      }

}

int main()

{

    int i,j;

    for(i=;i<=;i++)

      for(j=;j<=;j++)

        {

          cin>>s;

          if(s=='W')g[i][j]=;//白棋

          if(s=='B')g[i][j]=;//黑棋

        }

    for(i=;i<=;i++)

      for(j=;j<=;j++)

        if(!g[i][j])//空格

          {

              Dfs(i,j,,);//先走白棋

              Dfs(i,j,,);//先走黑棋

          }

    cout<<minn<<endl;

    return ;

}