计蒜客跳跃游戏（dfs）

女爷i 2024-02-17 22:03 34阅读 0赞

给定一个非负整数数组，假定你的初始位置为数组第一个下标。

数组中的每个元素代表你在那个位置能够跳跃的最大长度。

请确认你是否能够跳跃到数组的最后一个下标。

例如：A=\[2,3,1,1,4\]A = \[2,3,1,1,4\]A=\[2,3,1,1,4\] 能够跳跃到最后一个下标，输出`true`；

A=\[3,2,1,0,4\]A = \[3,2,1,0,4\]A=\[3,2,1,0,4\] 不能跳跃到最后一个下标，输出`false`。

#### 输入格式 ####

第一行输入一个正整数 n(1≤n≤500)n(1 \\leq n \\leq 500)n(1≤n≤500)，接下来的一行 nnn 个整数，输入数组 AiA\_iAi。

#### 输出格式 ####

如果能跳到最后一个下标，输出`true`，否则输出`false`。

##### 样例输入 #####

5
    2 0 2 0 1

##### 样例输出 #####

true

分析：dfs求解

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=500+10;
    int a[maxn];
    int vis[maxn];
    int n;
    int flag;
    
    void dfs(int i){
    	if(i==n){
    		flag=1;
    		return ;
    	}
    	
    	for(int j=1;j<=a[i];j++){
    		if(!vis[j+i]){
    			vis[i+j]=1;
    			dfs(i+j);
    		}
    	}
    }
    int main(){
    	while(scanf("%d",&n)==1){
    		for(int i=1;i<=n;i++)
    		scanf("%d",&a[i]);
    		
    		flag=0;
    		memset(vis,0,sizeof(vis));
    		dfs(1);
    		
    		if(flag)printf("true\n");
    		else printf("false\n");
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，34人围观）

还没有评论，来说两句吧...

相关阅读

相关计蒜客强迫症的吃货（dfs+枚举）

晓萌作为一个营养学专家，吃东西的时候总是要考虑是否能满足他的各种营养物质需求，大家都说他是一个有强迫症的吃货。晓萌知道每种食品中营养物质的含量，请你帮他安排食谱，以保持他获得所

缺乏、安全感/ 2024年02月17日 22:14/ 0 赞/ 182 阅读

相关计蒜客跳跃游戏（dfs）

给定一个非负整数数组，假定你的初始位置为数组第一个下标。数组中的每个元素代表你在那个位置能够跳跃的最大长度。请确认你是否能够跳跃到数组的最后一个下标。例如：A=\[

女爷i/ 2024年02月17日 22:03/ 0 赞/ 35 阅读

相关【算法积累】计蒜客迷宫三问 (DFS & BFS)

计蒜客T1595 - 迷宫（一） [题目链接][Link 1] 一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。看在

心已赠人/ 2022年09月04日 00:52/ 0 赞/ 288 阅读

相关计蒜客组合运算式（简单DFS）

[题目传送门][Link 1] 代码： include<bits/stdc++.h> using namespace std; int

忘是亡心i/ 2022年05月14日 01:36/ 0 赞/ 197 阅读

相关计蒜客奇异家庭

[题目传送门][Link 1] dp\[i\]\[j\] – i 个节点不超过 j 层的方案数有dp\[i\]\[j\]+=dp\[t\]\[j-1\]\dp\[i-t

末蓝、/ 2022年05月14日 00:26/ 0 赞/ 204 阅读

相关计蒜客习题：蒜头君的新游戏

题目描述：工作空闲之余，蒜头君经常带着同事们做游戏，最近蒜头君发明了一个好玩的新游戏：n 位同事围成一个圈，同事 A 手里拿着一个兔妮妮的娃娃。蒜头君喊游戏开始，每位手

男娘i/ 2022年03月10日 03:36/ 0 赞/ 210 阅读

相关 (计蒜客) 取石子游戏 (gcd算法灵活运用)

蒜头君和花椰妹在玩一个游戏，他们在地上将 n 颗石子排成一排，编号为 1 到 n。开始时，蒜头君随机取出了 2 颗石子扔掉，假设蒜头君取出的 2 颗石子的编号为 a, b。游戏

港控/mmm°/ 2022年02月21日 10:42/ 0 赞/ 233 阅读

相关计蒜客踏青 dfs

题目： https://www.jisuanke.com/course/2291/182234 思路：紫书P163联通块问题。 1.遍历所有块，找到草地，判断合法性，

系统管理员/ 2022年01月06日 11:47/ 0 赞/ 248 阅读

相关【计蒜客】走迷宫

总而言之，关于迷宫好像大部分都是搜索题.... 先看一下题：（数据范围好小啊给一个n行m列的2维的迷宫，`'S'`表示迷宫的起点，`'T'`表示迷宫的

╰+哭是因爲堅強的太久メ/ 2021年12月21日 20:55/ 0 赞/ 293 阅读

相关计蒜客 - 汉诺塔

问题: ![1516087-20190501155629805-481143157.png][] 思路: 汉诺塔问题非常经典，不懂推荐去看B站正月点灯笼老师的对于汉诺塔的

悠悠/ 2021年12月03日 15:55/ 0 赞/ 313 阅读