Linux Cワンストップ学習問題解答12.3.3迷宮問題深さ優先

スタックで興味深い問題を解決し、2 D配列を定義します.

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つの迷路を表して、その中の1は壁を表して、0は歩くことができる道を表して、横に歩くか縦に歩くしかなくて、斜めに歩くことができなくて、プログラムに左上の角から右下の角までのルートを探し出すように要求します.
3、前節ではスタックベースのプログラムを実装し、それを再帰プログラムに書き換え、自分が実装したスタックの代わりに関数呼び出しのスタックフレームを用いた.本節のDFSアルゴリズムもスタックベースですので、それを再帰プログラムに書き換えてください.書き換えは使用を避けることができます.predecessorデータ構造、どうすればいいか考えてみましょう.
注:転載はソースアドレスを明記してください.http://blog.csdn.net/whorus1/article/list/2あ、ありがとう!

#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("
");
	}
	printf("*********
");
}

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)
", path[i].row, path[i].col);
	}
}

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