题解 P2346 【四子连棋】

Xiao_Mi · 2018-07-28 12:35:40 · 题解

这题可以用迭代加深搜索来做

用ans枚举多少步可以达到棋局，然后再dfs，若超过ans就返回，一直到可移动到目标棋局为止。

这样就不会超时了。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[11][11],ans;
int fkx[5]={0,-1,1,0,0},
    fky[5]={0,0,0,-1,1};
int check(){//查看是否到目标棋局
    for(int i=1;i<=4;i++){
        if(a[i][1]==a[i][2]&&a[i][2]==a[i][3]&&a[i][3]==a[i][4]) return 1;
        if(a[1][i]==a[2][i]&&a[2][i]==a[3][i]&&a[3][i]==a[4][i]) return 1;
    }
    if(a[1][1]==a[2][2]&&a[2][2]==a[3][3]&&a[3][3]==a[4][4]) return 1;
    if(a[1][4]==a[2][3]&&a[2][3]==a[3][2]&&a[3][2]==a[4][1]) return 1;
    return 0;
}
int dfs(int x,int y,int xx,int yy,int color,int teg){//color：上一组的颜色，teg：第几层
    if(ans==teg){
        if(check()) return 1;
        else return 0;
    }
    for(int i=1;i<=4;i++){
        int dx=fkx[i]+x;
        int dy=fky[i]+y;
        int ddx=fkx[i]+xx;
        int ddy=fky[i]+yy;
        if(dx>0&&dx<=4&&dy>0&&dy<=4&&a[dx][dy]!=color){
            swap(a[x][y],a[dx][dy]);
            if(dfs(dx,dy,xx,yy,(color==1?2:1),teg+1)) return 1;;
            swap(a[dx][dy],a[x][y]);
        }
        if(ddx>0&&ddx<=4&&ddy>0&&ddy<=4&&a[ddx][ddy]!=color){
            swap(a[xx][yy],a[ddx][ddy]);
            if(dfs(x,y,ddx,ddy,(color==1?2:1),teg+1)) return 1;
            swap(a[ddx][ddy],a[xx][yy]);
        }
    }
    return 0; 
}
int main(){
    int i,j,fx1=0,fy1=0,fx2=0,fy2=0;
    char c;
    for(i=1;i<=4;i++){
        for(j=1;j<=4;j++){
            cin>>c;
            if(c=='B') a[i][j]=1;
            if(c=='W') a[i][j]=2;
            if(c=='O') a[i][j]=0;
            if(a[i][j]==0&&!fx1) fx1=i,fy1=j;
            else if(a[i][j]==0) fx2=i,fy2=j;
        }
    }
    //枚举多少步可到达棋局
    for(ans=1;ans<=0x3f3f3f;ans++){
     //先黑再白，注意顺序
        if(dfs(fx1,fy1,fx2,fy2,1,0)) break;
        if(dfs(fx1,fy1,fx2,fy2,2,0)) break;
    }
    cout<<ans;
    return 0; 
}