先是这周是搜索的题，网站：http://acm.hdu.edu.cn/webcontest/contest_show.php?cid=6041
主要内容是BFS,A*,IDA*，还有一道K短路的,.....木做，本来1009是说要用迭代加深做，但是我在他讲之前就用BFSA了，虽然很耗时，但还是过了，10000MS的时限，我8000+MS.......
1001 Eight 八数码问题
先把代码放上来
题目网址： http://acm.hdu.edu.cn/showproblem.php?pid=1043
| 500MS | 3524K | 3183 B |
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
class Node
{
public:
int maze[][]; //八数码具体情况
int h,g; //两个估价函数
int x,y; //空位的位置
int Hash; //HASH值
bool operator<(const Node n1)const{ //优先队列第一关键字为h,第二关键字为g
return h!=n1.h?h>n1.h:g>n1.g;
}
bool check() //判断是否合法
{
if(x>=&&x<&&y>=&&y<)
return true;
return false;
}
}s,u,v;
int HASH[]={,,,,,,,,}; //HASH的权值
int des=; //目标情况的HASH值
int vis[]; //判断状态已遍历，初始为-1，否则为到达这步的转向
int pre[]; //路径父节点
int way[][]={{,},{,-},{,},{-,}}; //四个方向
int get_hash(Node tmp) //获得HASH值
{
int a[],k=;
for(int i=;i<;i++)
for(int j=;j<;j++)
a[k++]=tmp.maze[i][j];
int res=;
for(int i=;i<;i++){
int k=;
for(int j=;j<i;j++)
if(a[j]>a[i])
k++;
res+=HASH[i]*k;
}
return res;
}
bool isok(Node tmp){ //求出逆序对，判断是否有解
int a[],k=;
for(int i=;i<;i++)
for(int j=;j<;j++)
a[k++]=tmp.maze[i][j];
int sum=;
for(int i=;i<;i++)
for(int j=i+;j<;j++)
if(a[j]&&a[i]&&a[i]>a[j])
sum++;
return !(sum&); //由于目标解为偶数，所以状态的逆序数为偶数才可行
}
int get_h(Node tmp){ //获得估价函数H
int ans=;
for(int i=;i<;i++)
for(int j=;j<;j++)
if(tmp.maze[i][j])
ans+=abs(i-(tmp.maze[i][j]-)/)+abs(j-(tmp.maze[i][j]-)%);
return ans;
}
void astar(){ //搜索
priority_queue<Node>que; //优先队列
que.push(s);
while(!que.empty())
{
u=que.top();
que.pop(); //出队
for(int i=;i<;i++)
{
v=u;
v.x+=way[i][];
v.y+=way[i][];
if(v.check())
{
swap(v.maze[v.x][v.y],v.maze[u.x][u.y]); //将空位和相邻位交换
v.Hash=get_hash(v); //得到HASH值
if(vis[v.Hash]==-)//判断是否已遍历且是否可行
{
vis[v.Hash]=i; //保存方向
v.g++;; //代价++
pre[v.Hash]=u.Hash; //保存v的父节点u
v.h=get_h(v); //得到新的估价函数H
que.push(v); //入队
}
if(v.Hash==des)
return ;
}
}
}
}
void print()
{
string ans;
char wu[]={'r','l','d','u'};
ans.clear();
int nxt=des;
while(pre[nxt]!=-) //从终点往起点找路径
{
ans+=wu[vis[nxt]];
nxt=pre[nxt]; //上一个父节点
}
for(int i=ans.size()-;i>=;i--)
printf("%c",ans[i]);
printf("\n");
}
int main()
{
char str[];
while(gets(str)!=NULL)
{
int k=;
memset(vis,-,sizeof(vis));
memset(pre,-,sizeof(pre));
for(int i=;i<;i++)
for(int j=;j<;j++)
{
if((str[k]<=''&&str[k]>='')||str[k]=='x')
{
if(str[k]=='x')
{
s.maze[i][j]=;
s.x=i;
s.y=j;
}
else
s.maze[i][j]=str[k]-'';
}
else
j--;
k++;
}
if(!isok(s)) //起始状态不可行
{
printf("unsolvable\n");
continue;
}
s.Hash=get_hash(s);
if(s.Hash==des)
{
printf("\n");
continue;
}
vis[s.Hash]=-;
s.g=;s.h=get_h(s);
astar(); //A*
print(); //打印路径
}
return ;
}
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
class A
{
public:
int a[][];
int h,g;
int x,y;
int has;
bool operator<(const A n)const{return h!=n.h?h>n.h:g>n.g;}
bool check()
{
if (x>=&&x<=&&y>=&&y<=)
return true;
return false;
}
}s,w,r;
int H[]={,,,,,,,,};
int des=;
int v[];
int p[];
int d[][]={{,},{,-},{,},{-,}}; bool ok(A c)
{
int q[],k=,i,j,sum=;
for(i=;i<;i++)
for(j=;j<;j++)
q[k++]=c.a[i][j];
for(i=;i<;i++)
for(j=i+;j<;j++)
if(q[j]&&q[i]&&q[i]>q[j])
sum++;
return !(sum&);
} int gethas(A c)
{
int q[],k=,i,j,sum=;
for(i=;i<;i++)
for(j=;j<;j++)
q[k++]=c.a[i][j];
for(i=;i<;i++)
{
int o=;
for(j=;j<i;j++)
if(q[j]>q[i])
o++;
sum+=H[i]*o;
}
return sum;
} int geth(A c)
{
int sum=,i,j;
for(i=;i<;i++)
for(j=;j<;j++)
if(c.a[i][j])
sum+=abs(i-(c.a[i][j]-)/)+abs(j-(c.a[i][j]-)%);
return sum;
} void astar()
{
int i;
priority_queue<A>f;
f.push(s);
while(!f.empty())
{
w=f.top();
f.pop();
for(i=;i<;i++)
{
r=w;
r.x+=d[i][];
r.y+=d[i][];
if(r.check())
{
swap(r.a[w.x][w.y],r.a[r.x][r.y]);
r.has=gethas(r);
if(v[r.has]==-)
{
v[r.has]=i;
r.g++;
p[r.has]=w.has;
r.h=geth(r);
f.push(r);
}
if(r.has==des)
return ;
}
}
}
} void print()
{
string str;
char wu[]={'r','l','d','u'};
str.clear();
int next=des,i;
while(p[next]!=-)
{
str+=wu[v[next]];
next=p[next];
}
for(i=str.size()-;i>=;i--)
putchar(str[i]);
printf("\n");
} int main()
{
char b[];
int i,j,k;
while(gets(b)!=NULL)
{
memset(v,-,sizeof(v));
memset(p,-,sizeof(p));
k=;
for(i=;i<;i++)
for(j=;j<;j++)
{
if(b[k]=='x')
{
s.a[i][j]=;
s.x=i;
s.y=j;
}
else if(b[k]>=''&&b[k]<='')
s.a[i][j]=b[k]-'';
else
j--;
k++;
} if(!ok(s))
{
printf("unsolvable\n");
continue;
}
s.has=gethas(s);
if(s.has==des)
{
printf("\n");
continue;
}
v[s.has]=-;
s.g=;
s.h=geth(s);
astar();
print();
}
}
1006 The Rotation Game
第二题 IDA*算法，感觉比上面那个简单
题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=1667
| 296MS | 300K | 1895 B |
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int maxx(int x,int y,int z) {return max(max(x,y),z);} //三个数的最大值
int a[][]={
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,,
,,,,,,,
}; //每一纵行和横行的编号
int re[]={,,,,,,,,}; //往回移对应的编号
int mid[]={,,,,,,,,}; //中间的8个数的编号
char lu[]="OABCDEFGH"; //路径
int b[]; //现状
char father[]; //记录父节点的编号
int dep; //允许的深度 int geth(int b[]) //获得H值
{
int i,w[];
memset(w,,sizeof(w));
for(i=;i<=;i++)
w[b[mid[i]]]++;
return -maxx(w[],w[],w[]);
} int IDA(int g)
{
int i,H,t,j;
if(g>=dep)
return ;
for(i=;i<=;i++)
{
t=b[a[i][]];
for(j=;j<=;j++)
b[a[i][j]]=b[a[i][j+]];
b[a[i][]]=t;
father[g]=i; //记录父节点
H=geth(b); //获得最新的H
if(!H)
return ;
if(g+H<dep && IDA(g+)) //A*剪枝
return ;
t=b[a[re[i]][]]; //回到上一步
for(j=;j<=;j++)
b[a[re[i]][j]]=b[a[re[i]][j+]];
b[a[re[i]][]]=t;
}
return ;
} int main()
{
int i;
while(~scanf("%d",&b[])&&b[])
{
for(i=;i<=;i++)
scanf("%d",&b[i]);
dep=geth(b);
if(!dep) //不需要移动
{
printf("No moves needed\n");
printf("%d\n",b[]);
continue;
}
while(!IDA())
dep++;
for(i=;i<=dep-;i++)
printf("%c",lu[father[i]]);
printf("\n%d\n",b[]);
}
return ;
}