迷宫问题代码中出现的一些问题
程序员文章站
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();
}
上一篇: 最优加工顺序问题--贝尔曼规+回溯
下一篇: 数据结构-顺序表
推荐阅读
-
使用加载图片解决在Ajax数据加载中页面出现短暂空白的问题
-
快速找出php中可能导致cpu飙升问题的代码行_PHP教程
-
解析使用substr截取UTF-8中文字符串出现乱码的问题_PHP
-
在最新测试版中微软已修复Windows 11与AMD处理器出现的兼容问题
-
mysql中将textbox中的数据修改传给datatable语句出现问题
-
JavaScript中关于for循环删除数组元素内容时出现的问题
-
php中重复引入出现的问题
-
Kubernetes 中配置集群 ETCD 碰到的一些问题的解决!
-
Eclipse中关于mybatis插件geneartor的使用和遇到的一些问题
-
JSP中遇到的一些问题