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

广度优先搜索 by Leo Jay

狂汗，完全乱了……

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

• 改好格式了,很简单的,你看一下帮助就好了! -- Dreamingk

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

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

这里显示有问题，等我搞明白怎么整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;
}

深度优先搜索 by Leo Jay

这一题的第二种解法:) 这段时间没什么时间写文章，我想先把我知道的三种解法程序写出来， 再把文章写出来吧。(程序员嘛，写文章是最头大的……)

PS,谢谢Dreamingk兄及Zoom Quiet兄。小弟刚玩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     step[100];

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

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

// 检查状态x是否合法
/*
    注：由农夫，狼，羊，菜四者的真值表转成卡诺图后化简可得一逻辑函数式：
        所以IsLegal函数也可写为：
        bool IsLegal( bool bFarmer, bool bWolf, bool bSheep, bool bVeget )
        {
            return !( (!bFarmer&!bSheep) | bFarmer&(bSheep|bWolf&bVeget) | (!bWolf&bSheep&!bVeget) );
        }
        设当前状态为status，则调用方法是
        IsLegal( status&FARMER, status&WOLF, status&SHEEP, status&VEGET )
        注意，这个逻辑函数式形式简单，但可读性极差。
*/
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;
}

// 输出状态iStatus
void OutputStatus( int iStatus )
{
    if ( iStatus&FARMER )
    {
        cout << "Farmer ";
    } else
    {
        cout << "       ";
    }
    
    if ( iStatus&WOLF )
    {
        cout << "Wolf ";
    } else
    {
        cout << "     ";
    }
    
    if ( iStatus&SHEEP )
    {
        cout << "Sheep ";
    } else
    {
        cout << "      ";
    }
    
    if ( iStatus&VEGET )
    {
        cout << "Vegetable ";
    } else
    {
        cout << "          ";
    }
    cout << endl;
}

// 输出解
void OutputSolution( int iSteps )
{
    int i;
    for( i=0; i<=iSteps; i++ )
    {
        cout << "--> ";
        OutputStatus( step[i] );
    }
    cout << "-------------------------" << endl;
    cout << endl;
}

// 深度优先搜索
void DFSSearch( int iStatus, int iStep )
{
    int i;
    int iNewStatus;
    step[iStep] = iStatus;
    if( iStatus == 0 )                    // 如果找到目标，输出并返回
    {
        OutputSolution( iStep );
        return;
    }
    
    used[iStatus] = true;

    if ( iStatus & FARMER )     // 这里有农夫
    {
        iNewStatus = DelBit(iStatus,FARMER);
        if ( !used[iNewStatus] && IsLegal(iNewStatus) )       // 农夫什么都不带过去
        {
            // 如果可以的话，搜索下一步
            DFSSearch(iNewStatus, iStep+1);
        }

        for ( i=0; i<3; i++ )                   // 带一样东西过去
        {
            if ( (iStatus&(1<<i)) == 0 )     // 如果要带过去的不在这边
            {
                continue;
            }
            
            iNewStatus = DelBit(iStatus,FARMER|(1<<i) );
            if ( !used[iNewStatus] && IsLegal(iNewStatus) )       // 状态不存在且可行
            {
                // 如果可以的话，搜索下一步
                DFSSearch(iNewStatus, iStep+1);
            }
        }
    } else
    {
        iNewStatus = SetBit(iStatus,FARMER);
        if ( !used[iNewStatus] && IsLegal(iNewStatus) )       // 农夫什么都不带回来
        {
            // 如果可以的话，搜索下一步
            DFSSearch(iNewStatus, iStep+1);
        }
        
        for ( i=0; i<3; i++ )               // 带一样东西回来
        {
            if ( iStatus&(1<<i) )        // 如果要带回来的已经在这边
            {
                continue;
            }
            
            iNewStatus = SetBit(iStatus,FARMER|(1<<i) );
            if ( !used[iNewStatus] && IsLegal(iNewStatus) )   // 状态不存在且可行
            {
                // 如果可以的话，搜索下一步
                DFSSearch(iNewStatus, iStep+1);
            }
        }
    }
    
    used[iStatus] = false;
}

int main()
{
    memset( used, 0, sizeof(used) );
    
    DFSSearch( FARMER|WOLF|SHEEP|VEGET, 0 );
    return 0;
}

反馈

• 好！谢谢，分享！不过注释要有哪！特别是算法的解释…… ZoomQuiet