计蒜客跳跃游戏（dfs）

女爷i 2024-02-17 22:03 172阅读 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 条评论，172人围观）

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

相关阅读

相关计蒜客迷宫（bfs）

已知一个 n 行 m 列的上下左右四联通的迷宫，其中字符 'Y' 表示起点，字符 'C' 表示终点，在途中只有一个起点和终点，字符 '\' 表示可通过的收费站，每通过一次需要花

秒速五厘米/ 2024年02月17日 22:15/ 0 赞/ 68 阅读

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

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

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

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

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

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

相关计蒜客 “救援” 问题

救生船从大本营出发，营救若干屋顶上的人回到大本营，屋顶数目以及每个屋顶的坐标和人数都将由输入决定，求出所有人都到达大本营并登陆所用的时间。在直角坐标系的原点是大本营，救生船

迷南。/ 2023年07月07日 03:34/ 0 赞/ 38 阅读

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

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

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

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

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

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

相关计蒜客奇异家庭

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

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

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

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

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

相关计蒜客踏青 dfs

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

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

相关【计蒜客】走迷宫

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

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