预览效果:

Maze.pro文件

 #-------------------------------------------------
#
# Project created by QtCreator --26T14::
#
#------------------------------------------------- QT += core gui greaterThan(QT_MAJOR_VERSION, ): QT += widgets TARGET = Maze
TEMPLATE = app SOURCES += main.cpp\
mainwindow.cpp \
MAZE.cpp \
DijkstraWindow.cpp \
head.cpp HEADERS += mainwindow.h \
MAZE.h \
DijkstraWindow.h \
head.h FORMS += \
head.ui RESOURCES += \
img.qrc
DijkstraWindow.h文件
 #ifndef DIJKSTRAWINDOW_H
#define DIJKSTRAWINDOW_H #include <QWidget>
#include <iostream>
#include <QTime>
#include <QLineEdit>
#include <QPushButton>
#include <QPainter>
#include <QLabel>
#include <QMessageBox>
#include <QDebug>
#include <QKeyEvent>
#include <QPixmap>
#include <QTextEdit> class DijkstraWindow : public QWidget
{
Q_OBJECT public: DijkstraWindow(QWidget *parent = );
// void paintEvent(QPaintEvent *);
// void keyPressEvent(QKeyEvent *e);
void dijkstra();
void set_n(int tn){n = tn;}
int get_n(){return n;}
void set_m(int tm){m = tm;}
int get_m(){return m;}
~DijkstraWindow();
private:
QTextEdit *te_datain;
QPushButton *queding;
QLabel *bushu, *huafei, *bushuOut, *huafeiOut, *shuoming;
int n, m, s, t;
private slots:
void startDijkstra();
};
#endif // DIJKSTRAWINDOW_H

head.h文件

 #ifndef HEAD_H
#define HEAD_H #include <QWidget>
#include "DijkstraWindow.h"
#include "mainwindow.h" namespace Ui {
class Head;
} class Head : public QWidget
{
Q_OBJECT public:
explicit Head(QWidget *parent = );
~Head(); private slots:
void on_pushButton_clicked(); void on_pushButton_2_clicked(); private:
Ui::Head *ui;
DijkstraWindow d;
MainWindow w;
}; #endif // HEAD_H

mainwindow.h文件

 #ifndef MAINWINDOW_H
#define MAINWINDOW_H #include "MAZE.h"
#include <QMainWindow>
#include <QWidget>
#include <iostream>
#include <QTime>
#include <QLineEdit>
#include <QPushButton>
#include <QPainter>
#include <QLabel>
#include <QMessageBox>
#include <QDebug>
#include <QKeyEvent>
#include <QPixmap> class MainWindow : public QWidget
{
Q_OBJECT public:
MainWindow(QWidget *parent = );
void paintEvent(QPaintEvent *);
void keyPressEvent(QKeyEvent *e);
~MainWindow();
private:
QLabel *ql_shuru,*ql_bushu, *ql_bushuOut, *yongshi, *yongshiOut;
QLineEdit *infile;
QPushButton *queding;
QPushButton *zhaolu;
MAZE *m;
int X = ;
int Y = ;
bool bfs_fg = false;
private slots:
void startMaze();
void startBFS();
}; #endif // MAINWINDOW_H

MAZE.h文件

 #ifndef MAZE_H
#define MAZE_H static const int N = ; class MAZE
{
public:
int maze[N][N];
struct point
{
int x, y, pre;
}q[N*N], path[N*N];
MAZE();
void set_n(int tn);
int get_n();
int get_len_path(){return len_path;}
void set_len_path(int tn){len_path = tn;}
void printPath()
{
bfs();
for(int i = len_path-; i >= ; i--)
if(maze[path[i].x][path[i].y]==)
maze[path[i].x][path[i].y] = ;
}
void recoverPath()
{
for(int i = len_path-; i >= ; i--)
if(maze[path[i].x][path[i].y]==)
maze[path[i].x][path[i].y] = ;
}
void mazeInit();
int searchPath(int x, int y);
void print();
~MAZE();
private:
int n, len_path, nn;
void bfs();
void getPath(int pos);
}; #endif // MAZE_H
DijkstraWindow.cpp文件
 #include "DijkstraWindow.h"
#include <cstring>
#include <iostream>
#include <QString>
#include <QStringList> static const int maxn = ;
static const int inf = ;
int Tu_dist[maxn][maxn], Tu_pay[maxn][maxn], dis[maxn], pay[maxn], book[maxn]; DijkstraWindow::DijkstraWindow(QWidget *parent)
: QWidget(parent)
{
this->setFixedSize(,); shuoming = new QLabel(this);
shuoming->setText("说明:第一行输入4个数,分别表示\n点的个数,边的个数,起点,终点。\n之后每一行输入4个数u、v、d、p,\n表示u和v之间有一条长度为d的路,需\n要p的花费。给出图,可计算起点到终\n点的最短距离及其花费,如果最短距\n离有多条路线,则输出花费最少的。");
shuoming->setGeometry(, , , ); te_datain = new QTextEdit(this);
te_datain->setText("3 2 1 3\n1 2 5 6\n2 3 4 5");
te_datain->setGeometry(, , , ); queding = new QPushButton(this);
queding->setText("确定");
queding->setGeometry(, , , ); bushu = new QLabel(this);
bushu->setText("最短路径长度:");
bushu->setGeometry(, , , ); bushuOut = new QLabel(this);
bushuOut->setText("");
bushuOut->setGeometry(, , , ); huafei = new QLabel(this);
huafei->setText("花费:");
huafei->setGeometry(, , , ); huafeiOut = new QLabel(this);
huafeiOut->setText("");
huafeiOut->setGeometry(, , , ); connect(queding,SIGNAL(clicked()),this,SLOT(startDijkstra()));
} void DijkstraWindow::startDijkstra()
{ int a, b, d, p;
//QString str = te_datain->toPlainText();
int line_n=te_datain->document()->lineCount();
if(line_n != )
{
for(int i = ; i < line_n; i++)
{
QString str=te_datain->toPlainText().section('\n',i-line_n,i-line_n,QString::SectionSkipEmpty);
QStringList strlist=str.split(" ");
if(i == )
{
n = strlist[].toInt();
m = strlist[].toInt();
s = strlist[].toInt();
t = strlist[].toInt();
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
{
Tu_dist[i][j] =inf;
Tu_pay[i][j] = inf;
}
//std::cout<<n<<" "<<m<<" "<<s<<" "<<t<<std::endl;
}else
{
a = strlist[].toInt();
b = strlist[].toInt();
d = strlist[].toInt();
p = strlist[].toInt();
if(d<Tu_dist[a][b])
{
Tu_dist[a][b] = Tu_dist[b][a] = d;
Tu_pay[a][b] = Tu_pay[b][a] = p;
}
//std::cout<<a<<" "<<b<<" "<<d<<" "<<p<<std::endl;
}
} for(int i = ; i <= n; i++)
{
dis[i] = Tu_dist[s][i];
pay[i] = Tu_pay[s][i];
} memset(book, , sizeof(book));
book[s] = ;
dis[s] = ;
pay[s] = ; int mindist, u, v;
for(int i = ; i < n; i++)
{
mindist = inf;
for(int j = ; j <= n; j++)
{
if(book[j]==&&dis[j]<mindist)
{
mindist = dis[j];
u = j;
}
}
book[u] = ;
for(int v = ; v <= n; v++)
{
if(!book[v] && Tu_dist[u][v]<inf)
{
if(dis[v]>dis[u]+Tu_dist[u][v])
{
dis[v] = dis[u]+Tu_dist[u][v];
pay[v] = pay[u]+Tu_pay[u][v];
}
else if(dis[v]==(dis[u]+Tu_dist[u][v]))
pay[v] = (pay[u]+Tu_pay[u][v])<pay[v]?pay[u]+Tu_pay[u][v]:pay[v];
}
}
}
QString str;
bushuOut->setText(str.setNum(dis[t]));
huafeiOut->setText(str.setNum(pay[t])); update();
}
} DijkstraWindow::~DijkstraWindow()
{ }

head.cpp文件

 #include "head.h"
#include "ui_head.h" Head::Head(QWidget *parent) :
QWidget(parent),
ui(new Ui::Head)
{
ui->setupUi(this);
} Head::~Head()
{
delete ui;
} void Head::on_pushButton_clicked()
{
w.show();
} void Head::on_pushButton_2_clicked()
{
d.show();
}

main.cpp文件

 #include "head.h"
#include <QApplication> int main(int argc, char *argv[])
{
QApplication a(argc, argv);
Head h;
h.show(); return a.exec();
}

mainwindow.cpp文件

 #include "mainwindow.h"
#include "MAZE.h"
#include <iostream>
#include <time.h>
//#include <QTimer> #define size 20
using namespace std;
MainWindow::MainWindow(QWidget *parent)
: QWidget(parent)
{
int n = ;
m = new MAZE();
m->set_n(n);
m->mazeInit();
m->print();
//m->printPath();
this->setWindowTitle("迷宫");
this->setFixedSize((n+)*size,n*size);
//this->resize((n+10)*size,n*size);
this->setFocus(Qt::MouseFocusReason);
QPalette pa;
pa.setColor(QPalette::WindowText,Qt::black);
QFont ft;
ft.setPointSize(); ql_shuru = new QLabel(this);
ql_shuru->setText("迷宫大小");
ql_shuru->setPalette(pa);
ql_shuru->setFont(ft);
ql_shuru->setGeometry((n+)*size, *size, , ); infile = new QLineEdit(this);
infile->setText("");
infile->setGeometry((n+)*size, *size, , ); queding = new QPushButton(this);
queding->setText("创建");
queding->setGeometry((n+)*size, *size, ,); zhaolu = new QPushButton(this);
zhaolu->setText("找最短路");
zhaolu->setGeometry((n+)*size, (n-)*size, ,); ql_bushu = new QLabel(this);
ql_bushu->setText("最短路步数");
ql_bushu->setGeometry((n+)*size, (n-)*size, ,); //QString str;
ql_bushuOut = new QLabel(this);
//ql_bushuOut->setText(str.setNum(m->get_len_path()));
ql_bushuOut->setText("");
ql_bushuOut->setGeometry((n+)*size, (n-)*size, ,); yongshi = new QLabel(this);
yongshi->setText("用时");
yongshi->setGeometry((n+)*size, (n-)*size, ,); yongshiOut = new QLabel(this);
yongshiOut->setText("");
yongshiOut->setGeometry((n+)*size, (n-)*size, ,); connect(queding,SIGNAL(clicked()),this,SLOT(startMaze()));
connect(zhaolu,SIGNAL(clicked()),this,SLOT(startBFS()));
} MainWindow::~MainWindow()
{ } void MainWindow::paintEvent(QPaintEvent *)
{
QPainter painter(this);
// 反走样 painter.setRenderHint(QPainter::Antialiasing, true);
// 绘制图标 painter.drawPixmap(rect(), QPixmap(":/img/nwafu.jmp"));
//painter.setPen(Qt::black);
//painter.setRenderHint(QPainter::Antialiasing, true);// 设置画笔颜色、宽度
//painter.setPen(QPen(QColor(0, 160, 160), 1));
int n = m->get_n();
for(int i = ; i < n; i++)
{
for(int j = ; j < n; j++)
{
if(m->maze[i][j] ==){
painter.setPen(Qt::darkCyan);
painter.setBrush(QBrush(Qt::darkCyan,Qt::SolidPattern));
painter.drawRect(QRect(j*size,i*size,size,size));
}else if(m->maze[i][j] == ){
// painter.setPen(Qt::darkMagenta);
// painter.setBrush(QBrush(Qt::darkMagenta,Qt::SolidPattern));
// painter.drawRect(QRect(j*size,i*size,size,size));
painter.drawPixmap(j*,i*,,,QPixmap(":/new/prefix1/img/panda2.jpg").scaled(,));
}else if(m->maze[i][j] == ){
painter.setPen(Qt::red);
painter.setBrush(QBrush(Qt::red,Qt::SolidPattern));
painter.drawRect(QRect(j*size,i*size,size,size));
painter.drawPixmap(j*,i*,,,QPixmap(":/new/prefix1/img/bamboo.jpg").scaled(,));
}else if(m->maze[i][j] == ){
painter.setPen(Qt::white);
painter.setBrush(QBrush(Qt::white,Qt::SolidPattern));
painter.drawRect(QRect(j*size,i*size,size,size));
}else if(m->maze[i][j] == ){
// painter.setPen(Qt::darkGray);
// painter.setBrush(QBrush(Qt::darkGray,Qt::SolidPattern));
// painter.drawRect(QRect(j*size,i*size,size,size));
painter.drawPixmap(j*,i*,,,QPixmap(":/new/prefix1/img/foot.jpg").scaled(,));
}
}
}
} void MainWindow::keyPressEvent(QKeyEvent *e)
{
if(bfs_fg){
m->recoverPath();
bfs_fg = false;
ql_bushuOut->setText("");
update();
}
int tx = X, ty = Y;
int n = m->get_n();
if(e->key()==||e->key()==)//上
{
if(X> && m->maze[X-][Y] != )
{
X=X-;
}
}
else if(e->key()==||e->key()==)//下
{
if(X<n- && m->maze[X+][Y] != )
{
X=X+;
}
}
else if(e->key()==||e->key()==)//左
{
if(Y> && m->maze[X][Y-] != )
{
Y=Y-;
}
}
else if(e->key()==||e->key()==)//右
{ if(Y<n- && m->maze[X][Y+] != )
{
Y=Y+;
}
}
int tmp = m->maze[X][Y];
if(tmp == ){
QMessageBox::information(this,"提示","到达终点",QMessageBox::Yes);
}else{
m->maze[X][Y] = m->maze[tx][ty];
m->maze[tx][ty] = tmp;
}
update();
} void MainWindow::startMaze()
{
int n = infile->text().toInt();
//n = 2*n+2;
if(n<)n = ;
if(n>)n = ;
if(n% == )n++;
this->setFixedSize((n+)*size,n*size);
//this->resize((n+10)*size,n*size); // ql_shuru->setText("请输入迷宫的大小");
ql_shuru->setGeometry((n+)*size, *size, , );
infile->setGeometry((n+)*size, *size, , );
//queding->setText("创建");
queding->setGeometry((n+)*size, *size, ,);
//zhaolu->setText("找最短路");
zhaolu->setGeometry((n+)*size, (n-)*size, ,);
//ql_bushu->setText("最短路步数");
ql_bushu->setGeometry((n+)*size, (n-)*size, ,);
ql_bushuOut->setText("");
ql_bushuOut->setGeometry((n+)*size, (n-)*size, ,);
yongshi->setGeometry((n+)*size, (n-)*size, ,);
yongshiOut->setGeometry((n+)*size, (n-)*size, ,);
m->set_n(n);
m->mazeInit();
X = , Y = ;
this->setFocus(Qt::MouseFocusReason);
update();
} void MainWindow::startBFS()
{
time_t start, end;
time(&start);
m->printPath();
time(&end);
double cost = difftime(end,start);
QString str;
ql_bushuOut->setText(str.setNum(m->get_len_path()));
yongshiOut->setText(str.setNum(cost));
//cout<<"ok"<<endl;
bfs_fg = true;
this->setFocus(Qt::MouseFocusReason);
update();
}

MAZE.cpp文件

 #include "MAZE.h"
#include <iostream>
#include <windows.h>
#include <cstdio>
#include <cmath>
#include <time.h>
#include <cstring>
using namespace std;
int fa[N*N];
int dx[] = {, , -, };
int dy[] = {, , , -}; MAZE::MAZE(){} void MAZE::set_n(int tn)
{
n = tn;
nn = n/;
} int MAZE::get_n()
{
return n;
} void MAZE::print()
{
bfs();
// for(int i = 0; i < n; i++)
// {
// for(int j = 0; j < n; j++)
// cout<<maze[i][j]<<" ";
// cout<<endl;
// }
} void init()
{
for(int i = ; i < N*N; i++)
fa[i] = i;
} int getfa(int x)
{
if(fa[x] == x)return x;
else return fa[x] = getfa(fa[x]);
} void Merge(int a, int b)
{
int af = getfa(a);
int bf = getfa(b);
if(af != bf)
fa[bf] = af;
} int tolist(int x, int y, int n)
{
return x*n+y;
} void MAZE::mazeInit()
{
for(int i=; i<=nn*+; ++i)
for(int j=; j<=nn*+; ++j)
maze[i][j] = ; for(int i=, j=*nn+; i<=*nn+; ++i)
{
maze[i][] = ;
maze[i][j] = ;
}
for(int i=, j=*nn+; i<=*nn+; ++i)
{
maze[][i] = ;
maze[j][i] = ;
}
maze[][] = ;
maze[*nn][*nn+] = ; srand((unsigned)time(NULL));
searchPath(rand()%nn+, rand()%nn+); for(int i = ; i < n; i++)
{
for(int j = ; j < n; j++)
{
maze[i][j] = maze[i+][j+];
}
} len_path = ;
// int sx, sy, ex, ey, x, y;
// init();
// for(int i = 0; i < n; i++)
// for(int j = 0; j < n; j++)
// maze[i][j] = 1;
// for(int i = 1; i < n; i++)
// {
// if(i&1)
// for(int j = 1; j < n; j+=2)
// maze[i][j] = 0;
// }
// //print(n);
// //cout<<"*********************"<<endl;
// srand(time(NULL));
// int d;
// int tx1, ty1, tx2, ty2;
// sx = sy = 1;
// ex = ey = n-3; // //cout<<"ok"<<endl;
// maze[sx][sy] = maze[ex][ey] = 0;
// while(getfa(tolist(sx, sy, n)) != getfa(tolist(ex, ey, n)))
// {
// do
// {
// x = rand()%(n-2)+1;
// y = (rand()+2333)%(n-2)+1;
// }
// while(maze[x][y] != 1);
// d = x%2;
// if(!d)
// {
// tx1 = x+1;
// ty1 = y;
// tx2 = x-1;
// ty2 = y;
// if(getfa(tolist(tx1, ty1, n)) != getfa(tolist(tx2, ty2, n)))
// {
// maze[x][y] = 0;
// Merge(tolist(tx1, ty1, n), tolist(tx2, ty2, n));
// }
// }
// else
// {
// tx1 = x;
// ty1 = y+1;
// tx2 = x;
// ty2 = y-1;
// if(getfa(tolist(tx1, ty1, n)) != getfa(tolist(tx2, ty2, n)))
// {
// maze[x][y] = 0;
// Merge(tolist(tx1, ty1, n), tolist(tx2, ty2, n));
// }
// }
// }
// for(int i = 0; i < n; i++)
// {
// maze[i][n-1] = 1;
// maze[n-1][i] = 1;
// }
// maze[sx][sy] = 2;
// maze[ex][ey] = 3;
//print();
} int MAZE::searchPath(int x, int y)
{
static int dir[][] = {, , , , , -, -, };
int zx = x*;
int zy = y*;
int next, turn, i;
maze[zx][zy] = ;
turn = rand()% ? : ;
for(i=, next=rand()%; i<; ++i, next=(next+turn)%)
if(maze[zx+*dir[next][]][zy+*dir[next][]] == )
{
maze[zx+dir[next][]][zy+dir[next][]] = ;
searchPath(x+dir[next][], y+dir[next][]);
}
return ;
} void MAZE::getPath(int pos)
{
while(pos != -)
{
path[len_path].x = q[pos].x;
path[len_path].y = q[pos].y;
len_path++;
pos = q[pos].pre;
}
} void MAZE::bfs()
{
int front, tail, sx, sy;
for(int i = ; i < n; i++)
for(int j = ; j < n; j++)
if(maze[i][j] == )
{
sx = i; sy = j;
}
front = tail = ;
q[tail].x = sx;
q[tail].y = sy;
q[tail].pre = -;
tail++;
int x, y, nx, ny;
bool fg = false;
while(front < tail)
{
x = q[front].x;
y = q[front].y;
for(int i = ; i < ; i++)
{
nx = x+dx[i];
ny = y+dy[i];
if(nx>=&&nx<n&&ny>=&&ny<n&&maze[nx][ny]==)
{
maze[nx][ny] = ;
q[tail].x = nx;
q[tail].y = ny;
q[tail].pre = front;
tail++;
}
if(maze[nx][ny] == ){
q[tail].x = nx;
q[tail].y = ny;
q[tail].pre = front;
tail++;
fg = true;
len_path = ;
path[len_path].x = nx;
path[len_path].y = ny;
len_path++;
getPath(front);
}
}
if(fg)break;
front++;
}
for(int i = ; i < n; i++)
for(int j = ; j < n; j++)
if(maze[i][j] == )
maze[i][j] = ;
}

head.ui文件

 <?xml version="1.0" encoding="UTF-8"?>
<ui version="4.0">
<class>Head</class>
<widget class="QWidget" name="Head">
<property name="enabled">
<bool>true</bool>
</property>
<property name="geometry">
<rect>
<x>0</x>
<y>0</y>
<width>351</width>
<height>220</height>
</rect>
</property>
<property name="mouseTracking">
<bool>false</bool>
</property>
<property name="windowTitle">
<string>Maze</string>
</property>
<property name="windowIcon">
<iconset resource="img.qrc">
<normaloff>:/new/prefix1/img/xingong.jpg</normaloff>:/new/prefix1/img/xingong.jpg</iconset>
</property>
<property name="autoFillBackground">
<bool>false</bool>
</property>
<widget class="QPushButton" name="pushButton">
<property name="geometry">
<rect>
<x>50</x>
<y>140</y>
<width>101</width>
<height>51</height>
</rect>
</property>
<property name="font">
<font>
<family>微软雅黑</family>
<pointsize>12</pointsize>
<weight>75</weight>
<bold>true</bold>
</font>
</property>
<property name="styleSheet">
<string notr="true">background: rgb(0, 170, 127)</string>
</property>
<property name="text">
<string>Maze</string>
</property>
</widget>
<widget class="QPushButton" name="pushButton_2">
<property name="geometry">
<rect>
<x>200</x>
<y>140</y>
<width>101</width>
<height>51</height>
</rect>
</property>
<property name="font">
<font>
<family>微软雅黑</family>
<pointsize>12</pointsize>
<weight>75</weight>
<bold>true</bold>
</font>
</property>
<property name="cursor">
<cursorShape>ArrowCursor</cursorShape>
</property>
<property name="styleSheet">
<string notr="true">background: rgb(0, 170, 127)</string>
</property>
<property name="text">
<string>Dijkstra</string>
</property>
</widget>
<widget class="QFrame" name="frame">
<property name="geometry">
<rect>
<x>-1</x>
<y>-1</y>
<width>351</width>
<height>221</height>
</rect>
</property>
<property name="styleSheet">
<string notr="true">border-image: url(:/new/prefix1/img/mazeimg.jpg);</string>
</property>
<property name="frameShape">
<enum>QFrame::StyledPanel</enum>
</property>
<property name="frameShadow">
<enum>QFrame::Raised</enum>
</property>
</widget>
<zorder>frame</zorder>
<zorder>pushButton</zorder>
<zorder>pushButton_2</zorder>
</widget>
<resources>
<include location="img.qrc"/>
</resources>
<connections/>
</ui>

最新文章

  1. Linux下UPnP sample分析
  2. form表单提交问题
  3. 主流 SQLServer 迁移到 MySQL 工具对比
  4. Java排序算法——快速排序
  5. APP-SQLAP-10771:Could not reserve record (匹配PO时候)
  6. [Js]拖拽
  7. BufferedReader,缓冲输入字符流
  8. cocos2dx中的定时器及其分类
  9. PHP WAMP关闭notice等提示
  10. mvc annotation-driven作用
  11. css 三角实例
  12. Chrome开发者工具详解 (5):Application、Security、Audits面板
  13. .a与.framework的区别
  14. Bootstrap入门(三)&lt;p&gt;标签的css样式
  15. git常用命令学习笔记
  16. HDU - 4614 Vases and Flowers(二分+区间修改)
  17. VeeamOne(Free Edition 9.5 )-安装与配置
  18. ArcEngine获取要素数据集的容差和分辨率
  19. SQL Server2005/2008 作业执行失败的解决办法
  20. dede栏目添加自定义字段方法

热门文章

  1. Tasks and Back stack 详解
  2. windows 下nginx 虚拟主机搭建
  3. [iOS] 响应式编程开发-ReactiveCocoa(二)
  4. ICE BOX 配置,使用----第一篇
  5. HDU 5624 KK&#39;s Reconstruction
  6. javascript-函数及兼容
  7. MySQL-教学系统数据库设计
  8. 【动态规划】Gym - 101102A - Coins
  9. Nodejs之package.json介绍说明
  10. c++ split()实现