/* title
   青蛙跳
*/

/* comment *******************************************************

兩群青蛙, 左右各三隻, 中間有一個空格分開, 假設青蛙僅能往前移動
或往前跳過另一隻青蛙, 請找出步驟使得最後左邊的青蛙全部移到右邊, 
右側的青蛙全部移到左側

    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 ;
    
}



/***********************************************************************
  OUTPUT   OUTPUT   OUTPUT   OUTPUT   OUTPUT   OUTPUT   OUTPUT   OUTPUT
 ***********************************************************************

 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  

 ***********************************************************************/