home *** CD-ROM | disk | FTP | other *** search
// soukromé konstanty // konstanty pro hodnoty prom╪nné modCesta_ZpàsobZadáváníMíst # define modCesta_ZAD╡V╡N╓M╓ST_¼╓SELN╖ 1 # define modCesta_ZAD╡V╡N╓M╓ST_GRAFICKY 2 // konstanty pro hodnoty prom╪nné modCesta_Jak∞SouƒetSpojnicHledat # define modCesta_NEJMENµ╓_SOU¼ET 1 # define modCesta_NEJV╖Tµ╓_SOU¼ET 2 // soukromé prom╪nné int modCesta_PoƒetMíst; // poƒet míst, která lze navτtívit int *modCesta_Sou²adniceMíst; // sou²adnice míst, která lze navτtívit (kaºd∞ sud∞ [0,2,4..] prvek je X a kaºd∞ lich∞ [1,3,5..] prvek je Y) int modCesta_ZpàsobZadáváníMíst; // ƒíseln╪ nebo graficky (viz konstanty) int modCesta_PoƒetSpojnic; // poƒet spojnic, které lze p²i navτt╪vování míst pouºít int modCesta_AtributJeDélkaSpojnice; // zda se mají atributy spojnic automaticky nastavovat na grafickou vzdálenost míst, která spojnice spojuje struct modCesta_TypSpojnice { int Místo1; // první z míst, které tvo²í spojnici int Místo2; // druhé z míst, které tvo²í spojnici long Atribut; // hodnota atributu spojnice } *modCesta_Spojnice; // pole informací o spojnicích, které lze p²i navτt╪vování míst pouºít int modCesta_Jak∞SouƒetSpojnicHledat; // zda hledat nejmenτí nebo nejv╪tτí hodnotu prom╪nné SouƒetSpojnic (viz konstanty) int *modCesta_Cesta; // pole práv╪ testované cesty - jednotlivé prvky jsou po²adová ƒísla spojnic, které cestu tvo²í long modCesta_SouƒetSpojnic; // souƒet hodnot atributà vτech spojnic, ze kter∞ch se práv╪ testovaná cesta skládá int modCesta_Θroveσ; // úroveσ zano²ení v backtrackingu (kolik spojnic je v práv╪ testované cest╪ p²ítomno) int *modCesta_Nejlepτíⁿeτení_Cesta; // kopie pole Cesta, které je dosud nejlepτí nalezen∞m ²eτením long modCesta_Nejlepτíⁿeτení_SouƒetSpojnic; // kopie prom╪nné SouƒetSpojnic, která je dosud nejlepτím nalezen∞m ²eτením int modCesta_Nejlepτíⁿeτení_Θroveσ; // kopie prom╪nné Θroveσ, která byla aktuální v dob╪ nalezení nejlepτího nalezeného ²eτení // soukromé funkce void modCesta_VykresliMapu(int *modCesta_VykreslovanéPole, int modCesta_VykreslovanáΘroveσ) { int modCesta_Vykreslovan∞Prvek, modCesta_VykreslovanéMísto, modCesta_VykreslovanáSpojnice; int modCesta_VykreslovanéPísmenoX, modCesta_VykreslovanéPísmenoY; // uschování pàvodn╪ nastaven∞ch barev int modCesta_PàvodníBarvy = GrBarvy(); // smazání obrazovky GrNastavBarvuPozadí(PalBéºová); GrSmaºOkno(); // vykreslení jednotliv∞ch míst, která lze navτtívit GrNastavText(GrTextSPozadím); GrNastavBarvy(PalTmav╪Modrá<<4|Palªlutá); ¼ekejNaVR(); for(modCesta_VykreslovanéMísto=0; modCesta_VykreslovanéMísto<((!modCesta_VykreslovanéPole && modCesta_VykreslovanáΘroveσ+1)?modCesta_VykreslovanáΘroveσ:modCesta_PoƒetMíst); modCesta_VykreslovanéMísto++) { // vykreslení písmenného oznaƒení vykreslovaného místa GrNastavPozici(modCesta_Sou²adniceMíst[modCesta_VykreslovanéMísto*2], modCesta_Sou²adniceMíst[modCesta_VykreslovanéMísto*2+1]); GrNastavPozici((GrPoziceX()<4)?0:(GrPoziceX()>631?627:GrPoziceX()-4), (GrPoziceY()<5)?0:(GrPoziceY()>437?432:GrPoziceY()-5)); GrPiτZnak('A'+modCesta_VykreslovanéMísto); } GrNastavText(GrTextBezPozadí); // vykreslení jednotliv∞ch spojnic mezi místy, které lze p²i navτt╪vování míst pouºít GrNastavBarvuPop²edí(Pal¼erná); for(modCesta_VykreslovanáSpojnice=0; modCesta_VykreslovanáSpojnice<modCesta_PoƒetSpojnic; modCesta_VykreslovanáSpojnice++) { ¼ekejNaVR(); // urƒení místa, ze kterého má vést vykreslovaná ƒára modCesta_VykreslovanéMísto = modCesta_Spojnice[modCesta_VykreslovanáSpojnice].Místo1; // nastavení kurzoru na pozici místa, ze kterého má vést vykreslovaná ƒára GrNastavPozici(modCesta_Sou²adniceMíst[modCesta_VykreslovanéMísto*2], modCesta_Sou²adniceMíst[modCesta_VykreslovanéMísto*2+1]); // urƒení místa, do kterého má vést vykreslovaná ƒára modCesta_VykreslovanéMísto = modCesta_Spojnice[modCesta_VykreslovanáSpojnice].Místo2; // vykreslení ƒáry spojující první z míst tvo²ící spojnici s druh∞m z nich GrKresliLinkuDo(modCesta_Sou²adniceMíst[modCesta_VykreslovanéMísto*2], modCesta_Sou²adniceMíst[modCesta_VykreslovanéMísto*2+1]); } // pokud se má vykreslovat i cesta if(modCesta_VykreslovanéPole) { // vykreslení spojnic mezi místy tvo²ícími vykreslovanou cestu GrNastavBarvuPop²edí(PalBílá); GrNastavPozici(modCesta_Sou²adniceMíst[0], modCesta_Sou²adniceMíst[1]); modCesta_VykreslovanéMísto = 0; for(modCesta_Vykreslovan∞Prvek=0; modCesta_Vykreslovan∞Prvek<=modCesta_VykreslovanáΘroveσ; modCesta_Vykreslovan∞Prvek++) { ¼ekejNaVR(); // urƒení spojnice, kterou má p²edstavovat vykreslovaná ƒára modCesta_VykreslovanáSpojnice = modCesta_VykreslovanéPole[modCesta_Vykreslovan∞Prvek]; // urƒení místa, do kterého má vést vykreslovaná ƒára (urƒení sm╪ru, kter∞m je spojnice procházena) modCesta_VykreslovanéMísto = (modCesta_Spojnice[modCesta_VykreslovanáSpojnice].Místo1 == modCesta_VykreslovanéMísto)?modCesta_Spojnice[modCesta_VykreslovanáSpojnice].Místo2:modCesta_Spojnice[modCesta_VykreslovanáSpojnice].Místo1; // nakreslení ƒáry spojující p²edchozí místo s práv╪ vykreslovan∞m // kreslí se poslední místo a nekreslí se nejlepτí ²eτení => nastavení odliτné barvy ƒáry k n╪mu vedoucí if(modCesta_VykreslovanéPole != modCesta_Nejlepτíⁿeτení_Cesta && modCesta_Vykreslovan∞Prvek == modCesta_VykreslovanáΘroveσ) GrNastavBarvuPop²edí(Palªlutá); // nakreslení samotné ƒáry GrKresliLinkuDo(modCesta_Sou²adniceMíst[modCesta_VykreslovanéMísto*2], modCesta_Sou²adniceMíst[modCesta_VykreslovanéMísto*2+1]); } } // navrácení pàvodn╪ nastaven∞ch barev GrNastavBarvy(modCesta_PàvodníBarvy); } int modCesta_ZjistiVzdálenostMíst(int modCesta_Místo1, int modCesta_Místo2) { // zjiτt╪ní vzdálenosti mezi dv╪ma místy pomocí Pythagorovy v╪ty return sqrt(sqr(abs(modCesta_Sou²adniceMíst[modCesta_Místo1*2]-modCesta_Sou²adniceMíst[modCesta_Místo2*2])) + sqr(abs(modCesta_Sou²adniceMíst[modCesta_Místo1*2+1]-modCesta_Sou²adniceMíst[modCesta_Místo2*2+1]))); } string modCesta_PoleCestyNaⁿet╪zec(int *modCesta_P²evád╪néPole, int *modCesta_P²evád╪náΘroveσ, long *modCesta_P²evád╪n∞SouƒetSpojnic) { string modCesta_Vrátit = "A"; int modCesta_P²evád╪náSpojnice, modCesta_P²evád╪néMísto = 0; int modCesta_P²evád╪n∞Prvek; for(modCesta_P²evád╪n∞Prvek=0; modCesta_P²evád╪n∞Prvek<=*modCesta_P²evád╪náΘroveσ; modCesta_P²evád╪n∞Prvek++) { modCesta_P²evád╪náSpojnice = modCesta_P²evád╪néPole[modCesta_P²evád╪n∞Prvek]; modCesta_P²evád╪néMísto = (modCesta_Spojnice[modCesta_P²evád╪náSpojnice].Místo1 == modCesta_P²evád╪néMísto)?modCesta_Spojnice[modCesta_P²evád╪náSpojnice].Místo2:modCesta_Spojnice[modCesta_P²evád╪náSpojnice].Místo1; modCesta_Vrátit += (string)(char)('A'+modCesta_P²evád╪néMísto); } modCesta_Vrátit += " (souƒet "+StrL¼íslo(*modCesta_P²evád╪n∞SouƒetSpojnic,-1)+")"; return modCesta_Vrátit; } // ve²ejné funkce void modCesta_Start(void) { // v p²ípad╪ grafického reºimu: if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { // smazání obrazovky GrSmaºOkno(); // vykreslení mapy (pouze místa) modCesta_VykresliMapu(0, -1); } mod_VypiτHláτku("Po stisknutí klávesy nebo tlaƒítka myτi se rozb╪hne v∞poƒet...", mod_VYPIµHL╡µKU_NE¼EKEJ); VyprázdniFrontuKláves(); MyτZapni(); ¼ekej(NaKlávesu|NaMyτ); VyprázdniFrontuKláves(); MyτVypni(); // smazání obrazovky v p²ípad╪ textového reºimu if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { TxtSmaºObrazovku(); } mod_VypiτHláτku("Probíhá v∞poƒet...", mod_VYPIµHL╡µKU_NE¼EKEJ); // zaznamenání ƒasu startu v∞poƒtu Systémov∞¼as(mod_¼asStart); // inicializace prom╪nn∞ch pouºívan∞ch v∞poƒtem mod_HledatDál = 1; modCesta_SouƒetSpojnic = 0; modCesta_Θroveσ = 0; modCesta_Nejlepτíⁿeτení_SouƒetSpojnic = (modCesta_Jak∞SouƒetSpojnicHledat==modCesta_NEJMENµ╓_SOU¼ET?2147483647:0); // nejhorτí moºn∞ souƒet hodnot atributà spojnic - v reále nemoºn∞, bude nahrazen lepτím uº p²i nalezení první vyhovující cesty modCesta_Nejlepτíⁿeτení_Θroveσ = 0; // zapsání parametrà v∞poƒtu do souboru, pokud si to uºivatel p²ál if(mod_ZapisovatProtokol) { mod_ProtokolZapiτStart1(); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Reºim obrazovky: "+(mod_ReºimObrazovky==mod_TEXTOVφ_REªIM?"textov∞":"grafick∞")+"\n"); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Poƒet míst na map╪: "+StrL¼íslo(modCesta_PoƒetMíst,-1)+"\n"); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Zpàsob zadávání míst: "+(modCesta_ZpàsobZadáváníMíst==modCesta_ZAD╡V╡N╓M╓ST_¼╓SELN╖?"ƒíseln╪":"graficky")+"\n"); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Sou²adnice jednotliv∞ch míst [X, Y]: "); int modCesta_ProcházenéMísto; for(modCesta_ProcházenéMísto=0; modCesta_ProcházenéMísto<modCesta_PoƒetMíst; modCesta_ProcházenéMísto++) SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, StrL¼íslo(modCesta_Sou²adniceMíst[modCesta_ProcházenéMísto*2],-1)+","+StrL¼íslo(modCesta_Sou²adniceMíst[modCesta_ProcházenéMísto*2+1],-1)+" "); SouborPiτNov∞ⁿádek(mod_ZapisovatProtokol_Soubor); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Poƒet spojnic mezi místy: "+StrL¼íslo(modCesta_PoƒetSpojnic,-1)+"\n"); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Jednotlivé spojnice a jejich atributy [Místo1, Místo2, Atribut]: "); int modCesta_ProcházenáSpojnice; for(modCesta_ProcházenáSpojnice=0; modCesta_ProcházenáSpojnice<modCesta_PoƒetSpojnic; modCesta_ProcházenáSpojnice++) SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, (string)(char)('A'+modCesta_Spojnice[modCesta_ProcházenáSpojnice].Místo1)+","+(string)(char)('A'+modCesta_Spojnice[modCesta_ProcházenáSpojnice].Místo2)+","+StrL¼íslo(modCesta_Spojnice[modCesta_ProcházenáSpojnice].Atribut,-1)+" "); SouborPiτNov∞ⁿádek(mod_ZapisovatProtokol_Soubor); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Jak∞ souƒet hodnot atributà hledat: "+(modCesta_Jak∞SouƒetSpojnicHledat==modCesta_NEJMENµ╓_SOU¼ET?"nejmenτí":"nejv╪tτí")+"\n"); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Zobrazované pozice: "+(mod_ZobrazovanéPozice==mod_POUZE_ⁿEµEN╓?"jen nalezená ²eτení":"i pràb╪h hledání")+"\n"); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Vyƒkat po nalezení nového nejlepτího ²eτení na stisk klávesy: "+(mod_¼ekatNaKlávesu?"ano":"ne")+"\n"); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Zapisovat protokol o v∞poƒtu: "+(mod_ZapisovatProtokol?"ano":"ne")+"\n"); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Soubor protokolu: "+mod_ZapisovatProtokol_Název+"\n"); mod_ProtokolZapiτStart2(); } } void modCesta_Hotovo(void) { // uloºení ƒasu dokonƒení v∞poƒtu Systémov∞¼as(mod_¼asHotovo); // p²ekreslení mapy - vykreslení prázdné mapy if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { modCesta_VykresliMapu(0, -1); } // v p²ípad╪ grafického reºimu pípnutí - oznámení dokonƒení v∞poƒtu if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { Tón(1000); ¼ekej(1500); VypniTón(); } // pokud bylo vàbec nalezeno n╪jaké nejlepτí ²eτení if((modCesta_Jak∞SouƒetSpojnicHledat == modCesta_NEJMENµ╓_SOU¼ET && modCesta_Nejlepτíⁿeτení_SouƒetSpojnic < 2147483647) || (modCesta_Jak∞SouƒetSpojnicHledat == modCesta_NEJV╖Tµ╓_SOU¼ET && modCesta_Nejlepτíⁿeτení_SouƒetSpojnic > 0)) { // p²ekreslení mapy - vykreslení nejlepτího nalezeného ²eτení if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { modCesta_VykresliMapu(modCesta_Nejlepτíⁿeτení_Cesta, modCesta_Nejlepτíⁿeτení_Θroveσ); } } // v∞poƒet doby trvání v∞poƒtu mod_V∞poƒetDobyTrváníV∞poƒtu(); // zobrazení doby trvání v∞poƒtu mod_VypiτHláτku("Hotovo. Délka: "+StrL¼ísloZeroPad(mod_¼asRozdíl.Hodiny,2)+":"+StrL¼ísloZeroPad(mod_¼asRozdíl.Minuty,2)+":"+StrL¼ísloZeroPad(mod_¼asRozdíl.Sekundy,2)+"."+StrL¼ísloZeroPad(mod_¼asRozdíl.Setiny,2)+"...", mod_VYPIµHL╡µKU_¼EKEJNAKL╡VESUGRAFIKA); // zapsání informací t∞kajících se dokonƒení v∞poƒtu do souboru, pokud si to uºivatel p²ál if(mod_ZapisovatProtokol) { // pokud bylo vàbec nalezeno n╪jaké nejlepτí ²eτení if((modCesta_Jak∞SouƒetSpojnicHledat == modCesta_NEJMENµ╓_SOU¼ET && modCesta_Nejlepτíⁿeτení_SouƒetSpojnic < 2147483647) || (modCesta_Jak∞SouƒetSpojnicHledat == modCesta_NEJV╖Tµ╓_SOU¼ET && modCesta_Nejlepτíⁿeτení_SouƒetSpojnic > 0)) { SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "NEJLEPµ╓ ⁿEµEN╓: "); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, modCesta_PoleCestyNaⁿet╪zec(modCesta_Nejlepτíⁿeτení_Cesta, &modCesta_Nejlepτíⁿeτení_Θroveσ, &modCesta_Nejlepτíⁿeτení_SouƒetSpojnic)); SouborPiτNov∞ⁿádek(mod_ZapisovatProtokol_Soubor); } // jinak pokud nebylo nalezeno ºádné nejlepτí ²eτení else { SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Nebylo nalezeno ºádné ²eτení.\n"); } SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Hotovo: "+StrL¼ísloZeroPad(mod_¼asHotovo.Hodiny,2)+":"+StrL¼ísloZeroPad(mod_¼asHotovo.Minuty,2)+":"+StrL¼ísloZeroPad(mod_¼asHotovo.Sekundy,2)+"."+StrL¼ísloZeroPad(mod_¼asHotovo.Setiny,2)+"\n"); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Délka v∞poƒtu: "+StrL¼ísloZeroPad(mod_¼asRozdíl.Hodiny,2)+":"+StrL¼ísloZeroPad(mod_¼asRozdíl.Minuty,2)+":"+StrL¼ísloZeroPad(mod_¼asRozdíl.Sekundy,2)+"."+StrL¼ísloZeroPad(mod_¼asRozdíl.Setiny,2)+"\n"); mod_ProtokolZapiτHotovo(); } // pokud bylo vàbec nalezeno n╪jaké nejlepτí ²eτení if((modCesta_Jak∞SouƒetSpojnicHledat == modCesta_NEJMENµ╓_SOU¼ET && modCesta_Nejlepτíⁿeτení_SouƒetSpojnic < 2147483647) || (modCesta_Jak∞SouƒetSpojnicHledat == modCesta_NEJV╖Tµ╓_SOU¼ET && modCesta_Nejlepτíⁿeτení_SouƒetSpojnic > 0)) { mod_VypiτHláτku("NEJLEPµ╓ ⁿEµEN╓: " + modCesta_PoleCestyNaⁿet╪zec(modCesta_Nejlepτíⁿeτení_Cesta, &modCesta_Nejlepτíⁿeτení_Θroveσ, &modCesta_Nejlepτíⁿeτení_SouƒetSpojnic), mod_VYPIµHL╡µKU_¼EKEJNAKL╡VESU); } // jinak pokud nebylo nalezeno ºádné nejlepτí ²eτení else { mod_VypiτHláτku("Nebylo nalezeno ºádné ²eτení.", mod_VYPIµHL╡µKU_¼EKEJNAKL╡VESU); } } void modCesta_Θklid(void) { // uvoln╪ní pam╪ti pouºité pro pole sou²adnic míst HromadaUvolniPam╪£(modCesta_Sou²adniceMíst); modCesta_Sou²adniceMíst = 0; // uvoln╪ní pam╪ti pouºité pro pole spojnic HromadaUvolniPam╪£(modCesta_Spojnice); modCesta_Spojnice = 0; // uvoln╪ní pam╪ti pouºité pro pole cesty HromadaUvolniPam╪£(modCesta_Cesta); modCesta_Cesta = 0; // uvoln╪ní pam╪ti pouºité pro pole nejlepτího ²eτení HromadaUvolniPam╪£(modCesta_Nejlepτíⁿeτení_Cesta); modCesta_Nejlepτíⁿeτení_Cesta = 0; } void modCesta_ZadáníVstupu(void) { // INICIALIZACE REªIMU OBRAZOVKY if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { // p²epnutí do textového reºimu P²epniNaText(); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { GrSmaºOkno(); } // INFORMACE O REªIMU OBRAZOVKY if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Pouºívám textov∞ reºim...", mod_VYPIµHL╡µKU_VY¼KEJ); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { mod_VypiτHláτku("Pouºívám grafick∞ reºim...", mod_VYPIµHL╡µKU_VY¼KEJ); } // INICIALIZACE PROM╖NNφCH, KTERÉ JE POTⁿEBA M╓T INICIALIZOVANÉ JIª PⁿED JEJICH ZAD╡N╓M modCesta_PoƒetMíst = 0; modCesta_PoƒetSpojnic = 0; // ZJIµT╖N╓ PO¼TU M╓ST NA MAP╖, KTER╡ JE MOªNO PROJ╓T mod_VypiτHláτku("Zadejte, kolik míst na map╪ chcete vloºit [2-26]: ", mod_VYPIµHL╡µKU_NE¼EKEJ); if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { while((VyprázdniFrontuKláves(),Txt¼tiI¼íslo(modCesta_PoƒetMíst)) || modCesta_PoƒetMíst < 2 || modCesta_PoƒetMíst > 26); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN); while((VyprázdniFrontuKláves(),Gr¼tiI¼íslo("",modCesta_PoƒetMíst,2,0,PalTmav╪Modrá<<4|Palªlutá)) || modCesta_PoƒetMíst < 2 || modCesta_PoƒetMíst > 26); GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA); } // INFORMACE O PO¼TU M╓ST NA MAP╖, KTER╡ JE MOªNO PROJ╓T if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Budete vkládat "+StrL¼íslo(modCesta_PoƒetMíst,-1)+" míst...", mod_VYPIµHL╡µKU_VY¼KEJ); } // Pⁿ╓PRAVA POLE SOUⁿADNIC M╓ST // alokace pam╪ti pro pole modCesta_Sou²adniceMíst = (int*)HromadaAlokujPam╪£(modCesta_PoƒetMíst*2*sizeof(modCesta_Sou²adniceMíst[0])); // vynulování vτech prvkà pole memset(modCesta_Sou²adniceMíst, 0, modCesta_PoƒetMíst*2*sizeof(modCesta_Sou²adniceMíst[0])); // Pⁿ╓PRAVA POLE CESTY // alokace pam╪ti pro pole modCesta_Cesta = (int*)HromadaAlokujPam╪£((modCesta_PoƒetMíst-1)*sizeof(modCesta_Cesta[0])); // vynulování vτech prvkà pole memset(modCesta_Cesta, 0, (modCesta_PoƒetMíst-1)*sizeof(modCesta_Cesta[0])); // Pⁿ╓PRAVA POLE NEJLEPµ╓HO ⁿEµEN╓ // alokace pam╪ti pro pole modCesta_Nejlepτíⁿeτení_Cesta = (int*)HromadaAlokujPam╪£((modCesta_PoƒetMíst-1)*sizeof(modCesta_Nejlepτíⁿeτení_Cesta[0])); // vynulování vτech prvkà pole memset(modCesta_Nejlepτíⁿeτení_Cesta, 0, (modCesta_PoƒetMíst-1)*sizeof(modCesta_Nejlepτíⁿeτení_Cesta[0])); // ZJIµT╖N╓ ZP▐SOBU ZAD╡V╡N╓ SOUⁿADNIC JEDNOTLIVφCH M╓ST NA MAP╖, KTER╡ JE MOªNO PROJ╓T if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { // pokud je vybrán grafick∞ reºim, umoºníme zpàsob zadávání vybrat mod_NechZvolit_Volby[0] = "ƒíseln╪"; mod_NechZvolit_AccessKeys[0] = 'ƒ'; mod_NechZvolit_Volby[1] = "graficky"; mod_NechZvolit_AccessKeys[1] = 'g'; switch(mod_NechZvolit("Zvolte zpàsob zadávání sou²adnic míst na map╪:")) { case 0: modCesta_ZpàsobZadáváníMíst = modCesta_ZAD╡V╡N╓M╓ST_¼╓SELN╖; break; case 1: modCesta_ZpàsobZadáváníMíst = modCesta_ZAD╡V╡N╓M╓ST_GRAFICKY; break; } } else if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { // jinak pokud je vybrán textov∞ reºim, lze zadávat pouze ƒíseln╪ modCesta_ZpàsobZadáváníMíst = modCesta_ZAD╡V╡N╓M╓ST_¼╓SELN╖; } // ZJIµT╖N╓ SOUⁿADNIC JEDNOTLIVφCH M╓ST NA MAP╖, KTER╡ JE MOªNO PROJ╓T int modCesta_ZadávanéMísto; if(modCesta_ZpàsobZadáváníMíst == modCesta_ZAD╡V╡N╓M╓ST_¼╓SELN╖) { for(modCesta_ZadávanéMísto=0; modCesta_ZadávanéMísto<modCesta_PoƒetMíst; modCesta_ZadávanéMísto++) { // ZJIµT╖N╓ X SOUⁿADNICE PR╡V╖ ZAD╡VANÉHO M╓STA mod_VypiτHláτku("Zadejte X sou²adnici místa "+(string)(char)('A'+modCesta_ZadávanéMísto)+" v pixelech [0-635]: ", mod_VYPIµHL╡µKU_NE¼EKEJ); if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { while((VyprázdniFrontuKláves(),Txt¼tiI¼íslo(modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2])) || modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2] < 0 || modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2] > 635); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN); while((VyprázdniFrontuKláves(),Gr¼tiI¼íslo("",modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2],3,0,PalTmav╪Modrá<<4|Palªlutá)) || modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2] < 0 || modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2] > 635); GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA); } // ZJIµT╖N╓ Y SOUⁿADNICE PR╡V╖ ZAD╡VANÉHO M╓STA mod_VypiτHláτku("Zadejte Y sou²adnici místa "+(string)(char)('A'+modCesta_ZadávanéMísto)+" v pixelech [0-442]: ", mod_VYPIµHL╡µKU_NE¼EKEJ); if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { while((VyprázdniFrontuKláves(),Txt¼tiI¼íslo(modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2+1])) || modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2+1] < 0 || modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2+1] > 442); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN); while((VyprázdniFrontuKláves(),Gr¼tiI¼íslo("",modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2+1],3,0,PalTmav╪Modrá<<4|Palªlutá)) || modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2+1] < 0 || modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2+1] > 442); GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA); } // ZOBRAZEN╓ PR╡V╖ ZAD╡VANÉHO M╓STA SPOLU S OSTATN╓MI JIª ZADANφMI if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { modCesta_VykresliMapu(0, modCesta_ZadávanéMísto+1); } // INFORMACE O SOUⁿADNICI PR╡V╖ ZAD╡VANÉHO M╓STA if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Sou²adnice místa "+(string)(char)('A'+modCesta_ZadávanéMísto)+" je "+StrL¼íslo(modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2],-1)+","+StrL¼íslo(modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2+1],-1)+"...", mod_VYPIµHL╡µKU_VY¼KEJ); } } } else if(modCesta_ZpàsobZadáváníMíst == modCesta_ZAD╡V╡N╓M╓ST_GRAFICKY) { NastavJménoBankyP²edm╪tà("*\\backtraq"); MyτZapni(); MyτNastavGrKurzor(25); MyτNastavPozici(mod_GRAFIKA_VφSTUP_MOJEPLOCHA_X1+(mod_GRAFIKA_VφSTUP_MOJEPLOCHA_X2-mod_GRAFIKA_VφSTUP_MOJEPLOCHA_X1)/2, mod_GRAFIKA_VφSTUP_MOJEPLOCHA_Y1+(mod_GRAFIKA_VφSTUP_MOJEPLOCHA_Y2-mod_GRAFIKA_VφSTUP_MOJEPLOCHA_Y1)/2); for(modCesta_ZadávanéMísto=0; modCesta_ZadávanéMísto<modCesta_PoƒetMíst; modCesta_ZadávanéMísto++) { // ZJIµT╖N╓ X SOUⁿADNICE PR╡V╖ ZAD╡VANÉHO M╓STA mod_VypiτHláτku("Pomocí myτi zadejte sou²adnici místa "+(string)(char)('A'+modCesta_ZadávanéMísto)+".", mod_VYPIµHL╡µKU_NE¼EKEJ); // vykreslení mapy - pouze dosud zadaná místa modCesta_VykresliMapu(0, modCesta_ZadávanéMísto); // nastavení a zobrazení myτi MyτVyprázdniFrontuUdálostí(); MyτZobrazKurzor(); // vyƒkání na volbu pozice práv╪ zadávaného místa do{ Myτ¼tiUdálost(gMyτUdálost); }while(gMyτUdálost.Typ != MyτUdálostLevéTlNahoru); gMyτUdálost.X -= mod_GRAFIKA_VφSTUP_MOJEPLOCHA_X1; gMyτUdálost.Y -= mod_GRAFIKA_VφSTUP_MOJEPLOCHA_Y1; // schování kurzoru myτi MyτSchovejKurzor(); // uloºení zadan∞ch hodnot do pole modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2] = gMyτUdálost.X; modCesta_Sou²adniceMíst[modCesta_ZadávanéMísto*2+1] = gMyτUdálost.Y; } MyτVypni(); // vykreslení mapy - vτechna zadaná místa modCesta_VykresliMapu(0, -1); NastavJménoBankyP²edm╪tà("*\\backtraq.mod\\"+AktivníModul->KrátkéJméno); } // ZJIµT╖N╓ PO¼TU SPOJNIC, KTERÉ JE MOªNO PⁿI NAVµT╖VOV╡N╓ M╓ST POUª╓T mod_VypiτHláτku("Zadejte, kolik spojnic mezi místy chcete vloºit [1-"+StrL¼íslo(modCesta_PoƒetMíst*(modCesta_PoƒetMíst-1)/2,-1)+"]: ", mod_VYPIµHL╡µKU_NE¼EKEJ); if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { while((VyprázdniFrontuKláves(),Txt¼tiI¼íslo(modCesta_PoƒetSpojnic)) || modCesta_PoƒetSpojnic < 1 || modCesta_PoƒetSpojnic > modCesta_PoƒetMíst*(modCesta_PoƒetMíst-1)/2); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN); while((VyprázdniFrontuKláves(),Gr¼tiI¼íslo("",modCesta_PoƒetSpojnic,3,0,PalTmav╪Modrá<<4|Palªlutá)) || modCesta_PoƒetSpojnic < 1 || modCesta_PoƒetSpojnic > modCesta_PoƒetMíst*(modCesta_PoƒetMíst-1)/2); GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA); } // INFORMACE O PO¼TU SPOJNIC, KTERÉ JE MOªNO PⁿI NAVµT╖VOV╡N╓ M╓ST POUª╓T if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Budete vkládat "+StrL¼íslo(modCesta_PoƒetSpojnic,-1)+" spojnic...", mod_VYPIµHL╡µKU_VY¼KEJ); } // Pⁿ╓PRAVA POLE SPOJNIC // alokace pam╪ti pro pole modCesta_Spojnice = (struct modCesta_TypSpojnice*)HromadaAlokujPam╪£(modCesta_PoƒetSpojnic*sizeof(modCesta_Spojnice[0])); // vynulování vτech prvkà pole memset(modCesta_Spojnice, 0, modCesta_PoƒetSpojnic*sizeof(modCesta_Spojnice[0])); // ZJIµT╖N╓, ZDA M╡ BφT HODNOTA ATRIBUTU SPOJNICE AUTOMATICKY NASTAVOV╡NA NA GRAFICKOU VZD╡LENOST M╓ST, KTER╡ SPOJUJE mod_NechZvolit_Volby[0] = "ano"; mod_NechZvolit_AccessKeys[0] = 'a'; mod_NechZvolit_Volby[1] = "ne"; mod_NechZvolit_AccessKeys[1] = 'n'; switch(mod_NechZvolit("Nastavovat atributy spojnic automaticky na jejich grafickou délku v pixelech?")) { case 0: modCesta_AtributJeDélkaSpojnice = 1; break; case 1: modCesta_AtributJeDélkaSpojnice = 0; break; } // INFORMACE O TOM, ZDA M╡ BφT HODNOTA ATRIBUTU SPOJNICE AUTOMATICKY NASTAVOV╡NA NA GRAFICKOU VZD╡LENOST M╓ST, KTER╡ SPOJUJE if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Atributy spojnic "+(modCesta_AtributJeDélkaSpojnice?"budu":"nebudu")+" automaticky nastavovat na jejich grafickou délkou...", mod_VYPIµHL╡µKU_VY¼KEJ); } // ZJIµT╖N╓ INFORMAC╓ O SPOJNIC╓CH, KTERÉ JE MOªNO PⁿI NAVµT╖VOV╡N╓ M╓ST POUª╓T modCesta_VykresliMapu(0, -1); int modCesta_ZadávanáSpojnice; int modCesta_ProcházenáSpojnice; char modCesta_Naƒten∞Znak; for(modCesta_ZadávanáSpojnice=0; modCesta_ZadávanáSpojnice<modCesta_PoƒetSpojnic; modCesta_ZadávanáSpojnice++) { // ZJIµT╖N╓ PRVN╓HO Z M╓ST TVOⁿ╓C╓CH PR╡V╖ ZAD╡VANOU SPOJNICI mod_VypiτHláτku("Zadejte písmenné oznaƒení prvního z míst tvo²ícího "+StrL¼íslo(modCesta_ZadávanáSpojnice+1,-1)+". spojnici [A-"+(string)(char)('A'+modCesta_PoƒetMíst-1)+"]: ", mod_VYPIµHL╡µKU_NE¼EKEJ); if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { while((VyprázdniFrontuKláves(),(modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1=(int)((*(char*)StrNaVelká((string)(char)Txt¼tiZnak()))-'A'))==-1) || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1 < 0 || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1 > modCesta_PoƒetMíst-1); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN); while((VyprázdniFrontuKláves(),Gr¼tiZnak("",modCesta_Naƒten∞Znak,0,PalTmav╪Modrá<<4|Palªlutá)==-1||0*(modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1=(int)((*(char*)StrNaVelká((string)modCesta_Naƒten∞Znak))-'A'))) || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1 < 0 || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1 > modCesta_PoƒetMíst-1); GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA); } // ZJIµT╖N╓ DRUHÉHO Z M╓ST TVOⁿ╓C╓CH PR╡V╖ ZAD╡VANOU SPOJNICI mod_VypiτHláτku("Zadejte písmenné oznaƒení druhého z míst tvo²ícího "+StrL¼íslo(modCesta_ZadávanáSpojnice+1,-1)+". spojnici [A-"+(string)(char)('A'+modCesta_PoƒetMíst-1)+"]: ", mod_VYPIµHL╡µKU_NE¼EKEJ); if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { while((VyprázdniFrontuKláves(),(modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2=(int)((*(char*)StrNaVelká((string)(char)Txt¼tiZnak()))-'A'))==-1) || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2 < 0 || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2 > modCesta_PoƒetMíst-1); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN); while((VyprázdniFrontuKláves(),Gr¼tiZnak("",modCesta_Naƒten∞Znak,0,PalTmav╪Modrá<<4|Palªlutá)==-1||0*(modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2=(int)((*(char*)StrNaVelká((string)modCesta_Naƒten∞Znak))-'A'))) || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2 < 0 || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2 > modCesta_PoƒetMíst-1); GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA); } // KONTROLA PLATNOSTI PR╡V╖ ZAD╡VANÉ SPOJNICE // kontrola zadání neexistující spojnice (vedoucí z jednoho místa do stejného) if(modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1 == modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2) { mod_VypiτHláτku("Chyba: Spojnice nemàºe zaƒínat i konƒit ve stejném míst╪. Zadejte jinou.", mod_VYPIµHL╡µKU_¼EKEJNAKL╡VESUGRAFIKA); modCesta_ZadávanáSpojnice--; continue; } // kontrola druhého zadávání jiº jednou zadané spojnice for(modCesta_ProcházenáSpojnice=0; modCesta_ProcházenáSpojnice<modCesta_ZadávanáSpojnice; modCesta_ProcházenáSpojnice++) { if((modCesta_Spojnice[modCesta_ProcházenáSpojnice].Místo1 == modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1 && modCesta_Spojnice[modCesta_ProcházenáSpojnice].Místo2 == modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2) || (modCesta_Spojnice[modCesta_ProcházenáSpojnice].Místo2 == modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1 && modCesta_Spojnice[modCesta_ProcházenáSpojnice].Místo1 == modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2)) { // zadávaná spojnice jiº byla zadána mod_VypiτHláτku("Chyba: Stejná spojnice jiº byla d²íve zadána. Zadejte jinou.", mod_VYPIµHL╡µKU_¼EKEJNAKL╡VESUGRAFIKA); break; } } if(modCesta_ProcházenáSpojnice < modCesta_ZadávanáSpojnice) { modCesta_ZadávanáSpojnice--; continue; } // ZJIµT╖N╓ HODNOTY ATRIBUTU PR╡V╖ ZAD╡VANÉ SPOJNICE if(modCesta_AtributJeDélkaSpojnice) { // automatické nastavení atributu spojnice na grafickou vzdálenost míst, která spojuje modCesta_Spojnice[modCesta_ZadávanáSpojnice].Atribut = modCesta_ZjistiVzdálenostMíst(modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1, modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2); } else { // ruƒní zadání hodnoty atributu spojnice mod_VypiτHláτku("Zadejte hodnotu atributu "+StrL¼íslo(modCesta_ZadávanáSpojnice+1,-1)+". spojnice [1-1000000]: ", mod_VYPIµHL╡µKU_NE¼EKEJ); if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { while((VyprázdniFrontuKláves(),Txt¼tiL¼íslo(modCesta_Spojnice[modCesta_ZadávanáSpojnice].Atribut)) || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Atribut < 1 || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Atribut > 1000000); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN); while((VyprázdniFrontuKláves(),Gr¼tiL¼íslo("",modCesta_Spojnice[modCesta_ZadávanáSpojnice].Atribut,7,0,PalTmav╪Modrá<<4|Palªlutá)) || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Atribut < 1 || modCesta_Spojnice[modCesta_ZadávanáSpojnice].Atribut > 1000000); GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA); } } // ZOBRAZEN╓ PR╡V╖ ZAD╡VANÉ SPOJNICE SPOLU S JIª ZADANφMI if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { modCesta_VykresliMapu(0, -1); } // INFORMACE O PR╡V╖ ZAD╡VANÉ SPOJNICI if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku(StrL¼íslo(modCesta_ZadávanáSpojnice+1,-1)+". spojnice spojuje místa "+(string)(char)('A'+modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo1)+" a "+(string)(char)('A'+modCesta_Spojnice[modCesta_ZadávanáSpojnice].Místo2)+" a má atribut hodnoty "+StrL¼íslo(modCesta_Spojnice[modCesta_ZadávanáSpojnice].Atribut,-1)+"...", mod_VYPIµHL╡µKU_VY¼KEJ); } } // ZJIµT╖N╓, JAKφ SOU¼ET HODNOT ATRIBUT▐ VµECH SPOJNIC HLEDAT mod_NechZvolit_Volby[0] = "co nejmenτí"; mod_NechZvolit_AccessKeys[0] = 'm'; mod_NechZvolit_Volby[1] = "co nejv╪tτí"; mod_NechZvolit_AccessKeys[1] = 'v'; switch(mod_NechZvolit("Jak∞ souƒet hodnot atributà vτech spojnic na cest╪ se má hledat?")) { case 0: modCesta_Jak∞SouƒetSpojnicHledat = modCesta_NEJMENµ╓_SOU¼ET; break; case 1: modCesta_Jak∞SouƒetSpojnicHledat = modCesta_NEJV╖Tµ╓_SOU¼ET; break; } // INFORMACE O TOM, JAKφ SOU¼ET HODNOT ATRIBUT▐ VµECH SPOJNIC HLEDAT if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Budu hledat co "+(modCesta_Jak∞SouƒetSpojnicHledat==modCesta_NEJMENµ╓_SOU¼ET?"nejmenτí":"nejv╪tτí")+" souƒet hodnot atributà vτech spojnic na cest╪...", mod_VYPIµHL╡µKU_VY¼KEJ); } // ZJIµT╖N╓, KTERÉ POZICE ZOBRAZOVAT mod_NechZvolit_Volby[0] = "jen ²eτení"; mod_NechZvolit_AccessKeys[0] = '²'; mod_NechZvolit_Volby[1] = "i pràb╪h hledání"; mod_NechZvolit_AccessKeys[1] = 'p'; switch(mod_NechZvolit("Zobrazovat jen nalezená ²eτení nebo i pràb╪h hledání (upozorn╪ní: pomalé)?")) { case 0: mod_ZobrazovanéPozice = mod_POUZE_ⁿEµEN╓; break; case 1: mod_ZobrazovanéPozice = mod_VµECHNY_POZICE; break; } // INFORMACE O TOM, KTERÉ POZICE ZOBRAZOVAT if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Budu zobrazovat "+(mod_ZobrazovanéPozice==mod_POUZE_ⁿEµEN╓?"jen nalezená ²eτení":"i pràb╪h hledání")+"...", mod_VYPIµHL╡µKU_VY¼KEJ); } // ZJIµT╖N╓, ZDA ¼EKAT PO NALEZEN╓ NOVÉHO NEJLEPµ╓HO ⁿEµEN╓ NA STISK KL╡VESY if(mod_ZobrazovanéPozice == mod_POUZE_ⁿEµEN╓) { // pokud se zobrazuje pouze v∞sledné nalezené ²eτení, po nalezení jednotliv∞ch nov∞ch nejlepτích ²eτení se nikdy neƒeká mod_¼ekatNaKlávesu = 0; } else { mod_NechZvolit_Volby[0] = "ano, vyƒkat"; mod_NechZvolit_AccessKeys[0] = 'a'; mod_NechZvolit_Volby[1] = "ne, neƒekat"; mod_NechZvolit_AccessKeys[1] = 'n'; switch(mod_NechZvolit("Vyƒkat po nalezení nového nejlepτího ²eτení na stisknutí klávesy?")) { case 0: mod_¼ekatNaKlávesu = 1; break; case 1: mod_¼ekatNaKlávesu = 0; break; } // INFORMACE O TOM, ZDA PO NALEZEN╓ NOVÉHO NEJLEPµ╓HO ⁿEµEN╓ ¼EKAT NA STISK KL╡VESY if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Po nalezení nového nejlepτího ²eτení "+(mod_¼ekatNaKlávesu?"budu":"nebudu")+" ƒekat na stisk klávesy...", mod_VYPIµHL╡µKU_VY¼KEJ); } } // ZJIµT╖N╓, ZDA ZAPISOVAT PROTOKOL O VφPO¼TU DO SOUBORU mod_NechZvolit_Volby[0] = "ano, zapisovat"; mod_NechZvolit_AccessKeys[0] = 'a'; mod_NechZvolit_Volby[1] = "ne, nezapisovat"; mod_NechZvolit_AccessKeys[1] = 'n'; switch(mod_NechZvolit("Zapisovat protokol o v∞poƒtu do souboru?")) { case 0: mod_ZapisovatProtokol = 1; break; case 1: mod_ZapisovatProtokol = 0; break; } // INFORMACE O TOM, ZDA ZAPISOVAT PROTOKOL O VφPO¼TU DO SOUBORU if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Protokol o v∞poƒtu "+(mod_ZapisovatProtokol?"budu":"nebudu")+" zapisovat do souboru...", mod_VYPIµHL╡µKU_VY¼KEJ); } if(mod_ZapisovatProtokol) { // ZJIµT╖N╓ N╡ZVU SOUBORU, KAM ZAPISOVAT PROTOKOL O VφPO¼TU mod_VypiτHláτku("Zadejte název souboru: ", mod_VYPIµHL╡µKU_NE¼EKEJ); mod_ZapisovatProtokol_Název = ""; if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { Txtⁿádkov∞Editor(mod_ZapisovatProtokol_Název,50,50,-1,0); TxtPiτNov∞ⁿádek(); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { GrNastavV∞stup(mod_GRAFIKA_VφSTUP_POKYN); VyprázdniFrontuKláves(); Grⁿádkov∞Editor(mod_ZapisovatProtokol_Název,50,-1,0,-1,PalTmav╪Modrá<<4|Palªlutá); GrNastavV∞stup(mod_GRAFIKA_VφSTUP_MOJEPLOCHA); } if(StrKopie(mod_ZapisovatProtokol_Název, 1, 1) != ":") mod_ZapisovatProtokol_Název = "*\\" + mod_ZapisovatProtokol_Název; // INFORMACE O N╡ZVU SOUBORU, KAM ZAPISOVAT PROTOKOL O VφPO¼TU if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { mod_VypiτHláτku("Zvolen soubor "+mod_ZapisovatProtokol_Název+"...", mod_VYPIµHL╡µKU_VY¼KEJ); } } } void modCesta_OptimalizaceVstupu(void) { } void modCesta_OpakováníInicializace(void) { modCesta_Cesta[modCesta_Θroveσ] = 0; } int modCesta_OpakováníTest(void) { // kdyº je jeτt╪ jaké spojnice procházet (procházení jeτt╪ nebylo dokonƒeno) if(modCesta_Cesta[modCesta_Θroveσ] < modCesta_PoƒetSpojnic) { // p²ipoƒtení hodnoty atributu práv╪ procházené spojnice k souƒtu hodnot atributà celé cesty modCesta_SouƒetSpojnic += modCesta_Spojnice[modCesta_Cesta[modCesta_Θroveσ]].Atribut; // vrácení informace o tom, ∞e se má pokraƒovat v procházení return 1; } else { // vrácení informace o tom, ∞e procházení jiº bylo dokonƒeno return 0; } } void modCesta_OpakováníIterace(void) { // odeƒtení hodnoty atributu práv╪ procházené spojnice od souƒtu hodnot atributà celé cesty modCesta_SouƒetSpojnic -= modCesta_Spojnice[modCesta_Cesta[modCesta_Θroveσ]].Atribut; // p²echod k následující spojnici modCesta_Cesta[modCesta_Θroveσ]++; } void modCesta_Dalτí¼lánek_P²ed(void) { // zv∞τení úrovn╪ backtrackingu (poƒet spojnic v práv╪ testované cest╪) modCesta_Θroveσ++; } void modCesta_Dalτí¼lánek_Po(void) { // zmenτení úrovn╪ backtrackingu (poƒet spojnic v práv╪ testované cest╪) modCesta_Θroveσ--; } int modCesta_TestVyhovuje(void) { int modCesta_Procházen∞Prvek; struct modCesta_TypSpojnice modCesta_ProcházenáSpojnice; // zjiτt╪ní, zda nalezená pozice vyhovuje podmínkám úlohy // kontrola, zda práv╪ p²idaná spojnice navazuje na p²edchozí spojnici struct modCesta_TypSpojnice modCesta_P²edchozíSpojnice; struct modCesta_TypSpojnice modCesta_P²edp²edchozíSpojnice; int modCesta_NavazovanéMísto; int modCesta_P²idávanéMísto; modCesta_ProcházenáSpojnice = modCesta_Spojnice[modCesta_Cesta[modCesta_Θroveσ]]; // zjiτt╪ní p²edchozí a p²edp²edchozí spojnice if(modCesta_Θroveσ == 0) { // pokud se jedná o první spojnici na cest╪ modCesta_P²edchozíSpojnice.Místo1 = 0; modCesta_P²edchozíSpojnice.Místo2 = 0; modCesta_P²edp²edchozíSpojnice.Místo1 = 0; modCesta_P²edp²edchozíSpojnice.Místo2 = 0; } else if(modCesta_Θroveσ == 1) { // pokud se jedná o druhou spojnici na cest╪ modCesta_P²edchozíSpojnice = modCesta_Spojnice[modCesta_Cesta[modCesta_Θroveσ-1]]; modCesta_P²edp²edchozíSpojnice.Místo1 = 0; modCesta_P²edp²edchozíSpojnice.Místo2 = 0; } else { // pokud se nejedná o první ani o druhou spojnici na cest╪ modCesta_P²edchozíSpojnice = modCesta_Spojnice[modCesta_Cesta[modCesta_Θroveσ-1]]; modCesta_P²edp²edchozíSpojnice = modCesta_Spojnice[modCesta_Cesta[modCesta_Θroveσ-2]]; } // rozliτení navazovaného a p²idávaného místa if((modCesta_ProcházenáSpojnice.Místo1 == modCesta_P²edchozíSpojnice.Místo1 && (modCesta_P²edchozíSpojnice.Místo2 == modCesta_P²edp²edchozíSpojnice.Místo1 || modCesta_P²edchozíSpojnice.Místo2 == modCesta_P²edp²edchozíSpojnice.Místo2)) || (modCesta_ProcházenáSpojnice.Místo1 == modCesta_P²edchozíSpojnice.Místo2 && (modCesta_P²edchozíSpojnice.Místo1 == modCesta_P²edp²edchozíSpojnice.Místo1 || modCesta_P²edchozíSpojnice.Místo1 == modCesta_P²edp²edchozíSpojnice.Místo2))) { modCesta_NavazovanéMísto = modCesta_ProcházenáSpojnice.Místo1; modCesta_P²idávanéMísto = modCesta_ProcházenáSpojnice.Místo2; } else if((modCesta_ProcházenáSpojnice.Místo2 == modCesta_P²edchozíSpojnice.Místo1 && (modCesta_P²edchozíSpojnice.Místo2 == modCesta_P²edp²edchozíSpojnice.Místo1 || modCesta_P²edchozíSpojnice.Místo2 == modCesta_P²edp²edchozíSpojnice.Místo2)) || (modCesta_ProcházenáSpojnice.Místo2 == modCesta_P²edchozíSpojnice.Místo2 && (modCesta_P²edchozíSpojnice.Místo1 == modCesta_P²edp²edchozíSpojnice.Místo1 || modCesta_P²edchozíSpojnice.Místo1 == modCesta_P²edp²edchozíSpojnice.Místo2))) { modCesta_NavazovanéMísto = modCesta_ProcházenáSpojnice.Místo2; modCesta_P²idávanéMísto = modCesta_ProcházenáSpojnice.Místo1; } else { // vrácení informace, ºe nalezená pozice nevyhovuje podmínkám úlohy return 0; } // kontrola, zda n╪které z míst jiº v cest╪ obsaºen∞ch není shodné s místem práv╪ do cesty p²idan∞m prost²ednictvím práv╪ p²idané spojnice for(modCesta_Procházen∞Prvek=0; modCesta_Procházen∞Prvek<modCesta_Θroveσ; modCesta_Procházen∞Prvek++) { modCesta_ProcházenáSpojnice = modCesta_Spojnice[modCesta_Cesta[modCesta_Procházen∞Prvek]]; if(modCesta_ProcházenáSpojnice.Místo1 == modCesta_P²idávanéMísto || modCesta_ProcházenáSpojnice.Místo2 == modCesta_P²idávanéMísto) { // vrácení informace, ºe nalezená pozice nevyhovuje podmínkám úlohy return 0; } } // je testovaná pozice stále lepτí neº doposud nejlepτí nalezené ²eτení? if(modCesta_Jak∞SouƒetSpojnicHledat == modCesta_NEJMENµ╓_SOU¼ET && !(modCesta_SouƒetSpojnic < modCesta_Nejlepτíⁿeτení_SouƒetSpojnic)) { // ne, není => pozice tedy není vyhovující (hledá se jen to nejlepτí ²eτení) return 0; } // pozn.: p²i hledání co nejv╪tτího souƒtu nelze rozhodovat jiº o kvalit╪ ƒásteƒného ²eτení (tj. na tomto míst╪), lze tak uƒinit aº p²i nalezení kompletního ²eτení // zobrazení práv╪ testované pozice, pokud si uºivatel toto nastavil if(mod_ZobrazovanéPozice == mod_VµECHNY_POZICE) { if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { TxtPiτⁿet╪zec(modCesta_PoleCestyNaⁿet╪zec(modCesta_Cesta, &modCesta_Θroveσ, &modCesta_SouƒetSpojnic)); TxtPiτNov∞ⁿádek(); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { modCesta_VykresliMapu(modCesta_Cesta, modCesta_Θroveσ); if(modCesta_PoƒetSpojnic > 1 && modCesta_PoƒetSpojnic <= 10) ¼ekej(1.0/modCesta_PoƒetSpojnic*6000-200); } if(mod_ZapisovatProtokol) { SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "Testuji "); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, modCesta_PoleCestyNaⁿet╪zec(modCesta_Cesta, &modCesta_Θroveσ, &modCesta_SouƒetSpojnic)); SouborPiτNov∞ⁿádek(mod_ZapisovatProtokol_Soubor); } } // vrácení informace, ºe nalezená pozice vyhovuje podmínkám úlohy return 1; } int modCesta_TestNalezeno(void) { // nov∞ kandidát na ²eτení byl nalezen, pokud je práv╪ nalezené ²eτení kompletní struct modCesta_TypSpojnice modCesta_TestovanáSpojnice; modCesta_TestovanáSpojnice = modCesta_Spojnice[modCesta_Cesta[modCesta_Θroveσ]]; return (modCesta_TestovanáSpojnice.Místo1 == modCesta_PoƒetMíst-1 || modCesta_TestovanáSpojnice.Místo2 == modCesta_PoƒetMíst-1); } void modCesta_Nalezeno(void) { // je nalezené ²eτení lepτí neº doposud nejlepτí nalezené? if(modCesta_Jak∞SouƒetSpojnicHledat == modCesta_NEJV╖Tµ╓_SOU¼ET && !(modCesta_SouƒetSpojnic > modCesta_Nejlepτíⁿeτení_SouƒetSpojnic)) { // ne, není => ²eτení nemá smysl zaznamenávat (hledá se jen to nejlepτí) return; } // pozn.: p²i hledání co nejv╪tτího souƒtu nelze rozhodovat jiº o kvalit╪ ƒásteƒného ²eτení (jako se tomu d╪je p²i hledání nejmenτího souƒtu), lze tak uƒinit aº p²i nalezení kompletního ²eτení (tj. na tomto míst╪) // ano => uloºení nalezeného ²eτení jako dosud nejlepτího memmove(modCesta_Nejlepτíⁿeτení_Cesta, modCesta_Cesta, modCesta_PoƒetMíst*sizeof(modCesta_Cesta[0])); modCesta_Nejlepτíⁿeτení_SouƒetSpojnic = modCesta_SouƒetSpojnic; modCesta_Nejlepτíⁿeτení_Θroveσ = modCesta_Θroveσ; // zobrazení práv╪ nalezeného ²eτení if(mod_ReºimObrazovky == mod_TEXTOVφ_REªIM) { TxtPiτⁿet╪zec("Nalezeno dosud nejlepτí ²eτení: "); TxtPiτⁿet╪zec(modCesta_PoleCestyNaⁿet╪zec(modCesta_Cesta, &modCesta_Θroveσ, &modCesta_SouƒetSpojnic)); TxtPiτNov∞ⁿádek(); } else if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM) { mod_VypiτHláτku("Nalezeno dosud nejlepτí ²eτení: " + modCesta_PoleCestyNaⁿet╪zec(modCesta_Cesta, &modCesta_Θroveσ, &modCesta_SouƒetSpojnic), mod_VYPIµHL╡µKU_NE¼EKEJ); if(mod_ZobrazovanéPozice == mod_POUZE_ⁿEµEN╓) modCesta_VykresliMapu(modCesta_Nejlepτíⁿeτení_Cesta, modCesta_Nejlepτíⁿeτení_Θroveσ); } // zápis práv╪ nalezeného ²eτení do souboru, pokud si to uºivatel p²ál if(mod_ZapisovatProtokol) { SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, "NALEZENO DOSUD NEJLEPµ╓ ⁿEµEN╓: "); SouborPiτⁿet╪zec(mod_ZapisovatProtokol_Soubor, modCesta_PoleCestyNaⁿet╪zec(modCesta_Cesta, &modCesta_Θroveσ, &modCesta_SouƒetSpojnic)); SouborPiτNov∞ⁿádek(mod_ZapisovatProtokol_Soubor); } // v p²ípad╪ grafického reºimu, pokud se ale nezobrazují pouze nalezená ²eτení, pípnutí - oznámení nalezení nového nejlepτího ²eτení if(mod_ReºimObrazovky == mod_GRAFICKφ_REªIM && !(mod_ZobrazovanéPozice == mod_POUZE_ⁿEµEN╓)) { Tón(1000); ¼ekej(100); VypniTón(); } // vyƒkání na stisk klávesy, pokud si to uºivatel p²ál if(mod_¼ekatNaKlávesu) ¼ekejNaKlávesu(); } void modCesta_InfoOModulu(struct _ModulInfo* ModulInfo) { ModulInfo->KrátkéJméno = "Cesta"; ModulInfo->DlouhéJméno = "Hledání nejlepτí cesty"; ModulInfo->Popis = "P²i cestování se ƒlov╪k ƒasto ocitne v situaci, kdy má k dispozici n╪kolik ràzn∞ch cest, kter∞mi se màºe vydat. Ideální samoz²ejm╪ je zvolit tu nejlepτí (nejkratτí, ƒasov╪ nejmén╪ nároƒnou, nejlevn╪jτí...). Jak ji ale poznat, pokud se n╪které z nabízejících se cest jeτt╪ dále rozd╪lují a jiné naopak spojují - kdyº je sí£ cest p²íliτ sloºitá? Tady letm∞ pohled nepomàºe, pro nalezení té nejlepτí cesty se prost╪ musí vyzkouτet vτechny moºnosti. Tento modul vyuºívá algoritmus backtrackingu k vyhledání nejlepτí cesty za vás."; ModulInfo->Verze = 1.0; ModulInfo->Datum.Den = 20; ModulInfo->Datum.M╪síc = 9; ModulInfo->Datum.Rok = 2002; ModulInfo->Autor = "Marek Blahuτ"; ModulInfo->Kontakt = "blahus@seznam.cz"; ModulInfo->Start = &modCesta_Start; ModulInfo->Hotovo = &modCesta_Hotovo; ModulInfo->Θklid = &modCesta_Θklid; ModulInfo->ZadáníVstupu = &modCesta_ZadáníVstupu; ModulInfo->OptimalizaceVstupu = &modCesta_OptimalizaceVstupu; ModulInfo->OpakováníInicializace = &modCesta_OpakováníInicializace; ModulInfo->OpakováníTest = &modCesta_OpakováníTest; ModulInfo->OpakováníIterace = &modCesta_OpakováníIterace; ModulInfo->Dalτí¼lánek_P²ed = &modCesta_Dalτí¼lánek_P²ed; ModulInfo->Dalτí¼lánek_Po = &modCesta_Dalτí¼lánek_Po; ModulInfo->TestVyhovuje = &modCesta_TestVyhovuje; ModulInfo->TestNalezeno = &modCesta_TestNalezeno; ModulInfo->Nalezeno = &modCesta_Nalezeno; } 
