漢諾塔VII(題目鏈接)
思路
本文參考了下列文章
-
首先用數(shù)組將每一個樣例的狀態(tài)存儲
- 數(shù)組的每一行存儲一個柱子的狀態(tài)
- 每一行的第0列存儲柱子上盤子的數(shù)目
- 其后從下到上存儲柱子對應(yīng)位置上的盤子的編號
-
使用函數(shù)根據(jù)在移動盤子的過程中的規(guī)律判斷
- 當(dāng)盤子的數(shù)目為奇數(shù)時剩膘，在移動過程中烫罩，第奇數(shù)個柱子的最低位置上的盤子編號為奇數(shù)
- 當(dāng)盤子的數(shù)目為偶數(shù)時膏执，則相反
- 并且每一個柱子上的盤子的編號必定交替出現(xiàn)
代碼
#include <iostream>
using namespace std;
//存儲輸入的狀態(tài)帜平，tab[i][0]表示第i個柱子上的盤子數(shù)目稿蹲，后面依次為盤子的編號
int tab[3][65];
//判斷tab中的狀態(tài)是不是移動n個盤子時的中間狀態(tài)
int f(int n){ //輸入為盤子的數(shù)目
for(int i = 0; i < 3; ++i){ //分別判斷三個柱子
if(0 == tab[i][0]){ //若該柱子沒有盤子
continue; //直接判斷下一個柱子
}
//奇數(shù)個盤子時在第奇數(shù)個柱子的最下面的盤子的編號為奇數(shù)，偶數(shù)相反
if((n+i) % 2 != tab[i][1] % 2){ //若不相同
return 0; //直接返回false
}
//每個柱子上的盤子編號應(yīng)該是奇偶數(shù)交替
for(int j = 2; j <= tab[i][0]; ++j){ //循環(huán)柱子上的每一個盤子
if((tab[i][j-1]+tab[i][j]) % 2 == 0){ //若編號不是交替
return 0; //直接返回false
}
}
}
return 1; //條件滿足懦趋，返回true
}
int main(){
int t, n; //定義變量
cin >> t; //輸入樣例數(shù)
while(t--){ //循環(huán)t次
cin >> n; //輸入盤子數(shù)目
//輸入柱子上的盤子狀態(tài)
for(int i = 0; i < 3; ++i){ //循環(huán)
cin >> tab[i][0]; //輸入柱子上盤子數(shù)目
for(int j = 1; j <= tab[i][0]; ++j){ //循環(huán)
cin >> tab[i][j]; //輸入柱子上的盤子編號
}
}
if(f(n)){ //若返回為 1
cout << "true" << endl; //輸出true
}else{ //否則
cout << "false" << endl; //輸出false
}
}
return 0;
}
總結(jié)
當(dāng)看到題目時函匕，基本的模擬做出來了之后，應(yīng)該仔細思考看看有沒有什么規(guī)律
