Wa#1#2求助
查看原帖
Wa#1#2求助
893933
zhaoziyue2022楼主2024/8/6 16:20
#include<bits/stdc++.h>
using namespace std;
int a[10][10];
int wx[5]={0,0,0,1,-1};
int wy[5]={0,1,-1,0,0};
int ax,ay,bx,by;
int deep;
bool check(){
    for(int i=1;i<=4;i++){
        int b=1;
        for(int j=2;j<=4;j++){
            if(a[i][j]!=a[i][j-1]){
                b=0;
                break;
            }
        }
        if(b){
            return 1;
        }
    }
    for(int i=1;i<=4;i++){
        int b=1;
        for(int j=2;j<=4;j++){
            if(a[j][i]!=a[j-1][i]){
                b=0;
                break;
            }
        }
        if(b){
            return 1;
        }
    }
    if(a[1][1]==a[2][2]&&a[1][1]==a[3][3]&&a[1][1]==a[4][4]){
        return 1;
    }
    if(a[1][4]==a[2][3]&&a[1][4]==a[3][2]&&a[1][4]==a[4][1]){
        return 1;
    }
    return 0;
}
void dfs(int x,int y,int xx,int yy,int c,int d){
    if(d>deep){
        if(check()){
            cout<<deep;
            exit(0);
            //return ;
        }
        return ;
    }
    for(int i=1;i<=4;i++){
        int cx=wx[i]+x;
        int cy=wy[i]+y;
        if(cx<1||cy<1||cx>4||cy>4||a[cx][cy]==c){
            continue;
        }
        swap(a[x][y],a[cx][cy]);
        dfs(x,y,cx,cy,c^1,d+1);
        swap(a[x][y],a[cx][cy]);
    }
    for(int i=1;i<=4;i++){
        int cx=wx[i]+xx;
        int cy=wy[i]+yy;
        if(cx<1||cy<1||cx>4||cy>4||a[cx][cy]==c){
            continue;
        }
        swap(a[xx][yy],a[cx][cy]);
        dfs(x,y,cx,cy,c^1,d+1);
        swap(a[xx][yy],a[cx][cy]);
    }
}
int main(){
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            char c;
            cin>>c;
            if(c=='B'){
                a[i][j]=1;
            }else if(c=='W'){
                a[i][j]=0;
            }else if(c=='O'){
                a[i][j]=-1;
                if(!ax){
                    ax=i;
                    ay=j;
                }else{
                    bx=i;
                    by=j;
                }
            }
        }
    }
    //deep=0;
    for(deep=0;;deep++){
        dfs(ax,ay,bx,by,1,1);
        dfs(ax,ay,bx,by,0,1);
    }
    return 0;
}
2024/8/6 16:20
加载中...