迷宫问题的递归c++实现

迷宫问题问题描述:把一只小白鼠放入一个迷宫,问能否找到一条路让小白鼠出来。迷宫用数组表示。能通过则给出图……

不同于上次用栈实现,这里的“栈”自动地由系统分配,So……

 

#include <iostream>

struct Pos
{
 int x;
 int y;
};

int map[7][7]={{0,0,0,0,0,0,0},{0,1,0,1,1,1,0},{0,1,1,0,0,1,0},{0,1,0,1,1,1,0},{0,1,1,1,0,1,0},{0,1,0,0,1,1,0},{0,0,0,0,0,0,0}};
Pos d[4]={{1,0},{-1,0},{0,1},{0,-1}};
int CurStep=1;

void print()
{
 int i,j;
  for(i=0;i<7;i++)
 {
  for(j=0;j<7;j++)
  {
   std::cout.width(2);
   std::cout<<map[i][j]<<" ";
  }
  std::cout<<std::endl;
 }
}

bool Pass(Pos p)
{
 return map[p.x][p.y]==1;
}

Pos GetNext(Pos p,int di)
{
 p.x+=d[di].x;
 p.y+=d[di].y;
 return p;
}

bool Maze(Pos Start,Pos End,Pos CurPos)
{
 if(Pass(CurPos))
 {
  map[CurPos.x][CurPos.y]=CurStep;
  CurStep++;
  if(CurPos.x==End.x && CurPos.y==End.y)
  {
   print();
  }
  int i;
  for(i=0;i<3;i++)
  {
   Maze(Start,End,GetNext(CurPos,i));
  }
  map[CurPos.x][CurPos.y]=-1;
  CurStep–;
 }
 else
 {
  if(CurPos.x==Start.x && CurPos.y==Start.y)
  {
   return false;
  }
 }
}

 

int main()
{
 Pos Start={1,1},End={5,5},p={1,1};
 Maze(Start,End,p);

 return 0;
}

Leave a Reply

Your email address will not be published.