问题描述
这是原题目，后面附上我的代码，刚刚接触DFS，不是很熟练，求教育……谢谢！！！TUT
这是题目，我大概概括一下用’※’和’.’组成如图所示的矩阵字符串，’※’是石头，’.’是河水，过河只能踩着石头过，而且必须是你所在的石头的下一竖列的正前方或者最近的两个斜对角的石头，用example里那种纵向数字表示石头的标号，求出一个过河的路线，打印出路线经过的石头的标号
int j=0;char Q[80];int x=0,y=0,res=0;char river[5][11],visited[5][11];void dfs(y,x){ Q[x]=y; //储存每一步落脚石纵向坐标的数组 visited[x][y]=1; int dx=1; for (int dy=-1; dy<=1; dy++) {int ny=y+dy,nx=x+dx;//如果nxny在河的范围内，是石头，而且没有被访问过，就递归if (nx>=0 && nx<11 && ny>=0 && ny<5 && river[ny][nx]==’*’ && visited[ny][nx]==0) { dfs(ny, nx);} }//如果没有合适的落脚石，而且当前在第一竖列，就向下继续寻找第一竖列未被访问的石头，找不到就结束dfs函数 if (x==0) {for (j=y+1; !strchr(&river[j][0], ’*’)&&visited[j][0]!=0&&j<5; j++);if (j<5) { dfs(j, 0);}else return; }//如果没有合适的落脚石,且不在第一竖列，就返回上一块落脚石重新选择 dfs(Q[x-1], x-1);return; }int main(){ for (int m=0; m<11; m++) {for (int n=0; n<5; n++) { visited[n][m]=0;} } //输入五行字符 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; } dfs(j,0);if (strlen(Q)==11) {//打印函数求得的数组for (int i=0; i<strlen(Q); i++) { printf('%d',Q[i]);} } else{printf('no solution'); } return 0;}
问题解答
回答1：你这个递归写得……真是死循环一般的存在……
DFS的递归里起码要返回一个值才能进行递归运算分析，例如这道题就应该返回这个节点可不可以被走通（boolean）。递归时先判断当前节点是否可以走，不能走直接返回 false，能走则分散到相连的节点上去，返回相连的节点里是否存在可以走通的节点（这时候递归下去，走过的路不进递归）。
走不通原路返回就是递归本身退栈实现的，你这里居然往回走又进栈，也是醉了
回答2：为什么这么复杂，见https://segmentfault.com/q/1010000004191381的回答
