Linux C一站式学习习题答案12.3.3迷宫问题深度优先

现在我们用堆栈解决一个有意思的问题，定义一个二维数组：

int maze[5][5] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 0, 0,
	0, 1, 1, 1, 0,
	0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。

#include <stdio.h>
#define MAX_LEN_STK 512
#define MAX_ROW 5
#define MAX_COL 5

int top = 0;

struct point{int row, col;};

struct point path[MAX_LEN_STK];		/*使用一个数组代替堆栈*/

struct point make_from_cor(int prow, int pcol)
{
	struct point p;
	p.row = prow;
	p.col = pcol;
	return p;
}

int maze[MAX_ROW][MAX_COL] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 0, 0,
	0, 1, 1, 1, 0,
	0, 0, 0, 1, 0,
};

void print_maze()
{
	int i, j;
	for (i = 0; i < MAX_ROW; i++)
	{
		for (j = 0; j < MAX_COL; j++)
		{
			printf("%d ", maze[i][j]);
		}
		printf("\n");
	}
	printf("*********\n");
}

int path_search(struct point p)
{
	maze[p.row][p.col] = 2;
	print_maze();

	if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)		/* goal */
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.col < MAX_COL - 1 && maze[p.row][p.col+1] == 0)	 /* right */
			&&	(path_search(make_from_cor(p.row, p.col+1))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.row < MAX_ROW - 1 && maze[p.row+1][p.col] == 0)	/* down */
			&&	(path_search(make_from_cor(p.row+1, p.col))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.col > 0 && maze[p.row][p.col-1] == 0)			/* left */
			&&	(path_search(make_from_cor(p.row, p.col-1))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}
	if ((p.row > 0 && maze[p.row-1][p.col] == 0)			/* up */
			&& 	(path_search(make_from_cor(p.row-1, p.col))))
	{
		path[top++] = make_from_cor(p.row, p.col);
		return 1;
	}

	return 0;
}

void print_path()
{
	int i;
	--top;
	
	for (i = top; i >= 0; i--)
	{	
		printf("(%d, %d)\n", path[i].row, path[i].col);
	}
}

int main(void)
{
	struct point p = {0, 0};
	if (path_search(p))
	{
		print_path();
	}
	else
		printf("No path!\n");
	return 0;
}

Linux C一站式学习习题答案12.3.3迷宫问题深度优先,古老的榕树,5-wow.com