Chinaunix首页 | 论坛 | 博客
  • 博客访问: 496186
  • 博文数量: 80
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1916
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-11 22:01
个人简介

从事实时计算多年,熟悉jstorm/spark/flink/kafka/rocketMq, 热衷于开源,希望在这里和前辈们一起学习与分享,得到长足的进步!邮箱:hustfxj@gmail.com 我的githup地址是:https://github.com/hustfxj。欢迎和大家一起交流探讨问题。

文章分类

全部博文(80)

文章存档

2017年(11)

2015年(3)

2014年(33)

2013年(33)

分类: C/C++

2014-03-23 19:50:58

参照了文章:http://blog.csdn.net/afeiluo/article/details/9162631
该问题可以结合广度优先和深度优先


点击(此处)折叠或打开

  1. //迷宫问题---广度优先搜索-----队列
  2. #include <stdio.h>
  3. #include <queue>
  4. #include <iostream>
  5. using namespace std;
  6. #define MAX_ROW 5
  7. #define MAX_COL 5

  8. struct point
  9. {
  10.     int row;
  11.     int col;
  12. };

  13. queue<point> s;

  14. int maze[MAX_ROW][MAX_COL] =
  15. {
  16.     0,0,0,0,0,
  17.     0,0,0,1,0,
  18.     0,1,0,0,0,
  19.     0,0,0,0,0,
  20.     0,0,0,1,0
  21. };

  22. void print_maze()
  23. {
  24.     for(int i=0; i<MAX_ROW; ++i)
  25.     {
  26.         for(int j=0; j<MAX_COL; ++j)
  27.         {
  28.             printf("%d ",maze[i][j]);
  29.         }
  30.         printf("\n");
  31.     }
  32.     printf("************************\n");
  33. }

  34. struct point predecessor[MAX_ROW][MAX_COL] =
  35. {
  36.     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
  37.     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
  38.     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
  39.     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}},
  40.     {{-1,-1},{-1,-1},{-1,-1},{-1,-1},{-1,-1}}
  41. };

  42. void visit(int row,int col,struct point pre)
  43. {
  44.     point visit_point = {row,col};
  45.     maze[row][col] = 2;
  46.     predecessor[row][col] = pre;
  47.     s.push(visit_point);
  48. }

  49. int main()
  50. {
  51.     point p = {0,0};
  52.     maze[p.row][p.col] = 2;
  53.     s.push(p);
  54.     while(!s.empty())
  55.     {
  56.         p = s.front();
  57.         s.pop();
  58.         //抵达目的地
  59.         if(p.row == MAX_ROW-1 && p.col == MAX_COL-1)
  60.         {
  61.             break;
  62.         }

  63.         //向下移动
  64.         if(p.row+1 < MAX_ROW && maze[p.row+1][p.col]==0)
  65.         {
  66.             visit(p.row+1,p.col,p);
  67.         }

  68.         //向右移动
  69.         if(p.col+1 < MAX_COL && maze[p.row][p.col+1]==0)
  70.         {
  71.             visit(p.row,p.col+1,p);
  72.         }

  73.         //向上移动
  74.         if(p.col-1 >= 0 && maze[p.row][p.col-1]==0)
  75.         {
  76.             visit(p.row,p.col-1,p);
  77.         }
  78.         //向左移动
  79.         if(p.row-1>=0 && maze[p.row-1][p.col]==0)
  80.         {
  81.             visit(p.row-1,p.col,p);
  82.         }
  83.         print_maze();
  84.     }
  85.     if(p.row == MAX_ROW-1 && p.col == MAX_COL-1)
  86.     {
  87.         printf("(%d,%d)\n",p.row,p.col);
  88.         while(predecessor[p.row][p.col].row != -1)
  89.         {
  90.             p = predecessor[p.row][p.col];
  91.             printf("(%d,%d)\n",p.row,p.col);
  92.         }
  93.     }
  94.     else
  95.     {
  96.         cout <<"NO Path"<<endl;
  97.     }
  98.     return 0;
  99. }

阅读(1587) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~