Wacky_rubia

Untitled

Mar 17th, 2014
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 5.97 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Drawing;
  4. using System.Linq;
  5. using System.Windows;
  6. using System.Collections;
  7.  
  8. namespace Flies
  9. {
  10.  
  11.     class Dec<T> : IEnumerable<T>
  12.     {
  13.         class DecItem<T>
  14.         {
  15.             public T value;
  16.             public DecItem<T> next;
  17.             public DecItem<T> previous;
  18.         }
  19.  
  20.         DecItem<T> last;
  21.         DecItem<T> first;
  22.  
  23.         public void PushInTheEnd(T arg)
  24.         {
  25.             var newitem = new DecItem<T> { value = arg, previous = last };
  26.             if (last != null)
  27.                 last.next = newitem;
  28.             else
  29.                 first = newitem;
  30.             last = newitem;
  31.  
  32.         }
  33.  
  34.         public void PushInTheStart(T arg)
  35.         {
  36.             var newitem = new DecItem<T> { value = arg, next = first };
  37.             if (first != null)
  38.                 first.previous = newitem;
  39.             else
  40.                 last = newitem;
  41.             first = newitem;
  42.         }
  43.  
  44.         public T Pop()
  45.         {
  46.             if (first == null) throw new Exception("");
  47.             var result = first.value;
  48.             first = first.next;
  49.             if (first == null)
  50.                 last = null;
  51.             return result;
  52.         }
  53.  
  54.         public bool IsEmpty()
  55.         {
  56.             return first == null;
  57.         }
  58.  
  59.         public IEnumerator<T> GetEnumerator()
  60.         {
  61.             var item = first;
  62.             while (item != null)
  63.             {
  64.                 yield return item.value;
  65.                 item = item.next;
  66.             }
  67.         }
  68.  
  69.         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  70.         {
  71.             return GetEnumerator();
  72.         }
  73.     }
  74.  
  75.     public class Answer
  76.     {
  77.         public int countOfSteps;
  78.         public int countOfChangeBoots;
  79.     }
  80.  
  81.     public class PathFinder
  82.     {
  83.  
  84.         static Point[] Neighbours = new Point[] { new Point(0, 1), new Point(0, -1), new Point(1, 0), new Point(-1, 0), new Point(1, 1), new Point(-1, -1), new Point(-1, 1), new Point(1, -1) };
  85.  
  86.         private static IEnumerable<Point> GetNeighbours(Point from, int[,] map, PointAndCount[,] boolMap)
  87.         {
  88.             return Neighbours.Select(x => new Point(from.X + x.X, from.Y + x.Y))
  89.                 .Where(x => CanMove(x.X, x.Y, map, boolMap))
  90.                 .ToArray();
  91.         }
  92.  
  93.         static bool CanMove(int x, int y, int[,] map, PointAndCount[,] boolMap)
  94.         {
  95.             return x >= 0 && y >= 0 && x < map.GetLength(0) && y < map.GetLength(1) && map[x, y] != 0;
  96.         }
  97.  
  98.         public static Answer DFS(Point source, Point target, int[,] map, PointAndCount[,] boolMap)
  99.         {
  100.             var answer = new Answer();
  101.             if (target == source)
  102.             {
  103.                 answer.countOfSteps = 1;
  104.                 return answer;
  105.             }
  106.             var queue = new Dec<Point>();
  107.             queue.PushInTheEnd(source);
  108.             map[source.X, source.Y] = 0;
  109.             boolMap[source.X, source.Y].Step = 0;
  110.             while (!queue.IsEmpty())
  111.             {
  112.                 Point top = queue.Pop();
  113.                 foreach (var neighbour in GetNeighbours(top, map, boolMap))
  114.                 {
  115.                     if (boolMap[top.X, top.Y].Step + 1 < boolMap[neighbour.X, neighbour.Y].Step ||
  116.                         boolMap[neighbour.X, neighbour.Y].point == new Point(-1, -1))
  117.                     {
  118.                         if (map[neighbour.X, neighbour.Y] == map[top.X, top.Y])
  119.                             queue.PushInTheStart(neighbour);
  120.                         else
  121.                             queue.PushInTheEnd(neighbour);
  122.                         boolMap[neighbour.X, neighbour.Y].Step = boolMap[top.X, top.Y].Step + 1;
  123.                         boolMap[neighbour.X, neighbour.Y].point = top;
  124.                     }
  125.                 }
  126.             }
  127.             var currentPoint = target;
  128.             while (boolMap[currentPoint.X, currentPoint.Y].point != source)
  129.             {
  130.                 if (boolMap[currentPoint.X, currentPoint.Y].point == new Point(-1, -1))
  131.                     return new Answer();
  132.                 answer.countOfSteps++;
  133.                 if (map[currentPoint.X, currentPoint.Y] != map[boolMap[currentPoint.X, currentPoint.Y].point.X, boolMap[currentPoint.X, currentPoint.Y].point.Y])
  134.                     answer.countOfChangeBoots++;
  135.                 currentPoint = boolMap[currentPoint.X, currentPoint.Y].point;
  136.             }
  137.             answer.countOfSteps += 2;
  138.             return answer;
  139.         }
  140.     }
  141.  
  142.     public class PointAndCount
  143.     {
  144.         public Point point;
  145.         public int Step;
  146.         public PointAndCount(Point p, int s)
  147.         {
  148.             this.point = p;
  149.             this.Step = s;
  150.         }
  151.     }
  152.  
  153.     class Program
  154.     {
  155.         public static void Main()
  156.         {
  157.             var temp = Console.ReadLine().Split();
  158.             var M = int.Parse(temp[0]);
  159.             var N = int.Parse(temp[1]);
  160.             temp = Console.ReadLine().Split();
  161.             var computer = new Point(int.Parse(temp[0]) - 1, int.Parse(temp[1]) - 1);
  162.             temp = Console.ReadLine().Split();
  163.             var refreg = new Point(int.Parse(temp[0]) - 1, int.Parse(temp[1]) - 1);
  164.             var map = new int[M, N];
  165.             for (int i = 0; i < M; i++)
  166.             {
  167.                 var tempString = Console.ReadLine();
  168.                 for (int j = 0; j < N; j++)
  169.                     map[i, j] = int.Parse(tempString[j].ToString());
  170.             }
  171.             var boolMap = new PointAndCount[M, N];
  172.             for (var i = 0; i < boolMap.GetLength(0); i++)
  173.                 for (var j = 0; j < boolMap.GetLength(1); j++)
  174.                 {
  175.                     boolMap[i, j] = new PointAndCount(new Point(-1, -1), N * M + 1);
  176.                 }
  177.             var answer = PathFinder.DFS(computer, refreg, map, boolMap);
  178.             Console.WriteLine("{0} {1}", answer.countOfSteps, answer.countOfChangeBoots);
  179.         }
  180.     }
  181. }
Advertisement
Add Comment
Please, Sign In to add comment