网站做目录,网教网站源码,WordPress调用文章改变属性,天猫建设网站的理由奇怪的电梯
题目链接
题目描述
呵呵#xff0c;有一天我做了一个梦#xff0c;梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯#xff0c;而且第 i i i 层楼#xff08; 1 ≤ i ≤ N 1 \le i \le N 1≤i≤N#xff09;上有一个数字 K i K_i Ki#xff08; 0…奇怪的电梯
题目链接
题目描述
呵呵有一天我做了一个梦梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯而且第 i i i 层楼 1 ≤ i ≤ N 1 \le i \le N 1≤i≤N上有一个数字 K i K_i Ki 0 ≤ K i ≤ N 0 \le K_i \le N 0≤Ki≤N。电梯只有四个按钮开关上下。上下的层数等于当前楼层上的那个数字。当然如果不能满足要求相应的按钮就会失灵。例如 3 , 3 , 1 , 2 , 5 3, 3, 1, 2, 5 3,3,1,2,5 代表了 K i K_i Ki K 1 3 K_13 K13 K 2 3 K_23 K23……从 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 1≤N≤200 1 ≤ A , B ≤ N 1 \le A, B \le N 1≤A,B≤N。
第二行为 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 1≤N≤200 1 ≤ A , B ≤ N 1 \le A, B \le N 1≤A,B≤N 0 ≤ K i ≤ N 0 \le K_i \le N 0≤Ki≤N。
本题共 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(){Queuepos 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;
}
