Advertisement
krutzz

Untitled

Sep 5th, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.23 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace task1
  8. {
  9.     class Tree : IComparable<Tree>
  10.     {
  11.         public int x;
  12.         public int h;
  13.  
  14.         public Tree(int x, int h)
  15.         {
  16.             this.x = x;
  17.             this.h = h;
  18.         }
  19.  
  20.         public int CompareTo(Tree other)
  21.         {
  22.             return this.x.CompareTo(other.x);
  23.         }
  24.     }
  25.  
  26.     class Node
  27.     {
  28.         public int i;
  29.         public int d;
  30.  
  31.         public Node(int i, int d)
  32.         {
  33.             this.i = i;
  34.             this.d = d;
  35.         }
  36.     }
  37.  
  38.     class Program
  39.     {
  40.         static void Main(string[] args)
  41.         {
  42.             var line = Console.ReadLine().Split(' ');
  43.  
  44.             int n = int.Parse(line[0]);
  45.             int mj = int.Parse(line[1]);
  46.             int mh = int.Parse(line[2]);
  47.  
  48.             var trees = new Tree[n];
  49.             for (int i = 0; i < n; i++)
  50.             {
  51.                 line = Console.ReadLine().Split(' ');
  52.                 trees[i] = new Tree(int.Parse(line[0]), int.Parse(line[1]));
  53.             }
  54.  
  55.             Array.Sort(trees);
  56.  
  57.             var visited = new bool[n];
  58.  
  59.             var q = new Queue<Node>();
  60.  
  61.             visited[0] = true;
  62.  
  63.             q.Enqueue(new Node(0, 0));
  64.             while (q.Count != 0)
  65.             {
  66.                 var p = q.Dequeue();
  67.  
  68.                 for (int i = p.i + 1; i < n; i++)
  69.                 {
  70.                     if (visited[i] == true)
  71.                     {
  72.                         continue;
  73.                     }
  74.  
  75.                     if (Math.Abs(trees[p.i].x - trees[i].x) >= mj)
  76.                     {
  77.                         break;
  78.                     }
  79.  
  80.                     if (Math.Abs(trees[p.i].h - trees[i].h) >= mh)
  81.                     {
  82.                         continue;
  83.                     }
  84.  
  85.                     if (i == n - 1)
  86.                     {
  87.                         Console.WriteLine(p.d + 1);
  88.                         return;
  89.                     }
  90.                     q.Enqueue(new Node(i, p.d + 1));
  91.                     visited[i] = true;
  92.                 }
  93.             }
  94.             Console.WriteLine(-1);
  95.  
  96.         }
  97.     }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement