【HDU 1997】汉诺塔VII

汉诺塔VII(题目链接)

思路

本文参考了下列文章

• 汉诺塔的回顾和深刻 汉诺塔VII

• 首先用数组将每一个样例的状态存储

  • 数组的每一行存储一个柱子的状态
  • 每一行的第0列存储柱子上盘子的数目
  • 其后从下到上存储柱子对应位置上的盘子的编号

• 使用函数根据在移动盘子的过程中的规律判断

  • 当盘子的数目为奇数时，在移动过程中，第奇数个柱子的最低位置上的盘子编号为奇数
  • 当盘子的数目为偶数时，则相反
  • 并且每一个柱子上的盘子的编号必定交替出现

代码

#include <iostream>
using namespace std;

//存储输入的状态，tab[i][0]表示第i个柱子上的盘子数目，后面依次为盘子的编号 
int tab[3][65];

//判断tab中的状态是不是移动n个盘子时的中间状态 
int f(int n){                                       //输入为盘子的数目 
    for(int i = 0; i < 3; ++i){                     //分别判断三个柱子 
        if(0 == tab[i][0]){                         //若该柱子没有盘子 
            continue;                               //直接判断下一个柱子 
        }
        //奇数个盘子时在第奇数个柱子的最下面的盘子的编号为奇数，偶数相反 
        if((n+i) % 2 != tab[i][1] % 2){             //若不相同 
            return 0;                               //直接返回false 
        }
        //每个柱子上的盘子编号应该是奇偶数交替 
        for(int j = 2; j <= tab[i][0]; ++j){        //循环柱子上的每一个盘子 
            if((tab[i][j-1]+tab[i][j]) % 2 == 0){   //若编号不是交替 
                return 0;                           //直接返回false 
            }
        }       
    }
    return 1;                                       //条件满足，返回true 
}

int main(){
    int t, n;                                       //定义变量 
    cin >> t;                                       //输入样例数 
    while(t--){                                     //循环t次 
        cin >> n;                                   //输入盘子数目
        //输入柱子上的盘子状态                 
        for(int i = 0; i < 3; ++i){                 //循环 
            cin >> tab[i][0];                       //输入柱子上盘子数目 
            for(int j = 1; j <= tab[i][0]; ++j){    //循环 
                cin >> tab[i][j];                   //输入柱子上的盘子编号
            }
        }
        if(f(n)){                                   //若返回为 1 
            cout << "true" << endl;                 //输出true 
        }else{                                      //否则 
            cout << "false" << endl;                //输出false 
        }
    }
    
    
    return 0;
} 

总结

当看到题目时，基本的模拟做出来了之后，应该仔细思考看看有没有什么规律