Matematické Fórum

using System;
using System.Collections.Generic;
using System.Text;

namespace Domino
{
    class Kostka //jedna dominová kostka
    {
        public byte pole1, pole2;

        public Kostka(byte pole_1, byte pole_2)
        {
            pole1 = pole_1;
            pole2 = pole_2;
        }

        public void Otoc() //Otočí čísla kostky.
        {
            byte tmp = pole1;
            pole1 = pole2;
            pole2 = tmp;
        }

        public static bool operator == (Kostka kostka1, Kostka kostka2) //Uvažuje i rovnost stejných, avšak vzájemně otočených kostek.
        {
            return (((kostka1.pole1.Equals(kostka2.pole1)) && (kostka1.pole2.Equals(kostka2.pole2))) || ((kostka1.pole1.Equals(kostka2.pole2)) && (kostka1.pole2.Equals(kostka2.pole1))));
        }

        public static bool operator !=(Kostka kostka1, Kostka kostka2) //Uvažuje i nerovnost stejných, avšak vzájemně otočených kostek.
        {
            return !(((kostka1.pole1.Equals(kostka2.pole1)) && (kostka1.pole2.Equals(kostka2.pole2))) || ((kostka1.pole1.Equals(kostka2.pole2)) && (kostka1.pole2.Equals(kostka2.pole1))));
        }

        public static bool KostkyMajiAsponJednoShodnePole(Kostka kostka1, Kostka kostka2) //Oznamuje, že kostky mají alespoň jedno shodné pole s číslem.
        {
            return ((kostka1.pole1.Equals(kostka2.pole1)) || (kostka1.pole2.Equals(kostka2.pole2)) || (kostka1.pole1.Equals(kostka2.pole2)) || (kostka1.pole2.Equals(kostka2.pole1)));
        }
    }

    class Nacitac
    {
        private bool JeCislice(int znak) //Hlásí, zda vstupní znak je číslice.
        {
            return ((znak >= (int)'0') && (znak <= (int)'9'));
        }
        
        private byte NactiCislo() //Načte jedno číslo ze vstupu.
        {
            int vystup = 0;
            int prectenyZnak; //aktuálně přečtený znak
            do //Přeskoč všechny nečíselné znaky:
            {
                prectenyZnak = Console.Read();
            } while (!JeCislice(prectenyZnak));
            while (JeCislice(prectenyZnak)) //Čti číslo, dokud jsou na vstupu číslice:
            {
                vystup = vystup * 10 + (prectenyZnak - (int)'0');
                prectenyZnak = Console.Read();
            }
            return (byte)vystup;
        }
        
        public List<Kostka> NactiVstup(out byte pocetKostek) //Načte kostky na vstupu a vrátí je v poli kostek. Kostky, jejichž čísla nemají žádnou další do páru, jsou automaticky vyřazeny.
        {
            //System.IO.FileStream vstupniSoubor = new System.IO.FileStream("domino.in", System.IO.FileMode.Open, System.IO.FileAccess.Read);
            //System.IO.StreamReader vstup = new System.IO.StreamReader(vstupniSoubor);
            //Console.SetIn(vstup);
            pocetKostek = NactiCislo();
            List<Kostka> kostkyZeVstupu = new List<Kostka>();
            for (int i = 0; i < pocetKostek; i++)
            {
                kostkyZeVstupu.Add(new Kostka(NactiCislo(), NactiCislo()));
            }
            Kostka zpracovavanaKostka;
            bool maMoznehoSouseda;
            for (int i = 0; i < pocetKostek; i++) //Vyřazení kostek, které nejdou připojit k žádné jiné.
            {
                maMoznehoSouseda = false;
                zpracovavanaKostka = kostkyZeVstupu[i];
                for (int j = 0; j < pocetKostek;)
                {
                    if (i == j) {j++; continue;}
                    if(Kostka.KostkyMajiAsponJednoShodnePole(zpracovavanaKostka, kostkyZeVstupu[j])) maMoznehoSouseda = true;
                    j++;
                }
                if (maMoznehoSouseda == false) kostkyZeVstupu.Remove(zpracovavanaKostka);
            }
            pocetKostek = (byte) kostkyZeVstupu.Count;
            return kostkyZeVstupu;
        }
    }

    class Resitel //Instance této třídy bude mít za úkol najít pomocí rekurze řešení úlohy.
    {
        static int counter = 0;

        public void NajdiMaxRetezec(byte predchoziCislo, List<Kostka> zbyvajiciKostky, ref byte celkovyPocetKostek, ref int delkaMaxRady, ref bool hotovo, Resitel resitel)
        {
            int delkaAktualniRady = 0; //délka maximální řady pro aktuální způsob volby prvků
            List<Kostka> zpracovaneKostky = new List<Kostka>(); //zatím zpracované kostky
            List<Kostka> naslednici = zbyvajiciKostky.FindAll(delegate(Kostka kostka) { return ((predchoziCislo == kostka.pole1) || (predchoziCislo == kostka.pole2)); }); //Nalezení všech potenciálních následníků kostky.
            foreach (Kostka zpracovavanaKostka in naslednici)
            {
                if (zpracovaneKostky.Contains(zpracovavanaKostka)) continue; //Pokud již byla stejná kostka někdy zpracovávána, nemusím se současnou už dále zabývat a přejdu na další iteraci.
                zpracovaneKostky.Add(zpracovavanaKostka); //Nakonec je zpracovávaná kostka vložena do seznamu již zpracovaných kostek.
                byte noveCisloNaKonciRady = (predchoziCislo == zpracovavanaKostka.pole1) ? zpracovavanaKostka.pole2 : zpracovavanaKostka.pole1; //Zjisti nové číslo na konci řady.
                List<Kostka> zbyleKostky = resitel.VyradKostku(zbyvajiciKostky, zpracovavanaKostka);
                delkaAktualniRady = celkovyPocetKostek - zbyleKostky.Count;
                if (zbyleKostky.Count != 0) NajdiMaxRetezec(noveCisloNaKonciRady, zbyleKostky, ref celkovyPocetKostek, ref delkaMaxRady, ref hotovo, resitel); //Pokud nebyly vyčerpány všechny kostky, pokus se najít lepší řešení.
                else { delkaMaxRady = delkaAktualniRady; hotovo = true; }
                if (hotovo == true) break;
                if (delkaAktualniRady > delkaMaxRady) //Pokud bylo nalezeno delší řešení než dosavadní:
                {
                    delkaMaxRady = delkaAktualniRady;
                    if (delkaMaxRady == celkovyPocetKostek) hotovo = true; //Pokud bude nalezen řetězec o délce odpovídající počtu všech kostek, můžeme hned skončit.
                }
                else { if (++counter > (11000 * celkovyPocetKostek)) hotovo = true; };
                if (hotovo == true) break;
            }
        }
        public List<Kostka> VyradKostku(List<Kostka> seznamZbyvajicichKostek, Kostka vyrazovanaKostka) //Vytvoří nový seznam kostek, který už nebude obsahovat zadanou kostku.
        {
            List<Kostka> vyslednySeznam = new List<Kostka>(); //vytvoření nového seznamu kostek
            vyslednySeznam.AddRange(seznamZbyvajicichKostek); //zkopírování obsahu původního seznamu
            vyslednySeznam.Remove(vyrazovanaKostka); //odstranění požadované kostky
            return vyslednySeznam;
        }
    }

    class Program
    {
        
        static void Main(string[] args)
        {
            Nacitac nacitac = new Nacitac();
            byte celkovyPocetKostek;
            List<Kostka> kostkyZeVstupu = nacitac.NactiVstup(out celkovyPocetKostek);

            Resitel resitel = new Resitel();
            int delkaMaxRady = 1; //dosud maximální nalezená délka
            List<Kostka> zpracovaneKostky = new List<Kostka>(); //zatím zpracované kostky
            bool hotovo = false; //Pokud bude nalezen řetězec o délce odpovídající počtu všech kostek, můžeme hned skončit.
            foreach (Kostka zpracovavanaKostka in kostkyZeVstupu)
            {
                if (zpracovaneKostky.Contains(zpracovavanaKostka)) continue; //Pokud již byla stejná kostka někdy zpracovávána, nemusím se současnou už dále zabývat a přejdu na další iteraci.
                zpracovaneKostky.Add(zpracovavanaKostka); //Nakonec je zpracovávaná kostka vložena do seznamu již zpracovaných kostek.
                List<Kostka> zbyvajiciKostky = resitel.VyradKostku(kostkyZeVstupu, zpracovavanaKostka); //Vytvoření seznamu kostek, ze kterého vyřadíme už zvolenou první kostku.
                resitel.NajdiMaxRetezec(zpracovavanaKostka.pole2, zbyvajiciKostky, ref celkovyPocetKostek, ref delkaMaxRady, ref hotovo, resitel);
                if (delkaMaxRady == celkovyPocetKostek) break; //Pokud bude nalezen řetězec o délce odpovídající počtu všech kostek, můžeme hned skončit.
                zpracovavanaKostka.Otoc(); //Nyní zpracovávanou kostku otočím a pokusím se s ní znovu vyhledat co nejdelší řetězec.
                resitel.NajdiMaxRetezec(zpracovavanaKostka.pole2, zbyvajiciKostky, ref celkovyPocetKostek, ref delkaMaxRady, ref hotovo, resitel);
                if (delkaMaxRady == celkovyPocetKostek) break; //Pokud bude nalezen řetězec o délce odpovídající počtu všech kostek, můžeme hned skončit.
            }

            if (celkovyPocetKostek == 0) Console.Write(0); //vypsani vysledku
            else Console.Write(delkaMaxRady);
        }
    }
}