搜索-BFS 练习题 奇怪的电梯

2024-03-07 23:28

本文主要是介绍搜索-BFS 练习题 奇怪的电梯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

奇怪的电梯

题目链接

题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 i i i 层楼( 1 ≤ i ≤ N 1 \le i \le N 1iN)上有一个数字 K i K_i Ki 0 ≤ K i ≤ N 0 \le K_i \le N 0KiN)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: 3 , 3 , 1 , 2 , 5 3, 3, 1, 2, 5 3,3,1,2,5 代表了 K i K_i Ki K 1 = 3 K_1=3 K1=3 K 2 = 3 K_2=3 K2=3,……),从 1 1 1 楼开始。在 1 1 1 楼,按“上”可以到 4 4 4 楼,按“下”是不起作用的,因为没有 − 2 -2 2 楼。那么,从 A A A 楼到 B B B 楼至少要按几次按钮呢?

输入格式

共二行。

第一行为三个用空格隔开的正整数,表示 N , A , B N, A, B N,A,B 1 ≤ N ≤ 200 1 \le N \le 200 1N200 1 ≤ A , B ≤ N 1 \le A, B \le N 1A,BN)。

第二行为 N N N 个用空格隔开的非负整数,表示 K i K_i Ki

输出格式

一行,即最少按键次数,若无法到达,则输出 -1

样例 #1

样例输入 #1

5 1 5
3 3 1 2 5

样例输出 #1

3

提示

对于 100 % 100 \% 100% 的数据, 1 ≤ N ≤ 200 1 \le N \le 200 1N200 1 ≤ A , B ≤ N 1 \le A, B \le N 1A,BN 0 ≤ K i ≤ N 0 \le K_i \le N 0KiN

本题共 16 16 16 个测试点,前 15 15 15 个每个测试点 6 6 6 分,最后一个测试点 10 10 10 分。

题解

思路

这道题就是典型的BFS,广度优先搜索,借助队列就可以很简单实现,,因为只有上下两种状态,我们就写两个状态转移,过程中只需要注意出现负数或者大于n的情况就可以。

代码实现

import java.util.*;public class Main{static final int N = 210;static int n, a, b;static int[] k = new int[N];static boolean[] st = new boolean[N];public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();a = in.nextInt();b = in.nextInt();for(int i =1; i <= n; i ++){k[i] = in.nextInt();}int res = bfs();System.out.println(res);}public static int bfs(){Queue<pos> q = new ArrayDeque<>();pos p = new pos();p.level = a;p.step = 0;st[p.level] = true;q.add(p);while(!q.isEmpty()){p = q.poll();if(p.level == b){return p.step;}pos cur = new pos();cur.level = p.level + k[p.level];cur.step = p.step + 1;if(cur.level <= n && !st[cur.level]){st[cur.level] = true;q.add(cur);}cur = new pos(); // 必须new一下,或者重新创建一个pos对象,不然下边的操作会影响已经入队的数据cur.level = p.level - k[p.level];cur.step = p.step + 1;if(cur.level >= 1 && !st[cur.level]){st[cur.level] = true;q.add(cur);}}return -1;}
}
// 一个状态的类
class pos{int level;int step;
}

这篇关于搜索-BFS 练习题 奇怪的电梯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/785188

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

uva 10801(乘电梯dijkstra)

题意: 给几个电梯,电梯0 ~ n-1分别可以到达很多层楼。 换乘电梯需要60s时间。 问从0层到target层最小的时间。 解析: 将进入第0层的电梯60s也算上,最后减。 坑点是如果target为0输出0。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algori

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible