GetSafeWay.cs

CSharp · Console

/Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
					
public class Program
{
	class SafeWay
	{
		public double SafeValue { get; set; }
		public List<int> Crossroads { get; set; }
	}	
	
	static SafeWay GetSafeWay(int N, Dictionary<Tuple<int, int>, double> roadOfDeathDict)
	{
		// массив, где храним посещенные/непосещенные перекрестки
		var safeRoads = new int[N + 1];
		
		// i-й элемент массива хранит макс.вероятность спастись 
		// на пути из 1го перекрестка до i-го.
		var safeValues = new double[N + 1]; 
		
		// т.к. дорогу можно считать двусторонней, то 
		// (i, j, value) = (j, i, value)
		var keys = roadOfDeathDict.Keys.ToArray();
		foreach (Tuple<int, int> key in keys)
		{
			double safeValue = roadOfDeathDict[key] / 100.0; // работаем в абсолютных значениях
			roadOfDeathDict[key] = safeValue;
			roadOfDeathDict.Add(new Tuple<int, int>(key.Item2, key.Item1), safeValue);
		}
		
		var safeWay = new List<int>();
		safeValues[1] = 1; // на 1-м перекрестке вероятность спастись 100% (мышь пока не начала путь)
		int k = 0;
		
		// Алгоритм Дейкстры
		for (int i = 1; i < N; i++)
		{
			// На очередной итерации выбирается перекресток k
			// с наибольшей величиной safeValues[j] среди ещё не помеченных
			double max = 0;
			for (int j = 1; j <= N; j++)
			{
				if (safeRoads[j] != 1 && safeValues[j] > max)
				{
					max = safeValues[j];
					k = j;
				}
			}
			
			// далее просматриваем все перекрестки исходящие из выбранного k 
			// и для каждого такого перекрестка пытаемся улучшить вероятность спастись (берем макс.вероятность)
			for (int j = 1; j <= N; j++)
			{
				if (safeRoads[j] != 1)
				{
					double safeValue;
					roadOfDeathDict.TryGetValue(new Tuple<int, int>(k, j), out safeValue);
					safeValues[j] = Math.Max(safeValues[j], (safeValues[k] * safeValue));
				}
			}
			
			// помечем перекресток k как пройденный 
			// и сохраняем в наш маршрут
			safeRoads[k] = 1;
			safeWay.Add(k);
		}
		
		return new SafeWay
		{
			SafeValue = safeValues[N] * 100, // convert to %
			Crossroads = safeWay
		};
	}
	
	public static void Main()
	{
		Console.WriteLine("UniLecs");
		
		// для удобства используем обьект Dictionary, но тут можно было использовать обычный двухмерный массив!
		Dictionary<Tuple<int, int>, double> roadOfDeathDict = new Dictionary<Tuple<int, int>, double>()
		{
			{ new Tuple<int, int>(1, 2), 52 },
			{ new Tuple<int, int>(1, 3), 71.5 },
			{ new Tuple<int, int>(1, 4), 83.8 },
			{ new Tuple<int, int>(2, 3), 71 },
			{ new Tuple<int, int>(3, 4), 93 },
			{ new Tuple<int, int>(3, 5), 82 },
			{ new Tuple<int, int>(2, 5), 99.9 }
		};
		SafeWay result = GetSafeWay(5, roadOfDeathDict);
		
		// 1 -> 4 -> 3 -> 5
		// ~ 63.9
		Console.WriteLine(string.Format(
			"Safe way: {0}; \nSafe value of this way: {1} %", 
			string.Join(" -> ", result.Crossroads), 
			result.SafeValue ));
	}
}
;