百度之星

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

const int hashsize=70001; 
const int maxnode=50000; 
const int maxp=40; 
const int ten[]={1,10,100,1000,10000,100000,1000000,10000000,100000000}; 
const int C[]={2,3,2,3,4,3,2,3,2}; 
const int EP[][4]={{1,3,0,0},{0,2,4,0},{1,5,0,0},{0,4,6,0},{1,3,5,7},{2,4,8,0},{3,7,0,0},{4,6,8,0},{5,7,0,0}}; 

struct Tlist 
{ 
int data,d; 
Tlist *next; 
}; 
struct Thashpoint 
{ 
int data; 
Thashpoint *next; 
}; 
//Memory 
int ID; 
Tlist listM[maxnode],*q; 
Thashpoint hashM[maxnode],*p; 
//data 
int src,dest; 
//heap 
Tlist *head[maxp],*expand[maxp],*lp1,*lp2; 
//Hash 
Thashpoint *hash[hashsize]; 
//expand 
int nowp,A[9],arcT[9],dist[9][9],b,depth,swap[9][9]; 

   　  　   　 作者： 61.135.146.*  2005-10-20 16:43 　 回复此发言    

　  --------------------------------------------------------------------------------

  7  楼天城的比赛答题源码  
　 int data,G,newdata,newG; 
bool find_answer; 

void readdata(const char *filename,int &data) 
{ 
int i,v; 
FILE *f=fopen(filename,"r"); 
data=0; 
for (i=0;i<9;i++) 
{ 
fscanf(f,"%d",&v); 
data=data+v*ten[i]; 
} 
fclose(f); 
} 
bool check_noanswer() 
{ 
int p[9],i,b1,b2; 
bool vis[9]; 
for (i=0;i<9;i++) 
p[i]=arcT[src/ten[i]%10]; 
for (b1=0; src/ten[b1]%10!=0;b1++); 
for (b2=0;dest/ten[b2]%10!=0;b2++); 
int countP=0; 
memset(vis,false,sizeof(vis)); 
for (i=0;i<9;i++) 
if (!vis[i]) 
{ 
countP++; 
for (int k=i;!vis[k];k=p[k]) 
vis[k]=true; 
} 
return (countP-dist[b1][b2])%2==0; 
} 
void preprocess() 
{ 
ID=0; 
find_answer=false; 
memset(hash,0,sizeof(hash)); 
memset(head,0,sizeof(head)); 
memset(expand,0,sizeof(expand)); 
for (int k=0;k<9;k++) 
arcT[dest/ten[k]%10]=k; 
for (int u=0;u<9;u++) 
for (int v=0;v<9;v++) 
{ 
dist[u][v]=abs(u/3-v/3)+abs(u%3-v%3); 
swap[u][v]=ten[u]-ten[v]; 
} 
} 
void addnode() 
{ 
if (newdata==dest) 
{ 
printf("%d\n",depth); 
find_answer=true; 
return; 
} 
int address=newdata%hashsize; 
for (p=hash[address];p!=NULL;p=p->next) 
if (p->data==newdata) 
return; 
if (ID==maxnode) 
return; 
p=&hashM[ID]; 
p->data=newdata; 
p->next=hash[address]; 
hash[address]=p; 
q=&listM[ID]; 
ID++; 
q->data=newdata; 
q->d=depth; 
if (newG>=maxp) 
return; 
if (newG==nowp) 
{ 
q->next=expand[depth]; 
expand[depth]=q; 
} 
else 
{ 
q->next=head[newG]; 
head[newG]=q; 
} 
} 
void solve() 
{ 
nowp=-1; 
newdata=src; 
newG=0; 
for (int k=0;k<9;k++) 
if (src/ten[k]%10!=0) 
newG+=dist[arcT[src/ten[k]%10]][k]; 
depth=0; 
addnode(); 
if (find_answer) 
return; 
for (int p=0;p<maxp;p++) if (head[p]!=NULL) 
{ 
nowp=p; 
for (lp1=head[p];lp1!=NULL;lp1=lp2) 
{ 
lp2=lp1->next; 
lp1->next=expand[lp1->d]; 
expand[lp1->d]=lp1; 
} 
for (int d=0;d<=p;d++) 
for (;expand[d]!=NULL;) 
{ 
data=expand[d]->data; 
G=p-expand[d]->d; 
depth=expand[d]->d+1; 
expand[d]->d=-2; 
expand[d]=expand[d]->next; 
for (b=0;data/ten[b]%10!=0;b++); 
for (int v=0;v<C[b];v++) 
{ 
int u=EP[b][v]; 
int c=data/ten[u]%10; 
newdata=data+swap[b][u]*c; 
c=arcT[c]; 
newG=depth+G-dist[c][u]+dist[c][b]; 
addnode(); 
if (find_answer) 
return; 
} 
} 
} 
printf("-1\n"); 
} 
int main() 
{ 
readdata("start.txt",src); 
readdata("goal.txt",dest); 
preprocess(); 
if (check_noanswer()) 
printf("-1\n"); 
else 
solve(); 
return 0; 
} 

    

网址：百度之星 http://c.mxgxt.com/news/view/125269

相关内容

百度明星粉丝 百度明星控
演员的百度百科怎么做，百度明星简介怎么做的
百度年度明星票选
百度娱乐
百度app明星
看了你就懂！明星艺人百度百科怎么创建？娱乐人物百度百科创建技巧
明星网红名人为什么要建百度百科？
百度百科明星人气榜入口在哪里？
百度百家号打造「明星创作者计划」，聚集百亿流量实现生态共创
伞与大妖的魅力度简直是百分之百的加成！

随便看看