洛谷 P1242 新汉诺塔
原題鏈接
題目描述
設(shè)有n個(gè)大小不等的中空?qǐng)A盤，按從小到大的順序從1到n編號(hào)。將這n個(gè)圓盤任意的迭套在三根立柱上，立柱的編號(hào)分別為A、B、C，這個(gè)狀態(tài)稱為初始狀態(tài)。
現(xiàn)在要求找到一種步數(shù)最少的移動(dòng)方案，使得從初始狀態(tài)轉(zhuǎn)變?yōu)槟繕?biāo)狀態(tài)。
移動(dòng)時(shí)有如下要求：
·一次只能移一個(gè)盤；
·不允許把大盤移到小盤上面。
輸入輸出格式
輸入格式：
?
文件第一行是狀態(tài)中圓盤總數(shù)；
第二到第四行分別是初始狀態(tài)中A、B、C柱上圓盤的個(gè)數(shù)和從上到下每個(gè)圓盤的編號(hào)；
第五到第七行分別是目標(biāo)狀態(tài)中A、B、C柱上圓盤的個(gè)數(shù)和從上到下每個(gè)圓盤的編號(hào)。
?
輸出格式：
?
每行一步移動(dòng)方案，格式為：move I from P to Q
最后一行輸出最少的步數(shù)。
?
輸入輸出樣例
輸入樣例#1：?5 3 3 2 1 2 5 4 0 1 2 3 5 4 3 1 1 輸出樣例#1：?
move 1 from A to B move 2 from A to C move 1 from B to C move 3 from A to B move 1 from C to B move 2 from C to A move 1 from B to C 7
說明
圓盤總數(shù)≤45
每行的圓盤描述是從下到上的圓盤編號(hào)
?
題解
這道題目是經(jīng)典的漢諾塔問題，沒什么技術(shù)，但思維難度較高，如果條件判斷太多則編碼難度也會(huì)較高
?
首先，我們很容易想到一種假算法：（一定要注意它是錯(cuò)的，但對(duì)真算法有啟發(fā)意義）
因?yàn)榇蟊P子無法在小盤子上移動(dòng)，而大盤子移動(dòng)好之后又不會(huì)影響小盤子（這是本題所有操作的前提），故可以從大盤子開始移動(dòng)。
我們從第N號(hào)盤子開始操作，計(jì)當(dāng)前盤子為i號(hào)，如果它在原位置，那么就跳過，否則就將1~i-1號(hào)盤子都移動(dòng)到不會(huì)動(dòng)用的盤子，將目標(biāo)盤子空出，然后將i號(hào)盤子放進(jìn)去。經(jīng)過N次操作，一定可以完成，但不能保證最優(yōu)。
如圖所示，如果我們要將第1號(hào)樁上的1個(gè)大盤子移到2號(hào)樁，那么我們就先將1、2號(hào)樁上所有比i號(hào)盤子小的盤子都移到第3號(hào)樁
?
實(shí)現(xiàn)這一過程很簡(jiǎn)單，只要每次將1~i-1號(hào)盤子移動(dòng)到閑置的位置，然后移動(dòng)即可，代碼也十分簡(jiǎn)單
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int INF=1e9+7,MAXN=50; 5 int N,cur[MAXN],goal[MAXN],ans; 6 char tran[]={' ','A','B','C'};/*translate*/ 7 inline void input(int *array,int opt){ 8 int ii,jj; 9 scanf("%d",&ii); 10 while(ii--){ 11 scanf("%d",&jj); 12 array[jj]=opt; 13 } 14 } 15 void dfs(int from/*from idx*/,int to/*to pos*/){/*move the "from"-th plate to position "to"*/ 16 if(cur[from]==to) 17 return; 18 int other=6-cur[from]-to; 19 for(int i=from-1;i>=1;i--) 20 dfs(i,other); 21 printf("move %d from %c to %c\n",from,tran[cur[from]],tran[to]); 22 cur[from]=to; 23 ans++; 24 } 25 int main(){ 26 scanf("%d",&N); 27 input(cur,1); 28 input(cur,2); 29 input(cur,3); 30 input(goal,1); 31 input(goal,2); 32 input(goal,3); 33 34 for(int i=N;i>=1;i--) 35 dfs(i,goal[i]); 36 printf("%d",ans); 37 return 0; 38 } View Code?
但正如上面所說的，這是一個(gè)假算法。我們認(rèn)定如圖的變換方法是正確的，是建立在漢諾塔的性質(zhì)的基礎(chǔ)上的。在漢諾塔中，未歸位的盤子都是連續(xù)疊加的（如下圖1），不可能出現(xiàn)如圖2的情況
這樣的話，無論將這個(gè)連續(xù)的塔從哪里移動(dòng)到哪里都是等價(jià)的，故開始給出的假算法是成立的。
然而可惜的是，我們的塔最初是隨機(jī)擺放的，所以會(huì)有另一種方法
可以證明，沒有其他移動(dòng)方法了。但是否每次都要用兩種方法呢？顯然不是。觀察兩個(gè)圖組可以發(fā)現(xiàn)，在進(jìn)行了一次操作后，就還原到了漢諾塔的基本結(jié)構(gòu)：一串連續(xù)的盤子，就可以用常規(guī)的方法操作了。
那圖組2和圖組1的過程又怎么實(shí)現(xiàn)呢？我們需要三種操作
move函數(shù)的實(shí)現(xiàn)很簡(jiǎn)單，遞歸將1~idx-1號(hào)盤子移到閑置的位置，將idx號(hào)盤子移到to，再將1~idx-1號(hào)盤子移到to即可
void mov(int idx,int from,int to,int other){ /*move 1~"idx"-th to "to" in a heap*/if(!idx)return;mov(idx-1,from,other,to);ans[st][++sz[st]]=(state){idx,from,to};mov(idx-1,other,to,from); }?
merge函數(shù)也不難，將遞歸將1~idx-1號(hào)盤子移到閑置的位置（用merge），將idx號(hào)盤子移到to，再將1~idx-1號(hào)盤子移到to即可（用move）
void merg(int idx,int to){ /*move 1~"idx"-th to "to" not in a heap*/if(!idx)return;if(cur[idx]==to)return merg(idx-1,to);int other=6-cur[idx]-to;merg(idx-1,other);ans[st][++sz[st]]=(state){idx,cur[idx],to};mov(idx-1,other,to,cur[idx]); }?
solve函數(shù)的思想同上
void solve(int idx,int to){ /*put 1-"idx"-th into its place*/if(!idx)return;if(goal[idx]==to)return solve(idx-1,to);int other=6-goal[idx]-to;mov(idx-1,to,other,goal[idx]);ans[st][++sz[st]]=(state){idx,to,goal[idx]};solve(idx-1,other); }?
有了這些操作，解題就很簡(jiǎn)單了，我們按照上面講的兩種情況分類，輸出步數(shù)較少的方案即可
void work(int idx){if(!idx)return;if(cur[idx]==goal[idx])return work(idx-1);int other=6-cur[idx]-goal[idx];/*0:all to other, N to to*/st=0;merg(idx-1,other);ans[st][++sz[st]]=(state){idx,cur[idx],goal[idx]};solve(idx-1,other);/*1:all to to, N to other, all to from, N to to*/st=1;merg(idx-1,goal[idx]);ans[st][++sz[st]]=(state){idx,cur[idx],other};mov(idx-1,goal[idx],cur[idx],other);ans[st][++sz[st]]=(state) {idx,other,goal[idx]};solve(idx-1,cur[idx]); }?
最終給出AC代碼
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int INF=1e9+7,MAXN=50,MAXP=1e5; 5 int N,cur[MAXN],goal[MAXN],cnt; 6 char tran[]={'E','A','B','C'};/*translate*/ 7 inline void input(int *array,int opt){ 8 int ii,jj; 9 scanf("%d",&ii); 10 while(ii--){ 11 scanf("%d",&jj); 12 array[jj]=opt; 13 } 14 } 15 struct state{ int idx,from,to; }ans[2][MAXP]; 16 int st,sz[2]; 17 void mov(int idx,int from,int to,int other){ 18 /*move 1~"idx"-th to "to" 19 in a heap*/ 20 if(!idx) 21 return; 22 mov(idx-1,from,other,to); 23 ans[st][++sz[st]]=(state){idx,from,to}; 24 mov(idx-1,other,to,from); 25 } 26 void merg(int idx,int to){ 27 /*move 1~"idx"-th to "to" 28 not in a heap*/ 29 if(!idx) 30 return; 31 if(cur[idx]==to) 32 return merg(idx-1,to); 33 int other=6-cur[idx]-to; 34 merg(idx-1,other); 35 ans[st][++sz[st]]=(state){idx,cur[idx],to}; 36 mov(idx-1,other,to,cur[idx]); 37 } 38 void solve(int idx,int to){ 39 /*put 1-"idx"-th into its place*/ 40 if(!idx) 41 return; 42 if(goal[idx]==to) 43 return solve(idx-1,to); 44 int other=6-goal[idx]-to; 45 mov(idx-1,to,other,goal[idx]); 46 ans[st][++sz[st]]=(state){idx,to,goal[idx]}; 47 solve(idx-1,other); 48 } 49 void work(int idx){ 50 if(!idx) 51 return; 52 if(cur[idx]==goal[idx]) 53 return work(idx-1); 54 int other=6-cur[idx]-goal[idx]; 55 /*0:all to other, N to to*/ 56 st=0; 57 merg(idx-1,other); 58 ans[st][++sz[st]]=(state){idx,cur[idx],goal[idx]}; 59 solve(idx-1,other); 60 /*1:all to to, N to other, all to from, N to to*/ 61 st=1; 62 merg(idx-1,goal[idx]); 63 ans[st][++sz[st]]=(state){idx,cur[idx],other}; 64 mov(idx-1,goal[idx],cur[idx],other); 65 ans[st][++sz[st]]=(state) {idx,other,goal[idx]}; 66 solve(idx-1,cur[idx]); 67 } 68 int main(){ 69 scanf("%d",&N); 70 input(cur,1); 71 input(cur,2); 72 input(cur,3); 73 input(goal,1); 74 input(goal,2); 75 input(goal,3); 76 77 work(N); 78 79 for(int i=1,ed=min(sz[0],sz[1]),j=sz[0]>sz[1];i<=ed;i++) 80 printf("move %d from %c to %c\n",ans[j][i].idx,tran[ans[j][i].from],tran[ans[j][i].to]); 81 printf("%d",min(sz[0],sz[1])); 82 return 0; 83 } View Code轉(zhuǎn)載于:https://www.cnblogs.com/guoshaoyang/p/11114054.html
總結(jié)
以上是生活随笔為你收集整理的洛谷 P1242 新汉诺塔的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： uniGUI试用笔记（一）
- 下一篇： 修改input标签输入样式