【藍橋杯】2013-A組03 振興中華

• 2020 年 2 月 13 日
• 筆記

題目描述：

小明參加了學校的趣味運動會，其中的一個項目是：跳格子。地上畫著一些格子，每個格子里寫一個字，如下所示：

比賽時，先站在左上角的寫着「從」字的格子里，可以橫向或縱向跳到相鄰的格子里，但不能跳到對角的格子或其它位置，一直要跳到「華」字結束。要求跳過的路線剛好構成「從我做起振興中華」這句話。請你幫助小明算一算他一共有多少種可能的跳躍路線呢？

解題思路：

沒有坑，直接遞歸求解，要麼往下要麼往右，當下到第4行時就只能往右了return 1，或者右到第5行只能往下了return 1。遞歸求解的入口是「從」字所在的下標，即(1,1)。

AC代碼：

#include <bits/stdc++.h>  using namespace std;    int fun(int x,int y)  {      if(x==4 || y==5) return 1;      return fun(x+1,y)+fun(x,y+1);  }    int main()  {      ios::sync_with_stdio(false);      cin.tie(0),cout.tie(0);      cout << fun(1,1) << endl;      return 0;  }