c++ - '*'和'.'组成的符号矩阵假设是一条河，用C语言求过河路线，为什么我的代码总是在求下一步的递归那里break？

Question

这是题目，我大概概括一下
用'※'和'.'组成如图所示的矩阵字符串，'※'是石头，'.'是河水，过河只能踩着石头过，而且必须是你所在的石头的下一竖列的正前方或者最近的两个斜对角的石头，用example里那种纵向数字表示石头的标号，求出一个过河的路线，打印出路线经过的石头的标号
（还有一点不太懂，题里写着可以用#define定义矩阵？如何定义？）
（后面附上我的代码，递归没写好）

int i=0,j=0,flag=0;
char s[80];
int k=0,l=0;
char river[80][80];

//求下一步落脚石的函数
void NextStep(k,l){
    s[l]=k;    //储存每一步落脚石纵向坐标的数组
    
    //当K大于等于第二行的时候
    if (k>0) {
        
        //检测下一竖列与之对应的最近上中下位置是否有石头
        if (river[l+1][k-1]=='*') {
            l+=1;
            k-=1;
        }
        if (river[l+1][k]=='*') {
            l+=1;
        }
        if (river[l+1][k+1]=='*') {
            k+=1;
            l+=1;
        }
        
        //没有合适的落脚石的时候
        else {
            //如果此刻停留在第一竖列，继续向下找另一个'*'
            if (l==0) {
                for (int h=s[0]; h<5; h++) {
                    if (strchr(&river[h][l], '*')){
                        k=h;
                        s[l]=k;
                        flag=1;
                        break;
                    }
                }
                
            }
            //如果不在第一竖列，去第一竖列找下一个'*'，并把l归零
            if (l>0) {
                for (int h=s[0]; h<5; h++) {
                    if (strchr(&river[h][l], '*')){
                        k=h;
                        l=0;
                        s[l]=k;
                        flag=1;
                        break;
                    }
                        
                }
            }
            //找不到的时候，退出程序
            if (flag==0) {
                printf("没有合适的石头\n",l);
                exit(0);
            }

        }
        
    }
    
    //当K大于在第一行的时候(防止越界求K-1，单独列出来)，思路同上
    if (k==0) {
        if (river[k+1][l+1]=='*') {
            k+=1;
            l+=1;
        }
        if (river[k][l+1]=='*') {
            l+=1;
        }
        else {
            if (l==0) {
                for (int h=s[0]; h<5; h++) {
                    if (strchr(&river[h][l], '*')){
                        k=h;
                        s[l]=k;
                        flag=1;
                        break;
                    }
                }
                
            }
            if (l>0) {
                for (int h=s[0]; h<5; h++) {
                    if (strchr(&river[h][l], '*')){
                        k=h;
                        l=0;
                        s[l]=k;
                        flag=1;
                        break;
                    }
                    
                }
            }
            if (flag==0) {
                printf("没有合适的石头\n",l);
                exit(0);
            }
            
        }
    }
    unsigned long n=strlen(river[0]);
    //当落脚石没求到最后一竖列的时候，递归
    if (l<n-1)
        NextStep(k,l);    //编译的breakpoint
}

int main(){
    //输入五行字符
    for (j=0; j<5; j++) {
        printf("请输入第%d行",j+1);
        gets(river[j]);
    }
    //找到第一竖列第一个'*'
    for (j=0; j<5; j++) {
        if(strchr(&river[j][0], '*'))
            break;
    }
    k=j;
    l=0;
    NextStep(k,l);
    
    //打印函数求得的数组
    for (l=0; l<strlen(river[0]); l++) {
        printf("%d",s[l]);
    }
}

breakpoint在函数NextStep()的递归那里，不太懂为啥……
这段代码Bug还蛮多的…………
总之求前辈教育TUT

Answer 1

好久不寫C了，用Perl湊個數吧，很簡單的算法啊
（我把矩陣旋轉了九十度，方便程式讀取，其實一樣）

#/usr/bin/env perl
use strict;
use warnings;
my $River = <<ENDL;
*.*..
*..*.
.*..*
*..*.
.**.*
*..*.
..*..
...*.
.*..*
.*.*.
*...*
ENDL

my @Rivers = split /\n/, $River;
for (@Rivers) {
    $_ = [ split //, $_ ];
}
#Generate River Matrix

# GOGOGO
my @Path;
sub GetNext {
    my $Row    = shift;
    my $Column = shift;
    if ($Rivers[$Row]->[$Column] eq '*') {
        if ($Row + 1 > $#Rivers) {

            # Successful;
            print join "->", @Path;
            exit;
        }
        if ($Column - 1 >= 0) {
            push @Path, $Column - 1;
            GetNext($Row + 1, $Column - 1);

        }
        push @Path, $Column;
        GetNext($Row + 1, $Column);
        if ($Column + 1 <= 5) {
            push @Path, $Column + 1;
            GetNext($Row + 1, $Column + 1);
        }
    }
    pop @Path;
}

@Path = ();
push @Path, 0;
GetNext(0, 0);
@Path = ();
push @Path, 2;
GetNext(0, 2);

結果：
2->3->4->3->2->3->2->3->4->3->4->3