本文主要是介绍UVA - 10795 A Different Task，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给定一个初始状态和目标状，求从初始状态到目标状态最少要多少步，规则跟汗诺塔是一样的
思路：看了大白的是：先找到需要移动的最大的K，比它大的显然是不需要移动的可以不用考虑，那么可以考虑在将第K个盘子移动的前一步的状态一定是：K在第一根柱子，比大小的依次排在第3根柱子，将这个状态定位参考状态，那么初始状态到这个参考状态加上目标状态到参考状态的步数再+1就是答案了，那么在移动的过程中，如果当前需要移动的N在目标状态那么就不需要移动，就是等于前N-1的步数，否则就是要把前N-1个先移动到另一根暂放，而这个过程满足经典的汉诺塔问题,步数就是2^(N-1)-1,还要再加上移动第N个的1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 70;int n,start[MAXN],finish[MAXN];long long f(int *p,int i,int final){if (i == 0) return 0;if (p[i] == final)return f(p,i-1,final);return f(p,i-1,6-p[i]-final) + (1LL<<(i-1));
}int main(){int cas = 0;while (scanf("%d",&n) != EOF){for (int i = 1; i <= n; i++)scanf("%d",&start[i]);for (int i = 1; i <= n; i++)scanf("%d",&finish[i]);int k = n;while (k >= 1 && start[k] == finish[k]) k--;long long ans = 0;if (k >= 1){int other = 6 - start[k] - finish[k];ans = f(start,k-1,other) + f(finish,k-1,other) + 1;}printf("Case %d: %lld\n",++cas,ans);}return 0;
}这篇关于UVA - 10795 A Different Task的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
