Informatika gyűjtemény

Egy szinttel feljebb mb_ec.cs

2004050607080910

<<  8. óra  >>

<<  Kömal fórum feladat  >>

NézetNyomtat

mb_ec.cs (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 10 KB
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DLX
{
    class Program
    {
        public static int height;
        public static int width;

        static Alakzat[] alakzatok;

        static bool[] fedesavailable;
        static Fedes[] fedesek;

        static int[] lepesek;

        static Fal[] falak;

        static int count;
        static ulong cfedes;

        //BTGyorsito
        static bool BTGyorsito_on;
        static int[,] fedesmezo;

        //SelfCheck
        static int[] lep1, lep2;
        static int[,] mezofedes;

        static byte FirstFalse(ulong u) //gyorsítaniiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii wázeg
        {
            for (byte i = 1; i != 65; i++)
                if ((u >> 64 - i) % 2 == 0) return i;

            throw new Exception("EXCEPSÜN");
        }

        static bool IsTrue(ulong u, byte index)
        {
            if (((u >> (64 - index)) % 2 == 1)) return true;
            else return false;
        }

        static void Main(string[] args)
        {
            Init();
            Munka();

            Console.WriteLine("Vége");
            Console.Read();
        }

        static void Munka()
        {
            //BTGyorsito_on = true;
            FedesGyartas();
            FalGyartas();

            //ez a megoldás!
            int[] cfalak = new int[4];
            cfalak = new int[4] { 0, 10, 26, 83 };
            FedesSzures(cfalak);
            BTInit();
            BT(0);
            //eddig!

            for (cfalak[0] = 0; cfalak[0] != falak.Length - 3; cfalak[0]++) //forgatás tükrézést meg ezeket többször átnézi
            {
                Console.WriteLine(cfalak[0]);
                for (cfalak[1] = cfalak[0] + 1; cfalak[1] != falak.Length - 2; cfalak[1]++)
                {
                    Console.WriteLine(cfalak[0] + " " + cfalak[1]);
                    for (cfalak[2] = cfalak[1] + 1; cfalak[2] != falak.Length - 1; cfalak[2]++)
                    {
                        Console.WriteLine(cfalak[0] + " " + cfalak[1] + " " + cfalak[2]);
                        for (cfalak[3] = cfalak[2] + 1; cfalak[3] != falak.Length - 0; cfalak[3]++)
                        {
                            FedesSzures(cfalak);
                            BTInit();
                            BT(0);

                            if (count >= 2)
                            {
                                bool same = true;
                                for (int i = 0; i != lep1.Length && same; i++)
                                    if (lep1[i] != lep2[i]) same = false;
                                if (same)
                                    Console.WriteLine("BUG");
                            }

                            if (count == 1)
                                Console.WriteLine("HEY!!");
                        }
                    }
                }
            }
        }

        static void BT(int lvl)
        {
            if (count >= 2)
                return;

            if (lvl == 16) //készek vagyunk hurrá
            {
                /*for (int i = 0; i != 16; i++)
                {
                    ulong u = 0;
                    for (int j = 0; j != i + 1; j++) u = u | fedesek[lepesek[j]].fedes;
                    Fedes.Display(u);
                }
                Console.WriteLine();*/
                count++;
                if (count == 1)
                    lepesek.CopyTo(lep1, 0);
                if (count == 2)
                    lepesek.CopyTo(lep2, 0);
                
                for (int i = 0; i != 16; i++)
                {
                    Fedes.Display(fedesek[lepesek[i]].fedes);
                    Console.WriteLine("--------");
                }

                Fedes.Display(cfedes);
                return;
            }

            byte ff = FirstFalse(cfedes);
            for (int i = 0; i != fedesek.Length; i++)
                if (fedesavailable[i] && fedesek[i].fristtrue == ff)
                {
                    ulong f = fedesek[i].fedes;
                    if ((cfedes ^ f) == (cfedes | f))
                    {

                        lepesek[lvl] = i;
                        ulong ofedes = cfedes;
                        cfedes = cfedes | f;
                        BT(lvl + 1);
                        cfedes = ofedes;
                    }
                }
        }

        static void BTGyorsito() //CSAK FAL ESETÉN!!
        {
            fedesavailable = new bool[fedesek.Length];
            for (int i = 0; i != fedesek.Length; i++) fedesavailable[i] = true;

            fedesmezo = new int[fedesek.Length, 4];
            mezofedes = new int[64, 32];

            int c = 0;
            for (byte i = 1; i != 65; i++)
                for (int j = 0; j != fedesek.Length && c != 32; j++)
                    if (IsTrue(fedesek[j].fedes, i))
                    {
                        mezofedes[i, c] = j;
                        fedesmezo[j, c] = i;
                        c++;
                    }
        }

        static void BTInit()
        {
            lep1 = new int[16];
            lep2 = new int[16];
            lepesek = new int[16];
            count = 0;
            cfedes = 0;
        }

        static void Init()
        {
            height = 8;
            width = 8;

            bool[,] a;
            alakzatok = new Alakzat[8];

            a = new bool[2, 3] { { true, true, true }, { true, false, false } };      // xxx
            alakzatok[0] = new Alakzat(2, 3, a);                                      // x

            a = new bool[2, 3] { { true, false, false }, { true, true, true } };      // x
            alakzatok[1] = new Alakzat(2, 3, a);                                      // xxx

            a = new bool[2, 3] { { true, true, true }, { false, false, true } };      // xxx
            alakzatok[2] = new Alakzat(2, 3, a);                                      //   x

            a = new bool[2, 3] { { false, false, true }, { true, true, true } };      //   x
            alakzatok[3] = new Alakzat(2, 3, a);                                      // xxx

            /* xx
             * x
             * x 
             */
            a = new bool[3, 2] { { true, true }, { true, false }, { true, false } };
            alakzatok[4] = new Alakzat(3, 2, a);

            /* xx
             *  x
             *  x
             */
            a = new bool[3, 2] { { true, true }, { false, true }, { false, true } };
            alakzatok[5] = new Alakzat(3, 2, a);

            /* x
             * x
             * xx 
             */
            a = new bool[3, 2] { { true, false }, { true, false }, { true, true } };
            alakzatok[6] = new Alakzat(3, 2, a);

            /*  x
             *  x
             * xx
             */
            a = new bool[3, 2] { { false, true }, { false, true }, { true, true } };
            alakzatok[7] = new Alakzat(3, 2, a);

        }

        static void FedesGyartas()
        {
            int c = 0;
            fedesek = new Fedes[alakzatok.Length * (width - 1) * (height - 2)]; // 8 féle alakzat, a 2*3 as vagy 3*2-es téglalap pedig 7*6 helyre mehet
            for (byte i = 0; i != height; i++)
                for (byte j = 0; j != width; j++)
                    for (byte z = 0; z != alakzatok.Length; z++)
                    {
                        Alakzat a = alakzatok[z];
                        if (height >= a.height + i & width >= a.width + j) //befér
                            fedesek[c++] = a.ToFedes(i, j);
                    }
        }

        static void FalGyartas()
        {
            int c = 0;
            falak = new Fal[(width - 1) * height + (height - 1) * width];
            for (byte i = 1; i != 64; i++) //64es mezőhez már nem jön semmi!
            {
                if (i % 8 != 0) falak[c++] = new Fal(i, (byte)(i + 1));
                if (i + 8 <= 64) falak[c++] = new Fal(i, (byte)(i + 8));
            }
        }

        static void FedesSzures(int[] cfalak)
        {
            fedesavailable = new bool[fedesek.Length];
            for (int i = 0; i != fedesek.Length; i++)
            {
                fedesavailable[i] = true;

                for (int j = 0; j != cfalak.Length && fedesavailable[i]; j++)
                    if (IsTrue(fedesek[i].fedes, falak[cfalak[j]].m1) && IsTrue(fedesek[i].fedes, falak[cfalak[j]].m2))
                        fedesavailable[i] = false;
            }
        }

    }

    struct Alakzat
    {
        public int height;
        public int width;
        public bool[,] alakzat;

        public Alakzat(int height, int width, bool[,] alakzat)
        {
            this.height = height;
            this.width = width;
            this.alakzat = alakzat;
        }

        public Fedes ToFedes(byte h0, byte w0)
        {
            byte first;
            ulong u = 0;
            byte[] where = new byte[4];

            int c = 0;
            for (int h1 = 0; h1 != height; h1++)
                for (int w1 = 0; w1 != width; w1++)
                    if (alakzat[h1, w1])
                        where[c++] = ((byte)((h0 + h1) * Program.width + (w0 + w1) + 1));

            first = where[0];
            foreach (byte index in where)
                u = u | ((ulong)1 << (64 - index));

            return new Fedes(first, u);
        }
    }

    struct Fedes
    {
        public byte fristtrue;
        public ulong fedes;

        public Fedes(byte first, ulong fedes)
        {
            this.fristtrue = first;
            this.fedes = fedes;
        }

        public static void Display(ulong u)
        {
            string l = "";
            for (byte i = 1; i != 65; i++)
            {
                if ((u >> 64 - i) % 2 == 0) l += " ";
                else l += "X";
                if (i % 8 == 0)
                {
                    Console.WriteLine(l);
                    l = "";
                }
            }
            Console.WriteLine("--------");
        }

        public override string ToString()
        {
            string l = "";
            for (byte i = 1; i != 65; i++)
                if ((fedes >> 64 - i) % 2 == 1) l += i + " ";

            return l;
        }
    }

    struct Fal
    {
        public byte m1, m2;

        public Fal(byte m1, byte m2)
        {
            this.m1 = m1;
            this.m2 = m2;
        }
    }
}
(Vissza)