蓝桥杯C/C++省赛：振兴中华

题目描述

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

从我做起振 我做起振兴 做起振兴中 起振兴中华

比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。 要求跳过的路线刚好构成“从我做起振兴中华”这句话。 请你帮助小明算一算他一共有多少种可能的跳跃路线呢？

思路分析

一开始我的想法是用BFS或者DFS去找到满足的路径，但是我只会找到一个，没有办法找出所有的，后来发现这道题并不是考这个玩意，因为它的每一个格子都会有满足的路径（注意这句话），所以一个格子会有多种路径是满足的，而最多的路径数会出现在第一个格子，因为这是出发的地方，所有满足的路径都会经过它，所以我们只要找出第一个格子的路径数即可。

那么第一个的路径数如何解决呢，实际上第一个的路径数等于右边格子和下边格子的路径数之和，对吧？所以我们现在需要求解右边格子的路径数和下边格子的路径数，聪明的你有没有想到，这就是递归的思想。

递归过程，如果遇到边界，边界只有一条路径可以走，返回1即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
int Yezi(int i,int j){
    if(i==3||j==4)
        return 1;
    return Yezi(i+1,j)+ Yezi(i,j+1);
}
int main()
{
    cout<<Yezi(0,0);
    return 0;
}