farmer.cpp

农夫过河问题源代码2

//算法设计
//1、农夫先带兔子过河，然后空手回来
//2、带狐狸过河，但把兔子带回来
//3、把兔子留下，带蔬菜过河，空手回来
//4、带兔子过河
#include <iostream>
using namespace std;

const int VEGET     = 1;
const int RABBIT    = VEGET << 1;
const int FOX       = RABBIT << 1;
const int FARMER    = FOX << 1;

bool used[20];      // 状态是否到达过的标志
int bfs[1000];      // 广度优先搜索时存放状态
int pre[1000];      // 父结点

inline int SetBit( int x, int pos )
{
    return x | pos;
}

inline int DelBit( int x, int pos )
{
    return x & ~pos;
}

// 检查状态x是否合法
inline bool IsLegal( int x )
{
    if ( x & FARMER )       // 如果农夫在的话
    {
        // 菜和兔子都不在，或是兔子和狐狸都不在是不可以的
        if ( ((x&(VEGET|RABBIT))==0) || ((x&(RABBIT|FOX))==0) )
        {
            return false;
        }
    } else                  // 如果农夫不在的话
    {
        // 菜和兔子都在，或是兔子和狐狸都在是不可以的
        if ( ((x&(VEGET|RABBIT))==(VEGET|RABBIT)) || ((x&(RABBIT|FOX))==(RABBIT|FOX)) )
        {
            return false;
        }
    }

    // 否则，是合法的状态
    return true;
}

// 广度优先搜索
int BFSSearch()
{
    int i;
    int x;
    int iLeft       = -1;
    int iRight      =  1;
    bfs[0]          = FARMER|FOX|RABBIT|VEGET;
    used[ bfs[0] ]  = true;
    
    while( ++iLeft<iRight )             // 只要状态没有结束
    {
        if ( bfs[iLeft] & FARMER )      // 这里有农夫
        {
            x = DelBit(bfs[iLeft],FARMER);
            if ( !used[x] && IsLegal(x) )       // 农夫什么都不带过去
            {
                pre[iRight] = iLeft;
                bfs[iRight] = x;
                used[x] = true;
                iRight++;
            }

            for ( i=0; i<3; i++ )                   // 带一样东西过去
            {
                if ( (bfs[iLeft]&(1<<i)) == 0 )     // 如果要带过去的不在这边
                {
                    continue;
                }

                x = DelBit(bfs[iLeft],FARMER|(1<<i) );
                if ( !used[x] && IsLegal(x) )       // 状态不存在且可行
                {
                    pre[iRight] = iLeft;
                    bfs[iRight] = x;
                    used[x] = true;

                    if( x == 0 )                    // 如果找到目标，返回
                    {
                        return iRight;
                    }

                    iRight++;
                }
            }
        } else
        {
            x = SetBit(bfs[iLeft],FARMER);
            if ( !used[x] && IsLegal(x) )       // 农夫什么都不带回来
            {
                pre[iRight] = iLeft;
                bfs[iRight] = x;
                used[x] = true;
                iRight++;
            }
            
            for ( i=0; i<3; i++ )               // 带一样东西回来
            {
                if ( bfs[iLeft]&(1<<i) )        // 如果要带回来的已经在这边
                {
                    continue;
                }

                x = SetBit(bfs[iLeft],FARMER|(1<<i) );
                if ( !used[x] && IsLegal(x) )   // 状态不存在且可行
                {
                    pre[iRight] = iLeft;
                    bfs[iRight] = x;
                    used[x] = true;
                    if( x == 0 )
                    {
                        return iRight;
                    }
                    iRight++;
                }
            }
        }
    }

    return -1;
}

// 递归输出结果
void OutputSolution( int iRet )
{
    if ( pre[iRet] != -1 ) 
    {
        OutputSolution( pre[iRet] );
    }

    cout << " --> ";
    if ( bfs[iRet]&FARMER )  
    {
        cout << "Farmer ";
    } else
    {
        cout << "       ";
    }

    if ( bfs[iRet]&FOX )
    {
        cout << "Fox  ";
    } else
    {
        cout << "     ";
    }

    if ( bfs[iRet]&RABBIT )
    {
        cout << "Rabbit ";
    } else
    {
        cout << "       ";
    }

    if ( bfs[iRet]&VEGET )
    {
        cout << "Vegetable ";
    } else
    {
        cout << "          ";
    }

    cout << endl;
}

int main(int argc, char* argv[])
{
    memset( used, 0, sizeof(used) );
    memset( pre, 0xff, sizeof(pre) );

    int iRet = BFSSearch();
    if ( iRet == -1 )
    {
        cout << "No solution!" << endl;
    } else
    {
        OutputSolution( iRet );
    }
    return 0;
}

//输出结果解释：
//1、准备过河
//2、农夫、兔子过河
//3、兔子留下，农夫回来，剩下农夫、狐狸、蔬菜
//4、农夫、蔬菜过河，剩下狐狸
//5、农夫带兔子回来
//6、农夫带狐狸过河，剩下兔子
//7、农夫回来
//8、农夫带兔子过河