商人过河问题的C语言程序

#include "stdio.h" #include "stdlib.h" #define maxsize 2000 typedef struct //定义安全状态 { int x; int y; }statetype; typedef struct node //定义没经过每个点的坐标 { int x; int y; int pre; //pre的作用是记录是从哪个节点到达该节点的 int tag; //tag的作用是标记船的移动方向，tag=1表示船从此岸到彼岸，tag=-1表示船从彼岸到此岸。 }sqtype; //队列作为存储结构 sqtype sq[maxsize]; statetype state[10]; //安全状态，共10种 statetype move1[5]; //船从此岸向彼岸移动的五种方案 statetype move2[5]; //船从彼岸向此岸移动的五种方案 void init(void) { move1[0].x=-1;move1[0].y=0; //船从此岸向彼岸移动的五种方案 move1[1].x=0;move1[1].y=-1; move1[2].x=-1;move1[2].y=-1; move1[3].x=-2;move1[3].y=0; move1[4].x=0;move1[4].y=-2; move2[0].x=1;move2[0].y=0; //船从彼岸向此岸移动的五种方案 move2[1].x=0;move2[1].y=1; move2[2].x=1;move2[2].y=1; move2[3].x=2;move2[3].y=0; move2[4].x=0;move2[4].y=2; state[0].x=0;state[0].y=0; //安全状态，共10种 state[1].x=0;state[1].y=1; state[2].x=0;state[2].y=2; state[3].x=0;state[3].y=3; state[4].x=3;state[4].y=0; state[5].x=3;state[5].y=1; state[6].x=3;state[6].y=2; state[7].x=3;state[7].y=3; state[8].x=1;state[8].y=1; state[9].x=2;state[9].y=2; } void printpath(sqtype sq[],int rear) //打印路径 { int i; i=rear; do{ printf("(%d,%d)\n",sq[i].x,sq[i].y); i=sq[i].pre; }while(i!=0); } int is_save(statetype s[],int m,int x,int y) //判断移动后的状态是否为安全状态 { int i=0; for (i=0;i<m;i++) if(x==state[i].x && y==state[i].y) break; if(i>=m) return 0; //不是安全状态 else return 1; //是安全状态 } int shortpath(void) //返回1表示找到能够安全渡船的方法，返回0时表示没找到安全渡船的方法。 { int i,j,v,front,rear,x,y; sq[1].x=3; sq[1].y=3; sq[1].pre=0; sq[1].tag=1; front=1; rear=1; while(front<=rear) { x=sq[front].x; y=sq[front].y; if(sq[front].tag==1) //从此岸往彼岸运动 { for (v=0;v<5;v++) { i=x+move1[v].x; j=y+move1[v].y; if(is_save(state,10,x,y)==1) { rear++; sq[rear].x=i; sq[rear].y=j; sq[rear].pre=front; sq[rear].tag=-1; } if(i==0 && j==0) { printpath(sq,rear); return 1; } } } else //从彼岸往此岸运动 { for (v=0;v<5;v++) { i=x+move2[v].x; j=y+move2[v].y; //这里要加上相应的控制语句，以避免原路返回 if(is_save(state,10,x,y)==1 && (sq[sq[front].pre].x!=i || sq[sq[front].pre].y!=j) ) { rear++; sq[rear].x=i; sq[rear].y=j; sq[rear].pre=front; sq[rear].tag=1; } if(i==0 && j==0) { printpath(sq,rear); return 1; } } } front++; } return 0; } void main(void) { init(); int i; //起始位置 i=shortpath(); if(i==0) printf("没有找到应用路径!\n"); if(i==1) printf("\n找到了最佳路径!最佳路径为上面所显示的!\n"); }