四子连棋（迭代搜索——idfs）

四子连棋

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

BWBO
WBWB
BWBW
WBWO

样例输出 #1

5

思路

这道题对比之前的题，无非就多了要判断是谁下，因为他们两个是轮流下棋的，因此我们dfs的参数要有黑棋坐标，白棋坐标，当前谁下，步数。

拓展：对于步数求法我们有：bfs（结构体）——适用于单操作、dfs（迭代搜索，适用于复杂情形）

代码（更有说服力）

//这种棋盘步数问题也可以用迭代加深来做
//这种双对局的我们往往采取两次idfs

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 15;

int w[N][N];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int fx1,fy1,fx2,fy2;
int ans;

bool check(){
    //每行
    for(int i=1;i<=4;i++){
        if(w[i][1]==w[i][2]&&w[i][2]==w[i][3]&&w[i][3]==w[i][4]) return true;
        if(w[1][i]==w[2][i]&&w[2][i]==w[3][i]&&w[3][i]==w[4][i]) return true;
    }
    //对角线
    if(w[1][1]==w[2][2]&&w[2][2]==w[3][3]&&w[3][3]==w[4][4]) return true;
    if(w[1][4]==w[2][3]&&w[2][3]==w[3][2]&&w[3][2]==w[4][1]) return true;
    return false;
}

bool dfs(int u,int x,int y,int xx,int yy,int color){//color就是轮到谁了
    if(u==ans){
        if(check())return true;
        return false;
    }
    
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        int aa=xx+dx[i],bb=yy+dy[i];
        // if(a<1||b<1||a>4||b>4||w[a][b]==color)continue;
        if(a>0&&b>0&&a<=4&&b<=4&&w[a][b]!=color){
            swap(w[a][b],w[x][y]);
            if(dfs(u+1,a,b,xx,yy,(color==1?2:1)))return true;
            swap(w[x][y],w[a][b]);
            
        }
        if(aa>0&&bb>0&&aa<=4&&bb<=4&&w[aa][bb]!=color){
        // if(aa<1||bb<1||aa>4||bb>4||w[aa][bb]==color)continue;
            swap(w[aa][bb],w[xx][yy]);
            if(dfs(u+1,x,y,aa,bb,(color==1?2:1)))return true;
            swap(w[xx][yy],w[aa][bb]);
        }
    }
    
    return false;
}

int main(){
    bool f=false;
    
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            char a;
            cin>>a;
            if(a=='B')w[i][j]=1;//黑棋为1
            else if(a=='W')w[i][j]=2;//白棋为2
            else{
                if(!f){
                    f=true;
                    fx1=i,fy1=j;
                }else{
                    fx2=i,fy2=j;
                }
            }
        }
    }

    //直接枚举步数——一般这些步数都很少的
    for(ans=0;ans<=0x3f3f3f3f;ans++){
        if(dfs(0,fx1,fy1,fx2,fy2,1))break;
        if(dfs(0,fx1,fy1,fx2,fy2,2))break;
    }
    
    cout<<ans;
    
    return 0;
}