codevs1004 四子连棋

题目描述 Description

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

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

BWBO
WBWB
BWBW
WBWO

样例输出 Sample Output

5

//hash是个好东西（万物皆可哈）

 

#include<bits/stdc++.h>
#define UP(i,m,n) for(int i=m;i<=n;i++)
using namespace std;
int d[5000][5][5];
int next[5000]={1,2};
int step[5000];
bool hash[4000000];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int t=0,w=2,flag=0;
bool equ(int a1,int a2,int a3,int a4){if(a1!=a2||a2!=a3||a3!=a4)return 0;return 1;}
bool check(){
    UP(i,1,4){
        if(equ(d[w][i][1],d[w][i][2],d[w][i][3],d[w][i][4]))return 1;
        if(equ(d[w][1][i],d[w][2][i],d[w][3][i],d[w][4][i]))return 1;
    }
    if(equ(d[w][1][1],d[w][2][2],d[w][3][3],d[w][4][4]))return 1;
    if(equ(d[w][1][4],d[w][2][3],d[w][3][2],d[w][4][1]))return 1;
    return 0;
}
int Hash(){
    int s=0,k=1;
    UP(i,1,4)UP(j,1,4){s+=d[w][i][j]*k;k*=3;}
    s%=3733799;
    if(!hash[s]){hash[s]=1;return 1;}
    return 0;
}
bool pd(int x,int y){
    int k=next[t];
    if(x>4||y>4||x==0||y==0)return 0;
    else if(d[t][x][y]==k)return 1;
    return 0;
}
void move(int x,int y){
    UP(i,0,3){
        int p=x+dx[i],q=y+dy[i];
        if(pd(p,q)){
            UP(j,1,4)UP(k,1,4)d[w][j][k]=d[t][j][k];
            swap(d[w][x][y],d[w][p][q]);
            step[w]=step[t]+1;
            if(check()){cout<<step[w]<<endl;flag=1;return;}
            if(Hash()){         
                if(next[t]==1)next[w++]=2;
                if(next[t]==2)next[w++]=1;
            }
        }
    }
}
void BFS(){
    while(t<w){
        UP(i,1,4)UP(j,1,4){
            if(d[t][i][j]==0)move(i,j);
            if(flag)return;
        }
        t++;
    }
}
int main(){
    UP(i,1,4)UP(j,1,4){
        char x; cin>>x;
        if(x=='W')d[0][i][j]=d[1][i][j]=1;
        if(x=='B')d[0][i][j]=d[1][i][j]=2;
    }
    BFS();
    return 0;
}