Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m33pal:uloha1-2010 [2010/09/29 00:25]
redtop created
+++ courses:a4m33pal:uloha1-2010 [2025/01/03 18:28] (aktuální)
@@ Řádek 3: / Řádek 3: @@
 Make
-[[http://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4m33pal/cviceni/uloha1_make_popis.pdf|Provizorní zadání]]
+[[http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=make|Zadání]]
+Limit: 15s
+Jak na to:
+  * vytvořit z cílů a podcílů graf
+  * projít graf do hloubky a pro každý uzel si pamatuji stav (FRESH, OPEN, CLOSED)
+  * pokud při procházení narazím na OPEN uzel, vypsat chybu
+  * pokud při procházení narazím na CLOSED uzel, nevypisovat příkazy (vznikla by duplicita)
+  * rychlejší by měla být nerekurzivní varianta, ale dá se to v Javě stihnout i s rekurzí
+Jedná se v podstatě o topologické uspořádání grafu.
+<code java>
+package pal;
+import java.io.BufferedReader;
+import java.io.InputStreamReader;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.StringTokenizer;
+public class Main {
+    public static void main(String[] args) throws Exception {
+        BufferedReader br = new BufferedReader(new InputStreamReader(System.in, "cp1250"));
+        HashMap<String, Uloha> ulohy = new HashMap<String, Uloha>();
+        Uloha uloha = null;
+        boolean zacatek = true;
+        Uloha prvni = null;
+        String vz = br.readLine();
+        while (vz != null) {
+            if (vz.charAt(0) == '\t') {
+                uloha.prikazy.append(vz.substring(1));
+                uloha.prikazy.append("\n");
+            } else {
+                StringTokenizer st = new StringTokenizer(vz, " :");
+                String nazev = st.nextToken();
+                if (ulohy.containsKey(nazev)) {
+                    uloha = ulohy.get(nazev);
+                } else {
+                    uloha = new Uloha();
+                    if (zacatek) {
+                        prvni = uloha;
+                        zacatek = false;
+                    }
+                    ulohy.put(nazev, uloha);
+                }
+                while (st.hasMoreTokens()) {
+                    nazev = st.nextToken();
+                    if (!ulohy.containsKey(nazev)) {
+                        ulohy.put(nazev, new Uloha());
+                    }
+                    uloha.pridej(ulohy.get(nazev));
+                }
+            }
+            vz = br.readLine();
+        }
+        StringBuilder out = new StringBuilder();
+        prvni.vypis(out);
+        System.out.print(out);
+    }
+}
+class Uloha {
+    boolean vypsana = false;
+    boolean navstivena = false;
+    List<Uloha> podulohy = new ArrayList<Uloha>();
+    StringBuilder prikazy = new StringBuilder();
+    void pridej(Uloha poduloha) {
+        podulohy.add(poduloha);
+    }
+    void vypis(StringBuilder out) {
+        if (!vypsana) {
+            if (navstivena) {
+                System.out.println("ERROR");
+                System.exit(0);
+            }
+            navstivena = true;
+            for (Uloha uloha : podulohy) {
+                uloha.vypis(out);
+            }
+            out.append(prikazy);
+            vypsana = true;
+        }
+    }
+}
+</code>
 ~~DISCUSSION~~

courses/a4m33pal/uloha1-2010.1285712719.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru