Chinaunix首页 | 论坛 | 博客

韩轶明

首页　| 　博文目录　| 　关于我

enenshiwo

  • 博客访问： 260199
  • 博文数量： 84
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 927
  • 用 户 组： 普通用户
  • 注册时间： 2015-03-06 23:00
个人简介

growing

文章分类

全部博文（84）

文章存档

2017年（6）

2016年（61）

2015年（17）

我的朋友
最近访客
推荐博文
相关博文
【DS 】 迷宫问题 栈与递归

分类： C/C++

2015-03-07 17:46:40


点击(此处)折叠或打开

  1. template<class Type>
  2. class Stack
  3. {
  4.     public:
  5.         Stack()
  6.         {
  7.             capacity = STACK_SIZE;
  8.             base = new Type[capacity];
  9.             top = 0;
  10.         }
  11.         ~Stack()
  12.         {
  13.             capacity = 0;
  14.             delete []base;
  15.             base = NULL;
  16.             top = 0;
  17.         }
  18.     public:
  19.         bool isfull()const
  20.         {
  21.             return top >= capacity;
  22.         }
  23.         bool isempty()const
  24.         {
  25.             return top == 0;
  26.         }
  27.         void push(Type &x)
  28.         {
  29.             if(!isfull())
  30.             {
  31.                 base[top++] = x;
  32.             }
  33.         }
  34.         void pop()
  35.         {
  36.             if(!isempty())
  37.             {
  38.                 top--;
  39.             }
  40.         }
  41.         Type gettop()const
  42.         {
  43.             if(!isempty())
  44.             {
  45.                 return base[top-1];
  46.             }
  47.         }
  48.     private:
  49.         enum{STACK_SIZE=100};
  50.         Type *base;
  51.         size_t top;
  52.         size_t capacity;
  53. };

  55. /////////////////////////////////////////////
  56. #define ROW 10
  57. #define COL 10

  59. typedef enum
  60. {
  61.     RIGHT=1,
  62.     DOWN,
  63.     LEFT,
  64.     UP,
  65. }DIR;

  67. typedef int Maze[ROW][COL];//
  68. typedef struct Pos
  69. {
  70.     int x;
  71.     int y;
  72.     bool operator==(const Pos &p)
  73.     {
  74.         return ((x==p.x)&&(y==p.y));
  75.     }
  76. }Pos;

  78. typedef struct Man
  79. {
  80.     Pos pos;
  81.     DIR di;
  82. }Man;


  85. void ShowMaze(Maze maze)
  86. {
  87.     for(int i=0; i<10; ++i)
  88.     {
  89.         for(int j=0; j<10; ++j)
  90.         {
  91.             cout<<maze[i][j]<<" ";
  92.         }
  93.         cout<<endl;
  94.     }
  95. }

  97. bool Pass(Maze maze, Pos pos)
  98. {
  99.     return maze[pos.x][pos.y] == 0;
  100. }

  102. void FootMaze(Maze maze,Pos pos)
  103. {
  104.     maze[pos.x][pos.y] = 2;
  105. }

  107. Pos NextPos(Pos pos, DIR di)
  108. {
  109.     switch(di)
  110.     {
  111.     case RIGHT:
  112.         pos.y += 1;
  113.         break;
  114.     case DOWN:
  115.         pos.x += 1;
  116.         break;
  117.     case LEFT:
  118.         pos.y -= 1;
  119.         break;
  120.     case UP:
  121.         pos.x -= 1;
  122.         break;
  123.     }
  124.     return pos;
  125. }

  127. void MarkMaze(Maze maze, Pos pos)
  128. {
  129.     maze[pos.x][pos.y] = 4;
  130. }

  132. bool PassMaze(Maze maze,Pos start, Pos end)
  133. {
  134.     Man man; //pos di
  135.     Stack<Man> st;
  136.     Pos curpos = start;
  137.     do
  138.     {
  139.         if(Pass(maze,curpos))
  140.         {
  141.             man.pos = curpos;
  142.             man.di = RIGHT;
  143.             FootMaze(maze,man.pos);
  144.             if(curpos == end)
  145.                 return true;
  146.             st.push(man);
  147.             curpos = NextPos(man.pos,man.di);
  148.         }
  149.         else
  150.         {
  151.             if(!st.isempty())
  152.             {
  153.                 man = st.gettop();
  154.                 while(man.di==UP && !st.isempty())
  155.                 {
  156.                     st.pop();
  157.                     MarkMaze(maze,man.pos);
  158.                     if(!st.isempty())
  159.                     {
  160.                         man = st.gettop();
  161.                     }
  162.                     else
  163.                     {
  164.                         return false;
  165.                     }
  166.                     
  167.                 }
  168.                 if(man.di < UP)
  169.                 {
  170.                     st.pop();
  171.                     man.di = (DIR)(man.di+1);
  172.                     st.push(man);
  173.                     curpos = NextPos(man.pos,man.di);
  174.                 }
  175.             }
  176.         }
  177.     }while(!st.isempty());
  178.     return false;
  179. }

  181. void main()
  182. {
  183.     Pos start = {0,1};
  184.     Pos end = {9,8};
  185.     Maze maze =
  186.     {
  187.         {1,0,1,1,1,1,1,1,1,1},
  188.         {1,0,0,0,0,0,0,0,0,1},
  189.         {1,0,1,1,1,1,1,1,1,1},
  190.         {1,0,0,1,0,0,0,0,0,1},
  191.         {1,0,1,1,1,1,1,1,0,1},
  192.         {1,0,1,0,0,0,0,0,0,1},
  193.         {1,0,0,0,0,1,0,1,1,1},
  194.         {1,0,0,0,0,0,0,0,0,1},
  195.         {1,0,0,0,1,1,1,1,0,1},
  196.         {1,1,1,0,0,0,0,0,0,1}
  197.     };
  198.     ShowMaze(maze);
  199.     if(!PassMaze(maze,start,end))
  200.     {
  201.         cout<<"没有出路！"<<endl;
  202.         return;
  203.     }
  204.     cout<<"-------------------"<<endl;
  205.     ShowMaze(maze);

  207. }

阅读(1275) | 评论(0) | 转发(0) |
0

上一篇：【DS】hanoi问题 递归调用

下一篇：C练习小题

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6