发布时间 : 星期三 文章C语言程序设计大赛资料更新完毕开始阅读1f9997d476a20029bd642d1b
u=open[head++]; head=head%openlen; return(u); }
int canmoveto(int row, int col, int *p, int *q, int direction) { int r,c; r=row; c=col; switch(direction) { case 0: c--; //左 break; case 1: r++; //下 break; case 2: c++; //右 break; case 3: r--; //上 } *p=r; *q=c; if(r<0||r>=n||c<0||c>=n) //如果越界返回0 return(0); if(a[r][c]==0) //如果是空格返回1 return(1); return(0); //其余情况返回0 }
int isaim(int row, int col) { if(row*n+col==t) return(1); else return(0); }
int used(int row, int col) { if(a[row][col]==0) // 0表示空格 return(0); else return(1); }
void addtoopen(int row, int col) { int u; u=row*n+col; open[tail++]= u; tail=tail%openlen; }
void readdata() { int i,j,row,col; char str[20]; scanf(\
13
scanf(\起点坐标 s=row*n+col; scanf(\终点坐标 t=row*n+col; gets(str); for(i=0;i void init() { head=0; tail=1; open[0]=s; } 测试数据如下： 12 10 7 1 8 XXXXXXXXXXXX X......X.XXX X.X.XX.....X X.X.XX.XXX.X X.X.....X..X X.XXXXXXXXXX X...X.X....X X.XXX...XXXX X.....X....X XXX.XXXX.X.X XXXXXXX..XXX XXXXXXXXXXXX 注：测试数据可在运行时粘贴上去(点击窗口最左上角按钮，在菜单中选则“编辑”/“粘贴”即可)。 想一想：此程序都存在哪些问题，如果openlen太小程序会不会出错，加入代码使程序能自动报出此类错误。 3. 跳马 给一个200×200的棋盘，问国际象棋的马从给定的起点到给定的终点最少需要几步。 Sample Input 0 0 1 1 Sample output 4 状态：马所在的行、列。 程序如下： #include void readdata(); //读入数据 void init(); //初始化 int search(); //广度优先搜索 int emptyopen(); //判栈是否为空：空：1；非空：0。 long takeoutofopen(); //从栈中取出一个元素，并把该元素从栈中删除 int canmoveto(int,int,int*,int*,int); //判能否移动到该方向，并带回坐标(r,c) int isaim(int row, int col); //判断该点是否是目标 int used(int,int); //判断该点是否已经走过 void addtoopen(int,int); //把该点加入到open表 int a[200][200],n=200; //a存放棋盘，n为迷宫边长 14 long open[2000],head,tail,openlen=2000; //open表1367 long s,t; //起点和终点 int search() { long u; int row, col, r, c, i, num; while(!emptyopen()) //当栈非空 { u=takeoutofopen(); //从栈中取出一个元素，并把该元素从栈中删除 row=u/n; //计算该点所在的行 col=u%n; //计算该点所在的列 num=a[row][col]; //取得该点的步数 for(i=0;i<8;i++) { if(canmoveto(row,col,&r,&c,i)) //判能否移动到该方向，并带回坐标(r,c) { if(isaim(r,c)) //如果是目标结点 return(num+1); //返回最小步数 if(!used(r,c)) //如果(r,c)还未到达过 { a[r][c]=num+1; //记录该点的最小步数 addtoopen(r,c); //把该点加入到open表 } } } } return -1; } 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); 15 } 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 16