Zadanie polega na napisanie programu zgodnie z zaleceniami poniżej. Nie przechodzi jednego testu. Polecam wkleić kod do jakiegoś edytora, wtedy wygląda bardziej przejrzyście.
Jakieś pomysły? 
Story:
Help the fellowship! They are trapped in the mines of Moria, with orcs closing in from all sides. Their only hope is Gandalf’s wizardry. Gandalf can create portals through which they can quickly travel from one spot to another. However portals can be opened in limited spots only, and in a limited number of ways. Your program must print the path they should follow to be safely out.
--------------------------------------------------- xxx ---------------------------------------------------
Rules:
The Spots will be INDEXED as 0, 1, 2, 3, ...
You will be given the COORDINATES OF THE SPOTS to where Gandalf can create a portal.
You will be given the COORDINATES OF THE ORCS.
You will also be given the POSSIBLE PATHS from one spot to another. (the indexes)
(note: the paths are double sided. this means that if a path is possible from spot 2 to spot 5, then it is possible to go from 2 to 5, as also from 5 to 2)
--------------------------------------------------- xxx ---------------------------------------------------
The Problem:
Your algorithm should display the sequence of the spots in order of how the fellowship go in order to reach the end fastest, and safely.
(note: the fellowship can travel from one spot to another along the POSSIBLE PATHS only)
You will be given the index of the STARTING SPOT and also the ENDING SPOT.
--------------------------------------------------- xxx ---------------------------------------------------
Note:
1. For every move of the fellowship, each orc can move by a distance of 1. If you need N moves to reach a spot, and distance from the starting point of an orc to that spot is ≤ N, you cannot go there or you might be killed.
For example, if spot 2 and spot 5 are connected by a path, and coordinates of 2 is (1,0) and 5 is (2,2), and an orc is present at (1,2), then the fellowship cannot go from spot 2 to spot 5, as time taken by the fellowship is 1 UNIT, and distance moved by the orc in 1 unit time is 1 UNIT ((2,1) and (2,2) are separated by distance 1 UNIT).
2. The fellowship can only move along the paths from one spot to another.
For example, if spot 2 and spot 5 are connected by a path, and coordinates of 2 is (1,0) and 5 is (2,2), then from 2 the fellowship can move only to 5, and not to any random spot {say (1,2)} [i.e. they can only move to a spot, which is connected] .
3. Distances are calculated by the distance formula: dist = sqrt( (p1.x-p2.x)^2 + (p1.y-p2.y)^2 ) (i.e. distances are Pythagorean)
Kilka testów:
4
0
4
0 0
0 1
1 0
1 1
3 2
2 1
1 0
3 0
0
3
12
2
13
0 0
3 0
5 -2
5 2
8 2
8 -2
10 0
-2 10
5 -5
-3 -5
-3 0
-3 5
5 4
12 5
0 1
1 2
1 3
2 5
3 6
5 6
4 6
4 7
2 8
8 9
9 10
10 11
7 11
0
7
0 1 2 8 9 10 11 7
9
3
9
0 0
3 0
5 -2
5 2
8 2
8 -2
10 0
10 4
3 4
8 -4
1 4
10 8
0 1
1 2
1 3
2 5
3 4
5 6
4 7
4 6
3 8
0
6
0 1 3 4 6
Po zatwierdzeniu programu wszystkie testy przechodzą późnej jeszcze zostaje sprawdzony przez validator do którego nie mam wglądu .
Kod pisany 4fun z jak największą ilością linq, niekorzystająca z żadnych algorytmów do grafów.
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Point<T>
{
public T X;
public T Y;
public static void Print (Point<T> Point)
{
Console.Error.WriteLine("X: {0} Y: {1}", Point.X, Point.Y);
}
}
class Solution
{
static void Main (string[] args)
{
string[] inputs;
int N = int.Parse(Console.ReadLine());
int M = int.Parse(Console.ReadLine());
int L = int.Parse(Console.ReadLine());
List<Point<int>> Spots = new List<Point<int>>();
List<Point<int>> Orcs = new List<Point<int>>();
Dictionary<int, Tuple<int, int>> PathPointsIndices = new Dictionary<int, Tuple<int, int>>();
int StartPointIndice;
int StopPointIndice;
for ( int i = 0 ; i < N ; i++ )
{
inputs = Console.ReadLine().Split(' ');
int XS = int.Parse(inputs[0]);
int YS = int.Parse(inputs[1]);
Spots.Add(new Point<int> { X = XS, Y = YS });
}
for ( int i = 0 ; i < M ; i++ )
{
inputs = Console.ReadLine().Split(' ');
int XO = int.Parse(inputs[0]);
int YO = int.Parse(inputs[1]);
Orcs.Add(new Point<int> { X = XO, Y = YO });
}
for ( int i = 0 ; i < L ; i++ )
{
inputs = Console.ReadLine().Split(' ');
int N1 = int.Parse(inputs[0]);
int N2 = int.Parse(inputs[1]);
PathPointsIndices.Add(i, new Tuple<int, int>(N1, N2));
}
StartPointIndice = int.Parse(Console.ReadLine());
StopPointIndice = int.Parse(Console.ReadLine());
Console.Error.WriteLine("Starting Point: ");
Point<int>.Print(Spots[StartPointIndice]);
Console.Error.WriteLine("Spots Points: ");
Spots.ForEach(Point<int>.Print);
PathPointsIndices.ToList().ForEach(a => Console.Error.WriteLine(a.Value));
Orcs.ForEach(Point<int>.Print);
Console.Error.WriteLine("Start: {0}.", StartPointIndice);
Console.Error.WriteLine("Stop: {0}.", StopPointIndice);
//routes.Keys.ToList().ForEach(r => PathPointsIndices.Remove(r));
HashSet<string> result = FindPaths(routes: PathPointsIndices, pathPointsIndices: PathPointsIndices,
orcs: Orcs, spots: Spots, startPointIndice: StartPointIndice, stopPointIndice: StopPointIndice, indices: StartPointIndice.ToString());
Console.Error.WriteLine("Result:");
if ( result.Count != 0 )
{
result.ToList().ForEach(Console.Error.WriteLine);
var paths = result.ToList().Select(a => a.Split(' ').ToArray()).ToList();
var pathsInt = new List<int[]>();
foreach ( var r in paths )
{
pathsInt.Add(
Array.ConvertAll(r, e => Int32.Parse(e)));
}
var distance = pathsInt.Select(r => r.Aggregate((_e, e) => _e + e)).ToArray();
for ( int i = 0 ; i < paths.Count ; i++ )
{
Console.Error.WriteLine("Dostance for path: {0} = {1}.", paths[i].Aggregate((_e, e) => _e + " " + e), distance[i]);
}
var ans = result.OrderBy(o => o.Length).ToList();
Console.Error.WriteLine("Answer:");
Console.WriteLine(ans.First());
}
else Console.WriteLine("IMPOSSIBLE");
//Tests
Console.Error.WriteLine("Tests:");
Console.Error.WriteLine(CalcDistance<int>(new Point<int> { X = 0, Y = 0 }, new Point<int> { X = 1, Y = 1 }));
Console.Error.WriteLine(Math.Pow(2, 2));
//var res = calcDistance<string> (new Point<string>{X="asd",Y="ds"}, new Point<string>{X="asd",Y="ds"});
Console.ReadKey();
}
public static double CalcDistance<T> (Point<T> P1, Point<T> P2)
{
dynamic P11 = P1, P22 = P2;
double dd = Math.Pow(P11.X - P22.X, 2) + Math.Pow(P11.Y - P22.Y, 2);
return Math.Sqrt(dd);
}
public static bool isPossible<T> (Point<T> from, Point<T> to, List<Point<T>> Orcs)
{
var d1 = CalcDistance(from, to);
bool result = true;
Orcs.ForEach(o =>
{
var d2 = CalcDistance(o, to);
if ( d2 <= d1 ) result = false;
});
//return Orcs.Any(o => CalcDistance(o, to) >= d1);
return result;
}
static bool init = false;
public static HashSet<string> FindPaths (Dictionary<int, Tuple<int, int>> routes, Dictionary<int, Tuple<int, int>> pathPointsIndices,
List<Point<int>> orcs, List<Point<int>> spots, int startPointIndice, int stopPointIndice, string indices)
{
HashSet<string> stringRouts = new HashSet<string>();
Dictionary<int, Tuple<int, int>> _pathPointsIndices = new Dictionary<int, Tuple<int, int>>(pathPointsIndices);
Dictionary<int, Tuple<int, int>> _routes = new Dictionary<int, Tuple<int, int>>(routes);
Console.Error.WriteLine("FindPaths:");
string _indicies = indices;
//routes.Keys.ToList().ForEach(r => _pathPointsIndices.Remove(r));
//Found possibly paths
if ( !init )
{
var _indexesToReverse = _routes.Where(p => p.Value.Item2 == startPointIndice).Select(s => s.Key).ToList();
Console.Error.Write("Indexes to reverse: \n");
_indexesToReverse.ForEach(Console.Error.WriteLine);
_indexesToReverse.ForEach(i =>
{
Console.Error.WriteLine("Before Reverse: {0}", _routes[i]);
_routes[i] = new Tuple<int, int>(_routes[i].Item2, _routes[i].Item1);
Console.Error.WriteLine("After Reverse: {0}", _routes[i]);
});
_routes = routes.Where(e => e.Value.Item1 == startPointIndice).ToDictionary(i => i.Key, i => i.Value);
_routes.ToList().ForEach(r => _pathPointsIndices.Remove(r.Key));
init = true;
}
foreach ( var r in _routes )
{
//Check whetever of given routes already goes to Stop(S) point.
if ( r.Value.Item2 == stopPointIndice && isPossible<int>(spots[r.Value.Item1], spots[r.Value.Item2], orcs))
{
_indicies += " " + r.Value.Item2;
stringRouts.Add(_indicies);
Console.Error.WriteLine("Finished succes of route: {0}", _indicies);
break;
}
Console.Error.WriteLine("Founded routes starting at {0}.", r.Value.Item2);
//Find possibly paths
var indexesToReverse = _pathPointsIndices.Where(p => p.Value.Item2 == r.Value.Item2).Select(s => s.Key).ToList();
Console.Error.Write("Indexes to reverse: \n");
indexesToReverse.ForEach(Console.Error.WriteLine);
indexesToReverse.ForEach(i =>
{
Console.Error.WriteLine("Before Reverse: {0}", _pathPointsIndices[i]);
_pathPointsIndices[i] = new Tuple<int, int>(_pathPointsIndices[i].Item2, _pathPointsIndices[i].Item1);
Console.Error.WriteLine("After Reverse: {0}", _pathPointsIndices[i]);
});
_routes = _pathPointsIndices.Where(p => p.Value.Item1 == r.Value.Item2 &&
isPossible<int>(spots[p.Value.Item1], spots[p.Value.Item2], orcs) == true)
.ToDictionary(i => i.Key, i => i.Value);
_routes.ToList().ForEach(e => _pathPointsIndices.Remove(e.Key));
Console.Error.WriteLine("Possible routes");
_routes.ToList().ForEach(a => Console.Error.WriteLine(a));
if ( _routes.Count != 0 )
{
stringRouts.UnionWith(
FindPaths(_routes, _pathPointsIndices,
orcs, spots, startPointIndice, stopPointIndice, _indicies + " " + r.Value.Item2)
);
}
Console.Error.WriteLine("Finished of route: {0}", _indicies);
}
return stringRouts;
}
}