加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

迷宫问题的最短路径与最长路径

(2016-08-26 18:08:10)
标签：

maze

maxlength

minlength

stack

queue

 分类： 算法
《原创》未经博主允许不可转载，转载请注明出处。

    本算法采用双端队列数据结构，以及回溯法
 
    使用回溯算法时，用的双端队列的堆栈功能，即FILO
    输出路径用的是双端队列的队列功能，即FIFO
 
  1. #include
  2. #include
  3.  
  4. using namespace std;
  5.  
  6. int mz[10][10]= {{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
  7.              {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
  8.              {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
  9.              {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
  10.              {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
  11.              {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
  12.              {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
  13.              {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
  14.              {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
  15.              {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};
  16.  
  17. struct route
  18. {
  19.    int x;
  20.    int y;
  21.    int dir;
  22. };
  23.  
  24. typedef route RT;
  25.  
  26. RT rt;
  27.  
  28. deque st;
  29. deque minLength,maxLength;
  30.  
  31. int main(int argc, char** argv)
  32. {
  33.    void findPath(int x1, int y1, int x2, int y2);
  34.    findPath(1,1,8,8);
  35.    return 0;
  36. }
  37.  
  38. void findPath(int x1, int y1, int x2, int y2)
  39. {
  40.    rt.x = x1;
  41.    rt.y = y1;
  42.    rt.dir = -1;
  43.    st.push_back(rt);
  44.  
  45.    int x,y;
  46.    int count = 0;
  47.  
  48.    while (st.size() != 0)
  49.    {
  50.       x = st.back().x;
  51.       y = st.back().y;
  52.       if (x == x2 && y == y2)
  53.       {
  54.          //min
  55.          if (minLength.size() == 0)
  56.          {
  57.             minLength = st;
  58.          }else if (minLength.size() > st.size()) {
  59.             minLength = st;
  60.          }
  61.  
  62.          if (maxLength.size() == 0)
  63.          {
  64.             maxLength = st;
  65.          }else if (maxLength.size() < st.size()) {
  66.             maxLength = st;
  67.          }
  68.          count++;
  69.          st.pop_back();
  70.       }
  71.  
  72.       RT rt1,rt2;
  73.       int direction;
  74.       bool find;
  75.  
  76.       rt1 = st.back();
  77.       direction = rt1.dir;
  78.       find = false;
  79.       mz[rt1.x][rt1.y] = -1;
  80.       while (direction < 3)
  81.       {
  82.          direction++;
  83.          switch (direction)
  84.          {
  85.          case 0:
  86.             if (mz[rt1.x - 1][rt1.y] == 0)
  87.             {
  88.                st.back().dir = direction;
  89.                rt2.x = rt1.x - 1;
  90.                rt2.y = rt1.y;
  91.                rt2.dir = -1;
  92.                find = true;
  93.             }
  94.             break;
  95.          case 1:
  96.             if (mz[rt1.x][rt1.y + 1] == 0)
  97.             {
  98.                st.back().dir = direction;
  99.                rt2.x = rt1.x;
  100.                rt2.y = rt1.y + 1;
  101.                rt2.dir = -1;
  102.                find = true;
  103.             }
  104.             break;
  105.          case 2:
  106.             if (mz[rt1.x + 1][rt1.y] == 0)
  107.             {
  108.                st.back().dir = direction;
  109.                rt2.x = rt1.x + 1;
  110.                rt2.y = rt1.y;
  111.                rt2.dir = -1;
  112.                find = true;
  113.             }
  114.             break;
  115.          case 3:
  116.             if (mz[rt1.x][rt1.y - 1] == 0)
  117.             {
  118.                st.back().dir = direction;
  119.                rt2.x = rt1.x;
  120.                rt2.y = rt1.y - 1;
  121.                rt2.dir = -1;
  122.                find = true;
  123.             }
  124.             break;
  125.          }
  126.  
  127.          if (find)
  128.          {
  129.             break;
  130.          }
  131.       }
  132.  
  133.       if (find)
  134.       {
  135.          st.push_back(rt2);
  136.       }
  137.       else if (st.size() != 0)
  138.       {
  139.          mz[st.back().x][st.back().y] = 0;
  140.          st.pop_back();
  141.       }
  142.  
  143.    }
  144.    
  145.    std::cout<<"====================最小的路径长度为: "<<minLength.size()<<"========================="<<endl;
  146.    std::cout<<"====================begin output================"<<endl;
  147.    RT rt1;
  148.    int i = 0;
  149.    while (minLength.size() != 1)
  150.    {
  151.       rt1 = minLength.front();
  152.       i++;
  153.       std::cout<<"( "<<rt1.x<<", "<<rt1.y<<")"<<" -> ";
  154.       minLength.pop_front();
  155.       if (i % 5 ==0)
  156.       {
  157.          i = 0;
  158.          std::cout<<endl;
  159.       }
  160.    }
  161.    rt1 = minLength.front();
  162.    std::cout<<"( "<<rt1.x<<", "<<rt1.y<<")";
  163.    minLength.pop_front();
  164.    std::cout<<endl;
  165.    std::cout<<"====================end output================"<<endl;
  166.  
  167.    std::cout<<"====================最大的路径长度为: "<<maxLength.size()<<"========================="<<endl;
  168.    std::cout<<"====================begin output================"<<endl;
  169.    i = 0;
  170.    while (maxLength.size() != 1)
  171.    {
  172.       rt1 = maxLength.front();
  173.       i++;
  174.       std::cout<<"( "<<rt1.x<<", "<<rt1.y<<")"<<" -> ";
  175.       maxLength.pop_front();
  176.       if (i % 5 ==0)
  177.       {
  178.          i = 0;
  179.          std::cout<<endl;
  180.       }
  181.    }
  182.    rt1 = maxLength.front();
  183.    std::cout<<"( "<<rt1.x<<", "<<rt1.y<<")";
  184.    maxLength.pop_front();
  185.    std::cout<<endl;
  186.    std::cout<<"====================end output================"<<endl;
  187.  
  188. }

喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有