SHARE
TWEET

AOC2019_Graph

video_game Dec 5th, 2019 (edited) 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace Common
  6. {
  7.     public static class Graph
  8.     {
  9.         public static int ShortestDistanceBfs<T>(T from, T to, Dictionary<T, T[]> paths)
  10.         {
  11.             var explored = new HashSet<T>();
  12.             var exploreQueue = new List<(T loc, int dist)>() { (from, 0) };
  13.  
  14.             while (exploreQueue.Count > 0)
  15.             {
  16.                 var exploring = exploreQueue[0];
  17.                 exploreQueue.RemoveAt(0);
  18.  
  19.                 if (explored.Add(exploring.loc))
  20.                 {
  21.                     var newDist = exploring.dist + 1;
  22.                     if (paths.TryGetValue(exploring.loc, out var reachableFromHere))
  23.                     {
  24.                         var unexploredAndReachable = reachableFromHere.Where(dest => !explored.Contains(dest));
  25.  
  26.                         if (unexploredAndReachable.Contains(to))
  27.                         {
  28.                             return newDist;
  29.                         }
  30.  
  31.                         foreach (var newDest in unexploredAndReachable)
  32.                         {
  33.                             exploreQueue.Add((newDest, newDist));
  34.                         }
  35.                     }
  36.                 }
  37.             }
  38.  
  39.             throw new Exception("No path found.");
  40.         }
  41.     }
  42. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top