题目描述 大家都知道" 超级玛丽" 是一个很善于跳跃的探险家，他的拿手好戏是跳跃，但它一次只能向前跳一步或两步。有一次，他要经过一条长为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
#include<iostream> #include<algorithm> using namespace std; int isTrap[50]; int n,m,ans,flag; void dfs(int x) { if(flag)//连续两个陷阱的标记 { ans=0; return; } if(x==n) ans++; if(isTrap[x]||x>n) return; if(isTrap[x+1]) { if(x+2<=n&&isTrap[x+2])//如果发现有两个陷阱连续ans归零 没有解决方案 { flag=1; return; } else dfs(x+2); } else { dfs(x+1); dfs(x+2); } } int main() { int t; cin >> n >> m; for(int i=0;i<m;i++) { cin >> t; isTrap[t]=1; } dfs(1); cout << ans; }