fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Globalization;
  6. using System.Threading;
  7. using System.Drawing;
  8. using System.Collections;
  9.  
  10. namespace ConsoleApplication1
  11. {
  12.     class Vrchol
  13.     {
  14.         private int indexVrcholu;
  15.         private int indexPredchudce;
  16.         private int nejkratsiCestaZVrcholu;
  17.         private Point souradnice;
  18.  
  19.         public int IndexVrcholu {
  20.             get { return indexVrcholu; }
  21.             set { indexVrcholu = value; }
  22.         }
  23.  
  24.         public int IndexPredchudce
  25.         {
  26.             get { return indexPredchudce; }
  27.             set { indexPredchudce = value; }
  28.         }
  29.  
  30.         public int NejkratsiCestaZVrcholu
  31.         {
  32.             get { return nejkratsiCestaZVrcholu; }
  33.             set { nejkratsiCestaZVrcholu = value; }
  34.         }
  35.  
  36.         public Point Souradnice
  37.         {
  38.             get { return souradnice; }
  39.             set { souradnice = value; }
  40.         }
  41.  
  42.         public Vrchol(int a, int b, int c, Point p)
  43.         {
  44.             IndexVrcholu = a;
  45.             IndexPredchudce = b;
  46.             NejkratsiCestaZVrcholu = c;
  47.             Souradnice = p;
  48.         }
  49.  
  50.         public void ZapsatCestuDoMaticeSousednosti(int[][] maticeSousednosti)
  51.         {
  52.             try
  53.             {
  54.                 int radek, sloupec;
  55.                 if (this.IndexVrcholu > this.IndexPredchudce)
  56.                 {
  57.                     radek = maticeSousednosti[0].Length - this.IndexVrcholu;
  58.                     sloupec = this.IndexPredchudce;
  59.                 }
  60.                 else
  61.                 {
  62.                     radek = maticeSousednosti[0].Length - this.IndexPredchudce;
  63.                     sloupec = this.IndexVrcholu;
  64.                 }
  65.                 maticeSousednosti[radek][sloupec] = this.NejkratsiCestaZVrcholu;
  66.             }
  67.             catch (Exception)
  68.             {
  69.                 //Console.WriteLine(this.IndexVrcholu + " Chyba!");
  70.             }
  71.         }
  72.     }
  73.  
  74.     class Bludiste
  75.     {
  76.         //sever
  77.         readonly byte sever = 1;
  78.  
  79.         //vychod
  80.         readonly byte vychod = 2;
  81.  
  82.         //jih
  83.         readonly byte jih = 4;
  84.  
  85.         //západ
  86.         readonly byte zapad = 8;
  87.  
  88.         //konecný bod
  89.         readonly byte end = 16;
  90.  
  91.         private byte[,] bludiste;
  92.         private byte[,] bludisteObracene;
  93.         private int[][] maticeSousednosti;
  94.         private List<Vrchol> vrcholy;
  95.         private List<int> hotoveVrcholy;
  96.  
  97.         static void Main(string[] args)
  98.         {
  99.             Bludiste bludiste = new Bludiste();
  100.  
  101.             int r = 0;
  102.             int s = 0;
  103.             while (r == 0 || s == 0)
  104.             {
  105.                 try
  106.                 {
  107.                     Console.WriteLine("Zadejte pocet radku: ");
  108.                     r = int.Parse(Console.ReadLine());
  109.                     Console.WriteLine("Zadejte pocet sloupcu: ");
  110.                     s = int.Parse(Console.ReadLine());
  111.  
  112.                     if (r <= 0 || s <= 0)
  113.                     {
  114.                         throw new Exception();
  115.                     }
  116.                 }
  117.                 catch (Exception e)
  118.                 {
  119.                     Console.WriteLine("Zadejte nenulovou, kladnou hodnotu.");
  120.                 }
  121.             }
  122.  
  123.             bludiste.inicializuj(r, s);
  124.             bludiste.Generuj();
  125.             bludiste.vypisBludiste();
  126.             Console.WriteLine();
  127.         }
  128.  
  129.         /*******IMPROVING*****/
  130.  
  131.         private void ZapsatKrizovatkuDoBludiste(Vrchol v)
  132.         {
  133.             if (v.IndexPredchudce >= 0)
  134.             {
  135.                 int x1, x2, y1, y2;
  136.                 x1 = v.Souradnice.X;
  137.                 x2 = IndexNaSouradnice(v.IndexPredchudce).X;
  138.                 y1 = v.Souradnice.Y;
  139.                 y2 = IndexNaSouradnice(v.IndexPredchudce).Y;
  140.  
  141.                 if (x1 == x2)
  142.                 {
  143.                     if (y1 > y2)
  144.                     {
  145.                         bludiste[x1, y1] |= zapad;
  146.                         bludiste[x2, y2] |= vychod;
  147.                     }
  148.                     else
  149.                     {
  150.                         bludiste[x1, y1] |= vychod;
  151.                         bludiste[x2, y2] |= zapad;
  152.                     }
  153.                 }
  154.  
  155.                 if (y1 == y2)
  156.                 {
  157.                     if (x1 > x2)
  158.                     {
  159.                         bludiste[x1, y1] |= sever;
  160.                         bludiste[x2, y2] |= jih;
  161.                     }
  162.                     else
  163.                     {
  164.                         bludiste[x1, y1] |= jih;
  165.                         bludiste[x2, y2] |= sever;
  166.                     }
  167.                 }
  168.             }
  169.         }
  170.  
  171.         private void Generuj()
  172.         {
  173.             while (vrcholy.Count != 0)
  174.             {
  175.                 Vrchol min = null;
  176.                 if ((min = GetMinCestu()) != null)
  177.                 {
  178.                     PridejSousedyDoPole(min);
  179.                     DeleteVrchol(min.IndexVrcholu);
  180.                     min.ZapsatCestuDoMaticeSousednosti(maticeSousednosti);
  181.                     ZapsatKrizovatkuDoBludiste(min);
  182.                     VypisVrcholyVPoli();
  183.                 }
  184.             }
  185.         }
  186.  
  187.         private Point IndexNaSouradnice(int index)
  188.         {
  189.             return new Point(index/bludiste.GetLength(1), index%bludiste.GetLength(1));
  190.         }
  191.  
  192.         private int SouradniceNaIndex(Point souradnice)
  193.         {
  194.             return souradnice.X * bludiste.GetLength(1) + souradnice.Y;
  195.         }
  196.  
  197.         public bool VrcholJeHotovy(int index)
  198.         {
  199.             if (hotoveVrcholy.Contains(index)) {
  200.                 return true;
  201.             } else return false;
  202.         }
  203.  
  204.         private void PridejSousedyDoPole(Vrchol vrchol)
  205.         {
  206.             Random r = new Random();
  207.  
  208.             Vrchol sever = new Vrchol(vrchol.IndexVrcholu - bludiste.GetLength(1), vrchol.IndexVrcholu,
  209.                 r.Next(1, 100), new Point(vrchol.Souradnice.X - 1, vrchol.Souradnice.Y));
  210.  
  211.             r = new Random();
  212.  
  213.             Vrchol vychod = new Vrchol(vrchol.IndexVrcholu + 1, vrchol.IndexVrcholu,
  214.                 r.Next(1, 100), new Point(vrchol.Souradnice.X, vrchol.Souradnice.Y + 1));
  215.  
  216.             r = new Random();
  217.  
  218.             Vrchol jih = new Vrchol(vrchol.IndexVrcholu + bludiste.GetLength(1), vrchol.IndexVrcholu,
  219.                 r.Next(1, 100), new Point(vrchol.Souradnice.X + 1, vrchol.Souradnice.Y));
  220.  
  221.             r = new Random();
  222.  
  223.             Vrchol zapad = new Vrchol(vrchol.IndexVrcholu - 1, vrchol.IndexVrcholu,
  224.                 r.Next(1, 100), new Point(vrchol.Souradnice.X, vrchol.Souradnice.Y - 1));
  225.  
  226.  
  227.             PridejVrchol(sever);
  228.  
  229.             PridejVrchol(vychod);
  230.  
  231.             PridejVrchol(jih);
  232.  
  233.             PridejVrchol(zapad);
  234.         }
  235.  
  236.         private bool JeHranaVMatici(Vrchol v)
  237.         {
  238.             try
  239.             {
  240.                 int radek, sloupec;
  241.                 if (v.IndexVrcholu > v.IndexPredchudce)
  242.                 {
  243.                     radek = maticeSousednosti[0].Length - v.IndexVrcholu;
  244.                     sloupec = v.IndexPredchudce;
  245.                 }
  246.                 else
  247.                 {
  248.                     radek = maticeSousednosti[0].Length - v.IndexPredchudce;
  249.                     sloupec = v.IndexVrcholu;
  250.                 }
  251.                 if (maticeSousednosti[radek][sloupec] == 0)
  252.                 {
  253.                     return false;
  254.                 }
  255.                 else return true;
  256.             }
  257.             catch (IndexOutOfRangeException)
  258.             {
  259.                 return false;
  260.             }
  261.         }
  262.  
  263.         private void VypisVrcholyVPoli()
  264.         {
  265.             Console.WriteLine("I P D X Y");
  266.             Console.WriteLine("-----------");
  267.             foreach (Vrchol v in vrcholy)
  268.             {
  269.                 Console.WriteLine(v.IndexVrcholu + " " + v.IndexPredchudce + " " + v.NejkratsiCestaZVrcholu
  270.                     + " " + v.Souradnice.X + " " + v.Souradnice.Y);
  271.             }
  272.             Console.WriteLine();
  273.         }
  274.  
  275.         private bool VrcholJeOK(Vrchol vrchol)
  276.         {
  277.             int pocetRadku = bludiste.GetLength(0);
  278.             int pocetSloupcu = bludiste.GetLength(1);
  279.  
  280.             if (vrchol.IndexVrcholu >= 0 && vrchol.IndexVrcholu < pocetRadku * pocetSloupcu
  281.                 && vrchol.Souradnice.X >= 0 && vrchol.Souradnice.X < pocetRadku
  282.                 && vrchol.Souradnice.Y >= 0 && vrchol.Souradnice.Y < pocetSloupcu)
  283.             {
  284.                 return true;
  285.             }
  286.             else
  287.             {
  288.                 return false;
  289.             }
  290.         }
  291.  
  292.         private Vrchol VrcholJeVPoli(Vrchol vrchol)
  293.         {
  294.             foreach (Vrchol v in vrcholy)
  295.             {
  296.                 if (vrchol.IndexVrcholu == v.IndexVrcholu)
  297.                 {
  298.                     return v;
  299.                 }
  300.             }
  301.             return null;
  302.         }
  303.  
  304.         private Vrchol VrcholJeVPoli(int indexVrcholu)
  305.         {
  306.             foreach (Vrchol v in vrcholy)
  307.             {
  308.                 if (v.IndexVrcholu == indexVrcholu)
  309.                 {
  310.                     return v;
  311.                 }
  312.             }
  313.             return null;
  314.         }
  315.  
  316.         private void PridejVrchol(Vrchol vrchol)
  317.         {
  318.             Vrchol pom = VrcholJeVPoli(vrchol);
  319.             if (!VrcholJeHotovy(vrchol.IndexVrcholu))
  320.             {
  321.                 if (pom != null && vrchol.NejkratsiCestaZVrcholu < pom.NejkratsiCestaZVrcholu)
  322.                 {
  323.                     if (VrcholJeOK(vrchol))
  324.                     {
  325.                         DeleteVrchol(pom.IndexVrcholu);
  326.                         vrcholy.Add(vrchol);
  327.                     }
  328.                 }
  329.                 else if (pom == null)
  330.                 {
  331.                     if (VrcholJeOK(vrchol)) vrcholy.Add(vrchol);
  332.                 }
  333.             }
  334.         }
  335.  
  336.         private Vrchol GetMinCestu()
  337.         {
  338.             Vrchol pom = null;
  339.             int min = int.MaxValue;
  340.             foreach (Vrchol v in vrcholy)
  341.             {
  342.                 if (v.NejkratsiCestaZVrcholu < min)
  343.                 {
  344.                     min = v.NejkratsiCestaZVrcholu;
  345.                     pom = v;
  346.                 }                
  347.             }
  348.             return pom;
  349.         }
  350.  
  351.         private void DeleteVrchol(int indexVrcholu)
  352.         {
  353.             foreach (Vrchol v in vrcholy)
  354.             {
  355.                 if (v.IndexVrcholu == indexVrcholu)
  356.                 {
  357.                     vrcholy.Remove(v);
  358.                     hotoveVrcholy.Add(v.IndexVrcholu);
  359.                     break;
  360.                 }
  361.             }
  362.         }
  363.  
  364.         /*********************/
  365.  
  366.         private void inicializuj(int rad, int sl)
  367.         {
  368.             //inicializace bludeiste
  369.             bludiste = new byte[rad, sl];
  370.             bludisteObracene = new byte[rad, sl];
  371.             for (int r = 0; r < bludiste.GetLength(0); r++)
  372.             {
  373.                 for (int s = 0; s < bludiste.GetLength(1); s++)
  374.                 {
  375.                     bludiste[r, s] = 0;
  376.                     bludisteObracene[r, s] = 0;
  377.                 }
  378.             }
  379.  
  380.             //inicializace matice sousednosti pro uchování tvrdosti skály
  381.             int pocet = rad * sl - 1;
  382.             maticeSousednosti = new int[pocet][];
  383.             for (int r = 0, sPocet = pocet; r < pocet; r++, sPocet--)
  384.             {
  385.                 maticeSousednosti[r] = new int[sPocet];
  386.             }
  387.  
  388.             vrcholy = new List<Vrchol>();
  389.             Vrchol start = new Vrchol((bludiste.GetLength(0) - 1) * bludiste.GetLength(1),
  390.                 -1, 0, new Point(bludiste.GetLength(0) - 1, 0));
  391.             vrcholy.Add(start);
  392.             hotoveVrcholy = new List<int>();
  393.         }
  394.  
  395.         private int nastavTvrdostSkaly(int x, int y, int tvrdost, int bludisteX, int bludisteY)
  396.         {
  397.             try
  398.             {
  399.                 if (x < 0 || y < 0)
  400.                 {
  401.                     throw new IndexOutOfRangeException();
  402.                 }
  403.  
  404.                 if (bludiste[bludisteX, bludisteY] != 0)
  405.                 {
  406.                     return -1;
  407.                 }
  408.  
  409.                 int radek = x > y ? y : x;
  410.                 int sloupec = maticeSousednosti[0].Length - (x > y ? x : y) - 1;
  411.  
  412.  
  413.                 if (maticeSousednosti[radek][sloupec] != 0)
  414.                 {
  415.                     return maticeSousednosti[radek][sloupec];
  416.                 }
  417.  
  418.                 maticeSousednosti[radek][sloupec] = tvrdost;
  419.                 return tvrdost;
  420.             }
  421.             catch (IndexOutOfRangeException)
  422.             {
  423.                 return -1;
  424.             }
  425.         }
  426.  
  427.         private int getIndexBludiste(int radIndex, int slIndex)
  428.         {
  429.             try
  430.             {
  431.                 //pokud je index mimo rozsah, vyvolá vyjímku
  432.                 bludiste[radIndex, slIndex] = bludiste[radIndex, slIndex];
  433.                 return bludiste.GetLength(1) * radIndex + slIndex;
  434.             }
  435.             catch (IndexOutOfRangeException e)
  436.             {
  437.                 return -1;
  438.             }
  439.         }
  440.  
  441.         private void vypisBludiste()
  442.         {
  443.             Console.WriteLine();
  444.             for (int s = 0; s < bludiste.GetLength(1); s++)
  445.             {
  446.                 Console.Write(" _");
  447.             }
  448.             Console.WriteLine();
  449.  
  450.             for (int r = 0; r < bludiste.GetLength(0); r++)
  451.             {
  452.                 for (int s = 0; s < bludiste.GetLength(1); s++)
  453.                 {
  454.                     StringBuilder ch = new StringBuilder();
  455.                     if (((bludiste[r, s] & zapad) == zapad) || ((s - 1) >= 0 && (bludiste[r, s - 1] & vychod) == vychod))
  456.                     {
  457.                         ch.Append(" ");
  458.                     }
  459.                     else
  460.                     {
  461.                         ch.Append("|");
  462.                     }
  463.  
  464.                     if (((bludiste[r, s] & jih) == jih) || ((r + 1) < bludiste.GetLength(0) && (bludiste[r + 1, s] & sever) == sever) || (r == (bludiste.GetLength(0) - 1) && s == 0))
  465.                     {
  466.                         ch.Append(" ");
  467.                     }
  468.                     else
  469.                     {
  470.                         ch.Append("_");
  471.                     }
  472.  
  473.                     Console.Write(String.Format("{0}", ch));
  474.                 }
  475.                 Console.Write("|");
  476.                 Console.WriteLine();
  477.             }
  478.         }
  479.  
  480.         private void vypisMaticiSousednosti()
  481.         {
  482.             for (int i = 0; i < maticeSousednosti.Length; i++)
  483.             {
  484.                 for (int j = 0; j < maticeSousednosti[i].Length; j++)
  485.                 {
  486.                     Console.Write(maticeSousednosti[i][j] + " ");
  487.                 }
  488.                 Console.WriteLine();
  489.             }
  490.         }
  491.  
  492.         private void generujBludiste()
  493.         {
  494.             Random r = new Random();
  495.             int sl = 0;
  496.             int rad = bludiste.GetLength(0) - 1;
  497.             int rndMin = 1;
  498.             int rndMax = 100;
  499.             bool smer = true;
  500.             int pocetPruchodu = 1;
  501.  
  502.             //sousedni hrany: 0 = north, 1 = east, 2 = south, 3 = west
  503.             int[] sousedniHrany = new int[4];
  504.             while (true)
  505.             {
  506.                 if (smer == false && sl == 0 && rad == (bludiste.GetLength(0) - 1))
  507.                 {
  508.                     break;
  509.                 }
  510.  
  511.                 //spočítej tvrdost sousedních stěn
  512.                 //pokud byly stěny již vygenerovány, nebo neexistují (okraj bludiště), je jejich hodnota rovna -1
  513.                 sousedniHrany[0] = nastavTvrdostSkaly(getIndexBludiste(rad, sl), getIndexBludiste(rad - 1, sl), r.Next(rndMin, rndMax), rad - 1, sl);
  514.                 sousedniHrany[1] = nastavTvrdostSkaly(getIndexBludiste(rad, sl), getIndexBludiste(rad, sl + 1), r.Next(rndMin, rndMax), rad, sl + 1);
  515.                 sousedniHrany[2] = nastavTvrdostSkaly(getIndexBludiste(rad, sl), getIndexBludiste(rad + 1, sl), r.Next(rndMin, rndMax), rad + 1, sl);
  516.                 sousedniHrany[3] = nastavTvrdostSkaly(getIndexBludiste(rad, sl), getIndexBludiste(rad, sl - 1), r.Next(rndMin, rndMax), rad, sl - 1);
  517.  
  518.                 //nalezení minimální tvrdosti
  519.                 int min = int.MaxValue;
  520.                 int minIndex = -1;
  521.                 for (int i = 0; i < sousedniHrany.Length; i++)
  522.                 {
  523.                     if (sousedniHrany[i] < min && sousedniHrany[i] != -1)
  524.                     {
  525.                         min = sousedniHrany[i];
  526.                         minIndex = i;
  527.                     }
  528.                 }
  529.  
  530.                 //pokud neexistuje další hrana, změň směr a vracej se cestou zpět
  531.                 if (minIndex == -1)
  532.                 {
  533.                     if (smer == true)
  534.                     {
  535.                         bludiste[rad, sl] = end;
  536.                         Console.WriteLine("Stav po {0}. pruchodu", pocetPruchodu);
  537.                         this.vypisBludiste();
  538.                         Console.WriteLine();
  539.                         pocetPruchodu++;
  540.                     }
  541.  
  542.                     switch (bludisteObracene[rad, sl])
  543.                     {
  544.                         case 1:
  545.                             rad -= 1;
  546.                             break;
  547.                         case 2:
  548.                             sl += 1;
  549.                             break;
  550.                         case 4:
  551.                             rad += 1;
  552.                             break;
  553.                         case 8:
  554.                             sl -= 1;
  555.                             break;
  556.                         default:
  557.                             break;
  558.                     }
  559.  
  560.                     smer = false;
  561.                     continue;
  562.                 }
  563.  
  564.                 //existuje stěna, pro nastav směr a nastav pozici pro další průchod
  565.                 smer = true;
  566.  
  567.                 //minIndex: 0 = north, 1 = east, 2 = south, 3 = west
  568.                 //bludiste: b0001 = north, b0010 = east, b0100 = south, b1000 = west
  569.                 switch (minIndex)
  570.                 {
  571.                     case 0:
  572.                         bludiste[rad, sl] |= sever;
  573.                         rad -= 1;
  574.                         bludisteObracene[rad, sl] = jih;
  575.                         break;
  576.                     case 1:
  577.                         bludiste[rad, sl] |= vychod;
  578.                         sl += 1;
  579.                         bludisteObracene[rad, sl] = zapad;
  580.                         break;
  581.                     case 2:
  582.                         bludiste[rad, sl] |= jih;
  583.                         rad += 1;
  584.                         bludisteObracene[rad, sl] = sever;
  585.                         break;
  586.                     case 3:
  587.                         bludiste[rad, sl] |= zapad;
  588.                         sl -= 1;
  589.                         bludisteObracene[rad, sl] = vychod;
  590.                         break;
  591.                     default:
  592.                         break;
  593.                 }
  594.             }
  595.         }
  596.     }
  597. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
10
10
compilation info 
prog.cs(7,14): error CS0234: The type or namespace name `Drawing' does not exist in the namespace `System'. Are you missing an assembly reference?
prog.cs(42,44): error CS0246: The type or namespace name `Point' could not be found. Are you missing a using directive or an assembly reference?
prog.cs(36,16): error CS0246: The type or namespace name `Point' could not be found. Are you missing a using directive or an assembly reference?
prog.cs(187,17): error CS0246: The type or namespace name `Point' could not be found. Are you missing a using directive or an assembly reference?
prog.cs(192,39): error CS0246: The type or namespace name `Point' could not be found. Are you missing a using directive or an assembly reference?
prog.cs(7,14): error CS0234: The type or namespace name `Drawing' does not exist in the namespace `System'. Are you missing an assembly reference?
Compilation failed: 6 error(s), 0 warnings
stdout
copy 
Standard output is empty
https://ideone.com/CtAEc
language:
C# (gmcs 5.20.1)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!