#include <iostream>

 #include <vector>

 #include <cstring>

 using namespace std;

 typedef struct

 {

     int x;

     int y;

 }pos;

 #define N 4  //4*4 maze

 #define ENTER_X 0

 #define ENTER_Y 0

 #define EXIT_X N-1

 #define EXIT_Y N-1

 int Maze[N][N];

 int paths;  //sum of paths

 vector<pos> Path;  //svae paths

 vector<pos> BestPath; //save min distant path

 void InitMaze();

 bool MazeTrack(int x,int y); 

 int main()

 {

     InitMaze();

     int i =  , j = ;

     for(i=;i<N;i++)

     {    for(j=;j<N;j++)

             cout << Maze[i][j];

         cout << endl;

     }

     MazeTrack(ENTER_X,ENTER_Y);

     return ;

 }

 void InitMaze()

 {

     int    a[N][N] = {

         {,,,},

         {,,,},

         {,,,},

         {,,,}

         };

     memcpy(Maze,a,sizeof(a));

     paths = ;

 }

 bool MazeTrack(int x,int y)

 {

     bool IsPath = false;

     pos p;

     p.x = x;

     p.y = y;

     //set range of maze's x/y

     if(x<N && x>= && y<N && y>= && Maze[x][y]==)

     {

         //make

         Path.push_back(p);

         Maze[x][y] = ;  //if value is 1,you can't go there

         cout << "now,position is("<<x<<","<<y<<")" << endl;

         //terminal

         if(x==EXIT_X && y==EXIT_Y)

         {

             cout << "find a path" << endl;

             paths++;

             IsPath = true;

             vector<pos>::iterator it;

             for(it=Path.begin() ; it!=Path.end() ; it++)

                 cout << "("<< it->x <<","<< it->y <<")" << " ";

             cout << endl;

             return IsPath;

         }

         //search  (find forward solutions)

         IsPath = MazeTrack(x-,y) || MazeTrack(x,y-) || MazeTrack(x+,y) || MazeTrack(x,y+);

         //backtrack

         if(!IsPath)

         {

             Path.pop_back();

             Maze[x][y] = ;

         }

         cout << Path.size() << endl;

     }

     //fuction exit

     return IsPath;

 } 

now,position is(,)

now,position is(,)

now,position is(,)

now,position is(,)

now,position is(,)

now,position is(,)

now,position is(,)

now,position is(,)

now,position is(,)

now,position is(,)

find a path

(,) (,) (,) (,) (,) (,) (,) 

solution

  using namespace std;

  #define N 100

  #define M 100

  typedef struct

  {

         int x;

         int y;

  }Point; 

 vector<Point>solutionPath ;  //存放有解的坐标路径

 //主函数 x,y默认为起始结点，如(0,0), 得到从起始结点到目的结点的路径。

 bool hasSolutionFunction( template<typename T>* Matrix , int x, int y)

 {

     bool *visited = new bool[M*N];

     memset (visited,,M*N); //visited 存放每个结点是否被遍历，true为已经遍历过，false为否

     res =  hasSolutionCore(Matrix , x ,y)

     cout<<solutionPath<<endl;

     return res

 }

 //深度遍历求解路径的函数

 bool hasSolutionCore(template<typename T>*  Matrix , int x, int y)

 {

     hasSolution = false;

     Point p = Point(x,y);

     if (x,y) is terminal  //x,y 已经是终止条件，当求解到这个结点是叶结点或目的地

         {

         solutionPath.push_back(p);

         return true;

         }

     if ((x,y) && visited[x][y]==flase )// x,y是合法结点(具体条件可扩展)，且未被访问过

     {

         visited[x][y] = true;

         solutionPath.push_back(p);

         hasSolution = hasSolutionCore(Matrix,x-, y) ||hasSolutionCore(Matrix,x,y-)||... //如果不是叶结点，则该路径是否有解取决于其他方向的往后求解。

         // x,y结点以下的所有子路径都无解，则回溯

         if (!hasSolution)

         {

         visited[x][y] = false;

         solutionPath.pop_back();

         }

     }

     return hasSolution;

 }