发布时间 : 星期日 文章数据结构课程设计报告(农夫过河)更新完毕开始阅读1c9c3d9f51e79b89680226f5
}
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