Advertisement
shek_shek

BFS

Jan 29th, 2021
1,309
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.38 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.InputStreamReader;
  5. import java.io.OutputStream;
  6. import java.io.PrintWriter;
  7. import java.util.HashMap;
  8. import java.util.HashSet;
  9. import java.util.LinkedList;
  10. import java.util.List;
  11. import java.util.Map;
  12. import java.util.Queue;
  13. import java.util.Set;
  14. import java.util.StringTokenizer;
  15.  
  16. public class Main {
  17.  
  18.     private static class Pair implements Comparable<Pair> {
  19.         private Integer x;
  20.         private Integer y;
  21.  
  22.         Pair(Integer x, Integer y) {
  23.             this.x = x;
  24.             this.y = y;
  25.         }
  26.  
  27.         public Integer getX() {
  28.             return x;
  29.         }
  30.  
  31.         public void setX(Integer x) {
  32.             this.x = x;
  33.         }
  34.  
  35.         public Integer getY() {
  36.             return y;
  37.         }
  38.  
  39.         public void setY(Integer y) {
  40.             this.y = y;
  41.         }
  42.  
  43.         @Override
  44.         public int compareTo(Pair o) {
  45.             if (this.getX() < o.getX()) {
  46.                 return -1;
  47.             } else if (this.getX() > o.getX()) {
  48.                 return 1;
  49.             } else if (this.getX().equals(o.getX())) {
  50.                 if (this.getY() < o.getY()) {
  51.                     return -1;
  52.                 } else {
  53.                     return 1;
  54.                 }
  55.             }
  56.             return 0;
  57.         }
  58.     }
  59.  
  60.     public static void main(String[] args) {
  61.         InputStream inputStream = System.in;
  62.         OutputStream outputStream = System.out;
  63.         InputReader in = new InputReader(inputStream);
  64.         PrintWriter out = new PrintWriter(outputStream);
  65.         Task solver = new Task();
  66.         solver.solve(in, out);
  67.         out.close();
  68.     }
  69.  
  70.     static class Task {
  71.  
  72.         private long dist(Pair a, Pair b) {
  73.             return (long)Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
  74.         }
  75.  
  76.         public void solve(InputReader in, PrintWriter out) {
  77.             int n = in.nextInt();
  78.             HashMap<Integer, Pair> points = new HashMap<>();
  79.             HashMap<Integer, List<Integer>> g = new HashMap<>();
  80.             Map<Integer, Integer> d = new HashMap<>();
  81.             for (int i = 0; i < n; i++) {
  82.                 g.put(i, new LinkedList<>());
  83.                 d.put(i, 0);
  84.                 int x = in.nextInt(), y = in.nextInt();
  85.                 points.put(i, new Pair(x, y));
  86.             }
  87.             long k = in.nextLong();
  88.             int start = in.nextInt() - 1, end = in.nextInt() - 1;
  89.  
  90.             for (int i = 0; i < n; i++) {
  91.                 for (int j = i + 1; j < n; j++) {
  92.                     if (dist(points.get(i), points.get(j)) <= k) {
  93.                         g.get(i).add(j);
  94.                         g.get(j).add(i);
  95.                     }
  96.                 }
  97.             }
  98.  
  99.             Queue<Integer> q = new LinkedList<>();
  100.             q.add(start);
  101.  
  102.             Set<Integer> used = new HashSet<>();
  103.             used.add(start);
  104.  
  105.             while (!q.isEmpty()) {
  106.                 int v = q.poll();
  107.                 for (int to : g.get(v)) {
  108.                     if (!used.contains(to)) {
  109.                         used.add(to);
  110.                         q.add(to);
  111.                         d.put(to, d.get(v) + 1);
  112.                     }
  113.                 }
  114.             }
  115.             if (used.contains(end)) {
  116.                 out.println(d.get(end));
  117.             } else {
  118.                 out.println(-1);
  119.             }
  120.         }
  121.     }
  122.  
  123.     static class InputReader {
  124.         public BufferedReader reader;
  125.         public StringTokenizer tokenizer;
  126.  
  127.         public InputReader(InputStream stream) {
  128.             reader = new BufferedReader(new InputStreamReader(stream), 2000);
  129.             tokenizer = null;
  130.         }
  131.  
  132.         public String next() {
  133.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  134.                 try {
  135.                     tokenizer = new StringTokenizer(reader.readLine());
  136.                 } catch (IOException e) {
  137.                     throw new RuntimeException(e);
  138.                 }
  139.             }
  140.             return tokenizer.nextToken();
  141.         }
  142.  
  143.         public int nextInt() {
  144.             return Integer.parseInt(next());
  145.         }
  146.  
  147.         public long nextLong() {
  148.             return Long.parseLong(next());
  149.         }
  150.  
  151.         public double nextDouble() {
  152.             return Double.parseDouble(next());
  153.         }
  154.  
  155.     }
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement