Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- graphen:breitensuche:lee:start [2023/10/23 07:25] – Martin Pabst
+++ graphen:breitensuche:lee:start [2023/10/23 09:24] (aktuell) – Martin Pabst
@@ Zeile 8: / Zeile 8: @@
 {{ :graphen:breitensuche:lee:pasted:20231023-092529.png?500 }}
+Jetzt muss die Biene nur noch in absteigender Reihenfolge den Zahlen folgen um zum Diamanten zu finden.
+<WRAP center round tip 80%>
+Haben Sie gestutzt, als Sie gelesen haben, dass wir die Breitensuche beim Diamanten und nicht bei der Biene beginnen? Welches Problem würde entstehen, wenn wir bei der Biene beginnen?
+</WRAP>
+<HTML>
+<div class="java-online" style="height: 60vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'Lee1'}">
+<script type="text/plain" title="Level.java">
+new World(1600, 640);
+new Level();
+class Level extends Actor {
+   Block[][] felder;
+   Figur biene;
+   Figur diamant;
+   int spaltenAnzahl;
+   int zeilenAnzahl;
+   int t = 0;
+   Level() {
+      levelAufbauen();
+      diamant = new Figur(23, 1, 186);
+      biene = new Figur(5, 3, 264);
+      felderBewerten();
+   }
+   /**
+    * Die Methode felderBewerten() wird vom Programm zu Beginn aufgerufen. Sie soll
+    * via felder[spalte][zeile].setEntfernung(int e) in jedem Feld die Entfernung
+    * zum Diamanten speichern.
+    *    *
+    * istWand(spalte, zeile) gibt genau dann true zurück, wenn das Feld an der Position eine Wand ist.
+    * biene.geheZu(spalte, zeile) verschiebt die Biene an die angegebene Position
+    * biene.spalte, biene.zeile, diamant.spalte und diamant.zeile geben Ihnen die Positionen von Biene/Diamant
+    * felder[spalte][zeile].setEntfernung(int e) können Sie benutzen, um jedem Feld einen Wert zuzuweisen.
+    *
+    */
+   void felderBewerten() {
+      for (int spalte = 0; spalte < spaltenAnzahl; spalte++) {
+         for (int zeile = 0; zeile < zeilenAnzahl; zeile++) {
+            felder[spalte][zeile].setEntfernung(-1);  // -1 bedeutet: noch nicht besucht
+         }
+      }
+      // Breitensuche vom Feld des Diamanten aus
+      LinkedList<Block> warteschlange = new LinkedList<Block>();
+      Block aktuellesFeld = felder[diamant.spalte][diamant.zeile];
+      warteschlange.addLast(felder[diamant.spalte][diamant.zeile]);
+      aktuellesFeld.setEntfernung(0);
+      while (!warteschlange.isEmpty()) {
+         aktuellesFeld = warteschlange.removeFirst();
+         int aktuelleEntfernung = aktuellesFeld.getEntfernung();
+         // linkes Nachbarfeld:
+         if(aktuellesFeld.spalte > 1) {
+            Block linkerNachbar = felder[aktuellesFeld.spalte - 1][aktuellesFeld.zeile];
+            if(!linkerNachbar.istWand() && linkerNachbar.getEntfernung() < 0) {
+               linkerNachbar.setEntfernung(aktuelleEntfernung + 1);
+               warteschlange.addLast(linkerNachbar);
+            }
+         }
+         // rechtes Nachbarfeld:
+         if(aktuellesFeld.spalte < spaltenAnzahl - 1) {
+            Block rechterNachbar = felder[aktuellesFeld.spalte + 1][aktuellesFeld.zeile];
+            if(!rechterNachbar.istWand() && rechterNachbar.getEntfernung() < 0) {
+               rechterNachbar.setEntfernung(aktuelleEntfernung + 1);
+               warteschlange.addLast(rechterNachbar);
+            }
+         }
+         // oberes Nachbarfeld:
+         if(aktuellesFeld.zeile > 1) {
+            Block obererNachbar = felder[aktuellesFeld.spalte][aktuellesFeld.zeile - 1];
+            if(!obererNachbar.istWand() && obererNachbar.getEntfernung() < 0) {
+               obererNachbar.setEntfernung(aktuelleEntfernung + 1);
+               warteschlange.addLast(obererNachbar);
+            }
+         }
+         // unteres Nachbarfeld:
+         if(aktuellesFeld.zeile < zeilenAnzahl - 1) {
+            Block linkerNachbar = felder[aktuellesFeld.spalte][aktuellesFeld.zeile + 1];
+            if(!linkerNachbar.istWand() && linkerNachbar.getEntfernung() < 0) {
+               linkerNachbar.setEntfernung(aktuelleEntfernung + 1);
+               warteschlange.addLast(linkerNachbar);
+            }
+         }
+      }
+   }
+   void schritt() {
+      if(biene.spalte == diamant.spalte && biene.zeile == diamant.zeile) {
+         return; // Die Biene hat den Diamanten bereits erreicht => nichts mehr zu tun
+      }
+      // Bei allen Feldern ist jetzt der Abstand zum Diamanten hinterlegt. Wir suchen jetzt ein
+      // Nachbarfeld der Biene, das einen um eins geringeren Abstand hat als das Feld der Biene.
+      Block bienenfeld = felder[biene.spalte][biene.zeile];
+      int bienenAbstand = bienenfeld.getEntfernung();
+      if(felder[bienenfeld.spalte - 1][bienenfeld.zeile].getEntfernung() == bienenAbstand - 1) {
+         biene.geheZu(biene.spalte - 1, biene.zeile);
+      } else
+      if(felder[bienenfeld.spalte + 1][bienenfeld.zeile].getEntfernung() == bienenAbstand - 1) {
+         biene.geheZu(biene.spalte + 1, biene.zeile);
+      } else
+      if(felder[bienenfeld.spalte][bienenfeld.zeile - 1].getEntfernung() == bienenAbstand - 1) {
+         biene.geheZu(biene.spalte, biene.zeile - 1);
+      } else
+      if(felder[bienenfeld.spalte][bienenfeld.zeile + 1].getEntfernung() == bienenAbstand - 1) {
+         biene.geheZu(biene.spalte, biene.zeile + 1);
+      }
+   }
+   public void act() {
+      t++;
+      if(t == 30) {
+         t = 0;
+         schritt();
+      }
+   }
+   boolean istWand(int spalte, int zeile) {
+      return felder[spalte][zeile].istWand();
+   }
+   void levelAufbauen() {
+      String level = """
+      wwwwwwwwwwwwwwwwwwwwwwwww
+      w            w          w
+      w     w      w  wwwwwwwww
+      w     w      w          w
+      wwwwwww   wwwwwwwwwwww  w
+      w                  w    w
+      w            w     w    w
+      w            w          w
+      wwwwwwwwwwwwwwwwwwwwwwwww
+      """;
+      String[] lines = level.split("\n");
+      zeilenAnzahl = lines.length;
+      spaltenAnzahl = lines[0].length();
+      felder = new Block[spaltenAnzahl][zeilenAnzahl];
+      for (int zeile = 0; zeile < zeilenAnzahl; zeile++) {
+         String line = lines[zeile];
+         for (int spalte = 0; spalte < spaltenAnzahl; spalte++) {
+            char buchstabe = line.charAt(spalte);
+            felder[spalte][zeile] = new Block(spalte, zeile, buchstabe);
+         }
+      }
+   }
+}
+</script>
+<script type="text/plain" title="Block.java">
+class Block extends Sprite {
+   String art; // "w" bedeutet Wand, "b" bedeutet Boden
+   private int entfernung;
+   private Text entfernungsText;
+   int spalte;
+   int zeile;
+   public Block(int spalte, int zeile, String art) {
+      super(32 + 64 * spalte, 32 + 64 * zeile, SpriteLibrary.Plattforms, 4);
+      this.art = art;
+      this.spalte = spalte;
+      this.zeile = zeile;
+      if(art == "w") {
+         this.setImageIndex(48);
+      }
+      this.entfernungsText = new Text(16 + 64 * spalte, 16 + 64 * zeile, 32, "");
+      this.entfernungsText.setFillColor(Color.black);
+   }
+   public boolean istWand() {
+      return art == "w";
+   }
+   void setEntfernung(int entfernung) {
+      this.entfernung = entfernung;
+      this.entfernungsText.setText(entfernung);
+   }
+   int getEntfernung() {
+      return entfernung;
+   }
+}
+</script>
+<script type="text/plain" title="Figur.java">
+class Figur extends Sprite {
+   int spalte;
+   int zeile;
+   public Figur(int spalte, int zeile, int spriteIndex) {
+      super(32 + 64 * spalte, 32 + 64 * zeile, SpriteLibrary.Plattforms, spriteIndex);
+      this.spalte = spalte;
+      this.zeile = zeile;
+   }
+   public void geheZu(int spalte, int zeile) {
+      moveTo(32 + 64 * spalte, 32 + 64 * zeile);
+      this.spalte = spalte;
+      this.zeile = zeile;
+   }
+}
+</script>
+</div>
+</HTML>