Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Drawing;
- using System.Linq;
- using System.Windows;
- using System.Collections;
- namespace Flies
- {
- class Dec<T> : IEnumerable<T>
- {
- class DecItem<T>
- {
- public T value;
- public DecItem<T> next;
- public DecItem<T> previous;
- }
- DecItem<T> last;
- DecItem<T> first;
- public void PushInTheEnd(T arg)
- {
- var newitem = new DecItem<T> { value = arg, previous = last };
- if (last != null)
- last.next = newitem;
- else
- first = newitem;
- last = newitem;
- }
- public void PushInTheStart(T arg)
- {
- var newitem = new DecItem<T> { value = arg, next = first };
- if (first != null)
- first.previous = newitem;
- else
- last = newitem;
- first = newitem;
- }
- public T Pop()
- {
- if (first == null) throw new Exception("");
- var result = first.value;
- first = first.next;
- if (first == null)
- last = null;
- return result;
- }
- public bool IsEmpty()
- {
- return first == null;
- }
- public IEnumerator<T> GetEnumerator()
- {
- var item = first;
- while (item != null)
- {
- yield return item.value;
- item = item.next;
- }
- }
- System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
- {
- return GetEnumerator();
- }
- }
- public class Answer
- {
- public int countOfSteps;
- public int countOfChangeBoots;
- }
- public class PathFinder
- {
- 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) };
- private static IEnumerable<Point> GetNeighbours(Point from, int[,] map, Point[,] boolMap)
- {
- return Neighbours.Select(x => new Point(from.X + x.X, from.Y + x.Y))
- .Where(x => CanMove(x.X, x.Y, map, boolMap))
- .ToArray();
- }
- static bool CanMove(int x, int y, int[,] map, Point[,] boolMap)
- {
- return x >= 0 && y >= 0 && x < map.GetLength(0) && y < map.GetLength(1) && map[x, y] != 0 && boolMap[x, y] == new Point(-1, -1);
- }
- public static Answer DFS(Point source, Point target, int[,] map, Point[,] boolMap)
- {
- var answer = new Answer();
- if (target == source)
- {
- answer.countOfSteps = 1;
- return answer;
- }
- var queue = new Dec<Point>();
- queue.PushInTheEnd(source);
- map[source.X, source.Y] = 0;
- while (!queue.IsEmpty())
- {
- Point top = queue.Pop();
- foreach (var neighbour in GetNeighbours(top, map, boolMap))
- {
- boolMap[neighbour.X, neighbour.Y] = top;
- if (map[neighbour.X, neighbour.Y] == map[top.X, top.Y])
- queue.PushInTheStart(neighbour);
- else
- queue.PushInTheEnd(neighbour);
- }
- }
- var currentPoint = target;
- while (boolMap[currentPoint.X, currentPoint.Y] != source)
- {
- if (boolMap[currentPoint.X, currentPoint.Y] == new Point(-1,-1))
- return new Answer();
- answer.countOfSteps++;
- if (map[currentPoint.X, currentPoint.Y] != map[boolMap[currentPoint.X, currentPoint.Y].X, boolMap[currentPoint.X, currentPoint.Y].Y])
- answer.countOfChangeBoots++;
- currentPoint = boolMap[currentPoint.X, currentPoint.Y];
- }
- answer.countOfSteps += 2;
- return answer;
- }
- }
- class Program
- {
- public static void Main()
- {
- var temp = Console.ReadLine().Split();
- var M = int.Parse(temp[0]);
- var N = int.Parse(temp[1]);
- temp = Console.ReadLine().Split();
- var computer = new Point(int.Parse(temp[0]) - 1, int.Parse(temp[1]) - 1);
- temp = Console.ReadLine().Split();
- var refreg = new Point(int.Parse(temp[0]) - 1, int.Parse(temp[1]) - 1);
- var map = new int[M, N];
- for (int i = 0; i < M; i++)
- {
- var tempString = Console.ReadLine();
- for (int j = 0; j < N; j++)
- map[i, j] = int.Parse(tempString[j].ToString());
- }
- var boolMap = new Point[M, N];
- for (var i = 0; i < boolMap.GetLength(0); i++)
- for (var j = 0; j < boolMap.GetLength(1); j++)
- {
- boolMap[i, j].X = -1;
- boolMap[i, j].Y = -1;
- }
- var answer = PathFinder.DFS(computer, refreg, map, boolMap);
- Console.WriteLine("{0} {1}", answer.countOfSteps, answer.countOfChangeBoots);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment