基于QT实现dfs寻论算法的迷宫可视化

#include "mainwindow.h" #include "ui_mainwindow.h" #include<QDebug> #include<QLabel> #include<windows.h> #include<qtimer.h> #include <QThread> #include <QElapsedTimer> #include <QMessageBox> #include <QFileDialog> vector<vector<myPoint>>paths; MainWindow::MainWindow(QWidget *parent) : QMainWindow(parent) , ui(new Ui::MainWindow) { ui->setupUi(this); ui->widget->installEventFilter(this); connect(ui->GenerateMaze,&QPushButton::clicked,[=](){ Maze.clear(); ReadFile(); m=Maze.size()-2; n=Maze[0].size()-2; ui->label->setText("迷宫（绿色为起点与终点,白色为可通行路径，棕色为墙体）"); flag=1; update(); }); connect(ui->GeneratePathbyRecur,&QPushButton::clicked,[=](){ p_flag=0; ui->listWidget->clear(); paths.clear(); solution(); if(paths.size()==0){ QMessageBox::information(this,"提示","当前迷宫没有通路",QMessageBox::Ok); return; } QString tmp=QString("递归产生路径:共%1条").arg(QString::number(paths.size())); ui->label->setText(tmp); addItem(); }); connect(ui->StackAchieve,&QPushButton::clicked,[=](){ p_flag=1; ui->listWidget->clear(); paths.clear(); solution2(); if(paths.size()==0){ QMessageBox::information(this,"提示","当前迷宫没有通路",QMessageBox::Ok); return; } QString tmp=QString("栈产生路径:共%1条").arg(QString::number(paths.size())); ui->label->setText(tmp); addItem(); }); connect(ui->PathVisable,&QPushButton::clicked,[=](){ if(ui->PathNum->text()==""||ui->PathNum->text().toInt()>int(paths.size())||ui->PathNum->text().toInt()<=0){ QMessageBox::warning(this,"警告","未输入路径或路径不合法",QMessageBox::Ok); return; } Pathid=ui->PathNum->text().toInt()-1; flag=2; update(); }); } MainWindow::~MainWindow() { delete ui; } vector<int> split(QString str){ vector<int>nums; for(int i=0;i<str.size();i++){ if(str[i]=='0')nums.push_back(0); if(str[i]=='1')nums.push_back(1); } return nums; } void MainWindow::ReadFile(){ QString fileName=QFileDialog::getOpenFileName(this,tr("迷宫数据"),"E:/学习资料/数据结构/2022数据结构/栈/迷宫问题/",tr("Maze data (*.txt)")); QFile file(fileName); if(!file.open(QIODevice::ReadOnly | QIODevice::Text)) { QMessageBox::warning(this,"警告","文件打开失败",QMessageBox::Ok); } while(!file.atEnd()) { QByteArray line = file.readLine(); QString str(line); Maze.push_back(split(str)); } } bool MainWindow::eventFilter(QObject *watched, QEvent *event){ if(watched == ui->widget && event->type() == QEvent::Paint)//发生绘图事件，且是在label上发生的 { if(flag == 1)//标志位为1才在label上绘图，否者不绘图 { MyDraw(ui->widget); return true; } else if(flag==2){ MyDrawAns(ui->widget); return true; } else return false; } else return QMainWindow::eventFilter(watched,event);//其它绘图事件交给父类处理 } //绘制迷宫 void MainWindow::MyDraw(QLabel *widget){ int wid=widget->geometry().width(); int height=widget->geometry().height(); int x=wid/(n+2); int y=height/(m+2); QPen pen; //绘图前准备画笔、画刷 QBrush brush; //画刷。填充几何图形的调色板，由颜色和填充风格组成 QPainter painter; //可在QPaintDevice上绘制各种图形。QPaintDevice有之类QWidget、QImage、QOpenGLPaintDevice等 painter.begin(widget); painter.setPen(pen); for(int i=0;i<m+2;i++){ for(int j=0;j<n+2;j++){ if((i==1&&j==1)||(i==m&&j==n)){ brush.setColor(QColor(0,255,0)); } //画笔。绘制图形边线，由颜色、宽度、线风格等参数组成 //pen.setColor(QColor(255,0,0,255)); else if(Maze[i][j]==1){ brush.setColor(QColor(113,83,59)); } else{ brush.setColor(QColor(255,255,255)); } brush.setStyle(Qt::SolidPattern); painter.setBrush(brush); painter.drawRect(j*x,i*y,x,y); } } } void MainWindow::MyDrawAns(QLabel *widget){ int wid=widget->geometry().width(); int height=widget->geometry().height(); int x=wid/(n+2); int y=height/(m+2); QPen pen,pen2; //绘图前准备画笔、画刷 QBrush brush; //画刷。填充几何图形的调色板，由颜色和填充风格组成 pen2.setWidth(5); brush.setStyle(Qt::SolidPattern); QPainter painter,painter2; //可在QPaintDevice上绘制各种图形。QPaintDevice有之类QWidget、QImage、QOpenGLPaintDevice等 painter.begin(widget); painter.setPen(pen); for(int i=0;i<m+2;i++){ for(int j=0;j<n+2;j++){ if((i==1&&j==1)||(i==m&&j==n)){ brush.setColor(QColor(0,255,0)); } //画笔。绘制图形边线，由颜色、宽度、线风格等参数组成 //pen.setColor(QColor(255,0,0,255)); else if(Maze[i][j]==1){ brush.setColor(QColor(113,83,59)); } else{ brush.setColor(QColor(255,255,255)); } painter.setBrush(brush); painter.drawRect(j*x,i*y,x,y); } } if(p_flag==0){ pen2.setColor(QColor(255,0,0)); } else{ pen2.setColor(QColor(0,0,255)); } painter.setPen(pen2); painter.setBrush(brush); for (size_t i=0;i<paths[Pathid].size()-1;i++) { painter.drawLine(paths[Pathid][i].y*x+0.5*x,paths[Pathid][i].x*y+0.5*y,paths[Pathid][i+1].y*x+0.5*x,paths[Pathid][i+1].x*y+0.5*y); } } //递归实现 void MainWindow::dfs(vector<myPoint>&path,int i,int j,int **visited){ if(Maze[i][j]==1||visited[i][j]==1)return; myPoint p; p.x=i;p.y=j;p.di=-1; path.push_back(p); visited[i][j]=1; if(i==m&&j==n){ paths.push_back(path); visited[i][j]=0; path.pop_back(); return; } dfs(path,i-1,j,visited); dfs(path,i+1,j,visited); dfs(path,i,j-1,visited); dfs(path,i,j+1,visited); visited[i][j]=0; path.pop_back(); } void MainWindow::solution(){ int **visited=new int *[this->m+2]; int i; for (i=0;i<this->m+2;i++) { visited[i]=new int[this->n+2]; } vector<myPoint>path; for(int i=0;i<m+2;i++){ for(int j=0;j<n+2;j++){ visited[i][j]=0; } } dfs(path,1,1,visited); } //栈实现 void MainWindow::AchieveByStack(myStack& S,int **visited) { int i = 1, j = 1,di,flag; myPoint start(i, j, -1); S.push(start); visited[i][j] = 1; while (!S.isEmpty()) { myPoint cur = S.getTop(); i = cur.x; j = cur.y; di = cur.di; if (i == m && j == n) { vector<myPoint> path; int k = 0; while (k<=S.top) { path.push_back(S.data[k]); k++; } paths.push_back(path); visited[S.getTop().x][S.getTop().y] = 0; S.pop(); i = S.getTop().x; j = S.getTop().y; di = S.getTop().di; } flag = 0; while (flag == 0 && di < 4) { di++; switch (di) { case 0