本文共 1519 字，大约阅读时间需要 5 分钟。
思路：裸的IDA*，估计当前状态至少需要多少距离才能达到目标状态，剪枝即可。每一墩牌只需记录其最上面和最下面的牌型即可完成移动。
AC代码
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10#define inf 0x3f3f3f3f#define PI pair typedef long long LL;const int maxn = 10 + 2;struct node{ int top, bot;}sta[maxn]; //只需记录其最下面和最下面的牌就行 int get_h(node *a) { int cnt = 0, fir; for(int i = 0; i < 10; ++i) { if(a[i].bot) { fir = i; break; } } for(int i = fir+1; i < 10; ++i){ if(a[i].bot) { cnt += i - fir; fir = i; } } return cnt;}int maxd, nextd; bool dfs(int dis) { int h = get_h(sta); if(h + dis > maxd) { nextd = min(nextd, h+dis); return false; } if(h == 0) return true; node old[maxn]; memcpy(old, sta, sizeof(sta)); for(int i = 0; i < 10; ++i) { if(sta[i].bot && sta[i].bot < 10) { int bot = sta[i].bot; for(int j = 0; j <= maxd-dis+i; ++j) { if(sta[j].top == bot + 1) { //将i移到j sta[j].top = sta[i].top; sta[i].bot = sta[i].top = 0; //清空 if(dfs(dis+abs(i-j))) return true; break; } } } memcpy(sta, old, sizeof(old)); } return false;}int main() { int T; scanf("%d", &T); while(T--) { for(int i = 0; i < 10; ++i) { scanf("%d", &sta[i].top); sta[i].bot = sta[i].top; } for(maxd = 9; ;maxd = nextd) { nextd = maxd+1; if(dfs(0)) { printf("%d\n", maxd); break; } } } return 0;}
转载于:https://www.cnblogs.com/flyawayl/p/8305357.html