Wacky_rubia

Untitled

Mar 17th, 2014
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 5.36 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, Point[,] 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, Point[,] boolMap)
  94.         {
  95.             return x >= 0 && y >= 0 && x < map.GetLength(0) && y < map.GetLength(1) && map[x, y] != 0 && boolMap[x, y] == new Point(-1, -1);
  96.         }
  97.  
  98.         public static Answer DFS(Point source, Point target, int[,] map, Point[,] 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.             while (!queue.IsEmpty())
  110.             {
  111.                 Point top = queue.Pop();
  112.                 foreach (var neighbour in GetNeighbours(top, map, boolMap))
  113.                 {
  114.                     boolMap[neighbour.X, neighbour.Y] = top;
  115.                         if (map[neighbour.X, neighbour.Y] == map[top.X, top.Y])
  116.                             queue.PushInTheStart(neighbour);
  117.                         else
  118.                             queue.PushInTheEnd(neighbour);
  119.                 }
  120.             }
  121.             var currentPoint = target;
  122.             while (boolMap[currentPoint.X, currentPoint.Y] != source)
  123.             {
  124.                 if (boolMap[currentPoint.X, currentPoint.Y] == new Point(-1,-1))
  125.                     return new Answer();
  126.                 answer.countOfSteps++;
  127.                 if (map[currentPoint.X, currentPoint.Y] != map[boolMap[currentPoint.X, currentPoint.Y].X, boolMap[currentPoint.X, currentPoint.Y].Y])
  128.                     answer.countOfChangeBoots++;
  129.                 currentPoint = boolMap[currentPoint.X, currentPoint.Y];
  130.             }
  131.             answer.countOfSteps += 2;
  132.             return answer;
  133.         }
  134.     }
  135.  
  136.     class Program
  137.     {
  138.         public static void Main()
  139.         {
  140.             var temp = Console.ReadLine().Split();
  141.             var M = int.Parse(temp[0]);
  142.             var N = int.Parse(temp[1]);
  143.             temp = Console.ReadLine().Split();
  144.             var computer = new Point(int.Parse(temp[0]) - 1, int.Parse(temp[1]) - 1);
  145.             temp = Console.ReadLine().Split();
  146.             var refreg = new Point(int.Parse(temp[0]) - 1, int.Parse(temp[1]) - 1);
  147.             var map = new int[M, N];
  148.             for (int i = 0; i < M; i++)
  149.             {
  150.                 var tempString = Console.ReadLine();
  151.                 for (int j = 0; j < N; j++)
  152.                     map[i, j] = int.Parse(tempString[j].ToString());
  153.             }
  154.             var boolMap = new Point[M, N];
  155.             for (var i = 0; i < boolMap.GetLength(0); i++)
  156.                 for (var j = 0; j < boolMap.GetLength(1); j++)
  157.                 {
  158.                     boolMap[i, j].X = -1;
  159.                     boolMap[i, j].Y = -1;
  160.                 }
  161.             var answer = PathFinder.DFS(computer, refreg, map, boolMap);
  162.             Console.WriteLine("{0} {1}", answer.countOfSteps, answer.countOfChangeBoots);
  163.         }
  164.     }
  165. }
Advertisement
Add Comment
Please, Sign In to add comment