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

广度优先搜索 by Leo Jay

狂汗，完全乱了…… 好像这里不支持C++的Highlight，而小弟的Python是刚刚才学的……

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

}