C++寻路算法

介绍写寻路算法？最好有代码。

答案：迷宫寻找路径要不。。。。。。
#include <iostream>
#include<iomanip>
using namespace std;
#define M 10
#define N 10
typedef enum{X=0,up,dn,rt,lt} tDir;  //搜索方向
class Migong         
{
  public:
  int tag;         /*0 1*/    
  tDir comeDir;    /*退回*/
  int up,rt,dn,lt;   //方向
  int back;
};
int m[M][N]={     //初始化通道数据
  {0,0,1,1,1,1,1,1,1,1},
  {1,0,1,1,1,0,1,1,1,1},
  {1,0,0,0,1,0,1,1,1,1},
  {1,1,1,0,1,1,1,1,1,1},
  {1,0,0,0,1,0,0,0,1,1},
  {1,0,1,1,1,0,1,0,1,1},
  {1,0,1,0,0,0,1,0,0,1},
  {1,0,0,0,1,1,0,1,0,1},
  {1,1,1,1,1,1,0,1,0,1},
  {1,1,1,1,1,1,1,1,0,0},
  };
  int ini=0,inj=0;   //入点
  int outi=9,outj=9; //出口 
  int cnt=0;    //从入口到出口需多少步
  int path[M][N];   //记录找到路径后的迷宫
  Migong  maze[10][10]; 
void initmaze(Migong  mz[][10])  //初始化迷宫数据
{
 int i;
 int j;
 for(i=0;i<10;i++)
   for(j=0;j<10;j++)
   {
    mz[i][j].tag=m[i][j];
          mz[i][j].comeDir=X; 
    mz[i][j].up=0;
    mz[i][j].dn=0;
    mz[i][j].rt=0;
    mz[i][j].lt=0;
    mz[i][j].back=0;
   }
}
int find(Migong  mz[][10],int i,int j,tDir dir)  //搜索路径
{  
  if(i==outi&&j==outj)
   return 1;  ////if 当前节点是出口 then return 1;  
  if(dir!=X)  //if   不是是回退到本节点,then 记录来的方向  根据来的方向设定其相对方向已走
  {
   mz[i][j].comeDir=dir;
   if(dir==up)
    mz[i][j].dn=1;  //向N方向没有走&&可以走，则向N递归走
   if(dir==dn)
    mz[i][j].up=1;  //向E方向没有走&&可以走，则向N递归走
   if(dir==rt)
    mz[i][j].lt=1;  //向S方向没有走&&可以走，则向N递归走
   if(dir==lt)
    mz[i][j].rt=1;  //向W方向没有走&&可以走，则向N递归走
  }

  if(mz[i][j].up==0)  //if 向up方向没走&&不越界&&可以走 则向up递归走 
  {
   int ni;
   int nj;   
   mz[i][j].up=1;  //记录本节点  
   ni=i-1;
   nj=j;   //ni,nj表示i,j的上一个坐标   
   if(ni>=0 && mz[ni][nj].tag==0)
     if(find(maze,ni,nj,up))
   return 1;
  }
  if(mz[i][j].dn==0)   //if 向dn方向没走&&不越界&&可以走 则向dn递归走
  {
   int ni;
   int nj;   
   mz[i][j].dn=1;   //记录本节点 
   ni=i+1;
   nj=j;      //ni,nj表示i,j的下一个坐标 
   if(ni<10 && mz[ni][nj].tag==0)
     if(find(maze,ni,nj,dn)) 
   return 1;
  }
  if(mz[i][j].rt==0)   //if 向rt方向没走&&不越界&&可以走 则向rt递归走
  {  
 int ni;
 int nj; 
   mz[i][j].rt=1;    //记录本节点 
   ni=i;
   nj=j+1;      //ni,nj表示i,j的右一个坐标
   if(nj<10 && mz[ni][nj].tag==0)
      if(find(maze,ni,nj,rt))
    return 1;    
  }
  if(mz[i][j].lt==0)    //if 向lt方向没走&&不越界&&可以走 则向lt递归走
  { 
   int ni;
   int nj;  
   mz[i][j].lt=1;   //记录本节点 
   ni=i;
   nj=j-1;     //ni,nj表示i,j的左一个坐标   
   if(nj>=0 && mz[ni][nj].tag==0)
     if(find(maze,ni,nj,lt))
   return 1;
  }
  
  //四个方向都走完了还没有结果
 
  if(i==ini && j==inj)  // if 是入口 return 0
   return 0;
  else    // else 则回退
  {
   mz[i][j].back=1;
   if(mz[i][j].comeDir=up)  //如果回退的值等于up的值，则向up方向搜索
   {
    int ni;
    int nj;
       ni=i+1;
    nj=j;   //ni,nj表示i,j的下一个坐标 
       if(find(maze,ni,nj,X))
  return 1;
   }
   if(mz[i][j].comeDir=dn)   //如果回退的值等于dn的值，则向dn方向搜索
   {
    int ni;
    int nj;
       ni=i-1;
    nj=j;   //ni,nj表示i,j的上一个坐标
       if(find(maze,ni,nj,X))
  return 1;
   }
   if(mz[i][j].comeDir=rt)  //如果回退的值等于rt的值，则向rt方向搜索
   {
    int ni;
    int nj;
       ni=i;
    nj=j-1;  //ni,nj表示i,j的左一个坐标
       if(find(maze,ni,nj,X))
  return 1;
   }
   if(mz[i][j].comeDir=lt)  //如果回退的值等于lt的值，则向lt方向搜索
   {
    int ni;
    int nj;
       ni=i+1;
    nj=j+1;   //ni,nj表示i,j的左下角一个坐标
       if(find(maze,ni,nj,X)) 
  return 1;
   }
  }
  return 0;
}
int onway( Migong nd)  //判断点是否在路径上
{
 if(nd.tag!=0)
  return 0;    //墙
 if(nd.up==0&&nd.dn==0&&nd.rt==0&&nd.lt==0)
  return 0;    //没访问过
 if(nd.up==1&&nd.dn==1&&nd.rt==1&&nd.lt==1&&nd.back==1)
  return 0;    //访问过但不通
 return 1;
}
//打印
void print( Migong mz[][10])   //打印原迷宫
{
 int i;
 int j;
 cout<<"0表示可通过，1表示墙"<<endl;
 cout<<"-------------------------------";
 cout<<endl<<"       ";
 cout<<"▂▂▂▂▂▂▂▂"<<endl;
 for(i=0;i<10;i++)
 {
  cout<<setw(10)<<"▎ ";
  for(j=0;j<10;j++)
  
   cout<<mz[i][j].tag;
  cout<<"   ▎"<<endl;
    
  
 }
 cout<<"       ";
 cout<<"▂▂▂▂▂▂▂▂"<<endl;
}
void print1( Migong mz[][10])      //打印含路径迷宫
{    
 int i;
 int j;
cout<<endl<<"       ";
 cout<<"▂▂▂▂▂▂▂▂"<<endl;
  
 for(i=0;i<10;i++)
 { 
 cout<<setw(10)<<"▎ ";
   for(j=0;j<10;j++)
   { 
    if(i==9 && j==9) //出口
    {
          cnt++;
          cout<<"*";
    path[i][j]=0;
    }
   else
    if(onway(mz[i][j]))
 {
    cout<<"*";         //*表示路径
 cnt++;
 path[i][j];
 }
    else
 {
   cout<<mz[i][j].tag;
   path[i][j]=1;      //path[i][j]=0表示可通过，path[i][j]=1表示墙
 }
   }
cout<<"   ▎"<<endl;
 }
cout<<"       ";
 cout<<"▂▂▂▂▂▂▂▂"<<endl;
}
void print2( Migong mz[][10])   //打印路径坐标
{ 
  int i;
  int j;  
  int di;
  int dj;  //di,dj的值为-1，0，1，为了搜索坐标i,j附近的坐标
  int pi;
  int pj;  //pi,pj为上一个路径坐标
  int r;
  int count;  //统计输出了多少个坐标
  i=0;
  j=0;
  pi=1;
  pj=0;
  count=0;
  cout<<endl<<"路径坐标为:"<<endl<<endl;
 for(r=0;r<cnt;r++)
 {
  if(i>=10 || j>=10) //i,j的值不可能大于10
   continue;
  else
  {
    for(di=-1;di<2;di++)
         for(dj=-1;dj<2;dj++)
   {
       if(di==dj )  //path[i][j]的下一步不可能在它的左上角和右下角
                continue;
       if(di==1 && dj==-1)   //path[i][j]的下一步不可能在它的左下角
        continue;
       if(di==-1 && dj==1)   //path[i][j]的下一步不可能在它的右上角
        continue;
      if((i+di)<0 ||(j+dj)<0)  //i+di,j+dj小于0时不符
       continue;
    if(path[i+di][j+dj]!=0)  //i+di,j+dj不是路径上的坐标
     continue;
     if((i+di)==i && (j+dj)==j )  //path[i][j]的下一步不可能是它本身
      continue;
     else
       if((i+di)==pi && (j+dj)==pj)  //path[i][j]的下一步不可能是它的上一步
        continue;
    else
    {if(i==9&&j==9)
       cout<<"(9,9)";
    else
    {
    
      cout<<"("<<i<<","<<j<<")"<<"->";
   count++;
   if(count%5==0)
    cout<<endl;
  }
             pi=i;
     pj=j;
     i=i+di;
     j=j+dj;
     }
      }
  }    
 }
}
int main()
{
  initmaze(maze);   //初始化迷宫
  cout<<endl<<endl<<"原迷宫如下："<<endl;
  print(maze);     //打印原迷宫
  if (find(maze,ini,inj,rt)) //如果迷宫有路径
  {
  
   cout<<"-------------------------------";
  cout<<endl<<"含路径的迷宫,*表示通道"<<endl;
cout<<"-------------------------------";
     print1(maze);

上一个：C++程序设计 题目
下一个：C++代码求解释