Staonův svět - Průchod ulicí

A mám tady další veselou programovací úložku. A bohužel opět v Pascalu :(

Zadání

Zadání úlohy najdete opět na stránkách cvičícího. Zadání je uložené i v balíku ke stažení.

Řešení

Řešení je celkem přímočaré, prostě beru řádku za řádkou a vybarvuji dostupné části. Časová složitost je O(n.m2), kde n je počet řádek ulice, m je její šířka. Složitost je dána tím, že pro každou řádku barvím jednou zleva (O(m)), jednou zprava (O(m)) a nakonec se složitostí O(m2)sloučím ekvivalentní barvy. Paměťová složitost je O(m) – uchováváma dvě řádky ulice (aktuální a předchozí) plus ještě jednu řádku pro „zavržené“ barvy.

Program

  1. { -- potrebuji nacitaci unitu }
  2. uses ulice;
  3.  
  4. const
  5.   OUTPUT_FILE='vystup.txt';
  6.  
  7. type
  8.   { -- Jedno obarvovaci pole }
  9.   OBarvickyRadka = array[1 .. sirka] of integer;
  10.   { -- cely objekt barvicek }
  11.   OBarvicky = record
  12.     { -- aktualni a predchozi vybarveni ulice }
  13.     barvicky: array[0..1] of OBarvickyRadka;
  14.     { -- zavrzene barvy, ta ktere se pri barveni nezvolila }
  15.     zavrzene: OBarvickyRadka;
  16.     { -- index aktualni radky }
  17.     current: integer;
  18.     { -- aktualni nepouzita barva }
  19.     free_color: integer;
  20.     { -- nejvyssi index barvy v prvni radce }
  21.     first_color: integer;
  22.     { -- priznak, ze tato radka je dostupna }
  23.     reachable: boolean;
  24.   end;
  25.   { -- stav reseni }
  26.   OStatus = record
  27.     { -- stav obarvovani }
  28.     barvicky: OBarvicky;
  29.   end;
  30.  
  31. {====================================================
  32.    PRACE S BARVICKAMI
  33. ====================================================}
  34. { -- inicializace objektu s barvickami }
  35. procedure barvickyInit(var barvicky: OBarvicky);
  36. begin
  37.   barvicky.current := 0;
  38.   barvicky.free_color := 1;
  39.   barvicky.first_color := 0;
  40.   barvicky.reachable := FALSE;
  41. end;
  42.  
  43. { -- alokuje novou nepouzitou barvu }
  44. function barvickyAlloc(var barvicky: OBarvicky): integer;
  45. var
  46.   retval: integer;
  47. begin
  48.   retval := barvicky.free_color;
  49.   barvicky.free_color := barvicky.free_color + 1;
  50.   barvickyAlloc := retval;
  51. end;
  52.  
  53. { -- vrati aktualni nepouzitou barvu }
  54. function barvickyGetCurrColor(var barvicky: OBarvicky): integer;
  55. begin
  56.   barvickyGetCurrColor := barvicky.free_color;
  57. end;
  58.  
  59. { -- vraci novou barvu pro zadanou souradnici. V parametru up
  60.      ocekava barvu ctverce na aktualnim, v parametru next ceka
  61.      barvu predchoziho ctverce (levy nebo pravy podle smeru).
  62.      Zapornou hodnotu povazuje za prekazu). V parametru current
  63.      je barva aktualniho ctverce - pokud je zaporna, jedna se o
  64.      prekazku, pokud je 0, jedna se o zatim neurcenou barvu (v
  65.      prvnim pruchodu). V parametru denied vraci zavrzenou barvu,
  66.      nebo -1, pokud nebyla barva na vyber.}
  67. function barvickyGetNew(
  68.       var barvicky: OBarvicky;
  69.       up: integer;
  70.       next: integer;
  71.       current: integer;
  72.       var denied: integer): integer;
  73. var
  74.   retval: integer;
  75. begin
  76.   denied := -1;
  77.   if current < 0 then
  78.     { -- aktualni je prekazka, nova je take prekazka }
  79.     barvickyGetNew := -1
  80.   else
  81.   begin
  82.     if up < 0 then
  83.     begin
  84.       { -- horni je prekazka, proto zalezi pouze na vedlejsim }
  85.       if next < 0 then
  86.         retval := barvickyAlloc(barvicky)
  87.       else
  88.         retval := next;
  89.     end
  90.     else
  91.     begin
  92.       { -- horni neni prekazka }
  93.       if next < 0 then
  94.         retval := up
  95.       else
  96.       begin
  97.         { -- oba jsou platne, beru ten mensi }
  98.         if next < up then
  99.         begin
  100.           retval := next;
  101.           denied := up;
  102.         end
  103.         else
  104.         begin
  105.           retval := up;
  106.           denied := next;
  107.         end;
  108.       end
  109.     end;
  110.     { -- tady uz znam novou barvu, srovnam s puvodni }
  111.     if (current > 0) and (retval > current) then
  112.       retval := current;
  113.     barvickyGetNew := retval;
  114.   end;
  115. end;
  116.  
  117. { -- vraci index aktualni radky }
  118. function barvickyGetCurrent(var barvicky: OBarvicky): integer;
  119. begin
  120.   barvickyGetCurrent := barvicky.current;
  121. end;
  122.  
  123. { -- vraci index predchozi radky }
  124. function barvickyGetPrev(var barvicky: OBarvicky): integer;
  125. begin
  126.   barvickyGetPrev := 1 - barvicky.current;
  127. end;
  128.  
  129. { -- prehodi aktualni a predchozi radku }
  130. procedure barvickySwap(var barvicky: OBarvicky);
  131. begin
  132.   if barvickyGetCurrent(barvicky) = 0 then
  133.     barvicky.current := 1
  134.   else
  135.     barvicky.current := 0;
  136. end;
  137.  
  138. { -- prevede dany znak z radku ulice na cislo barvy (presneji na
  139.      neurcenou 0, nebo na -1 pro prekazku) }
  140. function barvickyGetColor(character: char): integer;
  141. begin
  142.   if character = '1' then
  143.     barvickyGetColor := -1
  144.   else
  145.     barvickyGetColor := 0;
  146. end;
  147.  
  148. { -- zinicializuje prvni pole podle zadane prvni radky ulice }
  149. procedure barvickySetFirst(var barvicky: OBarvicky; rada: t_rada);
  150. var
  151.   i: integer;
  152.   curr: integer;
  153.   denied: integer;
  154. begin
  155.   curr := barvickyGetCurrent(barvicky);
  156.  
  157.   barvicky.barvicky[curr][1] := barvickyGetNew(
  158.                                     barvicky,
  159.                                     -1, -1,
  160.                                     barvickyGetColor(rada[1]),
  161.                                     denied);
  162.   for i := 2 to sirka do
  163.     barvicky.barvicky[curr][i] := barvickyGetNew(
  164.                                     barvicky,
  165.                                     -1,
  166.                                     barvicky.barvicky[curr][i - 1],
  167.                                     barvickyGetColor(rada[i]),
  168.                                     denied);
  169.   { -- nastavim nejvyssi index barvy v prvni radce }
  170.   barvicky.first_color := barvickyGetCurrColor(barvicky);
  171.   barvicky.reachable := TRUE;
  172. end;
  173.  
  174. { -- provede pruchod zleva }
  175. procedure barvickyLeftRun(var barvicky: OBarvicky; rada: t_rada);
  176. var
  177.   i: integer;
  178.   curr, prev: integer;
  179. begin
  180.   curr := barvickyGetCurrent(barvicky);
  181.   prev := barvickyGetPrev(barvicky);
  182.  
  183.   barvicky.barvicky[curr][1] := barvickyGetNew(
  184.                                     barvicky,
  185.                                     barvicky.barvicky[prev][1],
  186.                                     -1,
  187.                                     barvickyGetColor(rada[1]),
  188.                                     barvicky.zavrzene[1]);
  189.   for i := 2 to sirka do
  190.     barvicky.barvicky[curr][i] := barvickyGetNew(
  191.                                     barvicky,
  192.                                     barvicky.barvicky[prev][i],
  193.                                     barvicky.barvicky[curr][i - 1],
  194.                                     barvickyGetColor(rada[i]),
  195.                                     barvicky.zavrzene[i]);
  196. end;
  197.  
  198. { -- provede pruchod zprava }
  199. procedure barvickyRightRun(var barvicky: OBarvicky);
  200. var
  201.   i: integer;
  202.   curr, prev: integer;
  203.   denied: integer;
  204. begin
  205.   curr := barvickyGetCurrent(barvicky);
  206.   prev := barvickyGetPrev(barvicky);
  207.  
  208.   barvicky.barvicky[curr][sirka] := barvickyGetNew(
  209.                                     barvicky,
  210.                                     barvicky.barvicky[prev][sirka],
  211.                                     -1,
  212.                                     barvicky.barvicky[curr][sirka],
  213.                                     denied);
  214.   for i := sirka - 1 downto 1 do
  215.     barvicky.barvicky[curr][i] := barvickyGetNew(
  216.                                     barvicky,
  217.                                     barvicky.barvicky[prev][i],
  218.                                     barvicky.barvicky[curr][i + 1],
  219.                                     barvicky.barvicky[curr][i],
  220.                                     denied);
  221. end;
  222.  
  223. { -- sloucim ekvivalentni barvy. Tenhle algoritmus neni tak uplne nejhezci,
  224.      ale protoze je umerny kvadratu sirky ulice a sirka ulice je velmi
  225.      kratka, tak se nezatezuji nejakym slozitejsim algoritmem. }
  226. procedure barvickyMerge(var barvicky: OBarvicky);
  227. var
  228.   i, j: integer;
  229.   curr: integer;
  230.   a, b: integer;
  231. begin
  232.   curr := barvickyGetCurrent(barvicky);
  233.   barvicky.reachable := FALSE;
  234.  
  235.   for i := 1 to sirka do
  236.   begin
  237.     { -- pokud tato barva vznikla z nejake zavrzene, nahradim tuto zavrzenou novou }
  238.     if (barvicky.zavrzene[i] > 0) and (barvicky.barvicky[curr][i] <> barvicky.zavrzene[i]) then
  239.     begin
  240.       a := barvicky.zavrzene[i]; b := barvicky.barvicky[curr][i];
  241.       for j := 1 to sirka do
  242.         if barvicky.barvicky[curr][j] = a then
  243.           barvicky.barvicky[curr][j] := b;
  244.     end;
  245.  
  246.     { -- nastavim priznak pruchodnosti }
  247.     if
  248.       (barvicky.barvicky[curr][i] > 0)
  249.       and (barvicky.barvicky[curr][i] < barvicky.first_color) then
  250.       barvicky.reachable := TRUE;
  251.   end;
  252. end;
  253.  
  254. { -- provede jeden krok algoritmu }
  255. procedure barvickyDoStep(var barvicky: OBarvicky; rada: t_rada);
  256. begin
  257.   { -- prehodim aktualni a predchozi radku }
  258.   barvickySwap(barvicky);
  259.   { -- nejprve provedu pruchod zleva }
  260.   barvickyLeftRun(barvicky, rada);
  261.   { -- a ted pruchod zprava }
  262.   barvickyRightRun(barvicky);
  263.   { -- sloucim stejne barvy }
  264.   barvickyMerge(barvicky);
  265. end;
  266.  
  267. { -- vraci TRUE, pokud je aktualni radka dostupna (platne az pro provedeni
  268.      jednoho kroku) }
  269. function barvickyIsReachable(var barvicky: OBarvicky): boolean;
  270. begin
  271.   barvickyIsReachable := barvicky.reachable;
  272. end;
  273.  
  274. {====================================================
  275.    HLAVNI CAST PROGRAMU
  276. ====================================================}
  277. { -- provede postuponou iteraci pres jednotlive radky. Vraci
  278.      TRUE, pokud je ulice pruchozi, jinak FALSE. }
  279. function mainIteration(var status: OStatus): boolean;
  280. var
  281.   rada: t_rada;
  282. begin
  283.   rada := next();
  284.   if rada = '' then
  285.     mainIteration := FALSE
  286.   else
  287.   begin
  288.     { -- zinicializuje prvni radu }
  289.     barvickySetFirst(status.barvicky, rada);
  290.  
  291.     { -- postupne prochazim ostatni radky }
  292.     rada := next();
  293.     while rada <> '' do
  294.     begin
  295.       barvickyDoStep(status.barvicky, rada);
  296.       rada := next();
  297.     end;
  298.  
  299.     mainIteration := barvickyIsReachable(status.barvicky);
  300.   end;
  301. end;
  302.  
  303. procedure main;
  304. var
  305.   status: OStatus;
  306.   ofile: text;
  307. begin
  308.   { -- inicializace barvicek }
  309.   barvickyInit(status.barvicky);
  310.  
  311.   { -- zinicializuji nacitaci unitu }
  312.   ulice_init();
  313.  
  314.  
  315.   { -- otevreni vystupniho souboru }
  316.   assign(ofile, OUTPUT_FILE);
  317.   rewrite(ofile);
  318.  
  319.   { -- proiteruji celou ulici }
  320.   if mainIteration(status) then
  321.     writeln(ofile, 'A')
  322.   else
  323.     writeln(ofile, 'N');
  324.  
  325.   { -- uzavru vystupni soubor }
  326.   close(ofile);
  327.  
  328.   { -- uzavru unitu }
  329.   ulice_done();
  330. end;
  331.  
  332. begin
  333.   main();
  334. end.

Ke stažení

Zdroják, zkušební datové soubory a uložené zadání lze stáhnout zde.

Staon | 1.12.2005 Čt 17:36 | <<< trvalý odkaz >>> | tisk | 5 komentářů

Komentáře k textu

Rss komentářů tohoto textu

[1] reaguj
Jimi mejl web 1.12.2005 Čt 18:47

Nejak som to nesledoval moc pozorne, ale zda sa mi ze vzhladom na to ze hlavnu rozhodovaciu sekvenciu mas na cca 20 riadkov je to pomerne dost dlhe :D Neviem ako presne by som to robil ja, ale urcite viac stredoskolsky :D

Hlavny problem vidim v tom, ze ked kontrolujes jedno policko, tak nevies ci nakoniec bude patrit do priechodnej casti alebo nie… to netusim ako by som vykseftil :-) Ale musim sa pochvalit ze som spravil vlastny algoritmus na hladanie najkratsej cesty v bludisku zlozenom zo sestuholnikov :P (a vsetky testy boli uspesne)

[2] reaguj
Staon mejl web 2.12.2005 Pá 09:33

[1] Jimi : která část konkrétně ti připadá dlouhá, já ji ještě nějak rozdělím… :-D

Máš přesně pravdu, jakmile ta cesta skrz ulici se někde „vrací,“ tak musím začít slučovat ekvivalenetní barvy a proto je tam ten blbý kvadratický člen ve složitosti. Ale vzhledem k maximální šířce ulice nehodlám vymýšlet něco lepšího :))

Jak jsi procházel bludištěm šestiúhelníků? Sem s tím, na to bych se rád kouknul :))

[3] reaguj
Jimi mejl web 2.12.2005 Pá 11:11

No ono to bolo vo Visual Basicu a potreboval som to na boj v hre :D Tam mas proste na bojovom poli sestuholniky a na niektorych su postavicky a nejaka ina postavicka musi okolo nich prejst aby sa dostala na svoj cielovy sestuholnik… a ten kod ma cca 100 riadkov. Pouzivam tam vlastne 2 zakladne algoritmy, t.j. ak je primarna x-ova suradnica a ak je primarna y-ova suradnica, ktore potom variabilne menim na vsetky mozne kombinacie striedania priorit pre x ci y suradnicu :D chapes? :D :D

[4] reaguj
Jimi mejl web 2.12.2005 Pá 12:10

btw narazil som na sutaz programator roku… nechces sa prihlasit? ;-)

http://www.zive.cz/experti/

[5] reaguj
Staon mejl web 2.12.2005 Pá 22:59

[3] Jimi : no samozřejmě, že chápu, čekal jsi snad něco jiného? :-DDDDD

[4] Jimi : Ani snad ne, taková programátorksá bedna fakt nejsem. Navíc je to moc orientované na Microsoft, vědomostní soutěž z Visual Studia bych vážně nezvládl :(

Přidej komentář!

  Gravatar povolen.

Příspěvěk je formátován Texy! syntaxí. Není povoleno HTML, odkazy se převádějí automaticky.
Kolik je 3 x 5?
Odpověd: nevím, ale násobení na reálných číslech tvoří komutativní grupu. 237

Autor vzhledu: Staon. Stránky jsou postaveny na redakčním systému RS2 (verze RC2).