Question

求一个求从迷宫的一点到另一点的最短路径的递归算法

我没有学过树之类的数据结构，书上的广搜貌似都是用树来讲解的，看不懂，麻烦大家给我粘一个通俗一点的用递归解决的算法，要完整代码，还有，必须是C或者C++的，谢谢！
一定要递归的，谢谢！

Answer 1

typedef struct node
{
int i;
struct node **nearby;//相邻结点可以有多个，所以这里用指针的指针
} MAPNODE;
MAPNODE a,b;
int minpath(a,b)//从a结点到b结点可以分成两步，1.从a到b的相邻结点。2.从相邻结点到b结点，这就是一个递归的过程
{
int dis=0;
int min=999999;//一个足够大的数据
MAPNODE **p;
if(a.i==b.i)//序号相同表示是同一结点，path为0
{
dis=0;
}
else
{
for(p=b.nearby;*p!=0;p++)
{
dis=0;
dis+=minpath(a,*p);
dis<min?min=dis:;
}
}
return dis;
}

Answer 2

计算机程序设计艺术

Answer 3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct pos
{
int x,y;
pos()
{
x=0;y=0;
}
void print()
{
printf("(%d,%d)\n",y+1,x+1);
}
void setxy(int a,int b)
{
x=a;
y=b;
}
}pos;

int maze[200][200];
int n,m;
int ex,ey;
int min=(int)2e30;
pos out;
pos stack[500];
pos *p=stack;

void push(int x,int y)
{
p->setxy(x,y);
p++;
}

void find(int x,int y,int num)
{
push(x,y);
if(y-1>=0&&maze[y-1][x]==num-1) find(x,y-1,num-1);
else if(y+1<n&&maze[y+1][x]==num-1) find(x,y+1,num-1);
else if(x+1<m&&maze[y][x+1]==num-1) find(x+1,y,num-1);
else if(x-1>=0&&maze[y][x-1]==num-1) find(x-1,y,num-1);
}

void set(int x,int y,int num)
{
if(maze[y][x]==-3)
{
if(num<min)
{
min=num;
out.setxy(x,y);
}
}
else
{
if(maze[y][x]>num||maze[y][x]==0)
{
maze[y][x]=num;
if(y-1>=0&&( maze[y-1][x]>num+1 || maze[y-1][x]==0 || maze[y-1][x]==-3) ) set(x,y-1,num+1);
if(y+1<n &&( maze[y+1][x]>num+1 || maze[y+1][x]==0 || maze[y+1][x]==-3) ) set(x,y+1,num+1);
if(x-1>=0&&( maze[y][x-1]>num+1 || maze[y][x-1]==0 || maze[y][x-1]==-3) ) set(x-1,y,num+1);
if(x+1<m&& ( maze[y][x+1]>num+1 || maze[y][x+1]==0 || maze[y][x+1]==-3) ) set(x+1,y,num+1);
}
}
}

int main()
{

freopen("input.txt","r",stdin);

scanf("%d%d",&n,&m);
char ch;
memset(maze,0,sizeof(maze));
scanf("\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%c",&ch);
if(ch=='#') maze[i][j]=-1;
else if(ch=='S')//入口
{
ex=j;ey=i;
}
else if(ch=='E')//出口
{
maze[i][j]=-3;
}
}
scanf("\n");
}

set(ex,ey,1);
printf("最短路径=%d步\n\n",min);
find(out.x,out.y,min);
for(int i=0;i<min;i++) stack[min-i-1].print();
return 0;
}