hedgezzz的部落格

#include <iostream>
#include <string>

#define N 2
#define M 2*N+1

void print(char s[M])
{
    for(int idx=0;idx<M;idx++){
        printf("(%c)",s[idx]) ;
    } //for
    printf("\n") ;
}

bool Solved( char s[M] )
{
    for(int idx=0;idx<M;idx++){
        if( idx < N ){
            if( s[idx] != 'B' )
                return false ;
        }else if( idx == N ){
            if( s[idx] != ' ' )
                return false ;
        }else{
            if( s[idx] != 'A' )
                return false ;
        }  
    } //for
    return true ;
}

void  FindSpace( char s[M],int& col )
{
    for(int idx=0;idx<M;idx++){
        if( s[idx] == ' '){
            col = idx ;
            break ;
        }
    }
}
bool solve( char s[M] )
{
    if( Solved( s ) )
        return true ;
    int col ;
    FindSpace(s,col)  ;
    for(int idx=0;idx<2;idx++){
        if( idx == 0 ){ //move 'A'
            if( col == 0 )
                continue ;
            if( s[col-1] == 'A' ){
                printf("before move A...") ;
                print(s) ;
                s[col-1] = ' ' ;
                s[col] = 'A' ;
                printf(" after move A...") ;
                print(s) ;
                if( solve(s) )
                    return true ;
                s[col-1] = 'A' ;
                s[col] = ' ' ;     
                printf("backwd move A...") ;
                print(s) ;
            }else if( s[col-1] == 'B' ){
                if( col < 2 )
                    continue ;
                if( s[col-2] == 'A' ){
                    printf("before move A...") ;
                    print(s) ;
                    s[col-2] = ' ' ;
                    s[col] = 'A' ;
                    printf(" after move A...") ;
                    print(s) ;
                    if( solve(s) )
                        return true ;
                    s[col-2] = 'A' ;
                    s[col] = ' ' ;
                    printf("backwd move A...") ;
                    print(s) ;
                }
            }
        }else{ // move 'B'
            if( col == M-1 )
                continue ;
            if( s[col+1] == 'B' ){
                printf("before move B...") ;
                print(s) ;
                s[col+1] = ' ' ;
                s[col] = 'B' ;
                printf(" after move B...") ;
                print(s) ;
                if( solve(s) )
                    return true ;
                s[col+1] = 'B' ;
                s[col] = ' ' ;
                printf("backwd move B...") ;
                print(s) ;
            }else if( s[col+1] == 'A' ){
                if( col+2 >= M  )
                    continue ;
                if( s[col+2] == 'B' ){
                    printf("before move B...") ;
                    print(s) ;
                    s[col+2] = ' ' ;
                    s[col] = 'B' ;
                    printf(" after move B...") ;
                    print(s) ;
                    if( solve(s) )
                        return true ;
                    s[col+2] = 'B' ;
                    s[col] = ' ' ;   
                    printf("backwd move B...") ;
                    print(s) ;
                }
            }
        }
    } //for
    return false ;
}

int main()
{
    char s[M] ;
    for(int idx=0;idx<M;idx++){
        if( idx < N )
            s[idx]='A' ;
        else if( idx == N )
            s[idx]= ' ' ;
        else
            s[idx]= 'B' ;
    } //for
    solve(s) ;
    print(s) ;
    printf("\n Done \n") ;
}

[informix@localhost test]$ ./puzzle2.exe
before move A...(A)(A)( )(B)(B)
 after move A...(A)( )(A)(B)(B)
before move A...(A)( )(A)(B)(B)
 after move A...( )(A)(A)(B)(B)
backwd move A...(A)( )(A)(B)(B)
before move B...(A)( )(A)(B)(B)
 after move B...(A)(B)(A)( )(B)
before move A...(A)(B)(A)( )(B)
 after move A...(A)(B)( )(A)(B)
before move A...(A)(B)( )(A)(B)
 after move A...( )(B)(A)(A)(B)
before move B...( )(B)(A)(A)(B)
 after move B...(B)( )(A)(A)(B)
backwd move B...( )(B)(A)(A)(B)
backwd move A...(A)(B)( )(A)(B)
before move B...(A)(B)( )(A)(B)
 after move B...(A)(B)(B)(A)( )
before move A...(A)(B)(B)(A)( )
 after move A...(A)(B)(B)( )(A)
backwd move A...(A)(B)(B)(A)( )
backwd move B...(A)(B)( )(A)(B)
backwd move A...(A)(B)(A)( )(B)
before move B...(A)(B)(A)( )(B)
 after move B...(A)(B)(A)(B)( )
before move A...(A)(B)(A)(B)( )
 after move A...(A)(B)( )(B)(A)
before move A...(A)(B)( )(B)(A)
 after move A...( )(B)(A)(B)(A)
before move B...( )(B)(A)(B)(A)
 after move B...(B)( )(A)(B)(A)
before move B...(B)( )(A)(B)(A)
 after move B...(B)(B)(A)( )(A)
before move A...(B)(B)(A)( )(A)
 after move A...(B)(B)( )(A)(A)
(B)(B)( )(A)(A)