蓝桥杯算法提高VIP-超级玛丽 （C++代码）

解题思路:

           用dfs搜索就好，搜索的时候提前判断是该处是否有坑，该处是否超过小道的长度n，剩下的就是

   dfs(step+1)//向前走一步      dfs(step+2) // 向前走两步    

注意事项:
           
参考代码:

#include <iostream>
#include <algorithm>
#include"stdio.h"
#include"math.h"
#include<vector>
#include<queue>
#include"cstring"
#include"set"
#include"map"
#include <memory.h>
#include<string>
#include<functional>
#include"time.h"
#define maxn 200001
using namespace std;

int n,m; // n代表总共的长度，m代表坑的个数
int a[50]; //保存坑的位置
int step; //用于保存当前走到第几步
int sum = 0; //用于保存所有的方案数
void dfs(int step) //搜索所有的可能性
{
     if(step>n)   return;   //判断是否超过最大长度，一定要加次判断，否则会进入死递归
    if(a[step] == 1)  return;   // 判断该处是否有坑
     if(step == n)  {sum++;return;}  // 递归出口，一种可能已经搜索完毕,将总的方案数加一

    dfs(step+1);   //走一步
    dfs(step+2);  //走两步
    
}
int main()
{
    cin>>n>>m;
     for(int i = 1;i<=m;i++)
    {
            int temp;
             cin>>temp;
            a[temp] = 1; // 将有坑的位置置为1
     }
       dfs(1); //开始搜索所有的可能
       cout<<sum<<endl;   //输出方案总数
}