迷宫递归算法

迷宫，递归实现：

  1 /*
  2     迷宫之递归，能够输出所有的路线。
  3 */
  4 #include <iostream>
  5 #include <time.h>
  6 using namespace std;
  7 typedef struct Position{
  8     int x;
  9     int y;
 10 }POSITION,*pPOSiTION;
 11 
 12 int MazeMapLineNumber =0;
 13 pPOSiTION pMazePath;
 14 int PathLength = 0;
 15 bool IsOutOfBorder(int x,int y);
 16 void Go(pPOSiTION pos);//将当前位置放入迷宫路线中
 17 void Try(int **pMap,pPOSiTION begin,pPOSiTION end);//开始找路
 18 bool Showpath();
 19 int main() {
 20     int **pMap = NULL;
 21     pPOSiTION begin = new POSITION;
 22     pPOSiTION end = new POSITION;
 23     int i=0,j=0;
 24     srand((unsigned)time(NULL));
 25     cout<<"Please input the row of the maze map:";
 26     cin>>MazeMapLineNumber;
 27     pMap = new int *[MazeMapLineNumber];
 28     for (i=0;i<MazeMapLineNumber;i++) {
 29         pMap[i] = new int [MazeMapLineNumber];
 30     }
 31 
 32     //动态生成一个二维数组，用于地图
 33     for (i=0;i<MazeMapLineNumber;i++) {
 34         for (j=0;j<MazeMapLineNumber;j++) {
 35             pMap[i][j] = rand()%2;
 36             cout<<pMap[i][j]<<" ";
 37         }
 38         cout<<"\n";
 39     }
 40     cout<<endl;
 41     //该for循环主要输出对应点的坐标，节省输入时间。
 42     for (i=0;i<MazeMapLineNumber;i++) {     
 43         for (j=0;j<MazeMapLineNumber;j++) {
 44             cout<<pMap[i][j]<<"("<<i<<","<<j<<")"<<" ";
 45         }
 46         cout<<"\n";
 47     }
 48     pMazePath = new POSITION[MazeMapLineNumber*MazeMapLineNumber];
 49     cout<<"Please input start's x and y:";
 50     cin>>begin->x>>begin->y;
 51     cout<<"Please input end's x and y:";
 52     cin>>end->x>>end->y;
 53     Go(begin);
 54     pMap[begin->x][begin->y] = 0;
 55     Try(pMap,begin,end);
 56 
 57     if(PathLength == 0) cout<<"There is no way to pass the maze"<<endl;
 58     return 0;
 59 }
 60 
 61 
 62 
 63 bool IsOutOfBorder(int x,int y) {
 64     if(x<0||x>=MazeMapLineNumber||y<0||y>=MazeMapLineNumber) return true;
 65     else return false;
 66 }
 67 
 68 void Go(pPOSiTION pos){
 69     pMazePath[PathLength].x=pos->x;
 70     pMazePath[PathLength].y=pos->y;
 71     PathLength++;
 72 }
 73 void Try(int **pMap,pPOSiTION begin,pPOSiTION end) {
 74     POSITION NextPos[4] = {{0,1},{1,0},{0,-1},{-1,0}};
 75     pPOSiTION next = new POSITION;
 76     next->x = begin->x;
 77     next->y = begin->y;
 78     //cout<<"next1:"<<next->x<<","<<next->y<<endl;    //方便调试。。下同
 79     int i=0;
 80     if(next->x==end->x && next->y==end->y) {
 81         Showpath();
 82     } else {
 83         for (i=0;i<4;i++) {
 84             //cout<<"begin1:"<<begin->x<<","<<begin->y<<endl;  
 85             next->x =begin->x + NextPos[i].x;
 86             next->y =begin->y + NextPos[i].y;
 87             //cout<<"begin2:"<<begin->x<<","<<begin->y<<endl;
 88             if(!IsOutOfBorder(next->x,next->y)&&pMap[next->x][next->y]==1) {
 89                 Go(next);
 90                 pMap[next->x][next->y] = 0;//将当前的点置为不可行
 91                 //cout<<"next2:"<<next->x<<","<<next->y<<endl;
 92                 Try(pMap,next,end);
 93                 pMap[next->x][next->y] = 1;//恢复可行，让下一次可以使用该点
 94                 PathLength--;//迷宫路线长度-1，代表该路线已经探索完毕。
 95             }
 96         }
 97     }
 98 
 99 }
100 
101 bool Showpath() {
102     static int num;
103     if(PathLength == 0) {
104         cout<<"There is no way to pass the maze"<<endl;
105         return false;
106     }
107     cout<<"Path"<<num++<<":"<<endl;
108     for(int i=0;i<PathLength-1;i++) {
109         cout<<"("<<pMazePath[i].x<<","<<pMazePath[i].y<<")"<<"->";
110     }
111     cout<<"("<<pMazePath[PathLength-1].x<<","<<pMazePath[PathLength-1].y<<")"<<endl;
112     return true;
113 }

Maze.cpp

之前用栈写了一个迷宫，但是无法输出全部路线，现在学到递归函数了，发现能够全部输出全部的路线
递归虽然占用资源，但是用起来却是很方便。一步一步踏踏实实的向前进行！加油！

顺带一个汉诺塔的小函数,同样是递归

 1 /*
 2 汉诺塔算法：1：将A上的n-1个盘子借助C移到B上。
 3             2：将A上的第n个盘子移到C上。
 4             3：将B上的n-1盘子借助A移到C上。
 5 */
 6 #include <stdio.h>
 7 void game(int n,char A,char B,char C);//将A上的盘子借助B移动到C
 8 int main() {
 9     char A = 'A',B='B',C='C';
10     game(2,A,B,C);
11     return 0;
12 }
13 
14 void game(int n,char A,char B,char C) {
15     if(1 == n) {
16         printf("Please put plate %d to %c from %c \n",n,C,A);
17     } else {
18         game(n-1,A,C,B);
19         printf("Please put plate %d to %c from %c \n",n,C,A);
20         game(n-1,B,A,C);    
21     }    
22 }

Hanoi.coo

上述两个应该都算入门级递归算法吧。为以后学习树和图打下好的基础吧。。。加油！