题目描述 

Description

在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。

●	○	●
○	●	○	●
●	○	●	○
○	●	○

 

输入描述 

Input Description

从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。

输出描述 

Output Description

用最少的步数移动到目标棋局的步数。

样例输入 

Sample Input

BWBO

WBWB

BWBW

WBWO

样例输出 

Sample Output

5

数据范围及提示 

Data Size & Hint

hi

 

#include
       
        #include
        
         using namespace std;int a[5][5]={
     0},ans=100;int xx[5]={
     0,0,0,1,-1},yy[5]={
     0,1,-1,0,0};void dfs(int x,int y,int sum,int bj){    int xn,yn,minn=0x7fffffff;    if (sum >= ans) return ;//返回上一层，查找是否还有更优解    for (int q=1;q<=4;q++)//枚举满足条件的情况       {          if (a[q][1]==a[q][2]&&a[q][2]==a[q][3]&&a[q][3]==a[q][4]&&(a[q][1]==1||a[q][1]==2)) minn=sum ;          if (a[1][q]==a[2][q]&&a[2][q]==a[3][q]&&a[3][q]==a[4][q]&&(a[1][q]==1||a[1][q]==2)) minn=sum ;      }    if (a[1][1]==a[2][2]&&a[2][2]==a[3][3]&&a[3][3]==a[4][4]&&(a[1][1]==1||a[1][1]==2)) minn=sum ;    if (a[1][4]==a[2][3]&&a[2][3]==a[3][2]&&a[3][2]==a[4][1]&&(a[1][4]==1||a[1][4]==2)) minn=sum ;    if (minn
         
          0&&xn<5&&yn>0&&yn<5&&a[xn][yn]==bj)            {                a[x][y]=a[xn][yn];                a[xn][yn]=0;                bj=bj==1?2:1;//黑白棋交替行走                 for (int i=1;i<=4;i++)                  for (int j=1;j<=4;j++)                    if (!a[i][j]) dfs (i,j,sum+1,bj);                bj=bj==1?2:1;//恢复原状态                 a[xn][yn]=a[x][y];                a[x][y]=0;            }                     }             }int main(){    for (int i=1;i<=4;i++)      for (int j=1;j<=4;j++)        {            char ch;            cin>>ch;            if (ch=='B') a[i][j]=1;            if (ch=='W') a[i][j]=2;         }    for (int i=1;i<=4;i++)      for (int j=1;j<=4;j++)        if (!a[i][j])          {               dfs (i,j,0,1);               dfs (i,j,0,2);          }    printf("%d",ans);    return 0;}