题目描述
大家都知道" 超级玛丽" 是一个很善于跳跃的探险家，他的拿手好戏是跳跃，但它一次只能向前跳一步或两步。有一次，他要经过一条长为n的羊肠小道，小道中有m个陷阱，这些陷阱都位于整数位置，分别是a1,a2,....am，陷入其中则必死无疑。显然，如果有两个挨着的陷阱，则玛丽是无论如何也跳过不去的。
现在给出小道的长度n，陷阱的个数及位置。求出玛丽从位置1开始，有多少种跳跃方法能到达胜利的彼岸（到达位置n）。
数据规模和约定
40> =n> =3,m> =1
n> m;
陷阱不会位于1及n上
输入
第一行为两个整数n,m
第二行为m个整数，表示陷阱的位置
输出
一个整数。表示玛丽跳到n的方案数
样例输入
4 1
2
样例输出
1
提示
C语言在线学习平台微信号dotcpp
来源
算法提高
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100;
int m,n;
bool no[N];
void DFS(int dep,int&res)
{
if(dep == n)
{
res++;
return;
}
else if(dep>n)
{
return ;
}
else
{
if(no[dep+1]==false) DFS(dep+1,res);
if(no[dep+2]==false) DFS(dep+2,res);
}
}
int main(void)
{
int res=0,x;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x;
no[x]=true;
}
DFS(1,res);
cout<<res;
return 0;
}
