十滴水问题求解器第二版（bfs+hash去重）

改进介绍

对比之前的程序：1.添加了hash去重，减少bfs扩展结点个数，加快了搜索个数，对于任何局面均可在1s内完成搜索。2.改变了对于某一局势的变化方式，从以前的dfs变成了强行模拟每一粒水滴，增加了准确性。

代码：

#include<bits/stdc++.h>
using namespace std;
const int bas = 6;
#define MOD 1000000007
#define mod(x) ((x)%MOD)
typedef long long int qq;
const int e = 17;
int mov[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
struct node{
    short x,y;
    int pre;
    node(){};
    node(short xx,short yy,short pp){
        x=xx;
        y=yy;
        pre=pp;
    }
};
vector<node>way;
struct point{
    short a[bas][bas];
    qq hast;
    qq hash(){
        hast=0;
        for(int i=0;i<bas;i++){
            for(int j=0;j<bas;j++){
                hast=hast*e+a[i][j];
            }
        }
        return hast;
    }
    print(){
        for(int i=0;i<bas;i++){
            for(int j=0;j<bas;j++){
                printf("%d",a[i][j]);
            }
            printf("\n");
        }
        printf("----%lld-------\n",hash());
    };
};
map<qq,bool>vis;
queue<point>q;
point input(){
    point ret;
    for(int i=0;i<bas;i++){
        char temp[10];
        scanf("%s",temp);
        for(int j=0;j<bas;j++){
            ret.a[i][j]=temp[j]-'0';
        }
    }
    way.push_back(node(-1,-1,0));
    return ret;
}
/*point boom(point now,int sx,int sy){ now.a[sx][sy]=0; for(int i=1;i<=4;i++){ int x=sx,y=sy; while(x>=0&&x<bas&&y>=0&&y<bas){ x+=mov[i][0]; y+=mov[i][1]; if(now.a[x][y]!=0){ now.a[x][y]++; break; } } if(now.a[x][y]==5) now=boom(now,x,y); } now.hash(); return now; }*/
point boom2(point now,int sx,int sy){
    int num=1;
    int wat[bas][bas][5]={0};
    now.a[sx][sy]=0;
    for(int i=1;i<=4;i++){
        wat[sx][sy][i]++;
    }

    while(num){//每次一步
        /*----------------将已经被击中的泡泡爆炸----------------*/
        for(int i=0;i<bas;i++)for(int j=0;j<bas;j++){
            for(int k=1;k<=4;k++){
                //if(wat[i][j][k]==0)continue;
                if(now.a[i][j]!=0){
                    while(now.a[i][j]<5&&wat[i][j][k]>0){//将当前水滴填充进泡泡
                        now.a[i][j]++;
                        wat[i][j][k]--;
                    }
                    if(now.a[i][j]==5){//当前泡泡爆炸
                        now.a[i][j]=0;
                        for(int kk=1;kk<=4;kk++){
                            wat[i][j][kk]++;
                        }
                    }
                }
            }
        }
        /*-------------所有水滴按照位移向量移动一格-------------------*/
        num=0;
        int temp[bas][bas][5]={0};
        for(int i=0;i<bas;i++)for(int j=0;j<bas;j++){
            for(int k=1;k<=4;k++){
                int x=i+mov[k][0];
                int y=j+mov[k][1];
                if(x<0||x>=bas||y<0||y>=bas)continue;
                temp[x][y][k]+=wat[i][j][k];
                num+=wat[i][j][k];
            }
        }
        for(int i=0;i<bas;i++)for(int j=0;j<bas;j++){
            for(int k=1;k<=4;k++){
                wat[i][j][k]=temp[i][j][k];
            }
        }
    }
    now.hash();
    return now;
}
void bfs(point s){
    int frt=0;
    s.hash();
    q.push(s);
    while(!q.empty()){
        point temp=q.front();
        for(int i=0;i<bas;i++)for(int j=0;j<bas;j++){//扩展新局面
            if(temp.a[i][j]==0)continue;
            temp.a[i][j]++;
            point now;
            if(temp.a[i][j]==5) now=boom2(temp,i,j);
            else now=temp;

            if(vis.count(now.hast)==0){//没出现过的新局面入队
                q.push(now);
                way.push_back(node(i,j,frt));
                vis[now.hast]=1;
            }
            if(now.hast==0)return;
            temp.a[i][j]--;

        }
        q.pop();
        frt++;
    }
}

void output(){
    node now=way[way.size()-1];
    int x[30],y[30],cnt=0;
    while(now.x!=-1&&now.y!=-1){
        x[cnt]=now.x;
        y[cnt]=now.y;
        cnt++;
        now=way[now.pre];
    }
    for(int i=cnt-1;i>=0;i--){
        printf("( %d %d )\n",x[i]+1,y[i]+1);
    }
}
void test(){
    point s=input();
    int x,y;
    while(scanf("%d%d",&x,&y)){
        x--;y--;
        s.a[x][y]++;
        if(s.a[x][y]==5){
            s=boom2(s,x,y);
        }
        s.print();
    }
}
void init(){
    way.clear();
    vis.clear();
    while(!q.empty())q.pop();

}
int main(){
    //test();
    while(1){
        init();
        point s=input();
        bfs(s);
        output();
    }
    return 0;
}
/* 小目标1：完成搜索找到最优策略 √ 小目标2：改成从初始状态生成一个边权图，找到起点s到终点t的最短路径 小目标3：加入图像识别系统，自动将输入图像完成 小目标4：将程序自动加入到页面中自动冲关。 */