人狼羊菜过河 -- Leo Jay[DateTime(2004-12-17T22:05:01Z)] TableOfContents

广度优先搜索 by Leo Jay

狂汗，完全乱了……

好像这里不支持C++的Highlight，而小弟的Python是刚刚才学的……

小弟我认为，这题至少有以下三种不同的解法：

• 广度优先搜索方法:
• 深度优先搜索
• 图论

这里显示有问题，等我搞明白怎么整wiki再说。这是我第一次wiki……

#include <iostream>
using namespace std;
 
const int VEGET     = 1;
const int SHEEP     = VEGET << 1;
const int WOLF      = SHEEP << 1;
const int FARMER    = WOLF  << 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|SHEEP))==0) || ((x&(SHEEP|WOLF))==0) )
        {
            return false;
        }
    } else                  // 如果农夫不在的话
    {
        // 菜和羊都在，或是羊和狼都在是不可以的
        if ( ((x&(VEGET|SHEEP))==(VEGET|SHEEP)) || ((x&(SHEEP|WOLF))==(SHEEP|WOLF)) )
        {
            return false;
        }
    }
 
    // 否则，是合法的状态
    return true;
}
 
// 广度优先搜索
int BFSSearch()
{
    int i;
    int x;
    int iLeft       = -1;
    int iRight      =  1;
    bfs[0]          = FARMER|WOLF|SHEEP|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]&WOLF )
    {
        cout << "Wolf ";
    } else
    {
        cout << "     ";
    }
 
    if ( bfs[iRet]&SHEEP )
    {
        cout << "Sheep ";
    } 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;
}