解题思路:
用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语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:479 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:901 |
回文数(一) (C语言代码)浏览:748 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:507 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:583 |
WU-蓝桥杯算法提高VIP-Quadratic Equation (C++代码)浏览:1752 |
IP判断 (C语言代码)浏览:763 |
a+b浏览:433 |
简单的a+b (C语言代码)浏览:460 |
C语言程序设计教程(第三版)课后习题9.2 (C语言代码)浏览:610 |