Форум breadcrumbs - Вы здесь:ФорумПрограммирование: С#Карлики
Вы должны войти, чтобы создавать сообщения и темы.

Карлики

Всем привет, решил порешать задачки на c# и наткнулся на эту. Уже около часа сижу туплю, подтолкните в сторону решения, пожалуйста.

ссылка на задачу

Привет!
Создал клас Gnome, который имеет список (HashSet) гномов поменьше, и если получилось так, что гном который выше, является дочерним дочернего гнома, то-есть меньше меньшего, тогда результат будет impossible.

Код

using System;
using System.Collections.Generic;

namespace ConsoleApp2
{
    class Gnome
    {
        public string Name { get; set; }
        public HashSet<Gnome> LesserGnomes { get; set; } = new HashSet<Gnome>();
    }

    class Program
    {
        static List<Gnome> gnomes = new List<Gnome>();

        /// <summary>
        /// Создаёт гнома и добавляем в список если его нет. Если есть - возвращает из списка.
        /// </summary>
        /// <param name="name">имя гнома</param>
        /// <returns>найденного или созданного гнома</returns>
        static Gnome FindOrCreateGnome(string name)
        {
            Gnome gnome = gnomes.Find(g => g.Name == name);

            if (gnome == null)
            {
                gnome = new Gnome { Name = name };
                gnomes.Add(gnome);
            }

            return gnome;
        }

        /// <summary>
        /// Рекурсивно проверяет является ли меньший гном выше
        /// </summary>
        /// <param name="higherGnomes">список гномов, которые выше</param>
        /// <param name="gnome">гном, которые содержит гномов, которые поменьше</param>
        /// <returns>true если меньший гном является выше, иначе false</returns>
        static bool Check(HashSet<Gnome> higherGnomes, Gnome gnome)
        {
            foreach (Gnome lesserGnome in gnome.LesserGnomes)
            {
                foreach (Gnome higherGnome in higherGnomes)
                {
                    if (higherGnome.Name == lesserGnome.Name)
                    {
                        return true;
                    }
                }

                higherGnomes.Add(lesserGnome);

                if (Check(higherGnomes, lesserGnome))
                {
                    return true;
                }

                higherGnomes.Remove(lesserGnome);
            }

            return false;
        }

        static void Main(string[] args)
        {
            int count = int.Parse(Console.ReadLine());

            for (int i = 0; i < count; i++)
            {
                string[] split = Console.ReadLine().Split();

                Gnome first = FindOrCreateGnome(split[0]);
                Gnome second = FindOrCreateGnome(split[2]);
                bool firstIsHigher = split[1] == ">";

                if (firstIsHigher)
                {
                    first.LesserGnomes.Add(second);
                }
                else
                {
                    second.LesserGnomes.Add(first);
                }
            }

            bool isImpossible = false;

            foreach (Gnome gnome in gnomes)
            {
                if (Check(new HashSet<Gnome> { gnome }, gnome))
                {
                    isImpossible = true;
                    break;
                }
            }

            Console.WriteLine(isImpossible ? "impossible" : "possible");
        }
    }
}


Результаты





Спасибо, буду разбираться.