膜拜大神，逢考必过

总算避开链表找到一个找最近路径的算法，大概类似于2楼答主的算法，但没有用递归，是找层的模式，应该可以递归吧，后期改善算法，附上代码及效果图，期待测试：

#include<stdio.h>
#define N 11
int setlevel(int a[][N],int x,int y,int l)
{//设置指定坐标点层级,如果坐标点是出口则返回1，否则返回0
    if(x<0||x>=N||y<0||y>=N)return 0; //坐标不合格以0返回
    if(a[x][y]==N*N+2)
        return 1;
    if(!a[x][y])a[x][y]=l+1;
    return 0;
}
int shortpath(char a[][N])
{//找最短路径，找到则标注并返回1，否则返回0
    int i,j,k,l,m=0,x,y,b[N][N],c[]={-1,0,1,0,0,-1,0,1};
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            b[i][j]=0;
            if(a[i][j]=='*')b[i][j]=N*N+1;
            if(a[i][j]=='E')b[i][j]=N*N+2;
            if(a[i][j]=='S')b[i][j]=1;
        }
    }
    for(k=1;k<N*N;k++)
    {
        for(i=0;i<N;i++)
        {
            for(j=0;j<N;j++)
            {
                if(b[i][j]==k)
                {
                    for(l=0;l<8;l+=2)
                    {
                        m=setlevel(b,i+c[l],j+c[l+1],k);
                        if(m)
                        {
                            for(x=0;x<N;x++)
                            {
                                for(y=0;y<N;y++)printf("%4d",b[x][y]);
                                printf("\n");
                            }
                            printf("\n%d:墙，%d:出口，1：入口 0：空地方\n\n",N*N+1,N*N+2);  
                            break;
                        }
                    }
                    if(m)break;
                }
                if(m)break;
            }
            if(m)break;
        }
        if(m)break;
    }
    if(m)
    {
        while(b[i][j]!=1)
        {
            a[i][j]='o';
            x=i;
            y=j;
            k=b[x][y];
            for(l=0;l<8;l+=2)
            {
                if(i+c[l]>=0&&i+c[l]<N&&j+c[l+1]>=0&&j+c[l+1]<N&&b[i+c[l]][j+c[l+1]]>0&&b[i+c[l]][j+c[l+1]]<k)
                {
                    x=i+c[l];
                    y=j+c[l+1];
                    k=b[x][y];
                }
            }
            i=x;
            j=y;
        }
    }
    return m;
}

int main()
{
    char k[N][N]=    
    {
        {"**********"},
        {"*  S*  *E*"},
        {"* *** ** *"},
        {"* * *  * *"},
        {"*        *"},
        {"*** * ** *"},
        {"**  *    *"},
        {"** ** ** *"},
        {"*        *"},
        {"**********"},
    };
    int m;
    for(m=0;m<N;m++)printf("%s\n",&k[m][0]);  //显示未标注路径的地图
    if(shortpath(k))
    {
        printf("Yes\n");
        for(m=0;m<N;m++)printf("%s\n",&k[m][0]);  //显示标注路径的地图
    }
    else printf("No\n");
    return 0;
}

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

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

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

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

[此贴子已经被作者于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


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

//KK虫暂时只得到求最高分的算法，没找到求路线的算法，努力ing
#include<stdio.h>
#include<time.h>
int**arr;
struct P{int x;int y;};
struct P*pos;
int ip;
int ToRightBottom(int x,int y)//计算从下标[0][0]走到指定下标处所能得到的最高分
{
    int mark1=0,mark2=0;int i;
    if(!x&&!y) return arr[0][0];
    if(!x)
    {
        return mark1=ToRightBottom(0,y-1)+arr[y][x];
    }
    if(!y)
    {
        return mark1=ToRightBottom(x-1,0)+arr[y][x];
    }
    mark1=ToRightBottom(x-1,y)+arr[y][x];
    mark2=ToRightBottom(x,y-1)+arr[y][x];
    return mark1>mark2?mark1:mark2;
}
int main()
{
    int x,y;int _x,_y;
    printf("输入列数：");scanf("%d",&x);
    printf("输入行数：");scanf("%d",&y);
    printf("共%d列%d行\n",x,y);
    arr=(int**)malloc(y*sizeof(int*));
    for(_y=0;_y<y;_y++)
        arr[_y]=(int*)malloc(x*sizeof(int));
    srand((unsigned int)time(0));
    for(_y=0;_y<y;_y++)
    {
        for(_x=0;_x<x;_x++)
        {
            arr[_y][_x]=(unsigned int)rand()%50;
            printf("%d\t",arr[_y][_x]);
        }
        printf("\n");
    }
    pos=(struct P*)malloc((x+y-1)*sizeof(struct P));
    pos[ip=0].x=0;pos[0].y=0;
    printf("最高分数：%d",ToRightBottom(_x-1,_y-1));
    return 0;
}

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