首页 > ACM题库 > HDU-杭电 > HDU 4260-The End of The World-动态规划-[解题报告]HOJ
2015
05-23

HDU 4260-The End of The World-动态规划-[解题报告]HOJ

The End of The World

问题描述 :

Legend says that there is a group of monks who are solving a large Towers of Hanoi puzzle. The Towers of Hanoi is a well-known puzzle, consisting of three pegs, with a stack of disks, each a different size. At the start, all of the disks are stacked on one of the pegs, and ordered from largest (on the bottom) to smallest (on the top). The object is to move this stack of disks to another peg, subject to two rules: 1) you can only move one disk at a time, and 2) you cannot move a disk onto a peg if that peg already has a smaller disk on it.
The monks believe that when they finish, the world will end. Suppose you know how far they’ve gotten. Assuming that the monks are pursuing the most efficient solution, how much time does the world have left?

输入:

There will be several test cases in the input. Each test case will consist of a string of length 1 to 63, on a single line. This string will contain only (capital) As, Bs and Cs. The length of the string indicates the number of disks, and each character indicates the position of one disk. The first character tells the position of the smallest disk, the second character tells the position of the second smallest disk, and so on, until the last character, which tells the position of the largest disk. The character will be A, B or C, indicating which peg the disk is currently on. You may assume that the monks’ overall goal is to move the disks from peg A to peg B, and that the input represents a legitimate position in the optimal solution. The input will end with a line with a single capital X.

输出:

There will be several test cases in the input. Each test case will consist of a string of length 1 to 63, on a single line. This string will contain only (capital) As, Bs and Cs. The length of the string indicates the number of disks, and each character indicates the position of one disk. The first character tells the position of the smallest disk, the second character tells the position of the second smallest disk, and so on, until the last character, which tells the position of the largest disk. The character will be A, B or C, indicating which peg the disk is currently on. You may assume that the monks’ overall goal is to move the disks from peg A to peg B, and that the input represents a legitimate position in the optimal solution. The input will end with a line with a single capital X.

样例输入:

AAA
BBB
X

样例输出:

7
0

题目大意:

hanoi塔问题的变形,给你3根柱子A,B,C。以及每根柱子上的盘子数(保证是最优状态)。现在把所有盘子移动到B柱上,还最少需要多少步。输入格式:一个字符串s,长度代表盘子数,第i个字母代表第i个大的盘子在哪个盘子上。字符串仅由A,B,C组成。

题解:

考察递归的好题,相当不错.

按照hanoi最优移动规则,假设我现在要把n号盘子移动到B柱子上,那么我先要把前n-1个盘子先移动到辅助柱子上(这步用递归解决),然后n号盘子移动到目标柱子上(步数+1),再把n-1个盘子移动到目标柱子上(2^(n-1)-1)。

#include<iostream>
#include<string>
using namespace std;
string s;
long long cal(long long x,char goal)
{
    for(long long i=x;i>=0;i--)
    if(s[i]!=goal) return cal(i-1,'A'^'B'^'C'^goal^s[i])+(1LL<<i);
    return 0;
}
int main()
{
    while(cin>>s,s!="X")
    {
        long long ans=cal(s.length()-1,'B');
        cout<<ans<<endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/hyogahyoga/article/details/7908627