[蓝桥省题](C2013_3) 振兴中华

3、(振兴中华)小明参加了学习的趣味运动会，其中一个项目是：跳格子。地上画着一些格子，每个格子里写一个字，如下所示：

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

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

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

答案是一个整数，请通过浏览器提交该数字，注意：不要提交解答过程，或其他辅助说明类的内容

题意：上述图案是一个矩阵，我们可以对应的看作一个二维数组，通过坐标的变化我们要求坐标序列构成“从我做起，振兴中华”题目要求算出所有达到要求的坐标序列。起始是（0,0）终点是（3,4）

思路：我们可以从图上得知，每个格子的方向只有<向右>和<向下>两种可能，通过这两个方向所走的路线之和就是所有路线总和，在"0,0"的位置和其余所有位置的选择都是一样的，如下图所示：

例如：在“从”的位置的位置选择和在“做的位置”的选择是一样的

那么结束条件就是达到“华”的位置即是一种走法，也就是说，每个位置不管向左还是向下，只要能达到"华"就是一种解法，则我们可以用递归将问题缩小求解

代码如下所示：

int f(int x, int y)//每层变化的就是坐标
{
    if (x == 3 && y == 4)//如果x和y等于(3,4)则达到结束条件
        return 1;
    if (x == 3 && y != 4)
        return f(x, y + 1);
    else if (x != 3 && y == 4)
        return f(x + 1, y);
    else
        return f(x + 1, y) + f(x, y + 1);
}
int main()
{
    int result = f(0, 0);
    printf("%d", result);
    system("pause");
    return 0;
}

根据思路我们可以画出它的树型图并与理解：

这题其实还能用排列组合来做，一共是七个位置(从开始包括从需要减一)其中三种向下，其他全部向右，这个序列的总和就是题目答案

C73=7x6x5/1x2x3=35

教学视频如下：

本文链接：