【C语言】之使用堆栈模型实现找迷宫的游戏

爱被打了一巴掌 2022-05-28 03:17 205阅读 0赞

/******************************************** * 文件名：MiGong.c * 文件描述：使用堆栈模型实现找迷宫的游戏 * 编辑人：王廷云 * 编辑日期：2017-11-21 * 修改日期：2018-2-1 *********************************************/
    #include <stdio.h>
    #include <stdlib.h>
    
    #define STACK_LEN 1024 // 栈的长度
    #define N 10 // 背景数据的维数
    #define NR(ar) (sizeof(ar)/sizeof(ar[0])) // 数组元素个数
    
    /* 点结构体封装 */
    typedef struct point
    { 
    	int x;	/* 点的列坐标 */
    	int y;	/* 点的横坐标 */
    } Point_t;
    
    /* 地图背景数据 */
    static int map[N][N] = { 
    	0,5,0,0,0,0,0,0,0,0,
        0,5,5,5,5,5,5,5,0,5,
        0,5,1,5,0,5,0,0,0,5,
        0,5,0,5,0,5,0,5,5,5,
        0,5,0,5,0,0,0,5,0,0,
        0,5,0,5,0,5,0,5,5,0,
        0,0,0,0,0,5,0,0,0,0,
        0,5,5,5,0,5,5,5,5,5,
        0,5,0,5,0,0,0,5,0,0,
        0,0,0,5,0,5,0,0,2,5,
    };
    
    /***********堆栈模型**************/
    static Point_t stack[STACK_LEN];    // 栈桢，每个栈中数据为一个点结构体
    static int sp = -1;                 // 栈顶
    void push(Point_t point);           // 入栈
    Point_t pop(void);                  // 出栈
    Point_t top(void);                  // 栈顶
    int isEmptyStack(void);             // 栈空
    int isFullStack(void);              // 栈满
    
    /*********迷宫相关函数************/
    Point_t searchPoint(int val);                   // 查找点的位置
    void printMap(void);                            // 打印地图
    char changeVal(int val);                        // 改变当前点的值
    void goStartByRecur(Point_t cur, Point_t end);  // 使用递归方法实现游戏
    void goStartByStack(Point_t cur, Point_t end);  // 使用栈的方法实现游戏
    
    int main(void)
    { 
    	Point_t start, end;
    
        /* 初始化游戏 */
    	printf("\033[2J");	    // 清屏
    	printf("\033[?25l");	// 关闭鼠标显示
    	printMap();             // 打印地图
    	start = searchPoint(1); // 获取起始点
    	end = searchPoint(2);   // 获取终点
    
    	/***********开始游戏**********/
    #if 1
    	/* 方法一：使用递归算法 */
    	goStartByRecur(start, end);	
    #else
    	/* 方法二：使用堆栈算法 */
    	goStartByStack(start, end);	
    #endif
    
    	return 0;
    }
    
    /* * 函数名：goStartByStack * 函数功能：使用堆栈算法实现游戏 * 参数：cur: 当前点位置 end：终点位置 * 返回值：void */
    void goStartByStack(Point_t cur, Point_t end)
    { 		
    	Point_t next;	/* 下一个点 */
    	int i;
    	Point_t ar[] = { 	/* 当前点的四个方向 */
    		/* {x,y} */
    		{ 1, 0}, 	/* 右 */
    		{ 0,-1}, 	/* 上 */
    		{ -1,0}, 	/* 左 */
    		{ 0, 1}, 	/* 下 */
    	};
    	
    	push(cur);      // 先压栈当前点位置
    	
    	/* 栈不为空,游戏继续 */
    	while (!isEmptyStack())
    	{ 
    		/* 尝试栈顶是否可走 */
    		cur = top();
    		if (map[cur.y][cur.x] > 2)
    		{ 
    			/* 不能走则往回走 */
    			map[cur.y][cur.x] = 8; 	/* 标记回走路 */
    			cur = pop();			/* 下一个栈点 */
    			getchar();
    			printMap();
    
    			continue;
    		}
    		
    		/* 能走则走 */
    		map[cur.y][cur.x] = 9;		/* 标记已走路 */
    		getchar();
    		printMap();
    		
    		/* 判断是否到达终点 */
    		if (cur.x == end.x && cur.y == end.y)
    		{ 
    			printf("\033[31mGame Over!\033[0m\n");
    		    printf("\033[?25h");	// 开启鼠标显示
    			exit(0);
    		}
    		
    		/* 尝试周围的点 */
    		for (i = 0; i < NR(ar); i++)
    		{ 
    			next.x = cur.x + ar[i].x;
    			next.y = cur.y + ar[i].y;
    			
    			/* 判断下一个点是否在数据范围内 */
    			if (next.x<0 || next.x>=N || next.y<0 || next.y>=N)
    			{ 
    				continue;
    			}
    			
    			/* 保存可走数据点 */
    			if (map[next.y][next.x] <= 2)
    			{ 
    				push(next);
    			}
    		}
    	}
    }
    
    /* * 函数名：goStartByRecur * 函数功能：使用递归算法实现游戏 * 参数：cur: 当前点位置 end：终点位置 * 返回值：void */
    void goStartByRecur(Point_t cur, Point_t end)
    { 
    	Point_t ar[] = { 	/* 当前点的四个方向 */
    		/* {x,y} */
    		{ 1, 0}, 	/* 右 */
    		{ 0,-1}, 	/* 上 */
    		{ -1,0}, 	/* 左 */
    		{ 0, 1}, 	/* 下 */
    	};
    	Point_t next;	/* 下一个点 */
    	
    	/* 判断当前点是否可走 */
    	if (map[cur.y][cur.x] > 2)
    	{ 
    		return;
    	}
    	
    	/* 能走则走 */
    	map[cur.y][cur.x] = 9; /* 标记已走 */
    	getchar();
    	printMap();
    	
    	/* 判断是否到达终点 */
    	if (cur.x == end.x && cur.y == end.y)
    	{ 
    		printf("\033[31mGame Over!\033[0m\n");
    		printf("\033[?25h");	// 开启鼠标显示
    		exit(0);
    	}
    	
    	/* 继续下一个点 */
    	int i;
    	for (i = 0; i < NR(ar); i++)    // 四个方向查看是否可走 
    	{ 
    		next.x = cur.x + ar[i].x;
    		next.y = cur.y + ar[i].y;
    		
    		/* 判断下一个点是否在数据范围内 */
    		if (next.x<0 || next.x>=N || next.y<0 || next.y>=N)
    		{ 
    			continue;
    		}
    		goStartByRecur(next,end);
    	}
    	
    	/*不能走则返回 */
    	map[cur.y][cur.x] = 8;
    	getchar();
    	printMap();
    
    	return;
    }
    
    /* * 函数名：searchPoint * 函数功能：查找下点的位置 * 参数：val: 需要查找点的值 * 返回值：返回值为val的点 */
    Point_t searchPoint(int val)
    { 
    	Point_t temp;
    	int i, j;
    
    	for (i = 0; i < N; i++)
    	{ 
    		for (j = 0; j < N; j++)
    		{ 
    			if (map[i][j] == val)
    			{ 
    				temp.x = j;
    				temp.y = i;
    				break;
    			}
    		}
    	}
    
    	return temp;
    }
    
    /* * 函数名：printMap * 函数功能：打印整个游戏地图数据 * 参数：void * 返回值：void */
    void printMap(void)
    { 
    	int i, j;
    	char ch;
    
    	printf("\033[1;1H");/* 定位到左上角 */
    	printf("===\033[32m请输入回车进行游戏\033[0m===\n");
    	
    	
    	/* 打印最上层 */
    	for (i = 0; i < N+2; i++)
    	{ 
    		printf("# ");
    	}
    	putchar('\n');
    	
    	/* 打印中间部分及数据 */
    	for (i = 0; i < N; i++)
    	{ 
    		printf("# "); /* 打印最左边 */
    		
    		/* 接下来根据地图数据打印不同的背景符号 */
    		for (j = 0; j < N; j++)
    		{ 
    			ch = changeVal(map[i][j]);
    			switch (ch)
    			{ 
    				case ' ': printf(" "); 			   break; 
    				case 's': printf("\033[32ms \033[0m"); break; 
    				case 'e': printf("\033[31me \033[0m"); break; 
    				case '#': printf("# "); 			   break; 
    				case '.': printf("\033[36m. \033[0m"); break; 
    				case '*': printf("\033[1;35m* \033[0m"); break; 
    			}
    		}
    		
    		printf("# "); /* 打印最右边 */
    		putchar('\n');
    	}
    	
    	/* 打印最下层 */
    	for (i = 0; i < N+2; i++)
    	{ 
    		printf("# ");
    	}
    	putchar('\n');
    }
    
    /* * 函数名：changeVal * 函数功能：把当前点的值转变为打印的背景符号 * 参数：当前点的值 * 返回值：返回当前点对应的背景符号 */
    char changeVal(int val)
    { 
    	switch (val)
    	{ 
    		case 0: return ' '; /* 没有走过的路 */
    		case 1: return 's'; /* 起始点 */
    		case 2: return 'e'; /* 终点 */
    		case 5: return '#'; /* 墙壁 */
    		case 8: return '.'; /* 返回的路 */
    		case 9: return '*'; /* 走过得路 */
    	}
    }
    
    /******************** 以下为堆栈模型函数 *********************/
    
    /* * 函数名：push * 函数功能：把数据入栈 * 参数：point: 需要入栈的数据 * 返回值：void */
    void push(Point_t point)
    { 
    	sp++;
    	
    	/* 入栈数据为结构体，需要把基本成员数据分别赋值入栈 */
    	stack[sp].x = point.x;
    	stack[sp].y = point.y;
    }
    
    /* * 函数名：pop * 函数功能：把栈顶数据出栈 * 参数：void * 返回值：返回栈顶数据 */
    Point_t pop(void)
    { 
    	return stack[sp--];
    }
    
    /* * 函数名：top * 函数功能：返回栈顶数据 * 参数：void * 返回值：栈顶数据 */
    Point_t top(void)
    { 
    	return stack[sp];
    }
    
    /* * 函数名：isEmptyStack * 函数功能：判断栈是否为空 * 参数：void * 返回值：栈为空返回1，不为空返回0 */
    int isEmptyStack(void)
    { 
    	return sp == -1;
    }
    
    /* * 函数名：isFullStack * 函数功能：判断栈是否为满 * 参数：void * 返回值：栈为满返回1，不满返回0 */
    int isFullStack(void)
    { 
    	return sp == STACK_LEN-1;
    }