using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Globalization;
using System.Threading;
using System.Drawing;
using System.Collections;

namespace ConsoleApplication1
{
    class Vrchol
    {
        private int indexVrcholu;
        private int indexPredchudce;
        private int nejkratsiCestaZVrcholu;
        private Point souradnice;

        public int IndexVrcholu {
            get { return indexVrcholu; }
            set { indexVrcholu = value; }
        }

        public int IndexPredchudce
        {
            get { return indexPredchudce; }
            set { indexPredchudce = value; }
        }

        public int NejkratsiCestaZVrcholu
        {
            get { return nejkratsiCestaZVrcholu; }
            set { nejkratsiCestaZVrcholu = value; }
        }

        public Point Souradnice
        {
            get { return souradnice; }
            set { souradnice = value; }
        }

        public Vrchol(int a, int b, int c, Point p)
        {
            IndexVrcholu = a;
            IndexPredchudce = b;
            NejkratsiCestaZVrcholu = c;
            Souradnice = p;
        }

        public void ZapsatCestuDoMaticeSousednosti(int[][] maticeSousednosti)
        {
            try
            {
                int radek, sloupec;
                if (this.IndexVrcholu > this.IndexPredchudce)
                {
                    radek = maticeSousednosti[0].Length - this.IndexVrcholu;
                    sloupec = this.IndexPredchudce;
                }
                else
                {
                    radek = maticeSousednosti[0].Length - this.IndexPredchudce;
                    sloupec = this.IndexVrcholu;
                }
                maticeSousednosti[radek][sloupec] = this.NejkratsiCestaZVrcholu;
            }
            catch (Exception)
            {
                //Console.WriteLine(this.IndexVrcholu + " Chyba!");
            }
        }
    }

    class Bludiste
    {
        //sever
        readonly byte sever = 1;

        //vychod
        readonly byte vychod = 2;

        //jih
        readonly byte jih = 4;

        //západ
        readonly byte zapad = 8;

        //konecný bod
        readonly byte end = 16;

        private byte[,] bludiste;
        private byte[,] bludisteObracene;
        private int[][] maticeSousednosti;
        private List<Vrchol> vrcholy;
        private List<int> hotoveVrcholy;

        static void Main(string[] args)
        {
            Bludiste bludiste = new Bludiste();

            int r = 0;
            int s = 0;
            while (r == 0 || s == 0)
            {
                try
                {
                    Console.WriteLine("Zadejte pocet radku: ");
                    r = int.Parse(Console.ReadLine());
                    Console.WriteLine("Zadejte pocet sloupcu: ");
                    s = int.Parse(Console.ReadLine());

                    if (r <= 0 || s <= 0)
                    {
                        throw new Exception();
                    }
                }
                catch (Exception e)
                {
                    Console.WriteLine("Zadejte nenulovou, kladnou hodnotu.");
                }
            }

            bludiste.inicializuj(r, s);
            bludiste.Generuj();
            bludiste.vypisBludiste();
            Console.WriteLine();
        }

        /*******IMPROVING*****/

        private void ZapsatKrizovatkuDoBludiste(Vrchol v)
        {
            if (v.IndexPredchudce >= 0)
            {
                int x1, x2, y1, y2;
                x1 = v.Souradnice.X;
                x2 = IndexNaSouradnice(v.IndexPredchudce).X;
                y1 = v.Souradnice.Y;
                y2 = IndexNaSouradnice(v.IndexPredchudce).Y;

                if (x1 == x2)
                {
                    if (y1 > y2)
                    {
                        bludiste[x1, y1] |= zapad;
                        bludiste[x2, y2] |= vychod;
                    }
                    else
                    {
                        bludiste[x1, y1] |= vychod;
                        bludiste[x2, y2] |= zapad;
                    }
                }

                if (y1 == y2)
                {
                    if (x1 > x2)
                    {
                        bludiste[x1, y1] |= sever;
                        bludiste[x2, y2] |= jih;
                    }
                    else
                    {
                        bludiste[x1, y1] |= jih;
                        bludiste[x2, y2] |= sever;
                    }
                }
            }
        }

        private void Generuj()
        {
            while (vrcholy.Count != 0)
            {
                Vrchol min = null;
                if ((min = GetMinCestu()) != null)
                {
                    PridejSousedyDoPole(min);
                    DeleteVrchol(min.IndexVrcholu);
                    min.ZapsatCestuDoMaticeSousednosti(maticeSousednosti);
                    ZapsatKrizovatkuDoBludiste(min);
                    VypisVrcholyVPoli();
                }
            }
        }

        private Point IndexNaSouradnice(int index)
        {
            return new Point(index/bludiste.GetLength(1), index%bludiste.GetLength(1));
        }

        private int SouradniceNaIndex(Point souradnice)
        {
            return souradnice.X * bludiste.GetLength(1) + souradnice.Y;
        }

        public bool VrcholJeHotovy(int index)
        {
            if (hotoveVrcholy.Contains(index)) {
                return true;
            } else return false;
        }

        private void PridejSousedyDoPole(Vrchol vrchol)
        {
            Random r = new Random();

            Vrchol sever = new Vrchol(vrchol.IndexVrcholu - bludiste.GetLength(1), vrchol.IndexVrcholu,
                r.Next(1, 100), new Point(vrchol.Souradnice.X - 1, vrchol.Souradnice.Y));

            r = new Random();

            Vrchol vychod = new Vrchol(vrchol.IndexVrcholu + 1, vrchol.IndexVrcholu,
                r.Next(1, 100), new Point(vrchol.Souradnice.X, vrchol.Souradnice.Y + 1));

            r = new Random();

            Vrchol jih = new Vrchol(vrchol.IndexVrcholu + bludiste.GetLength(1), vrchol.IndexVrcholu,
                r.Next(1, 100), new Point(vrchol.Souradnice.X + 1, vrchol.Souradnice.Y));

            r = new Random();

            Vrchol zapad = new Vrchol(vrchol.IndexVrcholu - 1, vrchol.IndexVrcholu,
                r.Next(1, 100), new Point(vrchol.Souradnice.X, vrchol.Souradnice.Y - 1));

            
            PridejVrchol(sever);

            PridejVrchol(vychod);

            PridejVrchol(jih);

            PridejVrchol(zapad);
        }

        private bool JeHranaVMatici(Vrchol v)
        {
            try
            {
                int radek, sloupec;
                if (v.IndexVrcholu > v.IndexPredchudce)
                {
                    radek = maticeSousednosti[0].Length - v.IndexVrcholu;
                    sloupec = v.IndexPredchudce;
                }
                else
                {
                    radek = maticeSousednosti[0].Length - v.IndexPredchudce;
                    sloupec = v.IndexVrcholu;
                }
                if (maticeSousednosti[radek][sloupec] == 0)
                {
                    return false;
                }
                else return true;
            }
            catch (IndexOutOfRangeException)
            {
                return false;
            }
        }

        private void VypisVrcholyVPoli()
        {
            Console.WriteLine("I P D X Y");
            Console.WriteLine("-----------");
            foreach (Vrchol v in vrcholy)
            {
                Console.WriteLine(v.IndexVrcholu + " " + v.IndexPredchudce + " " + v.NejkratsiCestaZVrcholu
                    + " " + v.Souradnice.X + " " + v.Souradnice.Y);
            }
            Console.WriteLine();
        }

        private bool VrcholJeOK(Vrchol vrchol)
        {
            int pocetRadku = bludiste.GetLength(0);
            int pocetSloupcu = bludiste.GetLength(1);

            if (vrchol.IndexVrcholu >= 0 && vrchol.IndexVrcholu < pocetRadku * pocetSloupcu
                && vrchol.Souradnice.X >= 0 && vrchol.Souradnice.X < pocetRadku
                && vrchol.Souradnice.Y >= 0 && vrchol.Souradnice.Y < pocetSloupcu)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        private Vrchol VrcholJeVPoli(Vrchol vrchol)
        {
            foreach (Vrchol v in vrcholy)
            {
                if (vrchol.IndexVrcholu == v.IndexVrcholu)
                {
                    return v;
                }
            }
            return null;
        }

        private Vrchol VrcholJeVPoli(int indexVrcholu)
        {
            foreach (Vrchol v in vrcholy)
            {
                if (v.IndexVrcholu == indexVrcholu)
                {
                    return v;
                }
            }
            return null;
        }

        private void PridejVrchol(Vrchol vrchol)
        {
            Vrchol pom = VrcholJeVPoli(vrchol);
            if (!VrcholJeHotovy(vrchol.IndexVrcholu))
            {
                if (pom != null && vrchol.NejkratsiCestaZVrcholu < pom.NejkratsiCestaZVrcholu)
                {
                    if (VrcholJeOK(vrchol))
                    {
                        DeleteVrchol(pom.IndexVrcholu);
                        vrcholy.Add(vrchol);
                    }
                }
                else if (pom == null)
                {
                    if (VrcholJeOK(vrchol)) vrcholy.Add(vrchol);
                }
            }
        }

        private Vrchol GetMinCestu()
        {
            Vrchol pom = null;
            int min = int.MaxValue;
            foreach (Vrchol v in vrcholy)
            {
                if (v.NejkratsiCestaZVrcholu < min)
                {
                    min = v.NejkratsiCestaZVrcholu;
                    pom = v;
                }                
            }
            return pom;
        }

        private void DeleteVrchol(int indexVrcholu)
        {
            foreach (Vrchol v in vrcholy)
            {
                if (v.IndexVrcholu == indexVrcholu)
                {
                    vrcholy.Remove(v);
                    hotoveVrcholy.Add(v.IndexVrcholu);
                    break;
                }
            }
        }

        /*********************/

        private void inicializuj(int rad, int sl)
        {
            //inicializace bludeiste
            bludiste = new byte[rad, sl];
            bludisteObracene = new byte[rad, sl];
            for (int r = 0; r < bludiste.GetLength(0); r++)
            {
                for (int s = 0; s < bludiste.GetLength(1); s++)
                {
                    bludiste[r, s] = 0;
                    bludisteObracene[r, s] = 0;
                }
            }

            //inicializace matice sousednosti pro uchování tvrdosti skály
            int pocet = rad * sl - 1;
            maticeSousednosti = new int[pocet][];
            for (int r = 0, sPocet = pocet; r < pocet; r++, sPocet--)
            {
                maticeSousednosti[r] = new int[sPocet];
            }

            vrcholy = new List<Vrchol>();
            Vrchol start = new Vrchol((bludiste.GetLength(0) - 1) * bludiste.GetLength(1),
                -1, 0, new Point(bludiste.GetLength(0) - 1, 0));
            vrcholy.Add(start);
            hotoveVrcholy = new List<int>();
        }

        private int nastavTvrdostSkaly(int x, int y, int tvrdost, int bludisteX, int bludisteY)
        {
            try
            {
                if (x < 0 || y < 0)
                {
                    throw new IndexOutOfRangeException();
                }

                if (bludiste[bludisteX, bludisteY] != 0)
                {
                    return -1;
                }

                int radek = x > y ? y : x;
                int sloupec = maticeSousednosti[0].Length - (x > y ? x : y) - 1;


                if (maticeSousednosti[radek][sloupec] != 0)
                {
                    return maticeSousednosti[radek][sloupec];
                }

                maticeSousednosti[radek][sloupec] = tvrdost;
                return tvrdost;
            }
            catch (IndexOutOfRangeException)
            {
                return -1;
            }
        }

        private int getIndexBludiste(int radIndex, int slIndex)
        {
            try
            {
                //pokud je index mimo rozsah, vyvolá vyjímku
                bludiste[radIndex, slIndex] = bludiste[radIndex, slIndex];
                return bludiste.GetLength(1) * radIndex + slIndex;
            }
            catch (IndexOutOfRangeException e)
            {
                return -1;
            }
        }

        private void vypisBludiste()
        {
            Console.WriteLine();
            for (int s = 0; s < bludiste.GetLength(1); s++)
            {
                Console.Write(" _");
            }
            Console.WriteLine();

            for (int r = 0; r < bludiste.GetLength(0); r++)
            {
                for (int s = 0; s < bludiste.GetLength(1); s++)
                {
                    StringBuilder ch = new StringBuilder();
                    if (((bludiste[r, s] & zapad) == zapad) || ((s - 1) >= 0 && (bludiste[r, s - 1] & vychod) == vychod))
                    {
                        ch.Append(" ");
                    }
                    else
                    {
                        ch.Append("|");
                    }

                    if (((bludiste[r, s] & jih) == jih) || ((r + 1) < bludiste.GetLength(0) && (bludiste[r + 1, s] & sever) == sever) || (r == (bludiste.GetLength(0) - 1) && s == 0))
                    {
                        ch.Append(" ");
                    }
                    else
                    {
                        ch.Append("_");
                    }

                    Console.Write(String.Format("{0}", ch));
                }
                Console.Write("|");
                Console.WriteLine();
            }
        }

        private void vypisMaticiSousednosti()
        {
            for (int i = 0; i < maticeSousednosti.Length; i++)
            {
                for (int j = 0; j < maticeSousednosti[i].Length; j++)
                {
                    Console.Write(maticeSousednosti[i][j] + " ");
                }
                Console.WriteLine();
            }
        }

        private void generujBludiste()
        {
            Random r = new Random();
            int sl = 0;
            int rad = bludiste.GetLength(0) - 1;
            int rndMin = 1;
            int rndMax = 100;
            bool smer = true;
            int pocetPruchodu = 1;

            //sousedni hrany: 0 = north, 1 = east, 2 = south, 3 = west
            int[] sousedniHrany = new int[4];
            while (true)
            {
                if (smer == false && sl == 0 && rad == (bludiste.GetLength(0) - 1))
                {
                    break;
                }

                //spočítej tvrdost sousedních stěn
                //pokud byly stěny již vygenerovány, nebo neexistují (okraj bludiště), je jejich hodnota rovna -1
                sousedniHrany[0] = nastavTvrdostSkaly(getIndexBludiste(rad, sl), getIndexBludiste(rad - 1, sl), r.Next(rndMin, rndMax), rad - 1, sl);
                sousedniHrany[1] = nastavTvrdostSkaly(getIndexBludiste(rad, sl), getIndexBludiste(rad, sl + 1), r.Next(rndMin, rndMax), rad, sl + 1);
                sousedniHrany[2] = nastavTvrdostSkaly(getIndexBludiste(rad, sl), getIndexBludiste(rad + 1, sl), r.Next(rndMin, rndMax), rad + 1, sl);
                sousedniHrany[3] = nastavTvrdostSkaly(getIndexBludiste(rad, sl), getIndexBludiste(rad, sl - 1), r.Next(rndMin, rndMax), rad, sl - 1);

                //nalezení minimální tvrdosti
                int min = int.MaxValue;
                int minIndex = -1;
                for (int i = 0; i < sousedniHrany.Length; i++)
                {
                    if (sousedniHrany[i] < min && sousedniHrany[i] != -1)
                    {
                        min = sousedniHrany[i];
                        minIndex = i;
                    }
                }

                //pokud neexistuje další hrana, změň směr a vracej se cestou zpět
                if (minIndex == -1)
                {
                    if (smer == true)
                    {
                        bludiste[rad, sl] = end;
                        Console.WriteLine("Stav po {0}. pruchodu", pocetPruchodu);
                        this.vypisBludiste();
                        Console.WriteLine();
                        pocetPruchodu++;
                    }

                    switch (bludisteObracene[rad, sl])
                    {
                        case 1:
                            rad -= 1;
                            break;
                        case 2:
                            sl += 1;
                            break;
                        case 4:
                            rad += 1;
                            break;
                        case 8:
                            sl -= 1;
                            break;
                        default:
                            break;
                    }

                    smer = false;
                    continue;
                }

                //existuje stěna, pro nastav směr a nastav pozici pro další průchod
                smer = true;

                //minIndex: 0 = north, 1 = east, 2 = south, 3 = west
                //bludiste: b0001 = north, b0010 = east, b0100 = south, b1000 = west
                switch (minIndex)
                {
                    case 0:
                        bludiste[rad, sl] |= sever;
                        rad -= 1;
                        bludisteObracene[rad, sl] = jih;
                        break;
                    case 1:
                        bludiste[rad, sl] |= vychod;
                        sl += 1;
                        bludisteObracene[rad, sl] = zapad;
                        break;
                    case 2:
                        bludiste[rad, sl] |= jih;
                        rad += 1;
                        bludisteObracene[rad, sl] = sever;
                        break;
                    case 3:
                        bludiste[rad, sl] |= zapad;
                        sl -= 1;
                        bludisteObracene[rad, sl] = vychod;
                        break;
                    default:
                        break;
                }
            }
        }
    }
}