maze.cpp

数据结构课程设计的一些源代码！

// Maze 类的定义
#include "Maze.h" 

// 构造函数，对迷宫的状态进行初始化
Maze::Maze()
{
	cout << "请输入迷宫阵列，1代表通路，0代表障碍，每输入一行用回车表确认"<< endl; 
    cout << "输入完成后请输入'ok'以表示之 " << endl;
	// 读入迷宫的状态
	string cellstr;
	cin >> cellstr;
	while (cellstr != "ok")
	{
		cells.push_back(cellstr);
		columns = cellstr.size();
		   // 迷宫阵的总列数
		cin >> cellstr;
	}
	rows = cells.size();
	  // 迷宫阵的总行数
}

// 迷宫求解函数
void Maze::solve()
{
	int row, column;
	row = column = 0;
	   // 设置出发点为(0,0)位置
	bool done = exitMaze( row, column);
	// 穿越成功，显示穿越路径，否则报道迷宫无法穿越
	if (done)
	{
		cout << "恭喜！成功穿过迷宫！穿越路径为：" << endl;
		for (int i = 0; i < rows; ++i )
		{
			for (int j = 0; j < columns; ++j)
				cout << cells[i][j];
			cout << endl;
		}// end for
	}// end if
	else
		cout << "对不起，此迷宫无法穿越" << endl;
}

// 从位置(row,column)出发，穿越迷宫，成功返回true
bool Maze::exitMaze( int row, int column)
{
	bool done = false;
	// 如果位置(row,column)可通行，标记之，并依次向四周搜索着前进
	if ( valid(row, column) )
	{
		// 走过的位置标记为'B'
        cells[row][column] = 'B'; 
		// 抵达终点时表示穿越完成
		if ( row == (rows - 1) && column == (columns - 1) )
			done = true;
		else
		{
			// 未到达终点前，首先选择向右走
			done = exitMaze ( row , column + 1);
            // 右走失败，转向下走
			if (!done)
				done = exitMaze ( row + 1, column);
			// 右走、下走失败，转向左走
            if (!done) 
				done = exitMaze ( row, column - 1);
			// 右走、下走、左走均失败，转向上走
            if (!done)
				done = exitMaze ( row - 1, column);
		}
		if (done)
			cells[row][column] = 'P'; 
              // 正确的路径标记为'P'
	}
	return(done);
}

// 判断位置(row,column)是否可通行，是则返回true
bool Maze::valid( int row, int column)
{
	bool path = false;
	// 如果位置(row,column)在迷宫内，且该处可通行
	if ( row >= 0 && row < rows && column >= 0 
		&& column < columns && cells[row][column] == '1' )
		path = true;
	return path;
}