数据结构课程设计报告(农夫过河)

}

int safe(int location) // 若状态安全则返回 true { }

void farmerProblem( ) {

int movers, i, location, newlocation; int route[16]; //记录已考虑的状态路径 int print[MAXNUM];

if ((goat(location) == cabbage(location)) && (goat(location) !=

return 0;

farmer(location)) )

if ((goat(location) == wolf(location)) && (goat(location) !=

return 0;

farmer(location)))

return 1; //其他状态是安全的

PSeqQueue moveTo;

moveTo = createEmptyQueue_seq( );//新的队列判断路径 enQueue_seq(moveTo, 0x00); //初始状态为0 for (i = 0; i < 16; i++)

route[i] = -1; //-1表示没有记录过路径 route[0]=0;

while (!isEmptyQueue_seq(moveTo)&&(route[15]== -1))//队列不为空，路径未 {

location = frontQueue_seq(moveTo); //从队头出队，location表示位置，0 deQueue_seq(moveTo);//已出队的删除

满时循环

为北岸，1为南岸

for (movers = 1; movers <= 8; movers<<= 1) //向左移位，movers分别0001，0010，0100，1000,也就是依次判断过河的可行性

{

if ((0 != (location & 0x08)) == (0 != (location & movers)))//判断 {

9

农夫和要移动的物品是否在同岸

newlocation = location^(0x08|movers);//过岸

if (safe(newlocation) && (route[newlocation] == -1))//判断是

否安全，以及路径是否可用

{

route[newlocation] = location;

enQueue_seq(moveTo, newlocation);//记录路径并入队，位置改

变 }

}

}

}

/* 打印出路径 */ if(route[15] != -1) { cout<<\过河步骤是 : \ i=0;

for(location = 15; location >= 0; location = route[location]) { print[i]=location; i++;

if (location == 0)

break;

}

int num=i-1; int temp[20][4];

int j;

for(i=num;i>=0;i--) { for(j=3;j>=0;j--)

{

10

}

}

temp[num-i][j]=print[i]%2; print[i]/=2; temp[0][j]=0; temp[num+1][j]=1;

/* for(i=0;i<=num;i++) {

for(j=0;j<4;j++)

cout<

}*/

for(i=1;i<=num;i++) {

cout<<\ if(i%2==1) {

if(temp[i][3]!=temp[i-1][3])

cout<<\农夫带羊过南岸\

if(temp[i][2]!=temp[i-1][2])

cout<<\农夫带白菜过南岸\ cout<<\农夫带狼过南岸\ if(temp[i][1]!=temp[i-1][1])

if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])

}

cout<<\农夫自己过南岸\

else if(i%2==0) {

if(temp[i][3]!=temp[i-1][3])

cout<<\农夫带羊回北岸\

if(temp[i][2]!=temp[i-1][2])

11

cout<<\农夫带白菜回北岸\ cout<<\农夫带狼回北岸\

if(temp[i][1]!=temp[i-1][1])

if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1]) cout<<\农夫自己回北岸\

}

cout<

}

}

else

cout<<\

}

int main() /*主函数*/ { farmerProblem();

return 0;

}

12