欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

迷宫问题代码中出现的一些问题

程序员文章站 2022-05-20 21:36:04
...

各位大牛们,我很好奇,这段代码整体没有见到一个输出‘□’的语句,但是为什么程序运行以后会出现‘□’,作为学生党的我真的很想知道为什么?希望大牛们能帮助我看看,谢谢了!


#include <Windows.h>
#include<iostream>
#include<stack>
using namespace std;
//Position定义坐标
struct Position
{
	int row;
	int col;
	int flag; 
};  

//Maze类创建迷宫并寻找最短路径
class Maze
{
private:
	int row;					//迷宫的宽度(列数) 
	int col;                   //迷宫的高度(行数)					 
	int show;					//1=演示寻径流程 或者 0=不演示寻径流程

	Position offset[4];			//上下左右的偏移量
    stack<Position> change;
	stack<Position> path;		//存储路径的堆栈
	char** maze;				//迷宫地图的数组
	char** mazeShow;			//用来显示迷宫寻径结果的数组

public:
	Maze(int row,int col,int show);              //构造函数 
	void ShowArray(char**array,int m,int n);	//输出m*n的二维数组
	bool FindPath();							//寻找迷宫出口的方法
	void DrawPath();							//绘制迷宫的寻径结果
	void ShowDetail(Position here,int option);				//展示寻径的流程
};

//迷宫数据的输入和偏移量的初始化
Maze::Maze(int row,int col,int show)
{
	this->row = row;
	this->col = col;
	this->show = show;

	//根据输入的行列初始化maze二维数组
	maze = new char*[row+2];          //加二是因为要给最外面加一层墙 
	for(int i=0; i<row+2; ++i)
		maze[i] = new char[col+2];

	//初始化mazeShow二维数组
	mazeShow = new char*[row+2];
	for(int i=0; i<row+2; ++i)
		mazeShow[i] = new char[col+2];

	//对偏移量进行初始化
	offset[0].row = 0;	offset[0].col = 1;	//向右
	offset[1].row = 1;	offset[1].col = 0;	//向下
	offset[2].row = 0;	offset[2].col = -1;	//向左
	offset[3].row = -1;	offset[3].col = 0;	//向上
	
	//输入迷宫的地图数据
	int mazeData[8][8] = 
	{
	{0,0,1,0,0,0,1,0},
	{0,0,1,0,0,0,1,0},
	{0,0,0,0,1,1,0,0},
	{0,1,1,1,0,0,0,0},
	{0,0,0,0,1,1,0,0},
	{0,1,0,0,0,1,0,0},
	{0,1,1,1,0,1,1,0},
	{1,0,0,0,0,0,0,0}
	};
	
	//将迷宫数据导入迷宫数组中
	for (int ii = 0;ii<row;ii++)
	{
		for (int jj = 0;jj<col;jj++){
			maze[ii+1][jj+1]=mazeData[ii][jj];       //ii+1和jj+1是为了避开最外面人为添加的外墙 
		}
	}
		
	//在迷宫外增加一圈障碍物
	for (int r = 0;r<=row+1;r++)
	{
		maze[0][r] = maze[row+1][r] = 1;	 
	}
	for (int c = 0;c<=col+1;c++)
	{
		maze[c][0] = maze[c][col+1] = 1;		
	}

//把maze数组整体赋值给mazeshow数组 
	for (int iii = 0;iii<row+2;iii++)
	{
		for (int jjj = 0;jjj<col+2;jjj++)
		{
			mazeShow[iii][jjj] = maze[iii][jjj];
		}
	}
	cout<<endl;
	cout<<"原始的地图:"<<endl;
	 
	ShowArray(maze,row+2,col+2);
   }

//遍历输出二维数组
void Maze::ShowArray(char**array,int m,int n)
{
	for (int i = 0;i<m;i++)
	{
		for (int j = 0;j<n;j++)
		{
			cout<<array[i][j]<<' ';
		}
		cout<<endl;
	}
}

//显示具体的寻径流程
void Maze::ShowDetail(Position here,int option){
	Sleep(1000);
	for (int t = 0; t<30;t++)		cout<<endl;
	char me = '+';
	for (int i = 0;i < row+2;i++)
	{
		for (int j = 0;j<col+2;j++){
			if (i==here.row&&j==here.col)
			{
				cout<<me<<" ";
			} 
			else
			{
				cout<<maze[i][j]<<" ";
			}
		}
		cout<<endl;
	} 
		     
	
	}


//寻找从位置(1,1)到出口(m,m)的路径
//如果成功则true,否则返回false
bool Maze::FindPath()
{
	Position here;
	here.row = 1;
	here.col = 1;
		
	maze[1][1] = 1;
	int option = 0;		//选择的移动方向
	int LastOption = 3;	//最后一个方向选择
	
	//寻找一条路径
	while (here.row!=row||here.col!=col)
	{
		//寻找并且移动到一个相邻的位置
		int r,c;
		while(option<=LastOption){
			here.flag=option;
			r = here.row + offset[option].row;
			c = here.col + offset[option].col;

			if(maze[r][c] == 0)
				break;
			option++;
		}
		
		//是否找到一个相邻的位置
		if (option<=LastOption)
		{
			//移动到maze[r][c]
			//将当前位置压入堆栈
			path.push(here);
			here.row = r;
			here.col = c;
		
			
			//设置障碍物以阻止再次访问
			maze[r][c] = 2;
			option = 0;
		} 
		else
		{
			//没有可用的相邻位置,回溯上一个节点
			if (path.empty())
				return false;
		
			here = path.top();
			path.pop();
			option = 0;
		}
		if (show)
		{
			ShowDetail(here,option);
		}
	}
	return true;
}


//绘制最终的寻径结果
void Maze::DrawPath()
{
	Position temp,text;
	while(!path.empty())
	{
	    temp = path.top();
		path.pop();
		change.push(temp);	
		mazeShow[temp.row][temp.col] = '+';
	}
	while(!change.empty())
	{
		text=change.top();
		change.pop();	
		printf("(%d,%d,%d)\n",text.row,text.col,text.flag);
	}

	cout<<endl<<"寻径后的迷宫地图:"<<endl;
	ShowArray(mazeShow,row+2,col+2);	
}


int main()
{
	cout<<"按‘1’展示流程,按‘2’直接显示结果"<<endl;
	char input;
	cin>>input;
	int show ; //是否展示迷宫寻径流程,1展示,0不展示
	if (input=='1')
		show = 1; 
	else if (input=='2')
		show = 0;
	else 
		return 0;

	Maze* myMaze = new Maze(8,8,show);
	myMaze->FindPath();
	myMaze->DrawPath();
}

相关标签: 迷宫问题