有下面二维数组表示的一个迷宫,1表示墙壁,0表示可以走的路,编程实现从原点(1,1)到终点(8,8)的一条路线,并输出线路。要求线路保存在栈中,使用堆栈的顺序存储实现。参考下面的提示信息,完成栈的定义,操作,在主函数中调用相关函数,完成题目。
#include
#include
#define N 10
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct Position{
int x, y; //坐标
}Position;
typedef struct PosStep{ //定义结构体,来保存走过的坐标,及在该坐标上尝试过的方向。
int i; //第几步
Position pos; //坐标
int step; //方向 走的方向是下,右,上,左的逆时针方向,分别用0,1,2,3代替
}PosStep;
typedef struct PosStep SElemType;
typedef struct sqstack
{
SElemType *base;
SElemType *top;
int stacksize;
}sqstack;
int init(sqstack *s)
{
s->base=(SElemType*)malloc(10*sizeof(SElemType));
if(!s->base) return 0;
s->top=s->base;
s->stacksize=10;
return 1;
}
int destroy(sqstack *s)
{
free(s->base);
s->base=NULL;
s->top=NULL;
s->stacksize=0;
return 1;
}
int empty(sqstack *s)
{
if(s->top=s->base) return 1;
else return 0;
}
int gettop(sqstack s,SElemType *e)
{
if(s.top>s.base)
{
e=(s.top-1);
return 1;
}
else return 0;
}
int push(sqstack *s,SElemType e)
{
*(s->top)++=e;
return 1;
}
int pop(sqstack *s,SElemType *e)
{
if(s->top==s->base)
return 0;
*e=*--s->top;
return 1;
}
//走的方向为下、右、上、左的顺序
PosStep NextPos(PosStep curstep)
{
switch(curstep.step)
{
case 0:
curstep.pos.x ++; //向下走
break;
case 1:
curstep.pos.y ++; //向右走
break;
case 2:
curstep.pos.x --; //向上走
break;
case 3:
curstep.pos.y --; //向左走
break;
}
return curstep;
}
int mazepass(char maze[N][N],Position start ,Position end)
{
sqstack s;
Position curpos=start;
PosStep e;
int curstep=0;
init(&s);
do{
if(maze[curpos.x][curpos.y]=='0')
{
maze[curpos.x][curpos.y]='i';
curstep++;
e.i=curstep;
e.pos=curpos;
e.step=0;
push(&s,e);
if(curpos.x==end.x&&curpos.y==end.y)
{
while(!empty(&s))
{
pop(&s,&e);
printf("%5d,%5d\n",e.pos.x,e.pos.y);
}
return 1;
}
e=NextPos(e);
curpos=e.pos;
}
else{
if(!empty(&s))
{
pop(&s,&e);
while(e.step==4&&!empty(&s))
{
maze[curpos.x][curpos.y]='@';
pop(&s,&e);
}
if(e.step<4)
{
e.step++;
push(&s,e);
e=NextPos(e);
curpos=e.pos;
}
}
}
}while(!empty(&s));
return 0;
}
int main(int argc, char *argv[])
{
char maze[N][N]={
{'1','1','1','1','1','1','1','1','1','1'},
{'1','0','0','1','0','0','0','1','0','1'},
{'1','0','0','1','0','0','0','1','0','1'},
{'1','0','0','0','0','1','1','0','0','1'},
{'1','0','1','1','1','0','0','0','0','1'},
{'1','0','0','0','1','0','0','0','0','1'},
{'1','0','1','0','0','0','1','0','0','1'},
{'1','0','1','1','1','0','1','1','0','1'},
{'1','1','1','0','0','0','0','0','0','1'},
{'1','1','1','1','1','1','1','1','1','1'}};
int i,j;
Position start,end;
start.x=1;
start.y=1;
end.x=8;
end.y=8;
printf("迷宫为\n");
for(i=0;ifor(j=0;jprintf("%4c",maze[i][j]);
}
printf("\n");
}
if(mazepass(maze,start,end))
printf("ok");
return 0;
}
为什么跑不出来
在 gettop 函数中,参数 e 应该是一个指针,应改为 *e,即 e=((s->top-1));。此外,在主函数中,判断迷宫是否有解时,应该在调用 mazepass 函数前先将终点标记为可走的路,即 maze[end.x][end.y] = '0';。
本题要求实现一个在数组中查找指定元素的简单函数。
函数接口定义:
int search( int list[], int n, int x );
其中list[]是用户传入的数组;n(≥0)是list[]中元素的个数;x是待查找的元素。如果找到
则函数search返回相应元素的最小下标(下标从0开始),否则返回−1。
裁判测试程序样例:
#include <stdio.h>
#define MAXN 10
int search( int list[], int n, int x );
int main()
{
int i, index, n, x;
int a[MAXN];
scanf("%d", &n);
for( i = 0; i < n; i++ )
scanf("%d", &a[i]);
scanf("%d", &x);
index = search( a, n, x );
if( index != -1 )
printf("index = %d\n", index);
else
printf("Not found\n");
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例1:
5
1 2 2 5 4
2
输出样例1:
index = 1
输入样例2:
5
1 2 2 5 4
0
输出样例2:
Not found
答案:顺序查找,简单。
int search( int list[], int n, int x ) {
for (int i = 0; i < n; ++i)
if (list[i] == x) return i;
return -1;
}