问题描述
这是题目，我大概概括一下用’※’和’.’组成如图所示的矩阵字符串，’※’是石头，’.’是河水，过河只能踩着石头过，而且必须是你所在的石头的下一竖列的正前方或者最近的两个斜对角的石头，用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
问题解答
回答1：好久不写C了，用Perl凑个数吧，很简单的算法啊（我把矩阵旋转了九十度，方便程序读取，其实一样）
#/usr/bin/env perluse strict;use warnings;my $River = <<ENDL;*.*..*..*..*..**..*..**.**..*...*.....*..*..*.*.*.*...*ENDLmy @Rivers = split /n/, $River;for (@Rivers) { $_ = [ split //, $_ ];}#Generate River Matrix# GOGOGOmy @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
