解题思路:
用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; //输出方案总数
}
0.0分
0 人评分
C语言训练-最大数问题 (C语言代码).........关于-1浏览:744 |
C语言训练-求函数值 (C语言代码)浏览:913 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:726 |
Hello, world! (C语言代码)浏览:1199 |
【明明的随机数】 (C++代码)浏览:779 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:1055 |
【蟠桃记】 (C语言代码)浏览:664 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:560 |
1048题解(读入回车问题)浏览:555 |
演讲大赛评分 (C语言代码)浏览:1629 |