写到一半才发现能够用双向搜索4层来写,但已经不愿意改了,干脆暴搜+剪枝水过去算了。
想到一个非常水的剪枝,h函数为 当前点到终点4个点的最短距离加起来除以2。由于最多一步走2格,然后在HDU上T了,又发现再搜索过程中。这个估价函数应该是递减的(贪心),再加上这个剪枝就过了。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<list> #include<cmath> #include<vector> #include<algorithm> using namespace std; #define stop system("pause") struct node { int x,y; }a[4],b[4]; int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0}; bool no(int x,int y) { for(int i=0;i<4;i++) if(a[i].x==x&&a[i].y==y) return false; return true; } bool isok(int x,int y) { return x>=1&&x<=8&&y>=1&&y<=8; } bool ed[9][9]; int h() { int cnt=0; for(int i=0;i<4;i++) { int mi=10000; for(int j=0;j<4;j++) { mi=min(mi,abs(a[i].x-b[j].x)+abs(a[i].y-b[j].y)); } cnt+=mi; } return cnt; } bool dfs(int dis,int last) { int t=h(); if(t==0) return true; t/=2; if(dis+t>=8||t>last) return false; for(int i=0;i<4;i++) { for(int d=0;d<4;d++) { if(isok(a[i].x+dx[d],a[i].y+dy[d])) { if(no(a[i].x+dx[d],a[i].y+dy[d])) { a[i].x+=dx[d]; a[i].y+=dy[d]; if(dfs(dis+1,t)) {return true;} a[i].x-=dx[d]; a[i].y-=dy[d]; } else if(isok(a[i].x+2*dx[d],a[i].y+2*dy[d])&&no(a[i].x+2*dx[d],a[i].y+2*dy[d])) { a[i].x+=2*dx[d]; a[i].y+=2*dy[d]; if(dfs(dis+1,t)) {return true;} a[i].x-=2*dx[d]; a[i].y-=2*dy[d]; } } } } return false; } int main() { int x,y; while(~scanf("%d%d",&a[0].x,&a[0].y)) { memset(ed,0,sizeof(ed)); for(int i=1;i<4;i++) scanf("%d%d",&a[i].x,&a[i].y); for(int i=0;i<4;i++) scanf("%d%d",&b[i].x,&b[i].y),ed[b[i].x][b[i].y]=true; if(dfs(0,10000)) puts("YES"); else puts("NO"); } return 0; }
本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5092467.html,如需转载请自行联系原作者