Advertisement
WheatleyHDD

Untitled

May 28th, 2022
533
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Drawing;
  3. using System.Linq;
  4. using System.Collections.Generic;
  5.  
  6. namespace Dungeon
  7. {
  8.     public class DungeonTask
  9.     {
  10.         public static MoveDirection[] FindShortestPath(Map map)
  11.         {
  12.             var start = map.InitialPosition;
  13.             var exit = map.Exit;
  14.             var chests = map.Chests;
  15.  
  16.             // если нет сундуков
  17.             var wayNoChest = BfsTask.FindPaths(map, start, new Point[] { exit }).FirstOrDefault();
  18.             if (wayNoChest == null) return new MoveDirection[0];
  19.             // пути от старта и конца
  20.             var wayFromStart = BfsTask.FindPaths(map, start, chests);
  21.             var wayFromExit = BfsTask.FindPaths(map, exit, chests).DefaultIfEmpty();
  22.  
  23.             var pathToExit = wayNoChest.ToList();
  24.             pathToExit.Reverse();
  25.             if (chests.Any(c => pathToExit.Contains(c)) || wayFromStart.FirstOrDefault() == null)
  26.                 return pathToExit.Zip(pathToExit.Skip(1), MoveTo).ToArray();
  27.  
  28.             return CalculatePath(wayFromStart, wayFromExit);
  29.         }
  30.  
  31.         private static MoveDirection[] CalculatePath(
  32.             IEnumerable<SinglyLinkedList<Point>> start,
  33.             IEnumerable<SinglyLinkedList<Point>> end)
  34.         {
  35.             var wayStartToExit = start.Join(end, e => e.Value, s => s.Value, (e, s) => new {
  36.                 Length = e.Length + s.Length,
  37.                 listFinish = e.ToList(),
  38.                 listStart = s.ToList()
  39.             });
  40.  
  41.             var pathList = wayStartToExit
  42.                 .OrderBy(l => l.Length)
  43.                 .Select(p => Tuple.Create(p.listFinish, p.listStart))
  44.                 .First();
  45.             pathList.Item1.Reverse();
  46.             pathList.Item1.AddRange(pathList.Item2.Skip(1));
  47.             return pathList.Item1.Zip(pathList.Item1.Skip(1), MoveTo).ToArray();
  48.         }
  49.  
  50.         private static MoveDirection MoveTo(Point start, Point finish)
  51.         {
  52.             var d = new Point(finish.X - start.X, finish.Y - start.Y);
  53.             if (d.X == -1) return MoveDirection.Left;
  54.             else if (d.X == 1) return MoveDirection.Right;
  55.             else if (d.Y == 1) return MoveDirection.Down;
  56.             return MoveDirection.Up;
  57.         }
  58.     }
  59. }
Advertisement
RAW Paste Data Copied
Advertisement