迷宫最短路径算法代码,C/C++代码库,德仔网

代码语言
代码分类
【C/C++】迷宫最短路径算法
作者:筱枚 / 发布于2016/8/14/ 813
#include "stdafx.h"
#include "Path.h"
Path::Path()
{
    px = 0;
    py = 0;
    step = 0;
    flag = 0;
    fp = NULL;
    bp = NULL;
    findDes = "";
}
 
int Path::Getflag()
{
    return this->flag;
}
 
Path::Path(int ix, int iy, int ifg)
{
    px = ix;
    py = iy;
    flag = ifg;
    fp = NULL;
    bp = NULL;
    step = 0;
}
 
void Path::AddFlag(Path* p, Path* p1)
{
    flag = 2;
    fp = p;
    step = p->step + 1;
    //如果p1->bp == p 说明现在开始用p1连接所有的step=this->step的点
    //否，则说明正连着，将此指针添加到父节点上
    if (p1->bp != p)
    {
        this->bp = p1->bp;
    }
    p1->bp = this;
}
//添加当前节点的子节点的兄弟节点
void Path::AddChildBroNode(Path* pCur, Path* pBr,string findDes)
{
    this->findDes = findDes;
    this->step = pCur->step + 1;
    this->fp = pCur;
    this->flag = 2;
    //如果不相等，则已经有兄弟节点了，将之前的兄弟节点组合一个链表
    //如果相等，则说明该节点为当前节点的第一个字节点
    if (pBr->bp != pCur)
    {
        this->bp = pBr->bp;
    }
     
    pBr->bp = this;
}
 
void Path::AddChildBroNode(Path* pCur, Path* pBr)
{
    this->step = pCur->step + 1;
    this->fp = pCur;
    this->flag = 2;
    //如果不相等，则已经有兄弟节点了，将之前的兄弟节点组合一个链表
    //如果相等，则说明该节点为当前节点的第一个字节点
    if (pBr->bp != pCur)
    {
        this->bp = pBr->bp;
    }
 
    pBr->bp = this;
}
 
//void GetPath()
//{
//  Path *p1 = new Path();
//  cout << "input two num that bigger 2,using space splite" << endl;
//  cin >> m >> n;
//  vector<vector<Path>>ce(m + 1, vector<Path>(n + 1));
//  for (int j = 1;j <= n;j++)   //j 为列数
//      for (int i = 1;i <= m;i++)     //i 为行数   
//      {
//          int f;
//          cin >> f;
//          getchar();
//          ce[i][j] = Path(i, j, f);
//      }
//  cout << "迷宫地形图" << endl;
//  for (int j = 1;j <= n;j++)
//  {
//      for (int i = 1;i <= m;i++)
//      {
//          cout << ce[i][j].flag;
//          cout << "(" << ce[i][j].px << ce[i][j].py << ")" << "";
//      }
//      cout << endl;
//  }
//  int bx, by;     //输入确定的x,y值
//  cout << "输入起点坐标和终点坐标" << flush;
//  cin >> bx >> by >> ex >> ey;
//  cout << bx << by << ex << ey << endl;
//  if (!ce[bx][by].Getflag())
//  {
//      cout << "起点为空" << endl;
//  }
//  //p 当前的位置
//  Path *p = &ce[bx][by];
//  p1->bp = p;
//  //当前坐标位置
//  int x = bx, y = by;
//  ce[bx][by].flag = 2;
//  while (p)
//  {
//      //if (dis(x, y, ex, ey) == 1)
//      //{
//      //  cout << "走到终点了！";
//      //  cout << "step=" << p->step;
//      //  while (p)
//      //  {
//      //      cout << "路径如下=" << "x=" << p->px << "y=" << p->py<<endl;
//      //      Path* fp = p->fp;            
//      //      p = fp;
//      //  }
//      //  break;
//      //}
//
//      if (IsEnd(x, y, ex, ey))
//      {
//          cout << "走到终点了！";
//          cout << "step=" << p->step;
//          while (p)
//          {
//              cout << "路径如下=" << "x=" << p->px << "y=" << p->py << endl;
//              Path* fp = p->fp;
//              p = fp;
//          }
//          break;
//      }
//
//      //对路径为1的点全方位扫描，并存储距离
//      if (y > 1 && ce[x][y - 1].flag == 1)
//          ce[x][y - 1].AddFlag(p, p1);
//      if (y < n&&ce[x][y + 1].flag == 1)
//          ce[x][y + 1].AddFlag(p, p1);
//      if (x > 1 && ce[x - 1][y].flag == 1)
//          ce[x - 1][y].AddFlag(p, p1);
//      if (x < m&&ce[x + 1][y].flag == 1)
//          ce[x + 1][y].AddFlag(p, p1);
//
//      if (p->bp)
//      {
//          p = p->bp;
//          x = p->px;
//          y = p->py;
//      }
//      else if (p != p1->bp)
//      {
//          p = p1->bp;
//          x = p->px;
//          y = p->py;
//      }
//      else
//      {
//          cout << "找不到合适的路径可以到达" << endl;
//          break;
//      }
//
//      cout << "x:" << x << "y:" << y << endl;
//  }
//  delete p1;
//}












#pragma once
#include <iostream>
using namespace std;
class Path
{
public:
    Path();
    explicit Path(int ix, int iy, int ifg);
 
public:
    int Getflag();
    void AddFlag(Path* p, Path *p1);
    void AddChildBroNode(Path *pCurr, Path *pBr,string findDes);
    void AddChildBroNode(Path *pCurr, Path *pBr);
public:
    int px;
    int py;
    int flag;    //0:不通  1:通   2:走过该点
    Path *fp;   //父指针，这是以后找路劲用的，只输出步数的话它就没什么用
    Path *bp;   //兄弟指针，通过它连在一起的点所花费的步数都相同
    int step;    //表示来到这里花了多少步
    string findDes;
};



//读取文件进行最优路径寻找
 
#include "stdafx.h"
#include "Path.h"
#include <iostream>
#include <string>
#include<fstream>  //用来打开文件
#include<stdlib.h>
#include <vector>
#include <map>
#include <tchar.h>
#include <sysinfoapi.h>
using namespace std;
 
static const int tv[3][4][3] = { { { 1,1,1 },{ 2,1,1 },{ 3,1,0 },{ 4,1,0 } },
{ { 1,2,1 },{ 2,2,1 },{ 3,2,1 },{ 4,2,1 } },
{ { 1,3,0 },{ 2,3,0 },{ 3,3,0 },{ 4,3,1 } } };
 
map<int,int>mpPoint;
vector<string>vDes;
vector<int>vPLine;
vector<int>vPRow;
 
 
vector<vector<Path>>ce;
 
static int iLm, iRm;  //行和列的数量
static int px=0;     //x点坐标
static int py=0;     //y点坐标
int iStep;      //计算可以走通的路的步数
 
static void OpenFile()
{
    ifstream myFile("binaaryImg.txt");
    //myFile.open;
    int line = 0;
    int num = 0;
    if (myFile.is_open())
    {
        char s[10000];  
        while (myFile.getline(s, 10000))
        {
            px = 0;     //将x坐标置为从1开始
            num = 0;
            vector<Path> rowCe;
            char *p = s;
            while (*p!='\0')
            {   
                //将值存入vectot中
                if (*p=='0'||*p=='1')
                {               
                    int flag = atoi(p);
                    num++;
    //              cout << "获取值=" << flag;
                    rowCe.push_back(Path(px, py, flag));
                    ++px;
                }
                ++p;
            }
            ++py;    //一行完毕后，y坐标增加
            line++;         
            ce.push_back(rowCe);
            /*cout << s << "end" << endl;
            cout << "当前行数=" << line << endl;
            cout << "该行数据总数=" << num << endl;*/
        }   
        int a = 9;
        iRm = num;
        iLm = line;
        myFile.close();
    }
}
 
static bool IsSuccess(int x, int y)
{
    return(x <= (iRm-1)&&y == (iLm-1));
}
 
bool FindPath_Copy(int sx, int sy)
{
    Path *pBr = new Path();      //保存兄弟指针列表
    int bx, by;     //开始的坐标位置
    int curx = 0, cury = 0;
    cout << "input entry point" << sx<<":"<<sy<<endl;
    bx = sx;
    by = sy;
//  cin >> bx >> by;
    Path *pCurr = &ce[by][bx]; //当前的指针
    if (pCurr->flag==1)
    {
        cout << "此点不能作为入口坐标" << endl;
        return false;
    }
    pBr->bp = pCurr;
    pCurr->flag = 2;
    curx = bx;
    cury = by;
    while (pCurr)
    {
        if (IsSuccess(curx, cury))
        {
            cout << "到达终点" << endl;
            cout << "step = " << pCurr->step << endl;
            cout << "Good!" << "已经找到一条路了，加油！" << endl;
        /*  while (pCurr)
            {*/
                 
            cout << "终点位置：" << pCurr->px << "," << pCurr->py << endl;
            cout << ",方向" << pCurr->findDes << endl;
            int a = 8;
    //          vPLine.insert(vPLine.begin(), (pCurr->py + 1));
    //          vPRow.insert(vPRow.begin(), pCurr->px + 1);
    //          vDes.insert(vDes.begin(), pCurr->findDes);
                /*vPLine.push_back(pCurr->py + 1);
                vPRow.push_back( pCurr->px + 1);
                vDes.push_back( pCurr->findDes);*/
    //          pCurr = pCurr->fp;
    //      }
    //      return true;
        }
 
        //初始化pBr->bp；防止不满足条件时，此值不变，造成死循环
        //如果此值一直为NULL，则表明该节点没有路可走
 
        if (curx > 0 && ce[cury][curx - 1].flag == 0)  //向左查找
        {
            ce[cury][curx - 1].AddChildBroNode(pCurr, pBr,"L");         
        }
 
        if (curx>0&& cury < (iLm - 1) && ce[cury + 1][curx - 1].flag == 0)    //左下查找
        {
            ce[cury + 1][curx - 1].AddChildBroNode(pCurr, pBr,"LD");
        }
 
        if (curx < (iRm - 1) && ce[cury][curx + 1].flag == 0)  //向右查找
        {
            ce[cury][curx + 1].AddChildBroNode(pCurr, pBr,"R");     
        }
 
        if (curx < (iRm - 1)&& cury < (iLm - 1) && ce[cury + 1][curx + 1].flag == 0)  //右下查找
        {
            ce[cury + 1][curx + 1].AddChildBroNode(pCurr, pBr,"RD");
        }
 
        if (cury > 0 && ce[cury - 1][curx].flag == 0)   //向上查找
            ce[cury - 1][curx].AddChildBroNode(pCurr, pBr,"U");
         
 
        if (cury > 0 && curx < (iRm - 1) && ce[cury - 1][curx + 1].flag == 0)  //右上角
            ce[cury - 1][curx + 1].AddChildBroNode(pCurr, pBr,"RU");
 
        if (curx > 0 && cury > 0&& ce[cury - 1][curx - 1].flag == 0)   //左上角()
            ce[cury - 1][curx - 1].AddChildBroNode(pCurr, pBr,"LU");
 
        if (cury < (iLm - 1) && ce[cury + 1][curx].flag == 0)   //向下查找
        {
            ce[cury + 1][curx].AddChildBroNode(pCurr, pBr,"D");
        }
 
        //遍历当前指针的所有兄弟
        if (pCurr->bp)
        {
            pCurr = pCurr->bp;
            curx = pCurr->px;
            cury = pCurr->py;
        }
        else if (pBr->fp == pBr->bp)     //从长兄开始，如果兄弟都没有子节点，则判定已经没有出路了
        {
            cout << "无路可逃了，重新规划路线" << endl;
            break;
        }
        else if (pCurr != pBr->bp)  //当前节点不是兄弟节点，则查找子节点
        {
            pCurr = pBr->bp;     
            curx = pCurr->px;
            cury = pCurr->py;
            pBr->fp = pCurr;
        }
        else        //当前节点为叶子节点了，则退出
        {
            cout << "无法走出迷宫，请检查数值是否正确" << endl;
            break;
        }
//      cout << "x" << curx << "y" << cury <<"Des"<<pCurr->findDes<<endl;
    }
 
    return false;
}
 
int main()
{
    OpenFile();
    int starttime = GetTickCount();
    if (FindPath_Copy(32, 10))   //32,10
    {
        /*  cout << "此点可以走通" << endl;
            int idx = 0;
            for (int idx=0;idx<vPLine.size();++idx)
            {
                cout << "走过的点（行，列,查找方向）:" << vPLine[idx] << "," << vPRow[idx] << "方向:" << vDes[idx] << endl;
            }*/
    }
    else
    {
        cout << "此路走不通" << endl;
    }
    int endtime = GetTickCount();
    int spendtime = endtime - starttime;
    cout << "共需时间" << spendtime << endl;
    return 0;
}
试试其它关键字
　迷宫　
同语言下
可能有用的
筱枚贡献的其它代码(13)