文章仅供学习，存在BUG
正常运行没问题
代码很水，不喜勿喷 o.o
第一次,请只运行下方代码，因为还未把数据放入文件中
//把数据写入文件中
int row = 10, col = 10;
int GameMap[10][10] =
{
{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 0, 1, 1 },
{ 1, 0, 1, 0, 1, 0 ,1, 0, 1, 1 },
{ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 1 },
{ 1, 0, 1, 0, 1, 0, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
};
FILE *pchar = fopen("3.Map", "wb");
fwrite(&row, sizeof(int), 1, pchar);
fwrite(&col, sizeof(int), 1, pchar);
for (int i = 0; i < row; i++)
{
fwrite(GameMap[i], sizeof(int)*col, 1, pchar);
}
fclose(pchar);
Main.cpp
#includeCMyPoint.h文件以及.cpp文件#include #include #include
#include "CMyPoint.h" #include "GameMap.h" using namespace std; CMyPoint *Near[4] = { new CMyPoint(1, 0), new CMyPoint(-1, 0), new CMyPoint(0, -1), new CMyPoint(0, 1) }; //开始的地方 CMyPoint StartPoint = { 0, 1 };//stack上一个节点 CMyPoint LastPathPoint;//记录stack的最后一个节点 CMyPoint EndPoint = { 9, 8 };//胜利点 bool IsDeadEnd = false;//是否是死胡同 bool IsVictory = false;//是否已经胜利 //使用栈来实现DFS stack pathStack;//删节点(正常运行) list MinPathList;//所有路径存放的链表 list LastPathList;//每条寻路最后的路径 list TempList;//临时链表，存储栈内元素 //从文件中读取数据 CGameMap *gameMap = new CGameMap("3.Map");//地图初始化 void PushStack(CMyPoint pointTemp) { //判断该点周围四个点是否可以过 for (int i = 0; i < 4; i++) { int xTemp = pointTemp.x + (*Near[i]).x; int yTemp = pointTemp.y + (*Near[i]).y; //进入点判断该店是否超过边界 if (xTemp < gameMap->Get_Row() && yTemp < gameMap->Get_Col() && xTemp > 0 && yTemp> 0 ) { if (0 == gameMap->Get_GameMap()[pointTemp.x + (*Near[i]).x][pointTemp.y + (*Near[i]).y] || 6 == gameMap->Get_GameMap()[pointTemp.x + (*Near[i]).x][pointTemp.y + (*Near[i]).y]) { //将这个这个节点放入栈中 CMyPoint pointTempTemp(pointTemp.x + (*Near[i]).x, pointTemp.y + (*Near[i]).y); pathStack.push(pointTempTemp); } } } } //使LastPathList遇到死胡同能够删除到下一个空地 void DelelteList() { while (!LastPathList.empty()) { //判断该店周围四个点是否可以过 for (int i = 0; i < 4; i++) { int xTemp = LastPathList.back().x + (*Near[i]).x; int yTemp = LastPathList.back().y + (*Near[i]).y; //进入点判断该店是否超过边界 if (xTemp < gameMap->Get_Row() && yTemp < gameMap->Get_Col() && xTemp > 0 && yTemp> 0) { if (0 == gameMap->Get_GameMap()[xTemp][yTemp] || 6 == gameMap->Get_GameMap()[xTemp][yTemp]) { return; } } } //四次循环后,发现周围没有0 //直接删除链表最后一个节点 //gameMap->Get_GameMap()[LastPathList.back().x][LastPathList.back().y] = 0; LastPathList.pop_back(); } cout << "这是个死胡同" << endl; exit(0); } //最后成功的路径转入MinPathList中 void LPathToMList() { list ::iterator it_List = LastPathList.begin(); for (; it_List != LastPathList.end(); ++it_List) { MinPathList.push_back(*it_List); } } //输出LastPathList路径 void DisplayLastList() { static int i = 1; gameMap->InitMap("3.Map"); //输出最终路径 list ::iterator it_list = LastPathList.begin(); for (; it_list != LastPathList.end(); it_list++) { StartPoint = *it_list; gameMap->Get_GameMap()[StartPoint.x][StartPoint.y] = 3; system("CLS"); gameMap->DisPlayMap(); } cout << "第" << i++ << "条路径" << "已经成功达到胜利点" << endl; system("PAUSE"); } //胜利后，让LastList删到stack最后一个节点的位置的附近 void DelelteLastToStackEnd() { while (true) { for (int i = 0; i < 4; i++) { int xTemp = LastPathList.back().x + (*Near[i]).x; int yTemp = LastPathList.back().y + (*Near[i]).y; //进入点判断该店是否超过边界 if (xTemp < gameMap->Get_Row() && yTemp < gameMap->Get_Col() && xTemp > 0 && yTemp> 0) { CMyPoint pointTemp(xTemp, yTemp); if (pointTemp == LastPathPoint) { //加上pathstack最后一个 LastPathList.push_back(pathStack.top()); return; } } } LastPathList.pop_back(); } } //检查第二条路径之后下Last是否进入死胡同 void CheckDeadEnd() { //看是否是死胡同就看stackTemp里面的第一个节点 //如果不是死胡同return if (pathStack.top() != LastPathPoint) { return; } else { cout << "该路径为死胡同" << endl; //如果是死胡同 //地图初始化 gameMap->InitMap("3.Map"); //lastPathlist删除到stack最后一个 DelelteLastToStackEnd(); //让last路径全部变成3 list ::iterator it_list = LastPathList.begin(); for (; it_list != LastPathList.end(); it_list++) { StartPoint = *it_list; gameMap->Get_GameMap()[StartPoint.x][StartPoint.y] = 3; system("CLS"); gameMap->DisPlayMap(); } } } void FindMinPath() { //开始找最小的路径 list ::iterator it_list = MinPathList.begin(); list ::iterator it_start1 = MinPathList.begin(); list ::iterator it_end1; list ::iterator it_start2; list ::iterator it_end2; int flag = 1; int Maxsize = 0; int size = 0; bool IsAddIt_list; while (it_list != MinPathList.end()) { size++; IsAddIt_list = false;//是否已经自加 if ((*it_list) == EndPoint) { ++flag; if (flag == 2)//分配第一路径 { it_end1 = it_list; it_start2 = it_list++;//★★★★这里自加了注意 Maxsize = size; size = 0; IsAddIt_list = true; } else//之后的路径 { //第一步将end2存入 it_end2 = it_list; if (size > Maxsize)//第二个路径大于第一个路径 { size = 0; it_start2 = it_list = MinPathList.erase(it_start2, it_end2); } else//第二个路径小于第一个路径 { Maxsize = size; it_start1 = MinPathList.erase(it_start1, it_end1); it_end1 = it_end2; it_start2 = ++it_list; IsAddIt_list = true; } } } if (!IsAddIt_list) { it_list++; } } gameMap->InitMap("3.Map"); it_list = MinPathList.begin(); for (; it_list != MinPathList.end(); it_list++) { gameMap->Get_GameMap()[(*it_list).x][(*it_list).y] = 3; system("CLS"); gameMap->DisPlayMap(); } cout << "最短路径如上" << endl; cout << "该路径长度为:" << Maxsize << endl; } int main() { //把数据写入文件中 int row = 10, col = 10; int GameMap[10][10] = { { 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 1, 1, 1, 0, 1, 1 }, { 1, 0, 1, 0, 1, 0, 0, 0, 1, 1 }, { 1, 0, 1, 0, 1, 0 ,1, 0, 1, 1 }, { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1 }, { 1, 0, 1, 0, 1, 0, 1, 0, 1, 1 }, { 1, 0, 1, 0, 1, 0, 1, 1, 1, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 }, }; FILE *pchar = fopen("3.Map", "wb"); fwrite(&row, sizeof(int), 1, pchar); fwrite(&col, sizeof(int), 1, pchar); for (int i = 0; i < row; i++) { fwrite(GameMap[i], sizeof(int)*col, 1, pchar); } fclose(pchar); //gameMap->MemeroyMap(); LastPathList.push_back(StartPoint); while (true) { system("CLS"); gameMap->DisPlayMap(); //入栈 PushStack(StartPoint); if (pathStack.empty()) { //所有路径都被走过 cout << "所有路径都被走过" << endl; system("pause"); break; } //检测路径是否是死胡同 CheckDeadEnd(); //进入胜利点的路径链表 LastPathList.push_back(pathStack.top()); StartPoint = pathStack.top(); gameMap->Get_GameMap()[StartPoint.x][StartPoint.y] = 3; pathStack.pop(); //该路径到达胜利点 if (StartPoint == EndPoint) { pathStack.pop(); //这里是显示正确 system("CLS"); gameMap->DisPlayMap(); //打印路径 DisplayLastList(); //把最终路径放到Min路径里面取 LPathToMList(); if (pathStack.empty()) { //所有路径都被走过 cout << "所有路径都被走过" << endl; system("pause"); break; } //把LastPath删到stack 的最后一个节点位置 DelelteLastToStackEnd(); IsVictory = true; } //记录stack最后一个节点 if (!pathStack.empty())// { LastPathPoint = pathStack.top(); IsVictory = false; } //删除list里面的死胡同节点 DelelteList(); } gameMap->InitMap("3.Map"); FindMinPath(); return 0; }
#ifndef __CMYPOINT_H__
#define __CMYPOINT_H__
class CMyPoint
{
public:
CMyPoint();
CMyPoint(int x, int y);
//重载 ==
bool operator==(const CMyPoint &point);
//重载 !=
bool operator!=(const CMyPoint &point);
~CMyPoint();
int x;
int y;
};
#endif //__CMYPOINT_H__
#include "CMyPoint.h"
CMyPoint::CMyPoint()
{
this->x = 0;
this->y = 0;
}
CMyPoint::CMyPoint(int x, int y)
{
this->x = x;
this->y = y;
}
//重载 ==
bool CMyPoint::operator==(const CMyPoint &point)
{
if (this->x == point.x &&this->y == point.y)
{
return true;
}
else
{
return false;
}
}
//重载 !=
bool CMyPoint::operator!=(const CMyPoint &point)
{
if (this->x == point.x &&this->y == point.y)
{
return false;
}
else
{
return true;
}
}
CMyPoint::~CMyPoint()
{
}
GameMap.h文件
#ifndef __GAMEMAP_H__
#define __GAMEMAP_H__
class CGameMap
{
public:
CGameMap();
CGameMap(char *pPositon);
void MemeroyMap();
void InitMap(char *pPositon);
void DisPlayMap();
~CGameMap();
int Get_Row() const { return m_Row; }
void Set_Row(int val) { m_Row = val; }
int Get_Col() const { return m_Col; }
void Set_Col(int val) { m_Col = val; }
int ** Get_GameMap() const { return m_GameMap; }
void Set_GameMap(int ** val) { m_GameMap = val; }
private:
int m_Row;
int m_Col;
int **m_GameMap;
};
#endif //__GAMEMAP_H__
GameMap.Cpp文件
析构函数没有写的哈
#include "GameMap.h" #includeusing namespace std; CGameMap::CGameMap() { this->Set_GameMap(nullptr); this->m_Row = 0; this->Set_Col(0); } CGameMap::CGameMap(char *pPositon) { //从文件中得到数据 FILE *pfile = fopen(pPositon, "rb"); fread(&this->m_Row, sizeof(int), 1, pfile); fread(&this->m_Col, sizeof(int), 1, pfile); fclose(pfile);//关闭文件，光标重置 //申请动态内存 this->Set_GameMap(new int*[m_Row]); for (int i = 0; i < m_Row; i++) { this->Get_GameMap()[i] = new int[Get_Col()]; } pfile = fopen(pPositon, "rb"); fseek(pfile, sizeof(int) * 2, SEEK_SET); for (int i = 0; i < m_Row; i++) { fread(Get_GameMap()[i], sizeof(int)*m_Col, 1, pfile); } fclose(pfile); } void CGameMap::InitMap(char *pPositon) { //从文件中得到数据 FILE *pfile = fopen(pPositon, "rb"); fread(&this->m_Row, sizeof(int), 1, pfile); fread(&this->m_Col, sizeof(int), 1, pfile); fclose(pfile);//关闭文件，光标重置 //申请动态内存 this->Set_GameMap(new int*[m_Row]); for (int i = 0; i < m_Row; i++) { this->Get_GameMap()[i] = new int[Get_Col()]; } pfile = fopen(pPositon, "rb"); fseek(pfile, sizeof(int) * 2, SEEK_SET); for (int i = 0; i < m_Row; i++) { fread(Get_GameMap()[i], sizeof(int)*m_Col, 1, pfile); } fclose(pfile); } void CGameMap::DisPlayMap() { for (int i = 0; i < m_Row; i++) { for (int j = 0; j < Get_Col(); j++) { switch (this->Get_GameMap()[i][j]) { case 0: cout << " "; break; case 1: cout << "■"; break; case 2: case 7: cout << "♀"; break; case 3: cout << "●"; break; case 4: cout << "酪"; break; case 5: cout << "入"; break; case 6: cout << "出"; break; case 9: cout << "☆"; break; } } cout << endl; } } void CGameMap::MemeroyMap() { FILE *pchar = fopen("1.Map", "wb"); fwrite(&this->m_Row, sizeof(int), 1, pchar); fwrite(&this->m_Col, sizeof(int), 1, pchar); for (int i = 0; i < m_Row; i++) { fwrite(Get_GameMap()[i], sizeof(int)*m_Col, 1, pchar); } fclose(pchar); // fwrite(GameMap, sizeof(int), row*col, pfile);//不要漏掉指针 } CGameMap::~CGameMap() { //析构没有写的哈 }
兄弟们，有问题，可以在下方评论区讨论。
