迷宮問題(続き)

プリコード:

struct pos
{
	pos(int row = 0, int col = 0)
		:_row(row)
		,_col(col)
	{}
	int _row;
	int _col;
};

void GetMaze(int *arr,  int n)
{
	FILE *fout = fopen("MazeMap.txt", "r");
	assert(fout);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n;)
		{
			char ch = fgetc(fout);
			if (ch != ' ' && ch != '
')
			{
				*(arr + i * n + j) = ch - '0';
				j++;
			}
		}
	}
}

一、出口を見つける

bool MazePath(int *arr, int n, const pos &entry, stack<pos> &path)   //           
{
	pos cur = entry;
	path.push(cur);
	while (!path.empty())
	{
		*(arr + n * (cur._row)+cur._col) = 2;
		if (cur._row == n - 1)
		{
			return true;
		}
		//  
		if 
		((cur._row + 1 < 10) && (*(arr + n * (cur._row + 1) + cur._col) == 0)) 
		{
			*(arr + n * (cur._row + 1) + cur._col) = 2;
			++cur._row;
			path.push(cur);
			continue;
		}
		//  
		if 
		((cur._row - 1 >= 0) && (*(arr + n * (cur._row - 1) + cur._col) == 0))  
		{
			*(arr + n * (cur._row - 1) + cur._col) = 2;
			--cur._row;
			path.push(cur);
			continue;
		}
		//  
		if 
		((cur._col - 1 >= 0) && (*(arr + n * cur._row + cur._col - 1) == 0))     
		{
			*(arr + n * cur._row + cur._col - 1) = 2;
			--cur._col;
			path.push(cur);
			continue;
		}
		//  
		if ((cur._col + 1 < 10) && (*(arr + n * cur._row + cur._col + 1) == 0))      
		{
			*(arr + n * cur._row + cur._col + 1) = 2;
			++cur._col;
			path.push(cur);
			continue;
		}

		//   
		cur._col = path.top()._col;
		cur._row = path.top()._row;
		path.pop();
	}
}

二、すべての出口を見つけて最短ルートを導く(最適解)

template <typename T>
void ClearPath(stack<T> &stack)
{
	while (!stack.empty())
	{
		stack.pop();
	}
}

static void SaveBestPath(stack<pos> &path, vector< stack<pos> > path_vec)
{
	stack<pos> best_path;
	int sz = (path_vec.back()).size();
	best_path = path_vec.back();
	while (!path_vec.empty())
	{
		if (sz > (path_vec.front()).size())
		{
			best_path = path_vec.front(); 
		}
		path_vec.pop_back();
	}
	path = best_path;
}

static struct Exit
{
	Exit(int row, int col)
		:_row(row)
		,_col(col)
	{}
	int _row;
	int _col;
};

 //           (       ，     )
static void BlockKnownExit(int *arr, vector< Exit> exit_vec, int n)		
{
	Exit ext1 = exit_vec.back();
	while (!exit_vec.empty())
	{
		ext1 = exit_vec.back();
		*(arr + n * ext1._row + ext1._col) = 3;
		exit_vec.pop_back();
	}
}

//           
bool MazePathMin(int *arr, int n, const pos &entry, stack<pos> &path)  
{
	vector< stack<pos> > path_vec;   //         
	vector< Exit > exit_vec;         //        
	pos cur = entry;
	path.push(cur);

	while (!path.empty() )
	{
		*(arr + n * (cur._row) + cur._col) = 2;
		if (cur._row == n - 1)
		{
			//      
			*(arr + n * (cur._row) + cur._col) = 3;
			Exit ext_tmp(cur._row, cur._col);
			path_vec.push_back(path);
			exit_vec.push_back(ext_tmp);

			//    ，            
			ClearPath(path);
			GetMaze(arr, n);
			BlockKnownExit(arr, exit_vec, n);
			cur = entry;
			path.push(cur);
		}
                 //  
		if ((cur._row + 1 < 10) && (*(arr + n * (cur._row + 1) + cur._col) == 0))
		{
			*(arr + n * (cur._row + 1) + cur._col) = 2;
			++cur._row;
			path.push(cur);
			continue;
		}
		//  
		if ((cur._row - 1 >= 0) && (*(arr + n * (cur._row - 1) + cur._col) == 0))  
		{
			*(arr + n * (cur._row - 1) + cur._col) = 2;
			--cur._row;
			path.push(cur);
			continue;
		}
		//  
		if ((cur._col - 1 >= 0) && (*(arr + n * cur._row + cur._col - 1) == 0))     
		{
			*(arr + n * cur._row + cur._col - 1) = 2;
			--cur._col;
			path.push(cur);
			continue;
		}
		//  
		if ((cur._col + 1 < 10) && (*(arr + n * cur._row + cur._col + 1) == 0))      
		{
			*(arr + n * cur._row + cur._col + 1) = 2;
			++cur._col;
			path.push(cur);
			continue;
		}

		//      ：
		cur._col = path.top()._col;
		cur._row = path.top()._row;
		path.pop();
	}

	//path  
	SaveBestPath(path, path_vec);   //         path （    ）
	return (!path.empty());
}

三、再帰で実現