本文主要是介绍SWUN 1425 - 疯狂的马儿，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
疯狂的马儿时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte 总提交 : 19 测试通过 : 5 描述
在一个5*5规模的棋盘上，放着黑马和白马。每种马都有12个，因此棋盘上恰好有一个空格。在任意时刻，马儿只允许移动到空格上（移动规则如下图所示）
现在，给定棋盘的初始状态，Snow_storm想知道最少移动几次可以达到如下图所示的目标状态：
输入
输入的第一行为正整数T(<=100)，表示测试组数。
对于每组测试数据，共有5行，每行有5个字符，表示棋盘的初始状态：其中’0’表示白马,’1’表示黑马，’ ’表示空格。
其中样例一对应的状态如下图所示：
输出 对于每组测试数据，若不能在16步之内(<16)达到目标状态，则输出Crazy horse，否则输出最小步数。更多的细节请参看样例输出。 样例输入 2 样例输出 Case 1: Crazy horse 题目来源 YB |
题目地址： http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1425
原题：http://www.lightoj.com 题号1143 。。。 PS： 此题在输出时对原题做了改动。
===================================================================================================
其实只要有想法，这题的代码还是比较好实现的。
初步写的时候，就是用B哥说的，KM匹配作为启发式，写IDA*。
KM匹配只看了一点。所以让怪叔叔代敲（直接套B哥的模版）。。。
匹配的建图自己建，一开始对于每次匹配都重新BFS一次建图。。。
结果TLE在第一组测试数据。。。 于是预处理所有位置到任意位置的步数，此时匹配的建图时间就只有O(5*5*12)。。。
再次TLE在第二组测试数据。。。
一开始想了个剪枝： 不走回头路。当你往前走时，记住此时走的方向，当你在下一个位置，判断一下，不走反方向。。。
但是仍然TLE在第二组，貌似剪枝没效果。。。
只能记录状态，判断重复状态了。。。 不懂B哥记录状态的方法（貌似与后向星有关？）
想了一下，突然想到用字典树。。。囧。。。 时间够了，样例却过不去，13步能走的，走了15步。。。
然后想了一下，找到了一个BUG： DFS是深搜，也就是这个方向第5步产生的状态，也许另一个方向只需要3步就能产生。。。
所以状态判断不能只判断是否曾走过，还要判步数少的能再次走。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char p[6][6]; // dfs时的当前地图
// KM匹配 ===================================
const int maxn=33;
const int inf=0x3fffffff;
int tol,n,m,mat[maxn],lx[maxn],ly[maxn],lack,map[maxn][maxn];
bool visx[maxn],visy[maxn];
bool Find(int x){
int i,v,y;
visx[x]=true;
for(i=1;i<=n;i++){
y=i;
if(!visy[y]){
int t=lx[x]+ly[y]-map[x][y];
if(!t){
visy[y]=true;
if(mat[y]==-1||Find(mat[y])){
mat[y]=x;
return true;
}
}
else if(lack>t) lack=t;
}
}
return false;
}
int KM(){
int i,j,x,y;
/* // 输出当前地图，与构图结果
cout<<"p------"<<endl;
for(i=0;i<5;i++){puts(p[i]);}
cout<<"map------"<<endl;
for(i=1;i<=n;i++){for(j=1;j<=m;j++)cout<<map[i][j]<<" ";cout<<endl;}
*/
memset(mat,-1,sizeof(mat));
for(i=1;i<=n;i++){
lx[i]=-inf;
ly[i]=0;
for(j=1;j<=n;j++){
x=map[i][j];
if(x>lx[i]) lx[i]=x;
}
}
for(i=1;i<=n;i++){
while(1){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
lack=inf;
if(Find(i)) break;
for(j=1;j<=n;j++){
if(visx[j]) lx[j]-=lack;
if(visy[j]) ly[j]+=lack;
}
}
}
int ret=0;
for(i=1;i<=n;i++){
if(mat[i]!=-1)
ret+=lx[mat[i]],ret+=ly[i];
}
return ret;
}
// 构图（用于KM匹配） ============
int fx[]={-2,2,-2,2,1,-1,1,-1};
int fy[]={-1,1,1,-1,2,-2,-2,2};
int d1[5][5]={{1,2,3,4,5},{0,6,7,8,9},{0,0,0,10,11},{0,0,0,0,12},{0,0,0,0,0}};
int d2[5][5]={{0,0,0,0,0},{12,0,0,0,0},{10,11,0,0,0},{6,7,8,9,0},{1,2,3,4,5}};
int rec[6][6][6][6];
struct Node{
int x,y;
Node(){}
Node(int a,int b){x=a,y=b;}
}que[20000];
void deal(){ // 预处理任意坐标(x1,y1)到任意坐标(x2,y2)之间的最短步数
int i,j,vis[6][6],ss,st,cnt=1,nx,ny,k,tx,ty;
for(i=0;i<5;i++)
for(j=0;j<5;j++){
memset(vis,-1,sizeof(vis));
que[ss=st=0]=Node(i,j);
vis[i][j]=0;
while(ss<=st){
nx=que[ss].x;
ny=que[ss].y;
ss++;
if(d1[nx][ny]!=0)
rec[i][j][nx][ny]=-vis[nx][ny];
if(d2[nx][ny]!=0)
rec[i][j][nx][ny]=-vis[nx][ny];
for(k=0;k<8;k++){
tx=nx+fx[k];
ty=ny+fy[k];
if(tx<0 || ty<0 || tx>4 || ty>4) continue;
if(vis[tx][ty]!=-1) continue;
vis[tx][ty]=vis[nx][ny]+1;
st++;
que[st].x=tx;
que[st].y=ty;
}
}
cnt++;
}
}
int BFS1(){ // 匹配黑马
int i,j,g,f,cnt=1;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
if(p[i][j]=='1'){
for(g=0;g<5;g++)
for(f=(g<2?g:g+1);f<5;f++)
map[cnt][d1[g][f]]=rec[i][j][g][f];
cnt++;
}
n=12,m=12;
return KM();
}
int BFS2(){ // 匹配白马
int i,j,g,f,cnt=1;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
if(p[i][j]=='0'){
for(g=0;g<5;g++)
for(f=(g>2?g:g-1);f>=0;f--)
map[cnt][d2[g][f]]=rec[i][j][g][f];
cnt++;
}
n=12,m=12;
return KM();
}
// 字典树（用于存储状态） ==================
struct Tree{
int step;
Tree *next[3];
};
Tree *root;
void init_(Tree *x){ // 初始化新节点
x->step=10000;
x->next[0]=x->next[1]=x->next[2]=0;
}
int cover(int step){ // 加入字典树
Tree *new_,*now=root;
int i,j,k,flag=0;
for(i=0;i<5;i++)
for(j=0;j<5;j++){
if(p[i][j]=='0') k=0;
else if(p[i][j]=='1') k=1;
else k=2;
if(now->next[k]==0){
new_=new Tree;
init_(new_);
now->next[k]=new_;
}
now=now->next[k];
}
if(now->step>step){ // 判断可否再走
now->step=step;
flag=1;
}
return flag;
}
void clr(Tree *x){ // 删除字典树 （释放内存）
if(x->next[0]) clr(x->next[0]);
if(x->next[1]) clr(x->next[1]);
if(x->next[2]) clr(x->next[2]);
delete x;
}
// 启发式搜索 =============
bool dfs(int x,int y,int step,int tol){
int k,h,nx,ny;
h=-(BFS1()+BFS2()); // 启发式
if(h==0) return true;
if(h+step>tol) return false;
for(k=0;k<8;k++){
nx=x+fx[k];
ny=y+fy[k];
if(nx<0 || ny<0 || nx>4 || ny>4) continue;
swap(p[nx][ny],p[x][y]);
if(cover(step+1)) // 查询此状态是否曾走过
if(dfs(nx,ny,step+1,tol)) return true;
swap(p[nx][ny],p[x][y]);
}
return false;
}
// 主函数 ===============
int main(){
int tt,t,si,sj,i,j;
bool res;
char mp[6][6];
deal();
scanf("%d",&t);
getchar();
for(tt=1;tt<=t;tt++){
for(i=0;i<5;i++){
gets(mp[i]);
memcpy(p[i],mp[i],5);
for(j=0;j<5;j++)
if(mp[i][j]==' ')
si=i,sj=j;
}
i=BFS1()+BFS2();
if(i<16)
for(i=0;i<16;i++){ // DIA*
for(j=0;j<5;j++)
memcpy(p[j],mp[j],5);
root=new Tree; // 创建字典树
init_(root);
cover(0);
res=dfs(si,sj,0,i);
clr(root);
if(res) break;
}
printf("Case %d: ",tt);
if(i<16) printf("%d\n",i);
else puts("Crazy horse");
}
return 0;
}
/*
1
00111
01111
11111
00 00
00000
*/
这篇关于SWUN 1425 - 疯狂的马儿的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
