首页 > 代码库 > bzoj1085题解
bzoj1085题解
【解题思路】
A*(上下界剪枝)。
答案上界：15。
答案下界：当前步数+当前状态剩余步数估价。
这里我们简单地设计估价函数为当前状态与目标状态不相同的棋子数-1，与0的较大值。这样保证了0≤估价≤正确步数。
复杂度o(25*C(24,12))。
【参考程序】
1 #include <bits/stdc++.h> 2 #define range(i,c,o) for(register int i=(c);i<(o);++i) 3 #define dange(i,c,o) for(register int i=(c);i>(o);--i) 4 using namespace std; 5 6 //#define __debug 7 #ifdef __debug 8 #define Function(type) type 9 #define Procedure void10 #else11 #define Function(type) __attribute__((optimize("-O2"))) inline type12 #define Procedure __attribute__((optimize("-O2"))) inline void13 #endif14 15 static const int INF=0x7f7f7f7f;16 static const int dx[8]={-2,-2,-1,-1, 1, 1, 2, 2};17 static const int dy[8]={-1, 1,-2, 2,-2, 2,-1, 1};18 static const char ED[5][5]=19 {20 {‘1‘,‘1‘,‘1‘,‘1‘,‘1‘},21 {‘0‘,‘1‘,‘1‘,‘1‘,‘1‘},22 {‘0‘,‘0‘,‘*‘,‘1‘,‘1‘},23 {‘0‘,‘0‘,‘0‘,‘0‘,‘1‘},24 {‘0‘,‘0‘,‘0‘,‘0‘,‘0‘},25 };26 27 static const int lim=15;28 static int ans; char cur[5][5];29 Function(int) eval()30 {31 int ret=0;32 range(i,0,5) range(j,0,5)33 {34 ret+=cur[i][j]!=ED[i][j];35 }36 return ret-1;37 }38 Procedure find(int&x,int&y)39 {40 range(i,0,5) range(j,0,5)41 {42 if(cur[i][j]==‘*‘) {x=i,y=j; return;}43 }44 }45 void DFS(const int&steps)46 {47 if(steps>lim) return;48 int x,y,E=eval();49 if(!~E) return void(ans=min(ans,steps));50 if(steps+E>min(ans-1,lim)) return;51 find(x,y);52 range(i,0,8)53 {54 int tx=x+dx[i],ty=y+dy[i];55 if(tx>=0&&ty>=0&&tx<5&&ty<5)56 {57 swap(cur[x][y],cur[tx][ty]);58 DFS(steps+1);59 swap(cur[x][y],cur[tx][ty]);60 }61 }62 }63 64 static int T;65 int main()66 {67 for(scanf("%d",&T);T--;)68 {69 range(i,0,5) range(j,0,5)70 {71 while(isspace(cur[i][j]=getchar()));72 }73 ans=INF,DFS(0);74 printf("%d\n",ans<INF?ans:-1);75 }76 return 0;77 }
bzoj1085题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。