codevs1004四子连棋

#include<iostream>
#include<cstdio>
#include<cstdio>

using namespace std;
int map[5][5],ans,flag;
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
inline void dfs(int ch, int deep);

inline void swap(int &a,int &b)
{
    int t = a;
    a = b;
    b = t;
}

bool check()//判断是否符合条件 
{
    for (int k=1;k<=4;k++)
    {
        if (map[k][1]==map[k][2]&&map[k][2]==map[k][3]&&map[k][3]==map[k][4])return 1;
        if (map[1][k]==map[2][k]&&map[2][k]==map[3][k]&&map[3][k]==map[4][k])return 1;
    }
    if (map[1][1]==map[2][2]&&map[2][2]==map[3][3]&&map[3][3]==map[4][4])return 1;
    if (map[1][4]==map[2][3]&&map[2][3]==map[3][2]&&map[3][2]==map[4][1])return 1;
    return 0;
}

void move(int ch,int deep,int x,int y) //ch表示下一个颜色 
{
    for(int i=1;i<=4;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(map[xx][yy]==ch&&xx>0&&xx<5&&yy>0&&yy<5)
        {
            swap(map[x][y],map[xx][yy]);
            dfs(ch,deep+1);
            swap(map[x][y],map[xx][yy]);
        }
    }
}

void dfs(int ch,int deep)
{
    int next=!ch;
    if(flag) return;
    if(ans==deep)
    {
        if(check()) flag=1;
        return;
    }
    for(int i=1;i<=4;i++)
      for(int j=1;j<=4;j++)
        if(map[i][j]==-1) move(next,deep,i,j);
}

int main()
{
    for(int i = 1; i <= 4; i++)
           for(int j = 1; j <= 4; j++)
           {
               char a;
               cin>>a;
               if(a == ‘B‘) map[i][j] = 1;
               if(a == ‘O‘) map[i][j] = -1;
           }
    for(ans = 1; flag == 0; ans++)
    {
        dfs(0, 0);
        if(flag) break;
        dfs(1, 0);
        if(flag) break;
    }
    printf("%d\n",ans);
}