Advertisement
Nickpips

bunnies

Sep 5th, 2016
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.09 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.Scanner;
  4.  
  5. public class bunnies {
  6.     public static void main(String[] args) {
  7.         Scanner in = new Scanner(System.in);
  8.  
  9.         int T = in.nextInt();
  10.  
  11.         for (int t = 1; t <= T; t++) {
  12.             int n = in.nextInt();
  13.             int[] tmps = new int[n];
  14.             int[] hums = new int[n];
  15.  
  16.             HashMap<Integer, ArrayList<Integer>> Phums = new HashMap<Integer, ArrayList<Integer>>();
  17.             HashMap<Integer, ArrayList<Integer>> Nhums = new HashMap<Integer, ArrayList<Integer>>();
  18.  
  19.             for (int i = 0; i < n; i++) {
  20.                 tmps[i] = in.nextInt();
  21.             }
  22.  
  23.             for (int i = 0; i < n; i++) {
  24.                 hums[i] = in.nextInt();
  25.             }
  26.  
  27.             for (int i = 0; i < n; i++) {
  28.                 int pos = tmps[i] + hums[i];
  29.                 int neg = tmps[i] - hums[i];
  30.  
  31.                 if (!Phums.containsKey(pos)) {
  32.                     Phums.put(pos, new ArrayList<Integer>());
  33.                 }
  34.                 Phums.get(pos).add(i);
  35.  
  36.                 if (!Nhums.containsKey(neg)) {
  37.                     Nhums.put(neg, new ArrayList<Integer>());
  38.                 }
  39.                 Nhums.get(neg).add(i);
  40.             }
  41.  
  42.             ArrayList<Integer> q = new ArrayList<Integer>();
  43.             boolean[] visited = new boolean[n];
  44.  
  45.             q.add(0);
  46.             visited[0] = true;
  47.  
  48.             int step;
  49.             for (step = 0; q.size() > 0 && !visited[n - 1]; step++) {
  50.                 ArrayList<Integer> nq = new ArrayList<Integer>();
  51.  
  52.                 while (q.size() > 0) {
  53.                     int ind = q.remove(q.size() - 1);
  54.  
  55.                     int pos = tmps[ind] + hums[ind];
  56.                     int neg = tmps[ind] - hums[ind];
  57.  
  58.                     if (Phums.containsKey(pos)) {
  59.                         for (int i : Phums.get(pos)) {
  60.                             if (!visited[i]) {
  61.                                 visited[i] = true;
  62.                                 nq.add(i);
  63.                             }
  64.                         }
  65.                         Phums.remove(pos);
  66.                     }
  67.  
  68.                     if (Nhums.containsKey(neg)) {
  69.                         for (int i : Nhums.get(neg)) {
  70.                             if (!visited[i]) {
  71.                                 visited[i] = true;
  72.                                 nq.add(i);
  73.                             }
  74.                         }
  75.                         Nhums.remove(neg);
  76.                     }
  77.                 }
  78.  
  79.                 q = nq;
  80.             }
  81.  
  82.             if (!visited[n - 1]) {
  83.                 step = -1;
  84.             }
  85.             System.out.println("Field #" + t + ": " + step + "\n");
  86.         }
  87.  
  88.         in.close();
  89.     }
  90.  
  91.     public static void debug(Object o) {
  92.         System.out.println("\tDEBUG: " + o.toString().replaceAll("\n", "\n\tDEBUG: "));
  93.     }
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement