【データ構造】遡及法で迷宮問題を解く

今日は、スタックでデータ構造の有名な問題である迷路問題を解きましょう.
私たちはまず迷路を作って、それをMazeに置きます.txtファイル内
Maze.txt

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1
1 1 0 1 0 0 0 0 1 1
1 1 0 1 0 1 1 0 1 1
1 1 0 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 1 1
1 1 0 1 1 1 1 0 1 1
1 1 0 1 1 1 1 0 1 1
1 1 0 1 1 1 1 0 1 1	

このうち、0は歩ける道、1は歩けない道(壁)
まず、座標を格納する構造体を定義します.

struct Pos
{
	size_t _row;// 
	size_t _col;// 
};

次はMazeからtxt迷宮に読み込む

void GetMaze(int *maze, size_t N)
{
	FILE *fp = fopen("1.txt","r");
	if (fp == NULL)
	{
		throw invalid_argument("Read maze filed");
	}
	for (size_t i = 0; i < N; ++i)
	{
		for (size_t j = 0; j < N;)
		{	
			char ch = fgetc(fp);
			if (ch == '0' || ch == '1')
			{	
				maze[i*N + j] = ch - '0';
				++j;
			}
			else if (ch == EOF)
			{
				throw invalid_argument("Maze Error");
			}
		}
	}
}

そして便利にするために、このステップが行けるかどうかを判断するために関数を制定しました.
この位置が0かどうかを判断することです

bool CheckIsAccess(int *maze, size_t N, Pos next)
{
	if (maze[next._row*N + next._col] == 0)
	{
		return true;
	}
	return false;
}

非再帰的な方法で解く

 
bool GetMazePath(int *maze, size_t n, Pos entry, stack&path)
{
	maze[entry._row*N + entry._col] = 2;
	Pos cur,next;
	cur = entry;
	path.push(entry);
	while (!path.empty())
	{
		cur = path.top();

		if (cur._row == N - 1)
		{
			return true;
		}

		next = cur;

		next._row += 1;
		if (CheckIsAccess((int*)maze, N, next) == true)
		{
			path.push(next);
			maze[next._row*N + next._col] = 2;
			continue;
		}
		next = cur;

		next._row -= 1;
		if (CheckIsAccess((int*)maze, N, next) == true)
		{
			path.push(next);
			maze[next._row*N + next._col] = 2;
			continue;
		}
		next = cur;

		next._col += 1;
		if (CheckIsAccess((int*)maze, N, next) == true)
		{
			path.push(next);
			maze[next._row*N + next._col] = 2;
			continue;
		}
		next = cur;

		next._col -= 1;
		if (CheckIsAccess((int*)maze, N, next) == true)
		{
			path.push(next);
			maze[next._row*N + next._col] = 2;
			continue;
		}
		next = cur;

		path.pop();
	}
	return false;
}

再帰的な方法で解く

void GetMazePath_R(int *maze, size_t N, Pos entry, stack&path)
{
	if (entry._row == N - 1)
	{
		return;
	}
	Pos cur,next;
	cur = entry;

	next = cur;

	next._row += 1;
	if (CheckIsAccess((int*)maze,N,next) ==  true)
	{
		path.push(next);
		maze[next._row*N + next._col] = 2;
		GetMazePath_R(maze, N, next, path);
	}
	next = cur;

	next._row -= 1;
	if (CheckIsAccess((int*)maze, N, next) == true)
	{
		path.push(next);
		maze[next._row*N + next._col] = 2;
		GetMazePath_R(maze, N, next, path);
	}
	next = cur;

	next._col += 1;
	if (CheckIsAccess((int*)maze, N, next) == true)
	{
		path.push(next);
		maze[next._row*N + next._col] = 2;
		GetMazePath_R(maze, N, next, path);
	}
	next = cur;

	next._col -= 1;
	if (CheckIsAccess((int*)maze, N, next) == true)
	{
		path.push(next);
		maze[next._row*N + next._col] = 2;
		GetMazePath_R(maze, N, next, path);
	}
	next = cur;
}

非再帰的な方法に対して最短の経路を求める
ReMazeは迷宮をリセットすることを表しています

void ReMaze(int* maze，size_t N)
{
	for (size_t i = 0; i < N; ++i)
	{
		for (size_t j = 0; j < N; ++j)
		{
			if (maze[i*N + j] != 1)
			{
				maze[i*N + j] = 0;
			}
		}
	}
}

void TestMaze()
{
	try
	{
		int maze[N][N] = { 0 };
		int curmaze[N][N] = { 0 }; 
		GetMaze((int*)maze, N);
		stack path,MinPath,empty;
		
		while (GetMazePath((int*)maze, N, { 2, 0 }, path))
		{
			if (path.size() < MinPath.size()||MinPath.size() == 0)
			{
				MinPath = path;
			}
			ReMaze((int*)maze,N);
			maze[path.top()._row][path.top()._col] = 1;//        1
			path = empty;
		}
		cout << "Min path:" << MinPath.size() << endl;
	}
	catch (exception &e)
	{
		cout << e.what() << endl;
	}
}