Mestint ZH feladat (Kusper csop.) - Szerzetes/ÉhesHuszár

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

namespace mestint_zh_mkrisztian
{
    // Absztrakt osztályok
    abstract class AbsztraktOperátor
    {
        public abstract AbsztraktÁllapot Op(AbsztraktÁllapot a);
    }

    abstract class AbsztraktÁllapot
    {
        public List<AbsztraktOperátor> operátorok = new List<AbsztraktOperátor>();
        public abstract bool ÁllapotE();
        public abstract bool CélÁllapotE();
        public abstract int OperátorokSzáma();
        public abstract AbsztraktÁllapot SzuperOperátor(int i);
        protected virtual object Clone() { return MemberwiseClone(); }
        public override bool Equals(Object a) { return false; }
        public override int GetHashCode() { return base.GetHashCode(); }
    }

    class ÉhesOperátor : AbsztraktOperátor
    {
        int x, y;
        public ÉhesOperátor(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
        public override AbsztraktÁllapot Op(AbsztraktÁllapot a)
        {
            ÉhesHuszárÁllapot új = a as ÉhesHuszárÁllapot;
            return új.lóLépés(x, y);
        }
    }

    class SzerzetesOperátor : AbsztraktOperátor
    {
        int sz, k;
        public SzerzetesOperátor(int sz, int k)
        {
            this.sz = sz;
            this.k = k;
        }
        public override AbsztraktÁllapot Op(AbsztraktÁllapot a)
        {
            SzerzetesekÉsKannibálokÁllapot új = a as SzerzetesekÉsKannibálokÁllapot;
            return új.hajókázás(sz, k);
        }
    }

    class Csúcs
    {
        AbsztraktÁllapot állapot;
        int mélység;
        Csúcs szülő;
        public Csúcs(AbsztraktÁllapot kezdőÁllapot)
        {
            állapot = kezdőÁllapot;
            mélység = 0;
            szülő = null;
        }
        public Csúcs(AbsztraktÁllapot állapot, int mélység, Csúcs szülő)
        {
            this.állapot = állapot;
            this.mélység = mélység;
            this.szülő = szülő;
        }
        public Csúcs GetSzülő() { return szülő; }
        public int GetMélység() { return mélység; }
        public bool TerminálisCsúcsE() { return állapot.CélÁllapotE(); }
        public int OperátorokSzáma() { return állapot.OperátorokSzáma(); }
        public Csúcs SzuperOperátor(int i)
        {
            AbsztraktÁllapot új = állapot.SzuperOperátor(i);
            if (új != null) return new Csúcs(új, mélység + 1, this);
            return null;
        }
        public override bool Equals(Object obj)
        {
            Csúcs cs = (Csúcs)obj;
            return állapot.Equals(cs.állapot);
        }
        public override int GetHashCode() { return állapot.GetHashCode(); }
        public override String ToString() { return állapot.ToString(); }

    }

    abstract class GráfKereső
    {
        private Csúcs startCsúcs;
        public GráfKereső(Csúcs startCsúcs)
        {
            this.startCsúcs = startCsúcs;
        }
        protected Csúcs GetStartCsúcs() { return startCsúcs; }
        public abstract Csúcs Keresés();
        public void megoldásKiírása(Csúcs egyTerminálisCsúcs)
        {
            if (egyTerminálisCsúcs == null)
            {
                Console.WriteLine("Nincs megoldás");
                return;
            }
            Stack<Csúcs> megoldás = new Stack<Csúcs>();
            Csúcs aktCsúcs = egyTerminálisCsúcs;
            while (aktCsúcs != null)
            {
                megoldás.Push(aktCsúcs);
                aktCsúcs = aktCsúcs.GetSzülő();
            }
            foreach (Csúcs akt in megoldás) Console.WriteLine(akt);
        }
    }

    class BackTrack : GráfKereső
    {
        int korlát;
        bool emlékezetes;
        public BackTrack(Csúcs startCsúcs, int korlát, bool emlékezetes)
            : base(startCsúcs)
        {
            this.korlát = korlát;
            this.emlékezetes = emlékezetes;
        }
        public BackTrack(Csúcs startCsúcs) : this(startCsúcs, 0, false) { }
        public BackTrack(Csúcs startCsúcs, int korlát) : this(startCsúcs, korlát, false) { }
        public BackTrack(Csúcs startCsúcs, bool emlékezetes) : this(startCsúcs, 0, emlékezetes) { }
        public override Csúcs Keresés() { return Keresés(GetStartCsúcs()); }

        private Csúcs Keresés(Csúcs aktCsúcs)
        {
            int mélység = aktCsúcs.GetMélység();
            if (korlát > 0 && mélység >= korlát) return null;
            Csúcs aktSzülő = null;
            if (emlékezetes) aktSzülő = aktCsúcs.GetSzülő();
            while (aktSzülő != null)
            {
                if (aktCsúcs.Equals(aktSzülő)) return null;
                aktSzülő = aktSzülő.GetSzülő();
            }
            if (aktCsúcs.TerminálisCsúcsE())
            {
                return aktCsúcs;
            }
            for (int i = 0; i < aktCsúcs.OperátorokSzáma(); i++)
            {
                Csúcs újCsúcs = aktCsúcs.SzuperOperátor(i);
                if (újCsúcs != null)
                {
                    Csúcs terminális = Keresés(újCsúcs);
                    if (terminális != null)
                    {
                        return terminális;
                    }
                }
            }
            return null;
        }
    }

    class ÉhesHuszárÁllapot : AbsztraktÁllapot
    {
        static int N = 3;
        int x, y;
        public ÉhesHuszárÁllapot()
        {
            x = 2;
            y = 2;
            for (int i = -2; i <= 2; i++)
            {
                for (int j = -2; j <= 2; j++)
                {
                    if (i == 0 || j == 0) continue;
                    if (preLóLépés(i, j)) operátorok.Add(new ÉhesOperátor(i, j));
                }
            }
        }
        public ÉhesHuszárÁllapot(int n)
            : this()
        {
            N = n;
        }
        public override bool CélÁllapotE()
        {
            return x == N + 1 && y == N + 1;
        }
        public override bool ÁllapotE()
        {
            return x >= 2 && y >= 2 && x <= N + 1 && y <= N + 1;
        }
        private bool preLóLépés(int x, int y)
        {
            if (!(x * y == 2 || x * y == -2)) return false;
            return true;
        }
        public AbsztraktÁllapot lóLépés(int x, int y)
        {
            if (!preLóLépés(x, y)) return null;
            ÉhesHuszárÁllapot új = (ÉhesHuszárÁllapot)this.Clone();
            új.x += x;
            új.y += y;
            if (új.ÁllapotE()) return új;
            return null;
        }
        public override AbsztraktÁllapot SzuperOperátor(int i)
        {
            return operátorok[i].Op(this);

            //switch (i)
            //{
            //    case 0: return lóLépés(1, 2);
            //    case 1: return lóLépés(1, -2);
            //    case 2: return lóLépés(-1, 2);
            //    case 3: return lóLépés(-1, -2);
            //    case 4: return lóLépés(2, 1);
            //    case 5: return lóLépés(2, -1);
            //    case 6: return lóLépés(-2, 1);
            //    case 7: return lóLépés(-2, -1);
            //    default: return null;
            //}
        }
        public override int OperátorokSzáma() { return operátorok.Count; }
        public override string ToString() { return (x - 2) + " : " + (y - 2); }
        public override bool Equals(Object a)
        {
            ÉhesHuszárÁllapot aa = (ÉhesHuszárÁllapot)a;
            return aa.x == x && aa.y == y;
        }
        public override int GetHashCode()
        {
            return x.GetHashCode() + y.GetHashCode();
        }
    }

    class SzerzetesekÉsKannibálokÁllapot : AbsztraktÁllapot
    {
        int szerzetesekSzáma; // ennyi szerzetes van összesen
        int kannibálokSzáma; // ennyi kannibál van összesen
        int szerzetesekBalOldal; // szerzetesek száma a bal oldalon
        int kannibálokBalOldal; // kannibálok száma a bal oldalon
        char csonakMelyikOldalon; // Hol a csónak? Értéke vagy 'B' vagy 'J'.
        int szerzetesekJobbOldal; // szerzetesek száma a jobb oldalon
        int kannibálokJobbOldal; // kannibálok száma a jobb oldalon

        public SzerzetesekÉsKannibálokÁllapot(int sz, int k)
        {
            this.szerzetesekSzáma = sz;
            this.kannibálokSzáma = k;
            szerzetesekBalOldal = sz;
            kannibálokBalOldal = k;
            csonakMelyikOldalon = 'B';
            szerzetesekJobbOldal = 0;
            kannibálokJobbOldal = 0;

            if (preOp(0, 1)) operátorok.Add(new SzerzetesOperátor(0, 1));
            if (preOp(0, 2)) operátorok.Add(new SzerzetesOperátor(0, 2));
            if (preOp(1, 1)) operátorok.Add(new SzerzetesOperátor(1, 1));
            if (preOp(2, 0)) operátorok.Add(new SzerzetesOperátor(2, 0));
            if (preOp(1, 0)) operátorok.Add(new SzerzetesOperátor(1, 0));
        }

        public override bool ÁllapotE()
        {
            return ((szerzetesekBalOldal >= kannibálokBalOldal) || (szerzetesekBalOldal == 0)) &&
            ((szerzetesekJobbOldal >= kannibálokJobbOldal) || (szerzetesekJobbOldal == 0));
        }
        public override bool CélÁllapotE()
        {
            return szerzetesekJobbOldal == szerzetesekSzáma && kannibálokJobbOldal == kannibálokSzáma;
        }

        private bool preOp(int szerz, int kann)
        {
            if (szerz + kann > 2 || szerz + kann < 0 || szerz < 0 || kann < 0) return false;
            if (csonakMelyikOldalon == 'B')
                return szerzetesekBalOldal >= szerz && kannibálokBalOldal >= kann;
            else
                return szerzetesekJobbOldal >= szerz && kannibálokJobbOldal >= kann;
        }
        public AbsztraktÁllapot hajókázás(int szerz, int kann)
        {
            if (!preOp(szerz, kann)) return null;
            SzerzetesekÉsKannibálokÁllapot új = (SzerzetesekÉsKannibálokÁllapot)this.Clone();
            if (új.csonakMelyikOldalon == 'B')
            {
                új.szerzetesekBalOldal -= szerz;
                új.kannibálokBalOldal -= kann;
                új.csonakMelyikOldalon = 'J';
                új.szerzetesekJobbOldal += szerz;
                új.kannibálokJobbOldal += kann;
            }
            else
            {
                új.szerzetesekBalOldal += szerz;
                új.kannibálokBalOldal += kann;
                új.csonakMelyikOldalon = 'B';
                új.szerzetesekJobbOldal -= szerz;
                új.kannibálokJobbOldal -= kann;
            }
            if (új.ÁllapotE()) return új;
            return null;
        }
        public override int OperátorokSzáma() { return operátorok.Count; }
        public override AbsztraktÁllapot SzuperOperátor(int i)
        {
            return operátorok[i].Op(this);
        }

        public override string ToString()
        {
            return szerzetesekBalOldal + "," + kannibálokBalOldal + "," + csonakMelyikOldalon + "," + szerzetesekJobbOldal + "," + kannibálokJobbOldal;
        }

        public override bool Equals(Object a)
        {
            SzerzetesekÉsKannibálokÁllapot aa = (SzerzetesekÉsKannibálokÁllapot)a;
            return aa.szerzetesekBalOldal == szerzetesekBalOldal && aa.kannibálokBalOldal == kannibálokBalOldal && aa.csonakMelyikOldalon == csonakMelyikOldalon;
        }
        public override int GetHashCode()
        {
            return szerzetesekBalOldal.GetHashCode() + kannibálokBalOldal.GetHashCode() + csonakMelyikOldalon.GetHashCode();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Csúcs startCsúcs;
            GráfKereső kereső;
            Console.WriteLine("Szerzetesek és kannibálok probléma:");
            startCsúcs = new Csúcs(new SzerzetesekÉsKannibálokÁllapot(3, 3));
            kereső = new BackTrack(startCsúcs, 12, true);
            kereső.megoldásKiírása(kereső.Keresés());
            Console.WriteLine("\nÉheshuszár probléma:");
            startCsúcs = new Csúcs(new ÉhesHuszárÁllapot(8));
            kereső = new BackTrack(startCsúcs, 10, true);
            kereső.megoldásKiírása(kereső.Keresés());
            Console.ReadLine();
        }
    }
}