天天看點
傳回

HDU 1067（HASH + BFS）

題意：如圖分部這的卡片，每次移動一個空格，讓比空格左邊的數大一的數移動到空格。最後達到目标狀态。問最少的步數。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define MAXN 1000007
typedef long long ll;
ll Hash[MAXN];

struct Node{
    int map[4][8],step;
    bool operator == (const Node &p) const {
        for(int i=0;i<4;i++)
            for(int j=0;j<8;j++)
                if(map[i][j]!=p.map[i][j])
                    return false;
        return true;
    }
    //手寫hash
    ll HashValue(){
        ll value=0;
        for(int i=0;i<4;i++)
            for(int j=0;j<8;j++)
                value+=(value<<ll(1))+(ll)map[i][j];
        return value;
    }
};

Node Start,End;

void Initaite(){
    memset(Hash,-1,sizeof(Hash));
    for(int i=0;i<4;i++){
        Start.map[i][0]=0;
        for(int j=1;j<8;j++){
            scanf("%d",&Start.map[i][j]);
        }
    }
    Start.step=0;
}

//最後的結果
void GetEnd(){
    for(int i=0;i<4;i++){
        End.map[i][7]=0;
        for(int j=0;j<7;j++){
            End.map[i][j]=(i+1)*10+(j+1);
        }
    }
}

//取得value的hash值+hash判重
bool HashInsert(ll value){
    int v=value%MAXN;
    while(Hash[v]!=-1&&Hash[v]!=value){
        v+=10;
        v%=MAXN;
    }
    if(Hash[v]==-1){
        Hash[v]=value;
        return true;
    }
    return false;
}

void bfs(){
    queue<Node>Q;
    Node p,q;
    Q.push(Start);
    HashInsert(Start.HashValue());
    while(!Q.empty()){
        p=Q.front();
        Q.pop();
        for(int i=0;i<4;i++){
            for(int j=0;j<8;j++){
                if(!p.map[i][j]){
                    q=p;
                    q.step++;
                    int value=p.map[i][j-1]+1;//找比map[i][j-1]大1的數
                    if(value==1||value%10==8)continue;//0或者value為7的不能移動
                    int x,y,flag=true;
                    for(int k=0;k<4&&flag;k++){
                        for(int l=1;l<8&&flag;l++){
                            if(p.map[k][l]==value){
                                x=k,y=l;
                                flag=false;
                            }
                        }
                    }
                    if(!flag){
                        swap(q.map[i][j],q.map[x][y]);
                        ll value=q.HashValue();
                        //hash判重
                        if(HashInsert(value)){
                            if(q==End){
                                printf("%d\n",q.step);
                                return ;
                            }
                            Q.push(q);
                        }
                    }
                }
            }
        }
    }
    puts("-1");
}

void Solve(){
    int k=0;
    //将11，21,31,41這四個數移到第0列
    for(int i=0;i<4;i++){
        for(int j=1;j<8;j++){
            if(Start.map[i][j]==(k+1)*10+1){
                swap(Start.map[i][j],Start.map[k][0]);
                k++,i=0,j=0;
            }
        }
    }
    if(Start==End){
        puts("0");//前四步不記錄總步數
        return ;
    }
    bfs();
}

int main(){
    int _case;
    scanf("%d",&_case);
    GetEnd();
    while(_case--){
        Initaite();
        Solve();
    }
    return 0;
}
           
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>
#define INF 1E9
using namespace std;
const char ss[32]={11,12,13,14,15,16,17,0,21,22,23,24,25,26,27,0,31,32,33,34,35,36,37,0,41,42,43,44,45,46,47,0};
string aim="";
struct node
{
    int x,y;
};
char m[4][8];
struct state
{
   node pos[50],blank[4];//pos确定每個數字位置，blank是4個空格位置
   string s;//圖
   int lvl;//步數
};
string m2s()//把圖變成字元串
{
    string now="";
    int i,j;
    for(i=0;i<4;i++)
     for(j=0;j<8;j++)
      now.push_back(m[i][j]);
    return now;
}
int get_hash(string s)//獲得hash值
{
    long long ans=0;
    for(int i=0;i<32;i++)
        ans=(ans<<1)+s[i];
    return ans%999991;
}
bool vis[1000000];
queue<state> q;
state now,next;
node temp;
int bfs()
{
    memset(vis,0,sizeof(vis));
    while(!q.empty())q.pop();
    int i,j,t=0,k,o,lvl;
    for(i=0;i<4;i++)
     for(j=0;j<8;j++)
     {
         temp.x=i;temp.y=j;
         if(m[i][j]==0)now.blank[t++]=temp;
         else now.pos[m[i][j]]=temp;
     }
    now.s=m2s();vis[get_hash(now.s)]=1;
    now.lvl=1;
    q.push(now);
    int Aim=get_hash(aim);
    while(!q.empty()&&!vis[Aim])
    {
        now=q.front();q.pop();
        next=now;
        next.lvl=now.lvl+1;
        for(i=0;i<4;i++)
        {
            node &b=next.blank[i];
            o=8*b.x+b.y-1;
            t=next.s[o];
            if(t%10==7||t==0)continue;//注意空格旁還是空格的情況
            k=t+1;
            node &p=next.pos[k];
            k=p.x*8+p.y;
            o++;
            swap(next.s[o],next.s[k]);//移動位置
            t=get_hash(next.s);
            if(!vis[t])
            {
                if(t==Aim)return next.lvl-1;
                swap(p,b);
                q.push(next);
                vis[t]=1;
                swap(p,b);
            }
            swap(next.s[o],next.s[k]);//恢複
        }
    }
    return vis[Aim]-1;
}
int main()
{
   int T;
   for(T=0;T<32;T++)aim.push_back(ss[T]);
   scanf("%d",&T);
   while(T--)
   {
       memset(m,0,sizeof(m));
       int i,j,t;
       for(i=0;i<4;i++)
        for(j=1;j<8;j++)
        {
            scanf("%d",&t);
            m[i][j]=(char)t;
            if(t%10==1) swap(m[i][j],m[(t/10)-1][0]);
        }
       printf("%d\n",bfs());
   }
}
           
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int MOD=1000007;
struct node
{
    int map[10][10];
    int d;
};
bool vis[MOD];
long long gethash(node &t)
{
    int tmp[70],k=0;
    memset(tmp,0,sizeof(tmp));
    int i,j;
    for(i=0;i<4;i++)
    {
        for(j=0;j<8;j++)
        {
            tmp[k++]=t.map[i][j]/10;
            tmp[k++]=t.map[i][j]%10;
        }
    }
    long long hash=0;
    for(i=0;i<k;i++)
    {
        hash=hash*7+tmp[i];
    }
    hash=(hash&0x7fffffff)%MOD;
    //hash=hash%MOD;
    return hash;

}
int aim[4][8]=
{
    {11,12,13,14,15,16,17,0},
    {21,22,23,24,25,26,27,0},
    {31,32,33,34,35,36,37,0},
    {41,42,43,44,45,46,47,0}
};
int getaim(node &t)
{
    int i,j;
    for(i=0;i<4;i++)
    {
        for(j=0;j<8;j++)
        {
            if(t.map[i][j]!=aim[i][j])
                return 0;
        }
    }
    return 1;
}
int change(node &t,int num)
{
    int i,j;
    for(i=0;i<4;i++)
    {
        for(j=0;j<8;j++)
        {
            if(t.map[i][j]==num+1)
            {
                t.map[i][j]=0;
                return 1;
            }
        }
    }
    return 0;
}
int bfs(node t)
{
    t.map[0][0]=11;
    t.map[1][0]=21;
    t.map[2][0]=31;
    t.map[3][0]=41;
    t.d=0;
    memset(vis,0,sizeof(vis));
    int hash=gethash(t);
    vis[hash]=1;
    queue<node> q;
    q.push(t);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(getaim(t))
            return t.d;
        int i,j;
        for(i=0;i<4;i++)
        {
            for(j=1;j<8;j++)
            {
                if(t.map[i][j]==0&&t.map[i][j-1]%10!=7&&t.map[i][j-1]!=0)
                {
                    node cur=t;
                    change(cur,cur.map[i][j-1]);
                    cur.map[i][j]=cur.map[i][j-1]+1;
                    cur.d=cur.d+1;
                    hash=gethash(cur);
                    if(!vis[hash])
                    {
                        vis[hash]=1;
                        q.push(cur);
                    }
                }
            }
        }
    }
    return -1;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int i,j;
        node t;
        memset(t.map,0,sizeof(t.map));
        for(i=0;i<4;i++)
        {
            for(j=1;j<8;j++)
            {
                scanf("%d",&t.map[i][j]);
                if(t.map[i][j]%10==1)
                    t.map[i][j]=0;
            }
        }
        int res=bfs(t);
        printf("%d\n",res);

    }
    return 0;
}
           
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define mod 1000007
long long tag;
long long base[33]={1};
struct cq
{
    int map[4][8];
    long long step;
    int bx[5];  //記錄4個空格
    int by[5];
};
queue<cq>Q;
int T;
long long hash[1000007];
bool flag;
long long gethash(int t[][8])
{
    long long h=0;
    for(int i=0;i<4;i++)
    for(int j=0;j<8;j++)
    h += t[i][j] * base[i*8+j];

    if(h==tag)flag=true;
    return h;
}

bool insert(long long value)
{
    long long v = value % mod;
    while(hash[v]!=-1 && hash[v]!=value)
    {
        v= (v+10)%mod;
    }
    if(hash[v]==-1)
    {
        hash[v]=value;
        return true;
    }
    return false;
}

bool work(int t[][8])
{
    long long sb=gethash(t);
    return insert(sb);
}

int aim[4][8]=
{
    11,12,13,14,15,16,17,0,
    21,22,23,24,25,26,27,0,
    31,32,33,34,35,36,37,0,
    41,42,43,44,45,46,47,0
};


int bfs()
{
    cq w,e;
    while(!Q.empty())
    {
        w=Q.front();
        Q.pop();
            for(int i=1;i<=4;i++)
            {
                e=w;
                int xx=e.bx[i];
                int yy=e.by[i];
                for(int a=0;a<4;a++)
                for(int b=0;b<8;b++)
                {
                    if(e.map[a][b]==0)continue;
                    if(e.map[a][b]!=e.map[xx][yy-1]+1)continue;
                        swap(e.map[a][b],e.map[xx][yy]);
                        if(work(e.map))
                        {
                            e.step = w.step + 1;
                            e.bx[i]=a;
                            e.by[i]=b;
                            Q.push(e);
                            if(flag)
                            return e.step;
                        }
                }
            }

    }
    return -1;
}


int main()
{
    for(int i=1;i<33;i++)
    {
        base[i]=base[i-1]*2;
    }
    cq w;
    tag = 98430874871LL;   //目标狀态
    scanf("%d",&T);
    while(T--)
    {
        while(!Q.empty())Q.pop();
        flag=false;
        int k=1;
        memset(hash,-1,sizeof(hash));
        //insert(tag);
        w.map[0][0]=w.map[1][0]=w.map[2][0]=w.map[3][0]=0;
        for(int i=0;i<4;i++)
        for(int j=1;j<8;j++)
        {
            scanf("%d",&w.map[i][j]);
            if(w.map[i][j]==11){w.bx[k]=i;w.by[k++]=j;swap(w.map[i][j],w.map[0][0]);}
            else if(w.map[i][j]==21){w.bx[k]=i;w.by[k++]=j;swap(w.map[i][j],w.map[1][0]);}
            else if(w.map[i][j]==31){w.bx[k]=i;w.by[k++]=j;swap(w.map[i][j],w.map[2][0]);}
            else if(w.map[i][j]==41){w.bx[k]=i;w.by[k++]=j;swap(w.map[i][j],w.map[3][0]);}
        }
        w.step=0;
        work(w.map);
        Q.push(w);
        if(flag)printf("0\n");
        else printf("%d\n",bfs());
    }
    return 0;
}


/*

4
26 31 13 44 21 24 42
17 45 23 25 41 36 11
46 34 14 12 37 32 47
16 43 27 35 22 33 15
*/
hash 搜尋 ACM HDU bfs
上一篇: 手把手教你使用Android Paging Library
下一篇: 線性回歸之随機梯度下降（sgd）

繼續閱讀