|
說 明 |
應用問題區首頁 |
兩群青蛙, 左右各三隻, 中間有一個空格分開, 假設青蛙僅能往前移動
或往前跳過另一隻青蛙, 請找出步驟使得最後左邊的青蛙全部移到右邊,
右側的青蛙全部移到左側
L L L _ R R R ---> R R R _ L L L
| |
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std ;
enum Status { Void , Left , Right };
class Flopping_Frog {
private :
int frog_no ; // 單一群青蛙個數
int void_pos ; // 無青蛙的位置
vector<Status> loc ; // 各位置的狀態
vector< vector<Status> > sol ; // 各步驟的狀態
// 最左邊的可移動青蛙下標
int left_index() const {
return void_pos > 1 ? void_pos - 2 : 0 ;
}
// 最右邊的可移動青蛙下標
int right_index() const {
return void_pos < loc.size()-2 ? void_pos + 2 : loc.size()-1 ;
}
// 是否結束
bool finish() const {
for ( int i = 0 ; i < loc.size() ; ++i ) {
if ( i < frog_no && loc[i] != Right ) return false ;
if ( i > frog_no && loc[i] != Left ) return false ;
}
return true ;
}
// 對調位置狀態
void swap( Status& a , Status& b ) const {
Status c = a ;
a = b ; b = c ;
}
public :
// n 為每一群青蛙的個數
Flopping_Frog( int n = 3 ) : frog_no(n) , void_pos(n) {
loc.resize(2*frog_no+1,Void) ;
for ( int i = 0 ; i < loc.size() ; ++i ) {
if ( i < frog_no )
loc[i] = Left ;
else if ( i > frog_no )
loc[i] = Right ;
}
sol.push_back(loc) ;
}
// 尋找對調方式
void swap_position() {
if ( finish() ) {
int i , j ;
for ( i = 0 ; i < sol.size() ; ++i ) {
cout << setw(2) << i+1 << " : " ;
for ( j = 0 ; j < sol[i].size() ; ++j ) {
if ( sol[i][j] == Left )
cout << "L" ;
else if ( sol[i][j] == Right )
cout << "R" ;
else
cout << " " ;
cout << " " ;
}
cout << endl ;
}
cout << endl ;
} else {
int m = void_pos ;
int a = left_index() ;
int b = right_index() ;
for ( int i = a ; i <= b ; ++i ) {
if ( ( ( i < m ) && ( loc[i] == Left ) ) ||
( ( i > m ) && ( loc[i] == Right ) ) ) {
void_pos = i ;
swap(loc[i],loc[m]) ;
sol.push_back(loc) ;
swap_position() ;
void_pos = m ;
swap(loc[i],loc[m]) ;
sol.pop_back() ;
}
}
}
}
};
int main() {
int n = 3 ;
Flopping_Frog frogs(n) ;
frogs.swap_position() ;
return 0 ;
}
|
輸 出 |
|---|
1 : L L L R R R
2 : L L L R R R
3 : L L R L R R
4 : L L R L R R
5 : L L R R L R
6 : L R L R L R
7 : L R L R L R
8 : R L L R L R
9 : R L R L L R
10 : R L R L R L
11 : R L R L R L
12 : R L R R L L
13 : R R L R L L
14 : R R L R L L
15 : R R R L L L
16 : R R R L L L
1 : L L L R R R
2 : L L L R R R
3 : L L R L R R
4 : L L R L R R
5 : L R L L R R
6 : L R L R L R
7 : L R L R L R
8 : L R L R R L
9 : L R R L R L
10 : R L R L R L
11 : R L R L R L
12 : R R L L R L
13 : R R L R L L
14 : R R L R L L
15 : R R R L L L
16 : R R R L L L
| |
|