振兴中华

果子

    小明参加了学校的趣味运动会，其中的一个项目是：跳格子。

    地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）
[blockquote]

从我做起振

我做起振兴

做起振兴中

起振兴中华[/blockquote]



    比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。


    要求跳过的路线刚好构成“从我做起振兴中华”这句话。

    请你帮助小明算一算他一共有多少种可能的跳跃路线呢？
[attachment=28]

boyfaceone

支持一下

那个谁

看了楼上的排列组合方式觉得还不错，我在网上找到了一种二叉树的递归调用的解法，感觉很好，分享给大家
#include<stdio.h>
int a[4][5];  
int sum;
/*dfs()function.
@parameter row:二维数组的行号。
@parameter col:二维数组的列号。
@parameter index:二维数组a[row][col]的值。
*/  
void dfs(int row,int col,int index)  
{
    if(a[row][col]==index && index==7)  
        sum++;  
    else
    {  
        if(row+1<4)  
            dfs(row+1,col,index+1);  
        if(col+1<5)  
            dfs(row,col+1,index+1);  
    }  
}  

int main()  
{  
    int row,col;  
    for(row=0;row<4;row++)  
        for(col=0;col<5;col++)  
            a[row][col]=row+col;  

    dfs(0,0,0);  
    printf("sum = %d\n",sum);  
    return 0;  
}

果子

tyrone2497谁:看了楼上的排列组合方式觉得还不错，我在网上找到了一种二叉树的递归调用的解法，感觉很好，分享给大家
#include<stdio.h>
int a[4][5];  
int sum;
/*dfs()function.
....... (2013-06-09 21:21)

不错，简洁直观。

boyfaceone

tyrone2497谁:看了楼上的排列组合方式觉得还不错，我在网上找到了一种二叉树的递归调用的解法，感觉很好，分享给大家
#include<stdio.h>
int a[4][5];&#160;&#160;
int sum;
/*dfs()function.
.......&#160;(2013-06-09 21:21)&#160;

这个就是传说中的回溯法吧？膜拜一下

a331397964

这个二叉树实现的代码，有解释么。

那个谁

a331397964:这个二叉树实现的代码，有解释么。 (2013-07-06 20:53)

它是利用了该题中的特殊规律来用二叉树的递归调用来解答的。看代码应该不难看懂，其实我之前也不知道为何用这种解法来解题。只是能看懂，又觉得算法简单明了就转帖上来了，如果有细节方面的问题再问吧。。。