这个是求迷宫的最短路径的代码~注意，当迷宫开口很大(像13楼那样)循环遍历次数就会超多，看上去貌似陷入（死循环）]~当然迷宫路径只有几条的时候求最优解是可以的~对比删了

if (n[x][y]=='o')
    n[x][y]=' ';

和保留，step的值是会有不同的~

这个是求最短路径的代码~

#include<stdio.h>//注意，迷宫节点不能太多，会影响执行效率
#include<stdlib.h>
#include<string.h>
#define N 11
int COUNT=-1;//计算起点和终点间的步数，如果不存在通向终点的路径，则保留初值-1
typedef struct Node
{
    int x;
    int y;
}Node;
Node run[N*N]={0};
Node run_2[N*N]={0};
void print(char K[][N])
{
    int i=0;

     for (i=0;i<N;i++)
        printf("%s\n",&K[i][0]);
}
int go(char n [][N],Node run[],int x,int y,int step)
{

    if (x<0||x>=N||y<0||y>=N)
        return 0;

    if (n[x][y]=='E'&&(COUNT==-1||step<COUNT))
    {
        int i=0;

        COUNT=step;

        for (i=0;i<COUNT;i++)
            run_2[i]=run[i];

        return 0;
    }
    else if (n[x][y]=='E')
        return 0;

    if (n[x][y]!=' ')
        return 0;

    n[x][y]='o';

    run[step].x=x;
    run[step].y=y;

    if (go(n,run,x-1,y,step+1))
        return 1;

    if (go(n,run,x+1,y,step+1))
        return 1;

    if (go(n,run,x,y-1,step+1))
        return 1;

    if (go(n,run,x,y+1,step+1))
        return 1;

    if (n[x][y]=='o')
        n[x][y]=' ';

    return 0;
}
int main()
{
  char K[N][N]=    
    {
        {"**********"},
        {"*  S*  *E*"},
        {"* *** ** *"},
        {"* * *  * *"},
        {"*        *"},
        {"*** * ** *"},
        {"**  *    *"},
        {"** ** ** *"},
        {"*        *"},
        {"**********"},
    };



     int i=0;
     int j=0;
     int step=0;

     for (i=0;i<N;i++)
     {
         for (j=0;j<N&&K[i][j]!='S';j++);
         if (j<N)
             break;
     }

    K[i][j]=' ';

    go(K,run,i,j,step);

    K[i][j]='S';

    for (i=1;i<COUNT;i++)
        K[run_2[i].x][run_2[i].y]='o';

    for (i=0;i<N;i++)
        printf("%s\n",&K[i][0]);

    printf("The step(s) is: %d\n",COUNT);

    printf("The Road is:\n");

   for (i=0;i<COUNT;i++)
    {
        printf("[%d][%d] ",run_2[i].x,run_2[i].y);

        if (i%10==9&&i!=COUNT-1)
            printf("\n");
    }

    printf("\n");

    return 0;
}

[此贴子已经被作者于2016-12-21 02:17编辑过]

嗯，这个是值得肯定的，我早期也有过这样的思路，模拟了一下，循环嵌套比较多，如果能把每次更新节点都能记录下来，下次直接搜索节点，这样能提高遍历效率（不就是队列嘛，我还刚刚起步呢，这个可以凑合用用）~

测试了一下，虽然循环嵌套较多，但也不是很难理解，况且遍历效率不错，先顶了

这个……够我花一段时间去琢磨一下了~

[此贴子已经被作者于2016-12-21 14:40编辑过]

我也要慢慢消化~要理解程序，先要自己有个解决问题的思路，然后再把自己的思路慢慢和这个程序耦合，不然被别人拖着走，很难理解的~没有经过消化的毕竟还是别人的东西~
这个不急理解，慢慢消化，等你到时有一定基础了，应该是不难接受的~

何况我自己也在消化啊~~~

和你说一些无关痛痒的小问题，还是关于那个"死循环"的，这个再深究下去意义不大了~
如果每次递归都有节点更新，那么递归可以说是"有限"的，只不过当网格很多的时候深度遍历意义不大了~

我和你的理解都没有错，关键是对"有限"和"无限"的看法不同，当一个数很大很大很大大到超出数据范围的时候实际意义不大了，可以说是"无限"的，但在数学上毕竟还是"有限"的~只不过这样大的数在实现上几乎没有意义了，可以等同于"无限"

诶，其实我是针对那个关于网格是否陷入"死循环"讨论的，现在说明白可以先放下了~

毕竟，现在觉得那个"死循环"的问题已经无关痛痒了，倒不如研究一下最短路径问题~

话说用递归算法难以完成，这个我也表示赞同~

不过我给你看看一道AC，里面也是可以通过递归算法深度搜索求最优解的,有兴趣可以做做，应该不算太难~






对哦，还附加了网址呢~

聪明的KK【河南2010ACM试题及答案】_百度文库

就附加一道关于递归算法的小练笔吧，直接在这里发，就不另外发新帖了~

http://wenku.baidu.com/view/c9caeaee102de2bd97058807.html?qq-pf-to=pcqq.c2c

到时可以看看里面的答案，并问一下那个答案算法算不算是递归~~~~

[此贴子已经被作者于2016-12-21 16:05编辑过]

对了，和上一题深度搜索比较，附加一题关于广度搜索的AC~





ACM竞赛试题_图文_百度文库

网址在这里，不过这次就没有答案了~

http://wenku.baidu.com/view/d6dab6c66137ee06eff918d0.html


看看怎么用广度搜索解决这题~

求路径可以参考19楼的深度搜索的保存路径方法~
其实，这条题除了递归外，还有一种绝妙的算法，算法名可是很闻名的~到时再说思路（不就是网址答案那个嘛，不过这可是我自己想的）~

这个虽然不及广度循环遍历效率高，但毕竟是通过深度递归做出来的，是个好东西我先收藏，有时间再慢慢消化~

虽然我没仔细看程序的性能，但我感觉是先把迷宫所有路标都遍历一遍，然后做个深度标记~遍历完毕再后续处理深度标记~我的想法是这样的，不知道你的算法是不是这样~如果是的话，那我就消化容易很多了~

我的理解是这样的，画程序较为花时间，我先在这里比划一下~

假设递归遍历深度标记为(0为墙)

1 2 3 12 11
0 0 4 0 10
0 0 5 0 9
0 0 6 7 8

由于3和12是连通的并且深度不是相差1，那么12就可以用4来代替，11就可以用5代替，直到所有深度标记都相差1~然后再从终点根据优化后的递归深度相差1逆推回起点，即为最短路径~就像22楼的算法一样，巧妙利用了已知点的深度递减只有唯一一条路径~
14:40更：已知点的深度递减只有唯一一条路径~的说法有误如果当最短路径不唯一时这个说法是不成立的~
深度优化后则为:

1 2 3 4 5
0 0 4 0 6
0 0 5 0 7
0 0 6 7 8

核心部分不是在递归--递归只是一种标记路径的方法，而是在后续优化递归深度部分~

[此贴子已经被作者于2016-12-22 14:38编辑过]