首页 > 代码库 > 遍历查找跳格子逻辑
遍历查找跳格子逻辑
package solution; import java.util.Scanner; import java.util.Stack; public class Jump { static boolean found=false; static int count=0; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); for(int cases=1;cases<=N;cases++){ int len=sc.nextInt(); int s=sc.nextInt()-1; int f=sc.nextInt()-1; int steps[]=new int[len]; for(int k=0;k<len;k++){ steps[k]=sc.nextInt(); } Stack<Integer> t=new Stack<Integer>(); Stack<Integer> q=new Stack<Integer>(); found=false; count=0; Jump j=new Jump(); j.findtarget(steps, s, f, t,q); if(found){ System.out.println("#"+cases+" "+(count)); for(int i=0;i<t.size();i++){ // print path //System.out.println(t.get(i)); } }else{ System.out.println("#"+cases+" -1"); } } sc.close(); } public void findtarget(int steps[],int s,int f,Stack<Integer> t,Stack<Integer> q){ if(checkbound(steps,s)&&!found) { //left if((s>1)&&checkbound(steps,s-steps[s])&&!q.contains(s)&&!q.contains(s-steps[s])&&!found){ t.add(s-steps[s]); q.add(s); count++; if(t.peek()==f){ found=true; }else{ findtarget(steps,t.peek(),f,t,q); } } else //right if((s<steps.length)&&checkbound(steps,s+steps[s])&&!q.contains(s)&&!q.contains(s+steps[s])&&!found){ t.add(s+steps[s]); q.add(s); count++; if(t.peek()==f){ found=true; }else{ findtarget(steps,t.peek(),f,t,q); } } } } public static boolean checkbound(int setpn[],int p){ boolean r=true; if( p>setpn.length || p<0) r=false; return r; } } /* 例如 有10个 整数 1 4 2 2 4 3 6 7 10 5 从第3个数开始 可以左右跳, 第三个数对应的值是2,所以可以向左或者向右跳2个位置, 比如向左跳2个位置,到达第1个数, 求 要到达数字6 要跳多少次? 如果没有到达最终的数字的可以打印 -1,如果有打印 次数。 给出下面5组用例, 以及每个用例包含的数字,和 开始位置 结束位置。 5 4 2 3 1 6 1 1 4 2 3 1 2 2 2 4 2 3 1 2 2 1 10 3 6 1 4 2 2 4 3 6 7 10 5 100 1 100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 #1 -1 #2 -1 #3 2 #4 3 #5 99 */
遍历查找跳格子逻辑
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。