-
数据结构 迷宫问题
2017-05-18 14:43:33迷宫问题#include <stdio.h>
#include <math.h>
#define M 8
#define N 8
#define MaxSize 100
typedef int ElemType;
int a[M+2][N+2]=
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,0,0,0,1,0,1},
{1,0,1,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,0,1,0,0,0,0,0,2,1},
{1,1,1,1,1,1,1,1,1,1}
};
typedef struct
{
int i; //当前方块的行号
int j; //当前方块的列号
int d; //di是下一可走相邻方位的方位号 1为向右走 2为向下走 3为向左走 4为向上走
} Box;
typedef struct
{
Box base[MaxSize];
int top; //栈顶指针
} SqList;
void MazePath(SqList S)
{
intq=0,m,n,k=0,l; //q 为计数器
m=1;
n=1;
S.top=-1;
do
{
k++;
if(a[m][n]==0)
{
a[m][n]=1;
S.top++;
S.base[S.top].i=m;
S.base[S.top].j=n;
S.base[S.top].d=1;
n=n+1;
q=q+1;
continue;
}
if(a[m][n]==1)
{
if(S.base[S.top].d==1)
{
n=n-1;
S.base[S.top].d=2;
m=m+1;
continue;
}
if(S.base[S.top].d==2)
{
m=m-1;
S.base[S.top].d=3;
n=n-1;
continue;
}
if(S.base[S.top].d==3)
{
n=n+1;
S.base[S.top].d=4;
continue;
}
if(S.base[S.top].d==4)
{
S.top--;
q--;
continue;
}
}
if(a[m][n]==2)
{
printf(" 步数为:%d\n",q);
break;
}
}while(S.top>-1);
printf("执行了%d次循环\n",k);
}
int main()
{
void MazePath(SqList S);
SqList S;
MazePath(S);
return 0;
}
-
数据结构迷宫问题
2019-04-04 22:12:19【问题描述】 有一个 10 x 10 的迷宫,起点是‘S’,终点是‘E’,墙是‘#’,道路是空格。一个机器人从起点走到终点。当机器人走到一个通道块,前面已经没有路可走时,它会转向到当前面向的右手方向继续走。如果...【问题描述】
有一个 10 x 10 的迷宫,起点是‘S’,终点是‘E’,墙是‘#’,道路是空格。一个机器人从起点走到终点。当机器人走到一个通道块,前面已经没有路可走时,它会转向到当前面向的右手方向继续走。如果机器人能够过,则留下足迹‘*’,如果走不通,则留下标记‘!’。
下面给出算法,请你模拟机器人的走法输出最终的状态。【输入形式】
一个 10 x 10 的二维字符数组。
【输出形式】
机器人走过的路径状态。
【样例输入】
##########
#S # # #
# # # #
# ## #
# ### #
# # ##include<iostream> #include<stdlib.h> #include<stdio.h> using namespace std; char a[10][10]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; struct Stack { int x[1000]; int y[1000]; int top; }; void Init(Stack *&s) { s=(Stack*)malloc(sizeof(Stack)); s->top=-1; } void Push(Stack *s,int x,int y) { if(s->top==999) { cout<<"栈已满,无法进行相应的操作!"; return; } s->top++; s->x[s->top]=x; s->y[s->top]=y; } void Pop(Stack *s) { if(s->top==-1) cout<<"该栈为空!"<<endl; s->top--; } void FootPrint(char a[][10],int x,int y) { a[x][y]='*'; } void Mark(char a[][10],int x,int y) { a[x][y]='!'; } int Getx(Stack *s) { return s->x[s->top]; } int Gety(Stack *s) { return s->y[s->top]; } int main() { Stack *s=NULL; Init(s); int i,j,startx,starty,x,y,topx,topy; for(i=0;i<10;i++) { for(j=0;j<10;j++) { scanf("%c",&a[i][j]); if(a[i][j]=='S') { startx=i; starty=j; } } getchar(); } x=startx; y=starty; Push(s,x,y); while(a[x][y]!='E') { FootPrint(a,x,y); if(a[x+dx[0]][y+dy[0]]==' '||a[x+dx[0]][y+dy[0]]=='E') { x=x+dx[0];y=y+dy[0]; Push(s,x,y); continue; } if(a[x+dx[1]][y+dy[1]]==' '||a[x+dx[0]][y+dy[0]]=='E') { x=x+dx[1];y=y+dy[1]; Push(s,x,y); continue; } if(a[x+dx[2]][y+dy[2]]==' '||a[x+dx[0]][y+dy[0]]=='E') { x=x+dx[2];y=y+dy[2]; Push(s,x,y); continue; } if(a[x+dx[3]][y+dy[3]]==' '||a[x+dx[0]][y+dy[0]]=='E') { x=x+dx[3];y=y+dy[3]; Push(s,x,y); continue; } else { Mark(a,x,y); Pop(s); topx=Getx(s); topy=Gety(s); x=topx; y=topy; } } a[x][y]='*'; for(i=0;i<10;i++) { for(j=0;j<10;j++) cout<<a[i][j]; cout<<endl; } }
# # # #
# ### ## #
## E#
##########【样例输出】
# # ########
# * * # ! ! ! # #
# * # ! ! ! # #
# * *! ! ## #
# * # # # #
# * * * # #
# # * * * # #
# ### * ## #
## * * * *#
######## # # -
C语言数据结构迷宫问题_数据结构迷宫代码
2020-02-24 11:21:05. . . #include <stdio.h> #include <stdlib.h> #include <time.h> #define M 20 #define N 20 #define visited 2 #define TRUE 1 #define FALSE 0 #define INITSIZE 100 typedef int Status; typedef struct{ //... -
数据结构迷宫问题C++实现
2017-05-27 22:27:52利用堆栈性质实现数据结构迷宫问题。出现实现图:
.h文件实现堆栈简易操作(此处没有将声明与实现分离,应注意!)
#pragma warning (disable : 4715) #ifndef STACK_H #define STACK_H struct Position//结构体位置,表示迷宫每一格的行号和 列号 { int row;//行号 int col;//列号 }; class Stack { public: Stack(int MaxSize = 10); ~Stack() { delete[] Element; }; bool IsEmpty() const { return top == -1; } bool IsFull() const { return top == Maxtop; } Position Top() const;//返回栈顶元素 Stack& Add(Position &x);//添加元素 Stack& Delete(Position &x);//删除元素 private: int top;//栈顶,入栈和出栈的地方。 int Maxtop;//栈顶元素位置。 Position *Element; }; Stack::Stack(int MaxSize) { Maxtop = MaxSize - 1; Element = new Position[MaxSize]; top = -1; } Position Stack::Top() const { if (IsEmpty()) { } else return Element[top]; } Stack& Stack::Add(Position &x) { if (IsFull()) { } else { ++ top; Element[top].row = x.row; Element[top].col = x.col; } return *this; } Stack& Stack::Delete(Position &x) { if (IsEmpty()) { } else { x.row = Element[top].row; x.col = Element[top].col; --top; } return *this; } #endif
源文件:#include<iostream> #include"STack.h" using namespace std; int main() { cout << "老鼠迷宫!" << endl; //构建迷宫。maze[1][1]表示入口, maze[10][10]表示出口。 char **maze = new char *[12]; for (int i = 0; i < 12; ++i) maze[i] = new char[12]; //给迷宫加“墙”。 for (int i = 0; i < 12; ++i) { maze[11][i] = '+'; maze[0][i] = '+'; maze[i][0] = '+'; maze[i][11] = '+'; } //构建迷宫,用符号+表示墙壁,空格表示通路,以使迷宫尽可能好看! for (int a = 1; a < 11; ++a) for (int b = 1; b < 11; ++b) maze[a][b] = ' '; for (int i = 2; i < 7; ++i) maze[1][i] = '+'; maze[2][6] = maze[2][8] = maze[3][4] = maze[3][6] = maze[4][2] = maze[4][4] = maze[4][6] = maze[4][8] = maze[4][9] = '+'; maze[5][2] = maze[5][4] = maze[5][6] = maze[5][8] = maze[6][2] = maze[6][3] = maze[6][4] = maze[6][6] = maze[6][8] = maze[6][10] = '+'; maze[7][2] = maze[7][6] = maze[7][8] = maze[7][10] = maze[8][2] = maze[8][4] = maze[8][5] = maze[8][6] = maze[8][8] = '+'; maze[9][1] = maze[9][8] = maze[10][5] = maze[10][6] = maze[10][7] = maze[10][8] = '+'; //输出迷宫 布局。 cout << "迷宫如下所示:" << endl; for (int a = 0; a < 12; ++a) { for (int b = 0; b < 12; ++b) cout << maze[a][b] << " "; cout << endl; } //构建迷宫完毕,开始寻找路径。 Stack* Path = new Stack(10*10 - 1);//栈用来储存路径以及遇到障碍物时方标返回上一步。 Position offset[4];//设置模拟移动方法。 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;//上移 Position here;//代表当前位置。 here.col = 1; here.row = 1; maze[1][1] = '#';//入口堵住,防止返回入口。 int option = 0;//上、下、左、右四种走法。记录走的次数,一共四次,上下左右分布探索。 int Lastoption = 3; //模拟移动,开始寻找出口。 while (here.row != 10 || here.col != 10) { int x, y; while (option <= Lastoption)//最多循环4次,尝试每种走法。 { x = here.row + offset[option].row; y = here.col + offset[option].col; if (maze[x][y] == ' ')//只要寻找得到通路,就退出循环。 break; option++; } if (option <= Lastoption) {//移动一次,是通路,此处位置入栈,移动数option归0。 Path->Add(here); here.row = x; here.col = y; maze[x][y] = '*';//将该处修改为墙壁,防止返回,做重复工作。 option = 0; } else//不是通路,会退一步,路径记录栈栈顶元素出栈。 { if (Path->IsEmpty())//出现空栈,表明该迷宫没有出口! cout << "这个迷宫没有出口!" << endl; Position next; next.col = next.row = 0; Path->Delete(next);//新的位置,表示here的前一步,用来回退。 if (next.row == here.row) option = 2 + next.col - here.col;//通过计算得出回退后应该执行哪一种走法! else option = 3 + next.row - here.row; here = next; } } cout << "老鼠找到了迷宫的出口!!" << endl;//以图形的样式输出寻找得到的路径。 for (int i = 0; i < 12; ++i) { for (int a = 0; a < 12; ++a) cout << maze[i][a] << " "; cout << endl; } system("pause"); }
-
07数据结构与输入断言_数据结构迷宫问题怎么自己输入迷宫
2020-04-13 06:23:50使用者自定义的数据结构 向量和矩阵不是MATLAB提供的将数据组合成一个实体的唯一手段使用者自定 义的数据结构也是有效的它能够使程序设计者创造出数字字符串和数组混 合在一起的变量类型作为例子我们创造一个包含一... -
【Qt】数据结构迷宫问题可视化解决程序
2021-01-12 14:35:48本篇博客实现了数据结构迷宫问题可视化解决程序。 先上一些效果图。 首先迷宫支持文件导入与手动输入。 文件导入(txt) 手动输入 点击生成迷宫与运行后会展示迷宫路径,动态,博客不便于展示。 同时路径也会...数据结构课程设计抽到了用栈和队列解决迷宫问题的题目,小组突发奇想为什么不把结果使用可视化程序展现出来呢,因为DOS窗口里只会立即显示结果没有动态迷宫路径展示。
本篇博客实现了数据结构迷宫问题可视化解决程序。
先上一些效果图。
首先迷宫支持文件导入与手动输入。
文件导入(txt)
手动输入
点击生成迷宫与运行后会展示迷宫路径,动态,博客不便于展示。
同时路径也会显示在输出结果栏目中。
话不多说,上源代码。
Qt目录
mainwindow.h#ifndef MAINWINDOW_H #define MAINWINDOW_H #include <QLineEdit> #include <QMainWindow> #include <stdio.h> #include <stdlib.h> #include <fstream> #include <typeinfo> #include <iostream> #include <sstream> #include <vector> #include <QDebug> #include "QFileDialog" #include <QtMath> #include <QPainter> #include <QPaintEvent> #include <QPointF> #include <QMessageBox> #include <QPropertyAnimation> #include <QTimer> using namespace std; #define OK 1 #define ERROR 0 #define MAXSIZE 100 typedef int Status; QT_BEGIN_NAMESPACE namespace Ui { class MainWindow; } QT_END_NAMESPACE struct node { int x; int y; char orientation; }; typedef struct snode { node pos; struct snode* next; }snode; typedef struct linkstack { snode* top; snode* bottom; int length; }linkstack; typedef struct { int rx; //位置x坐标 int cy; //位置y坐标 }Set; typedef struct { Set data[MAXSIZE]; int length; //路径长度 } PathType;//定义路径类型 struct Move { int x; int y; };//移动方向坐标 class MainWindow : public QMainWindow { Q_OBJECT public: MainWindow(QWidget *parent = nullptr); bool GenerateMaze(int irow, int icol, QString text); void readInput(); Status showPath(linkstack S); Status destroyStack(linkstack* S); ~MainWindow(); Status creat(linkstack *S); bool empty(linkstack S); int size(linkstack S); Status push(linkstack *S, node pos); Status pop(linkstack *S); Status gettop(linkstack S, node &pos); void paintPath(); void useStack(); void useRecursion(int xis, int yis, int xes, int yes, PathType paths, int maze[8][8]); private slots: void on_pushButton_clicked(); void on_pushButton_2_clicked(); void on_pushButton_3_clicked(); void on_pushButton_4_clicked(); void paintEvent(QPaintEvent *); private: Ui::MainWindow *ui; int row = 0; int col = 0; int flag = false; int num = 0; int minpath = 100, b = 0;//求最短路径 int maze[8][8] = {1}; QString str; Move mov[4] = { {-1,0},{0,1},{1,0},{0,-1} };//四个移动方向,右下左上 bool isCall = false; bool isDone = false; int pointCount = 1; int pathCount = 0; QLineEdit* input[MAXSIZE]; QTimer *timer; QPointF point; QPointF points[MAXSIZE]; QPointF path[MAXSIZE]; QPointF currentPoint; QPointF nextPoint; }; #endif // MAINWINDOW_H
main.cpp
#include "mainwindow.h" #include <QApplication> int main(int argc, char *argv[]) { QApplication a(argc, argv); MainWindow w; w.setWindowTitle("迷宫可视化"); w.setFixedSize(1200, 800); w.show(); return a.exec(); }
mainwindow.cpp
#include "mainwindow.h" #include "ui_mainwindow.h" /* 上N 左W x 东E 下S */ Status MainWindow::creat(linkstack* S) {//创建一个空栈 S->top = S->bottom = (snode*)malloc(sizeof(snode)); if (!S->top) { ui->label_3->setText("申请空间失败!"); return ERROR; } S->top->next = NULL; S->bottom->next = NULL; S->length = 0; return OK; } bool MainWindow::empty(linkstack S) {//判断栈是否为空 return !S.length; } int MainWindow::size(linkstack S) {//返回栈的大小 return S.length; } Status MainWindow::push(linkstack* S, node pos) {//元素入栈 snode* newx = (snode*)malloc(sizeof(snode));//新结点 if (!newx) {//创建失败 ui->label_3->setText("申请空间失败!"); return ERROR; } newx->pos = pos;//新结点的pos赋值 newx->next = S->top->next;//入栈 S->top->next = newx; if (!S->length)//length = 0 S->bottom = S->bottom->next; S->length++; return OK; } Status MainWindow::pop(linkstack* S) {//弹出栈顶元素 if (!S->length) { ui->label_3->setText("当前栈已经为空!"); return ERROR; } snode* del = S->top->next; S->top->next = del->next; free(del); S->length--; return OK; } Status MainWindow::gettop(linkstack S, node& pos) {//获得栈顶元素 存到pos中 if (!S.length) { ui->label_3->setText("当前栈已经为空!"); return ERROR; } pos = S.top->next->pos; return OK; } Status MainWindow::showPath(linkstack S) {//输出当前栈的内容 qDebug() << "showPath开始执行"; if (!S.length) { ui->label_3->setText("空!"); return ERROR; } snode* p = S.top->next; QString str = "栈:"; while (p) { QString s1 = QString::number(p->pos.x); QString s2 = QString::number(p->pos.y); QString s3; if(p->next && s1 == QString::number(p->next->pos.x) && s2 < QString::number(p->next->pos.y))//比如<1,1,E>→<1,2,x> s3 = QString("E"); if(p->next && s1 == QString::number(p->next->pos.x) && s2 > QString::number(p->next->pos.y))//比如<2,2,W>→<2,1,x> s3 = QString("W"); if(p->next && s2 == QString::number(p->next->pos.y) && s1 < QString::number(p->next->pos.x))//比如<1,1,S>→<2,1,x> s3 = QString("S"); if(p->next && s2 == QString::number(p->next->pos.x) && s1 > QString::number(p->next->pos.y))//比如<2,1,N>→<1,1,x> s3 = QString("N"); if(!(p->next)) { str += "<"+s1+","+s2 + ">"; } else { str += "<"+s1+","+s2+","+s3+">"; } path[pathCount] = QPointF(input[(p->pos.x - 1) * col + p->pos.y - 1]->pos().x() + 20,input[(p->pos.x - 1) * col + p->pos.y - 1]->pos().y() + 20); p = p->next; pathCount++; if(pathCount == 9) str += '\n'; qDebug() << str; } ui->label_3->setText(str); qDebug() << "showPath执行完毕"; return OK; } Status MainWindow::destroyStack(linkstack* S) {//销毁当前栈 snode* del; while (S->top) { del = S->top; S->top = S->top->next; free(del); } S->top = S->bottom = NULL; return OK; } void MainWindow::readInput()//读取用户在lineedit里输入的数据 { int k = 0; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { maze[i][j] = 1; } } for(int i = 0, m = 1; i < row; i++, m++)//显示lineedit { for (int j = 0, n = 1;j < col; j++, k++, n++) { if(j < col/2) maze[m][n] = input[k]->text().toInt(); else maze[m][n] = input[k]->text().toInt(); } } for (int i = 0; i < col*row; i++) { qDebug() << input[i]->text(); } for (int i = 0; i < 6; i++) { for (int j = 0; j < 6; j++) { qDebug() << "maze[i][j]" << i << j << maze[i][j]; } } qDebug() << "readInput执行完毕"; } bool MainWindow::GenerateMaze(int irow, int icol, QString text) { int k = 0; qDebug() << "GenerateMaze开始执行"; QFont font("黑体", 20, 75); //第一个属性是字体(微软雅黑),第二个是大小,第三个是加粗(权重是75) row = irow;//迷宫高度是行数 col = icol;//迷宫宽度是列数 QRegExp regx("[0-1]+$");//lineedit只允许设置0或1 for(int i = 0; i < row*col; i++)//生成row*col个lineedit { input[i] = new QLineEdit(QString::asprintf("0"), this);//最后一个参数一定为一个“父窗体”! input[i]->setMaxLength(1); input[i]->setAlignment(Qt::AlignHCenter);//内容居中显示 input[i]->setFont(font);//字体设置 if(i == 0) input[i]->setStyleSheet("background-color:green"); if(i == row*col - 1) input[i]->setStyleSheet("background-color:red"); QValidator *validator = new QRegExpValidator(regx, input[i]); input[i]->setValidator(validator); input[i]->hide(); input[i]->show(); } if(text != nullptr) { for (int i = 0; i < row*col; i++) { QString temp(text[i]); input[k++]->setText(temp); } } if(col%2)//col是奇数 { int k = 0; int x = 600 - 20 - col/2*80;//控件初始位置,1200/2 = 600,20是靠近中轴线的lineedit与中轴线的距离,两个lineedit距离为40,中轴线左边有col/2个lineedit和空挡。 int y = 40;//第一行lineedit和窗口顶部的距离 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { input[k++]->setGeometry(x + j*80, y + i*80,40,40); } } } else//col是偶数 { int k = 0; int x = 600 - 20 - col/2*40 - (col/2 - 1)*40; int y = 40; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { input[k++]->setGeometry(x + j*80, y + i*80,40,40); } } } for (int i = 0; i < row*col; i++) { points[i] = QPointF(input[i]->pos().x(), input[i]->pos().y()); } ui->pushButton->setEnabled(false);//一旦生成迷宫之后就不能再点击了,主要原因是input数组已经生成了,如果再点击,那么新生成的input也会出现在屏幕上,原先的linneedit不会消失 qDebug() << "GenerateMaze执行完毕"; return OK; } MainWindow::MainWindow(QWidget *parent) : QMainWindow(parent) , ui(new Ui::MainWindow) { ui->setupUi(this); ui->pushButton_2->setEnabled(false); ui->pushButton_4->setEnabled(false); } MainWindow::~MainWindow() { delete ui; } void MainWindow::on_pushButton_clicked()//生成迷宫按钮按下时 { GenerateMaze(ui->spinBox_2->value(),ui->spinBox->value(), nullptr);//出现迷宫 for (int i = 0; i < row*col; i++) input[i]->show(); ui->pushButton_2->setEnabled(true); } void MainWindow::on_pushButton_2_clicked()//运行按钮按下时 { readInput(); useStack(); // PathType paths; // paths.length = 0; //初始化路径长度 // useRecursion(1, 1, row, col, paths, maze); // ui->label_4->setText(str); // if (b == 0) // ui->label_4->setText("空!"); } void MainWindow::on_pushButton_3_clicked()//导入txt文件 { int irow = 0, icol = 0; QString text; QStringList infoList; //获取文件名 QString fileName = QFileDialog::getOpenFileName( this, tr("导入文件"), "", tr("text(*.txt)")); if (fileName.isEmpty()) { QMessageBox::warning(this, "错误", "打开文件失败!"); } else { QFile file(fileName); //打开文件 if(!file.open(QIODevice::ReadOnly | QIODevice::Text)) { qDebug()<<"无法打开!"<<endl; } //循环读取txt 并打印 while(!file.atEnd()) { QByteArray line = file.readLine(); QString str(line); if(str.contains("\n")) { str = str.replace("\n" , ""); } qDebug()<< str; icol = str.length() - 2; irow++; text += str.mid(1,icol); } irow -= 2; qDebug() << text; text = text.mid(icol,icol*irow); qDebug() << irow; qDebug() << icol; qDebug() << text; ui->pushButton_4->setEnabled(true); } GenerateMaze(irow, icol, text); } void MainWindow::on_pushButton_4_clicked()//导入txt文件后运行 { isCall = true; readInput(); int sx = 1, sy = 1, ex = row, ey = col;//sx,sy是startx,starty即迷宫起始位置,对应的是迷宫的下标,ex,ey是endx,endy是endx,endy即迷宫终点位置。 node now;//当前位置 now.x = sx; now.y = sy; now.orientation = 'E'; maze[sx][sy] = -1;//走过了 linkstack s; creat(&s);创建一个空栈 push(&s, now);//将now的信息亚展 while (!empty(s)) { gettop(s, now);//获得栈顶元素 存到now中 if (now.x == ex && now.y == ey)//now的x和y位置到达迷宫终点 break;//终点 if (!maze[now.x][now.y + 1]) {//右 为0表示可以走 now.orientation = 'E'; node next = now; next.y = now.y + 1;//向右走一步 maze[next.x][next.y] = -1;//走过了置-1 push(&s, next); continue; } //以下同理 if (!maze[now.x + 1][now.y]) {//下 now.orientation = 'S'; node next = now; next.x = now.x + 1; maze[next.x][next.y] = -1; push(&s, next); continue; } if (!maze[now.x][now.y - 1]) {//左 now.orientation = 'W'; node next = now; next.y = now.y - 1; maze[next.x][next.y] = -1; push(&s, next); continue; } if (!maze[now.x - 1][now.y]) {//上 now.orientation = 'N'; node next = now; next.x = now.x - 1; maze[next.x][next.y] = -1; push(&s, next); continue; } pop(&s); } linkstack path; creat(&path); node step; while (!empty(s)) { gettop(s, step); push(&path, step); pop(&s); }//换成正向 showPath(path); paintPath(); qDebug() << "执行完毕"; destroyStack(&s); destroyStack(&path); } void MainWindow::paintPath()//绘制路径函数 { timer = new QTimer(this); currentPoint = path[0]; nextPoint = path[1]; timer->start(50); qDebug() << "path0" << path[0]; qDebug() << "path1" << path[1]; qDebug() << "path2" << path[2]; qDebug() << "path3" << path[3]; qDebug() << "path4" << path[4]; qDebug() << "path5" << path[5]; qDebug() << "path6" << path[6]; qDebug() << "path[][]" << path[pathCount - 1]; connect(timer, &QTimer::timeout,this,[=](){ static int i = 0; static int j = 0; static int k = 2; double x = path[0].x() + 10*i; qDebug() << "x" << x; qDebug() << "i" << i; double y = path[0].y()+ 10*j; qDebug() << "y" << y; qDebug() << "j" << j; update(); if(x == nextPoint.x()) { point.setX(x); point.setY(y); if(y <= nextPoint.y()){ ++j;} else --j; if(y == nextPoint.y()) { // --j; currentPoint = QPointF(nextPoint.x(),nextPoint.y()); qDebug() << "currentPoint" << currentPoint; nextPoint = path[k++]; qDebug() << "nextPoint" << nextPoint; qDebug() << "到达一个点了"; pointCount++; if(x > nextPoint.x()) { --j; } if(x < nextPoint.x()) { --i; --j; } if(y < nextPoint.y()){} if(nextPoint == QPointF(0,0)){ input[row*col - 1]->setStyleSheet("background-color:green"); qDebug() << "已经到达终点"; timer->stop(); } } } if(y == nextPoint.y()) { point.setX(x); point.setY(y); if(x <= nextPoint.x()) ++i; else --i; if(x == nextPoint.x()) { currentPoint = QPointF(nextPoint.x(),nextPoint.y()); qDebug() << "currentPoint" << currentPoint; nextPoint = path[k++]; qDebug() << "nextPoint" << nextPoint; qDebug() << "到达一个点了"; pointCount++; if(x < nextPoint.x()){} if(y > nextPoint.y()) --i; if(y < nextPoint.y()) { --i; --j; } if(nextPoint == QPointF(0,0)){ input[row*col - 1]->setStyleSheet("background-color:green"); qDebug() << "已经到达终点"; timer->stop(); } } } qDebug() << x << "," << y; }); } void MainWindow::useStack() { isCall = true; int sx = 1, sy = 1, ex = row, ey = col;//sx,sy是startx,starty即迷宫起始位置,对应的是迷宫的下标,ex,ey是endx,endy是endx,endy即迷宫终点位置。 node now;//当前位置 now.x = sx; now.y = sy; now.orientation = 'E'; maze[sx][sy] = -1;//走过了 linkstack s; creat(&s);创建一个空栈 push(&s, now);//将now的信息入栈 while (!empty(s)) { gettop(s, now);//获得栈顶元素 存到now中 if (now.x == ex && now.y == ey)//now的x和y位置到达迷宫终点 break;//终点 if (!maze[now.x][now.y + 1]) {//右 为0表示可以走 now.orientation = 'E'; node next = now; next.y = now.y + 1;//向右走一步 maze[next.x][next.y] = -1;//走过了置-1 push(&s, next); continue; } //以下同理 if (!maze[now.x + 1][now.y]) {//下 now.orientation = 'S'; node next = now; next.x = now.x + 1; maze[next.x][next.y] = -1; push(&s, next); continue; } if (!maze[now.x][now.y - 1]) {//左 now.orientation = 'W'; node next = now; next.y = now.y - 1; maze[next.x][next.y] = -1; push(&s, next); continue; } if (!maze[now.x - 1][now.y]) {//上 now.orientation = 'N'; node next = now; next.x = now.x - 1; maze[next.x][next.y] = -1; push(&s, next); continue; } pop(&s); } linkstack path; creat(&path); node step; while (!empty(s)) { gettop(s, step); push(&path, step); pop(&s); }//换成正向 showPath(path); paintPath(); qDebug() << "执行完毕"; destroyStack(&s); destroyStack(&path); } void MainWindow::useRecursion(int xis, int yis, int xes, int yes, PathType paths, int maze[8][8]) { int k, i, j; str = "迷宫第" + QString::number(num) + "条路径如下:"; if (xis == xes && yis == yes) //找到出口,输出路径 { paths.data[paths.length].rx = xis; paths.data[paths.length].cy = yis; paths.length++; num++; if (paths.length < minpath) { minpath = paths.length; b = num; } for (k = 0; k < paths.length; k++) str += "(" + QString::number(paths.data[k].rx) + "," + QString::number(paths.data[k].cy) + ")" + " "; } else //(xis,yis)不是出口 { if (maze[xis][yis] == 0)//(xis,yis)可走 { for (int m = 0; m < 4; m++) // 找(xis, yis)的一个相邻位置(i, j) { i = xis + mov[m].x; j = yis + mov[m].y; paths.data[paths.length].rx = xis; paths.data[paths.length].cy = yis; paths.length++; maze[xis][yis] = -1; //避免重复找路径 useRecursion(i, j, xes, yes, paths, maze); paths.length--; //回退一个位置 maze[xis][yis] = 0; //恢复(xis,yis)为可走 } } } } void MainWindow::paintEvent(QPaintEvent *event) { Q_UNUSED(event); QPainter p(this); p.setRenderHint(QPainter::Antialiasing, true); p.setPen(QPen(Qt::green, 3)); if(isCall) { p.drawPolyline(path,pointCount); p.drawLine(currentPoint,point); } else{} }
UI布局
课程设计成绩最终也拿到了优秀,算是值了。不过由于时间匆忙,还有一些bug没有解决,但自己又懒,实在是不想再看咯。以上 如果此篇博客对您有帮助欢迎点赞与转发 有疑问请留言或私信 2021/1/12
-
数据结构 迷宫问题 C++ 栈方法
2018-01-30 18:25:37数据结构课程设计之C++编写的迷宫问题路径求解程序,使用的是栈方法,即将路径上每一步存在栈中,迷宫文件格式见程序提示,压缩包内已经给出了三个测试用的迷宫地图可用来测试,支持分步显示查找路径过程功能,当给... -
2.6 数据结构 迷宫问题
2020-03-11 11:49:40数据结构子目录https://www.jianshu.com/p/a344fa483655 题 有一个二维数组,表示迷宫(0为空,1为墙),求怎么走出迷宫。 问题 maze = [ [1,1,1,1,1,1,1,1,1,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,1,0,0,0,1... -
《数据结构迷宫问题实验报告》.doc
2019-12-14 11:25:49数据结构与算法设计 迷宫问题实验报告 实验二 专业物联网工程 班级物联网1班 学号15180118 姓名刘沛航 实验目的 ?本程序是利用非递归的方法求出一条走出迷宫的路径并将路径输出首先由用户输入一组二维数组来组成迷宫... -
数据结构迷宫问题_快速迭代器生成的数据结构
2021-01-21 14:42:49从去年4月开始更新的“极简数据结构”终于要完结了,目前已经上传了前9章视频,今年3月份会结束最后的第10章。从一开始,这个系列课程我就准备用快速迭代来完成,最初只有一个大概的初步提纲,其中的程序和具体讲义... -
尚硅谷Java数据结构 迷宫问题
2020-05-03 10:43:30public class duigui { public static void main(String[] args) { /* 思路 地图的创建 其中 1表示障碍物,2表示走过的路,3表示走过的路 但是路死了 决策 自由选择路径 可以先下->右->上->... -
数据结构迷宫问题实验报告
2010-03-23 17:39:41关于数据结构C的 严蔚敏般的 大二时做实验的 希望对你有帮助 -
数据结构迷宫问题(链式栈)
2019-11-04 20:45:04链式栈结构的实现 #include"fstream" #include<string> #include<iostream> using namespace std; #define OK 1 #define ERROR 0 typedef int SElemType; typedef int Status; typedef struct SNode ... -
数据结构迷宫问题C/C++链栈实现
2018-05-05 11:40:55更新:使用回溯法求解迷宫问题(获取最优路径) 原文章使用方法过于愚蠢,请忽略 说明 N 代表迷宫,A代表方位暂存器,V代表对应的N点是否被访问,AS代表方位存储器,Step代表下一步的操作。 #include<... -
数据结构迷宫问题_《数据结构和算法实践指南》第三章 栈和队列
2021-01-29 02:40:12本篇文章收录于《数据结构和算法实践指南》,意在帮助小伙伴们提升数据结构和算法实践能力,详情见前言。第3章需要掌握栈、队列以及其应用。基础题目(1)POJ 1363 Railshttp://poj.org/problem?id=1363poj.org(2... -
.数据结构迷宫问题的文档
2012-06-13 13:55:42a问题描述:以一个m * n的长方阵表示迷宫,0和1分别表示迷宫的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 b选做内容 (1)编写递归形式的算法,求得迷宫中... -
数据结构 迷宫问题逐渐形成的报告(bfs、栈)
2016-12-08 10:56:00实验四 图的搜索实验 ...3、明白编程的一些细节问题(加墙的问题、mark数组的问题) 此题目的是要找最短路径。 不能用dfs。因为dfs只能找到路的数量 而找到的不一定最短 -
求助。。在线等。数据结构迷宫问题,调试出错
2012-06-06 09:38:50编译没问题。用C-free调试,结果与书上不同,本来书上是能找出迷宫路径的、可C-free调试,不能通过了。换了VC6.0调,编译无误,可执行不了。一运行就提示cannot execute program.不知道怎么回事,大家帮帮在你们机器... -
java版数据结构解迷宫问题_C语言数据结构之迷宫问题
2021-03-14 12:21:53本文实例为大家分享了数据结构c语言版迷宫问题栈实现的具体代码,供大家参考,具体内容如下程序主要参考自严蔚敏老师的数据结构c语言版,在书中程序的大体框架下进行了完善。关于迷宫问题的思路可查阅原书。#include...