yls 算法设计与分析实验指导(5)

int main() //为了让search()显示在一页内和main函数换了以下 { //一般的算法程序main函数写在最上面读起来更方便 int number; readdata(); //读取数据 init(); //初始化 number=search(); //广搜并返回最小步数 printf(\ //打印结果 }

int emptyopen() { if(head==tail) return(1); else return(0); }

long takeoutofopen() { long u; if(head==tail) { printf(\ return(-1); } u=open[head++]; head=head%openlen; return(u); }

int used(int row, int col) { if(a[row][col]==0) return(0); else return(1); }

void addtoopen(int row, int col) { int u; if((head-tail)%openlen==1) printf(\ u=row; u=u*n+col; open[tail++]= u; tail=tail%openlen; }

void readdata() { long row,col; scanf(\ //起点坐标 s=row*n+col; scanf(\ //终点坐标 t=row*n+col; }

void init() { head=0; tail=1; open[0]=s; }

int isaim(int row, int col) { if(row*n+col==t) return(1); else return(0); }

思考：参考第4题，改为用结构体表示状态写此程序。 4. 独轮车

独轮车的轮子上有5种颜色，每走一格颜色变化一次，独轮车只能往前推，也可以在原地旋转，每走一格，需要一个单位的时间，每转90度需要一个单位的时间，转180度需要两个单位的时间。现给定一个20×20的迷宫、一个起点、一个终点和到达终点的颜色，问独轮车最少需要多少时间到达。

状态：独轮车所在的行、列、当前颜色、方向。 另外为了方便在结点中加上到达该点的最小步数。 程序如下： #include struct colornode { int row; //该状态的行 int col; // 列 int color; // 颜色 int direction; // 方向 int num; // 最小步数 };

int search(); //广搜返回目标结点的最小步数 void readdata(); //读入数据 void init(); //初始化

struct colornode moveahead(struct colornode u); //返回u向前走一格得到的结点 int used(struct colornode v); //判断该结点是否是到达过的结点 void addtoopen(struct colornode v); //加入到open表

int islegal(struct colornode v); //如果该结点是合法的结点(未越界且是空格) int isaim(struct colornode v); //判断该结点是否是目标结点

struct colornode takeoutofopen(); //从open表中取出一个结点并把该结点从open表中删除 struct colornode turntoleft(struct colornode u); //u向左转得到新结点v struct colornode turntoright(struct colornode u); //u向左转得到新结点v struct colornode s,t; //s:起始结点；t目标结点 struct colornode open[200]; //open表

int head,tail,openlen=200; //open表相关数据

int direct[4][2]={{0,-1},{1,0},{0,1},{-1,0}};//向左、下、右、上四个方向转时，行列的增加值 int a[20][20],n=20; //a数组表示迷宫；n为迷宫边长 int b[20][20][5][4]; //b数组表示搜索时的所有状态(0：未访问；1：已访问) int main() { int number; readdata(); init(); number=search(); printf(\}

int search() //广搜返回目标结点的最小步数 { struct colornode u,v; while(head!=tail) { u=takeoutofopen(); v=moveahead(u); //u向前走一格得到新结点v if(islegal(v)) //如果该结点是合法的结点(未越界且是空格) { if(isaim(v)) //判是否是目标结点 return(v.num); if(!used(v)) //如果是未到达过的结点 addtoopen(v); //加入到open表 } v=turntoleft(u); //u向左转得到新结点v if(!used(v)) addtoopen(v); v=turntoright(u); //u向右转得到新结点v if(!used(v)) addtoopen(v); } }

int used(struct colornode v) //判断该结点是否是到达过的结点 { if(b[v.row][v.col][v.color][v.direction]==0) return(0); else return(1); }

void addtoopen(struct colornode v) //加入到open表 { open[tail++]=v; tail=tail%openlen; b[v.row][v.col][v.color][v.direction]=1; }

struct colornode takeoutofopen() //从open表中取出一个结点并把该结点从open表中删除 { struct colornode v; v=open[head++]; head=head%openlen; return(v); }

void init() //初始化 { int i,j,k,l; for(i=0;i

void readdata() //读入数据 { char str[50]; int i,j; for(i=0;i

scanf(\ //读入起始结点信息 scanf(\ //读入目标结点信息 }

int isaim(struct colornode v) //判断该结点是否是目标结点 { if(v.row==t.row&&v.col==t.col&&v.color==t.color) return 1; else return 0; }

int islegal(struct colornode v) //如果该结点是合法的结点(未越界且是空格) { if(v.row<0||v.row>=n||v.col<0||v.col>=n) //若越界 return 0; if(a[v.row][v.col]==0) //0：表示空格 return 1; return 0; }

struct colornode moveahead(struct colornode u) //返回u向前走一格得到的结点 { struct colornode v; v.row=u.row+direct[u.direction][0]; v.col=u.col+direct[u.direction][1]; v.color=(u.color+1)%5; v.direction=u.direction; v.num=u.num+1; return(v); }

struct colornode turntoleft(struct colornode u) //u向左转得到新结点v { struct colornode v; v=u; v.direction=(v.direction+1)%4; v.num=v.num+1; return(v); }

struct colornode turntoright(struct colornode u) //u向左转得到新结点v { struct colornode v; v=u; v.direction=(v.direction+3)%4; v.num=v.num+1; return(v); }