Dies ist eine Reihe von Artikeln, die ich in meiner Studie und meinem Memo zusammengestellt habe. Der dritte. Dies ist eine Fortsetzung dieses Artikels. Einführung in Algorithmen mit Java-Suche (Tiefenprioritätssuche) In diesem Artikel
Ich werde darüber lernen.
Es wird auch BFS (Breitensuche) genannt. (Breite: Breite) Ich werde das während des Studiums schreiben. Den Unterschied zur Suche mit Tiefenpriorität, die wie ein Baum aussieht, finden Sie in diesem Artikel "Einführung in Algorithmen mit Java-Suche (Tiefenprioritätssuche)" Bitte gib mir.
Es scheint effektiv zu sein, wenn es darum geht, den kürzesten Weg eines Labyrinths zu finden.
Es scheint, dass eine Datenstruktur, die als Warteschlange bezeichnet wird, als Implementierungsmethode verwendet wird. Ausführliche Prioritätssuche, Stapel "first in, last out", Denken Sie daran, die Warteschlange "first in, first out" für die Suche nach der Breite zuerst zu verwenden.
Die Suche nach Tiefenpriorität könnte auch rekursiv implementiert werden, aber es scheint unmöglich oder schwierig zu sein, sie in der Reihenfolge der Warteschlange zu verarbeiten, wenn sie rekursiv ist. Verwenden Sie die Warteschlange? .. Ich möchte mich zu Beginn meines Studiums nicht an neue Bibliotheken oder Typen erinnern. .. .. Ich habe nicht das Gefühl, dass ich es sofort benutzen kann. ..
Übrigens werden Stapel und Hinweise in der Prüfung zum Basisinformationsingenieur angezeigt, daher denke ich, dass es in Ordnung ist, aber ich weiß es nicht! Für diejenigen, die sagen, dieser Artikel "Extreme Stapel und Warteschlangen! ~ Besonderheit bei Ideen und Verwendungen ~" scheint leicht zu verstehen, also studieren Sie ihn. Machen wir das.
Derzeit ist das Beispiel leicht zu verstehen Letztes Mal Ich dachte, ich würde versuchen, arc031-b in DFS zu implementieren, aber es passt möglicherweise nicht zu BFS. Also werde ich ein anderes Beispiel versuchen.
Beispiel: AtCoder --agc033-a "Darker and Darker"
(Abschnittsstart) 【Problemstellung】 Es werden schwarze und weiße Quadrate mit vertikalen H-Zeilen und horizontalen W-Spalten angegeben. Der Zustand der Quadrate wird durch HW-Zeichen von A11 bis AHW dargestellt. Wenn die Quadrate in der i-ten Zeile von oben und der j-ten Spalte von links schwarz sind, ist Aij #, die i-te Zeile von oben und j von links. Aij ist. Wenn die Zellen in der Spalte weiß sind.
Wiederholen Sie die folgenden Vorgänge, bis alle Zellen schwarz sind. Alle weißen Zellen, die sich eine Seite teilen und eine oder mehrere schwarze Zellen in benachbarten Zellen haben, werden schwarz. Finden Sie heraus, wie viele Operationen Sie ausführen werden. Es gibt jedoch mindestens eine schwarze Zelle in der ersten gegebenen Zelle.
[Beschränkungen] 1≦H,W≦1000 Aij ist # oder .. In der angegebenen Zelle befindet sich mindestens eine schwarze Zelle.
【Eingang】 Die Eingabe erfolgt über die Standardeingabe im folgenden Format.
H W
A11 A12 ... A1W
:
AH1 AH2 ... AHW
【Ausgabe】 Geben Sie die Anzahl der ausgeführten Operationen aus.
(Ende des Abschnitts)
[Antwortbeispiel]
main.java
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// height
int h = sc.nextInt();
// width
int w = sc.nextInt();
//Zustand der Quadrate
char[][] masu = new char[h][w];
//Bereiten Sie die BFS-Warteschlange vor
Deque<XY> q = new ArrayDeque<>();
//Eingaben empfangen& '#'EnQueue
for (int i = 0; i < h; i++) {
masu[i] = sc.next().toCharArray();
for (int j = 0; j < w; j++) {
if ('#' == masu[i][j]) {
q.add(new XY(i, j, 0));
}
}
}
// ans
int max_depth = 0;
//BFS-Hauptverarbeitung
for (;;) {
//Endlosschleifenstart
//Ausgangsbedingungen
if (q.size() < 1) {
break;
}
//Warteschlange zur Warteschlange
//Abfragemethode wird aus der Warteschlange abgerufen&Aus der Warteschlange entfernen
XY xy = q.poll();
int x = xy.x;
int y = xy.y;
int depth = xy.depth;
//Notieren Sie die Anzahl der Operationen
if (depth >= max_depth) {
max_depth = depth;
}
//Machen Sie den Bereich um die aktuelle Position schwarz
if (x + 1 < w && masu[y][x + 1] == '.') {
//Rechtes Quadrat
masu[y][x + 1] = '#';
q.add(new XY(y, x + 1, depth + 1));
}
if (x - 1 >= 0 && masu[y][x - 1] == '.') {
//Linkes Quadrat
masu[y][x - 1] = '#';
q.add(new XY(y, x - 1, depth + 1));
}
if (y + 1 < h && masu[y + 1][x] == '.') {
//Unteres Quadrat
masu[y + 1][x] = '#';
q.add(new XY(y + 1, x, depth + 1));
}
if (y - 1 >= 0 && masu[y - 1][x] == '.') {
//Oberes Quadrat
masu[y - 1][x] = '#';
q.add(new XY(y - 1, x, depth + 1));
}
}
System.out.println(max_depth);
}
}
class XY {
int y;
int x;
int depth;
XY(int y, int x, int d) {
this.x = x;
this.y = y;
depth = d;
}
}
Es ist so. Die Richtlinie lautet wie folgt.
In dieser Reihenfolge sind die Tiefen immer 0, 1, 2 ... und sie treten der Reihe nach in die Warteschlange ein. Die Tiefe, in der es schwarz wird, ist also die Mindesttiefe des Quadrats. Sobald es schwarz wird, ist es in Ordnung Dafür bin ich dankbar.
Handelt es sich übrigens um eine Variante der Suche nach Breitenpriorität, oder wird sie als BFS-Typ mit mehreren Startpunkten klassifiziert? Es scheint getan zu sein.
Ich habe gelernt, wie man Warteschlangen anstelle der Suche nach Breitenprioritäten verwendet. Lol Ich glaube, ich verwende häufig die Umfragemethode von Deque, deshalb möchte ich mich definitiv daran erinnern.
Ich möchte die Bewegung auch dieses Mal visuell sehen, wenn ich sie mit der Suche nach Breitenpriorität implementiere, aber da ich aus dem vorherigen Artikel gelernt habe (ich dachte, dass Sie sie verstehen können, w), werde ich aufhören. ** Ich habe Kommentare im Code auf leicht verständliche Weise geschrieben. Bitte folgen Sie ihnen. ** ** **
Wenn dies vorerst geschrieben wird, scheint es, dass die Anwendung funktionieren wird. Der Rest ist eine Problemübung. Nachdem Sie die Theorie gelernt haben, üben Sie sie wiederholt und lassen Sie sich nieder. Ich möchte mit den Zahlen Schritt halten.
Das ist alles für diese Zeit. Nächstes Mal werde ich auf die vollständige Suche eingehen. freue mich auf!
Recommended Posts