ADS - Kůň

/*
 * Na jisté šachovnici žil kulhavý kůň.
 * To je zvláštní šachová figurka, která v sudých tazích táhne jako jezdec, v lichých jako pěšec.
 * Vymyslete algoritmus, který z jednoho zadaného políčka dokulhá na druhé na nejmenší možný počet tahů.
 */

using System;
using System.Collections.Generic;

namespace KulhavyKun
{
    class Pozice : IEquatable<Pozice>
    {
        public int X;
        public int Y;
        public int pocitadlo;
        public Pozice() {  }
        public Pozice(int X, int Y, int pocitadlo) { this.X = X; this.Y = Y; this.pocitadlo = pocitadlo; }
        public bool Equals (Pozice pozice) { return pozice.X == X && pozice.Y == Y; }
    }
    class Program
    {
        // Šachovnici budu indexovat z levého horního rohu, tedy od 0 do 7 na obou osách.

        static Pozice KamMuzeJitPesec(Pozice odkud) // Metoda rozhoduje, na jakou pozici se může přesunout pěšec. Je vždy jen jedna (nebo žádná).
        {
            return odkud.Y == 0 ? null : new Pozice(odkud.X, odkud.Y - 1, odkud.pocitadlo + 1); // Když se nacházíme v "prvním řádku", cesta neexistuje. Zde výpočet této cesty končí.
        }

        static List<Pozice> KamMuzeJitJezdec(Pozice odkud) // Metoda rozhoduje, na jakou pozici se může přesunout jezdec.
        {
            List<Pozice> kam = new List<Pozice>();

            // "Doleva nahoru"
            if (odkud.X - 1 >= 0 && odkud.Y - 2 >= 0) { kam.Add(new Pozice(odkud.X - 1, odkud.Y - 2, odkud.pocitadlo + 1)); }
            if (odkud.X - 2 >= 0 && odkud.Y - 1 >= 0) { kam.Add(new Pozice(odkud.X - 2, odkud.Y - 1, odkud.pocitadlo + 1)); }

            // "Doprava nahoru"
            if (odkud.X + 1 <= 7 && odkud.Y - 2 >= 0) { kam.Add(new Pozice(odkud.X + 1, odkud.Y - 2, odkud.pocitadlo + 1)); }
            if (odkud.X + 2 <= 7 && odkud.Y - 1 >= 0) { kam.Add(new Pozice(odkud.X + 2, odkud.Y - 1, odkud.pocitadlo + 1)); }

            // "Doleva dolů"
            if (odkud.X - 1 >= 0 && odkud.Y + 2 <= 7) { kam.Add(new Pozice(odkud.X - 1, odkud.Y + 2, odkud.pocitadlo + 1)); }
            if (odkud.X - 2 >= 0 && odkud.Y + 1 <= 7) { kam.Add(new Pozice(odkud.X - 2, odkud.Y + 1, odkud.pocitadlo + 1)); }

            // "Doprava dolů"
            if (odkud.X + 1 <= 7 && odkud.Y + 2 <= 7) { kam.Add(new Pozice(odkud.X + 1, odkud.Y + 2, odkud.pocitadlo + 1)); }
            if (odkud.X + 2 <= 7 && odkud.Y + 1 <= 7) { kam.Add(new Pozice(odkud.X + 2, odkud.Y + 1, odkud.pocitadlo + 1)); }

            return kam.Count == 0 ? null : kam; // Pokud se z dané pozice nemůžeme s jezdcem nikam dostat, výpočet této cesty zde končí.
        }
        static void Main(string[] args)
        {
            Pozice odkud = new Pozice(5, 6, 0);
            Pozice kam = new Pozice(7, 0, 0);

            Queue<Pozice> Fronta = new Queue<Pozice>();
            Fronta.Enqueue(odkud); // BFS začneme v bodě, ve kterém se nachází náš kulhavý kůň.

            bool[,] Flags = new bool[8, 8]; // Zavedeme si značkovací pole, abychom věděli, kde jsme již byli a abychom se tak necyklili.

            Pozice aktualni;

            // Jedná se o klasické BFS s tím, že si u každé pozice pamatujeme, na kolik kroků jsme se tam dostali. Složitost by měla být O(n), kde n je počet vrcholů šachovnce. Tedy 64.
            while (!(aktualni = Fronta.Dequeue()).Equals(kam)) // Budeme iterovat do doby, dokud nedojdeme do chtěného umístění. Řekl bych, že taková cesta existuje vždy.
            {
                Flags[aktualni.X, aktualni.Y] = true;
                if (aktualni.pocitadlo % 2 == 0 && KamMuzeJitJezdec(aktualni) != null)
                    foreach (Pozice pozice in KamMuzeJitJezdec(aktualni)) if (!Flags[pozice.X, pozice.Y])
                            Fronta.Enqueue(pozice); else ;
                else if (aktualni.pocitadlo % 2 != 0 && KamMuzeJitPesec(aktualni) != null && !Flags[KamMuzeJitPesec(aktualni).X, KamMuzeJitPesec(aktualni).Y])
                    Fronta.Enqueue(KamMuzeJitPesec(aktualni));
                else continue;
            }

            Console.WriteLine(aktualni.pocitadlo);
        }
    }
}

/*
 * A ještě k tomu, že se můžeme z dané pozice dostat kamkoliv.
 * Důkaz provedeme rozborem případů.
 * Představme si, že se nacházíme ve vrcholu a chceme jít doprava - pak stačí pohnout pěšcem, skočit koněm doprava dolů a opět pohout pěšcem.
 * Obdobně pro případy, kdy chceme jít doleva nebo šikmo.
 * Pokud chceme jít dopředu, logicky stačí jen pohnout pěšcem.
 * Pokud chceme jít dolů, stačí skočit koněm BÚNO doleva dolů a pak doprava dolů. Zbytek kroků doplníme pěšci.
 * Podobně by se daly nasimlovat všechny krajní případy.
 *
 * PS: Doufám, že jsem právě nedokázal něco, co není pravda.
 */