任务描述:
根据如下的人大校园地图，给出起点、终点，寻找并显示一条通路，或告知通路不存在。
任务提示:
使用Stack数据结构
输入参数
//出题者给的人大校园地图，供参考
//怒问: 明德楼在哪里?
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1,1,1,1,1, 1,0,1,0,0,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1, 1,0,1,1,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,1,1,0,1,1,1,0,0,1, 1,0,1,1,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,1, 1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1, 1,0,1,1,0,1,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,0,0,1, 1,0,1,1,0,1,1,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,1,0,0,0,1, 1,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
C语言实现代码
工作环境: Xcode
#include <stdio.h>
#include <stdlib.h>
#define ERROR -1
#define W 28 //width
#define H 14 //height
#define INITSIZE (100)
#define INCREMENT (20)
/*Maze program V1.0 送检版*/
typedef struct{
int x;
int y;
/*dir 0:east; 1:south: 2:west: 3:north*/
int dir;
}ElemType;
typedef struct{
ElemType *base;
int top;
int stacksize;
}SqStack ;
void init_stack(SqStack *S) {
S->base = (ElemType *)malloc(INITSIZE*sizeof(ElemType));
if (!S) {printf("Out of space.\n"); exit(ERROR);}
S->top = 0;
S->stacksize = INITSIZE;
printf("Stack初始化完成. \n");
}
void push(SqStack *S, ElemType e) {
if (S->top >= S->stacksize-1) {
printf("Stack full.\n");
S->base = (ElemType *)realloc(S->base, (INITSIZE+INCREMENT)*sizeof(ElemType));
}
S->base[S->top] = e;
S->top++;
}
void pop(SqStack *S, ElemType *e) {
if (S->top == 0) {
printf("Stack empty.\n");
}
*e = S->base[S->top-1];
S->top--;
}
void print_map(int map[H][W]) {
int i, j;
printf("标记: 1代表墙壁,0代表通道,2代表走过的路径.\n");
printf("Map: \n");
for (i=0; i<H; i++) { //i表示行
for (j=0; j<W; j++) { //j表示列
printf("%d ",map[i][j]);
}
printf("\n");
}
}
int find_path(SqStack *S, int map[H][W], ElemType start, ElemType end) {
/*变量初始化*/
//1,设置起点为当前点
ElemType cur = start;
//2,用count记录走过的步数
int count = 0;
/*开始运行*/
do {
printf("loop\n");
count++;
/*是否终点*/
if (cur.x==end.x && cur.y==end.y) {
map[cur.y][cur.x] = 2;
printf("到达终点, 使用了%d步.\n",count);
return 0;
}
switch (0) { //switch先从东方向开始探测
/*东方向*/
case 0:
//先写好当前点的方向;
cur.dir = 0;
/*可以通行*/
//需要满足该点本身在图中是0, 而且没有被标记过;
if (map[cur.y][cur.x+1]==0){
/*跳入下一个位置*/
//1, 当前点入栈
push(S, cur);
//1, 修改地图上的当前点当做踩过的点为2
map[cur.y][cur.x] = 2;
printf("(%d,%d)\n",cur.x,cur.y);
//2, 修改当前点
cur.x++;
break; //这个break是跳出switch选择;
}
/*南方向*/
case 1:
//先写好当前点的方向;
cur.dir = 1;
/*可以通行*/
//需要满足该点本身在图中是0, 而且没有被标记过;
if (map[cur.y+1][cur.x]==0){
/*跳入下一个位置*/
//1, 当前点入栈
push(S, cur);
//1, 修改地图上的当前点当做踩过的点为2
map[cur.y][cur.x] = 2;
printf("(%d,%d)\n",cur.x,cur.y);
//2, 修改当前点
cur.y++;
break; //这个break是跳出switch选择;
}
/*西方向*/
case 2:
//先写好当前点的方向;
cur.dir = 2;
/*可以通行*/
//需要满足该点本身在图中是0, 而且没有被标记过;
if (map[cur.y][cur.x-1]==0){
/*跳入下一个位置*/
//1, 当前点入栈
push(S, cur);
//1, 修改地图上的当前点当做踩过的点为2
map[cur.y][cur.x] = 2;
printf("(%d,%d)\n",cur.x,cur.y);
//2, 修改当前点
cur.x--;
break; //这个break是跳出switch选择;
}
/*北方向*/
case 3:
//先写好当前点的方向;
cur.dir = 3;
/*可以通行*/
//需要满足该点本身在图中是0, 而且没有被标记过;
if (map[cur.y-1][cur.x]==0){
/*跳入下一个位置*/
//1, 当前点入栈
push(S, cur);
//1, 修改地图上的当前点当做踩过的点为2
map[cur.y][cur.x] = 2;
printf("(%d,%d)\n",cur.x,cur.y);
//2, 修改当前点
cur.y--;
break; //这个break是跳出switch选择;
}
/*四个方向都探测不通*/
default:
pop(S, &cur);
printf("(%d,%d)\n",cur.x,cur.y);
break;
}
} while (cur.x!=start.x || cur.y!=start.y); //当一路退回到了起点,就跳出循环,表示失败了;
printf("找不到终点.\n");
return 0;
}
int main()
{
int map[14][28]= //人大校园地图，供参考, W=28, H=14
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1,1,1,1,1,
1,0,1,0,0,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,1,1,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,1,1,0,1,1,1,0,0,1,
1,0,1,1,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,1,
1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1,
1,0,1,1,0,1,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,0,0,1,
1,0,1,1,0,1,1,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,1,0,0,0,1,
1,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
print_map(map);
/*变量初始化: start & end 初始化*/
SqStack S;
init_stack(&S);
ElemType start, end;
start.x = 1; start.y = 1; start.dir = 0;
end.x = W-1-1; end.y = H-1-1;
find_path(&S,map,start,end);
print_map(map);
return 0;
}
/*开发日志*/
//原本我想在ElemType中加入pre, next, 但是实际上是不必要的,用pop就可以得到上一个点
//也就是说,stack结构自然而然能找到上一个, 因此只要在每个元素中写入下个元素的方向就可以了;
//基础操作方法准备完毕;
//17:45第一次测试: bug发现是只循环4次
//23:00去掉了循环以后, 发现只进行一次寻找;
//8:28 代码出现了死循环; 而且当某个点发现不通了,退回上一点的时候, cur是否有把坐标还原到上一点呢? 另外, 还原到上一点以后, 是怎么保证能做继续探索其他方向来找下一点的, 直到都不行才继续往回退?
//8:55 代码运行成功, 最后阻止程序正确执行的原来是我的终点条件的x和y检查写错了, 居然写成cur.x==y而不是cur.x==x!
//8:59 添加了记录步数的count变量, 增加了注释;
//9:06 删除多余注释,程序完成,可以提交.
网友评论