991
hdu 1067 Gap
本來認為是個數學題或者dp題，但是後來看到規則發現用搜索完全可以做
因為規則限製，每次隻能把空白左邊下一位的數移動到空白處，所以每次最多走4種情況，這就可以bfs了
一開始用map的，但是TLE了（雖然不是這個問題）於是手寫hash，對999991取了個餘，雖然一定不完善，但是數據沒那麼強。
手寫hash後依舊TLE……最後檢查了好幾遍才發現是空格左邊可能仍是空格，這一點沒有考慮到，所以一直TLE（差點手寫隊列了o(╯□╰)o）
加了個判斷後，500ms就過了……
注意位運算的優先級，今天被坑好幾次了
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#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());
}
}
最後更新：2017-04-02 22:15:46