Nehmen Sie an ABC151 teil und fassen Sie es als Bewertung zusammen, die das D-Problem nicht lösen konnte
Schauen Sie sich das Wiki-Diagramm an, weil es so einfach zu verstehen ist ...
Nun, ich dachte, es gibt so einen Baum
Elternteil A.
├ Kind AA
AA ├ Sohn AAA
A └ Sohn AAB
├ Kind AB
A └ Sohn ABA
└ Kind AC
├ Sohn ACA
├ Sohn ACB
└ Sohn ACC
https://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
Suchen Sie nach allen untergeordneten Knoten, die am übergeordneten Knoten hängen, und suchen Sie dann nach allen Enkelknoten, die am durchsuchten untergeordneten Knoten hängen.
Lösen Sie mit einer Warteschlange
Die Reihenfolge der Suche ist Elternteil A → Kind AA → Kind AB → Kind AC → Enkel AAA → Enkel AAB → Enkel ABA → Enkel ACA → Enkel ACB → Enkel ACC
Bei der Suche nach Breitenpriorität wird in der Reihenfolge Eltern → Kind → Enkel gesucht
https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
Gehen Sie so weit wie möglich vom übergeordneten Knoten weg und suchen Sie dann nach anderen untergeordneten Knoten.
Dies ist ein Stapel, dies ist First-In-First-Out
Die Reihenfolge der Suche ist Elternteil A → Kind AC → Enkel ACC → Enkel ACB → Enkel ACA → Kind AB → Enkel ABA → Kind AA → Enkel AAA → Enkel AAB
Es ist ein Bild, wie man den Außenumfang des Baumes der Reihe nach betrachtet, aber es wird übertragen ...
Ich habe geschrieben, dass es einen Stapel verwendet, aber wenn Sie rekursiv suchen, wird es eine Suche mit Tiefenpriorität sein (können Sie das nicht sagen?)
https://atcoder.jp/contests/abc151/tasks/abc151_d
D - Maze Master
Herr Takahashi hat ein Labyrinth, das aus H × W-Quadraten mit vertikalen H-Quadraten und horizontalen W-Quadraten besteht. Die Zelle (i, j) in der i-ten Reihe von oben und der j-ten Spalte von links ist die Wand, wenn Sij "#" ist, und die Straße, wenn Sij "" ist. ". Vom Straßenplatz aus können Sie zum Straßenplatz wechseln, der oben, unten, links und rechts angrenzt. Sie können sich nicht aus dem Labyrinth herausbewegen, sich nicht zu einem Wandquadrat bewegen oder sich diagonal bewegen. Takahashi entscheidet frei über Start und Ziel vom Platz der Straße und übergibt das Labyrinth an Aoki. Aoki bewegt sich vom Start zum Ziel mit der minimalen Anzahl von Zügen. Wenn Takahashi Start und Ziel richtig positioniert, wie oft bewegt sich Aoki maximal?
1≤H,W≤20 Sij ist "." Oder "#" S enthält zwei oder mehr "." Sie können jeden Straßenplatz von jedem Straßenplatz mit 0 oder mehr Bewegungen erreichen
Die Eingabe erfolgt über die Standardeingabe im folgenden Format.
H W
S11...S1W
:
SH1...SHW
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] params = in.nextLine().split(" ");
int h = Integer.parseInt(params[0]);
int w = Integer.parseInt(params[1]);
String[][] ss = new String[h][w];
for (int i = 0; i < h; i++) {
params = in.nextLine().split("");
for (int j = 0; j < w; j++) {
ss[i][j] = params[j];
}
}
//Beantworten Sie die längste Entfernung ab allen Standorten
int maxDistance = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
maxDistance = Math.max( maxDistance , getMaxDistanceWithBfs( ss , i , j ) );
}
}
System.out.println(maxDistance);
}
/**
*Gibt die längste Entfernung bei der Suche nach Breitenpriorität zurück
* @param ss Labyrinth-Array
* @param startY Y-Koordinate des Startpunkts
* @param startX X-Koordinate des Startpunkts
* @längste Strecke zurück
*/
private static int getMaxDistanceWithBfs( String[][] ss , int startY , int startX ) {
int[][] distances = new int[ss.length][ss[0].length];
Queue<Integer> queue = new ArrayDeque<>();
//Abstandsdefinition allseitig Oben links unten rechts
int[] dx = { -1 , 0 , 1 , 0 };
int[] dy = { 0 , 1 , 0 , -1 };
int maxDistance = 0;
//Fügen Sie die Startposition zur Warteschlange hinzu
queue.add( startX );
queue.add( startY );
//Wenn die Warteschlange leer ist=Wenn es keine Orte mehr zu erkunden gibt
//Anzahl der Schleifen=Abstand von der Startposition
while( !queue.isEmpty() ) {
int x = queue.remove();
int y = queue.remove();
//Wenn der aktuelle Standort eine Wand ist, nicht verarbeiten
if( "#".equals( ss[y][x] ) ){
continue;
}
maxDistance = Math.max( maxDistance , distances[y][x] );
//Überprüfen Sie alle Seiten
for( int i = 0 ; i < 4 ; i++ ){
//Bestätigungszielkoordinaten
int xx = x + dx[i];
int yy = y + dy[i];
//Die Bestätigungszielkoordinaten liegen nicht außerhalb des Arrays
if( !( 0 <= yy && yy < ss.length && 0 <= xx && xx < ss[0].length ) ) {
continue;
}
//Die Bestätigungszielkoordinaten sind keine Wände
if( !".".equals( ss[yy][xx] ) ) {
continue;
}
//Nicht die Straße, die Sie bereits genommen haben
if( distances[yy][xx] != 0 ){
continue;
}
//Nicht der Ausgangspunkt
if( xx == startX && yy == startY ){
continue;
}
queue.add( xx );
queue.add( yy );
distances[yy][xx] = distances[y][x] + 1;
}
}
return maxDistance;
}
}
Überprüfen Sie alle Seiten anhand der aus der Warteschlange entnommenen Koordinaten und fügen Sie sie der Warteschlange hinzu, wenn dies ein guter Weg ist Bewahren Sie es zu diesem Zeitpunkt an einem Ort auf, an dem Sie die aktuelle Entfernung +1 überschreiten können
Weil ich das Beurteilungsarray geschrieben habe, ob es zusammen mit dem Array übergeben wurde, das den Abstand vom Startpunkt speichert Es war auch notwendig zu sehen, ob die Bestätigungszielkoordinaten der Ausgangspunkt waren
3 5
#####
#..##
#####
Bei einer solchen Eingabe ist Antwort 1 mit S22 als Startpunkt und S23 als Zielpunkt die richtige Antwort. Wenn Sie den Abstand vom Startpunkt messen,
#####
#0.##
#####
#####
#01##
#####
#####
#21##
#####
Auf diese Weise führt die längste Route zurück, nachdem festgestellt wurde, dass der Startpunkt (Entfernung vom Startpunkt: 0) noch nicht überschritten wurde. Es scheint, dass das Urteil etwas Ähnliches wie das oben Gesagte enthielt. Als ich es deaktivierte, wurde es zu WA
Java hat standardmäßig eine Koordinatenklasse namens Point. Vielleicht hätte ich das verwenden sollen Ich brauchte es nicht, weil ich beschlossen habe, jeweils 2 in der Reihenfolge X → Y zur Warteschlange hinzuzufügen / zu entfernen.
Das Problem ist diesmal, dass die Größe des zweidimensionalen Arrays bis zu 20 x 20 beträgt Selbst wenn ich alle Standorte als Ausgangspunkt überprüft habe, gab es einen Spielraum in der Ausführungszeit. Ist es unmöglich, wenn es breiter wird? Möchten Sie dieselbe Routenberechnung verwenden? Wird es schneller sein als dieses Schreiben?
Ich habe mich in den Antworten anderer Leute umgesehen Es scheint, dass dieses Problem beseitigt werden muss
Es ist möglicherweise besser, andere Probleme mithilfe der Suche nach Breitenpriorität zu betrachten
Als ich diesen Artikel schrieb, schrieb ich ihn zuerst so https://atcoder.jp/contests/abc151/submissions/9485696
Es ist dein eigenes
Vor der Korrektur.java
//Übergeben Sie eine Kopie, während Sie das Array während der Suche bearbeiten
for( int k = 0 ; k < h ; k++ ){
copy[k] = new String[w];
System.arraycopy( ss[k] , 0 , copy[k] , 0 , w );
}
int distance = getMaxDistanceWithBfs( copy , i , j );
Es ist bequem ...
Vor der Korrektur.java
int distance = getMaxDistanceWithBfs( copy , i , j );
if (maxDistance < distance) {
maxDistance = distance;
}
Vor der Korrektur.java
/**
*Klasse koordinieren
*/
public static class Position {
int x;
int y;
public Position( int x , int y ) {
this.x = x;
this.y = y;
}
}
Queue<Position> queue = new ArrayDeque<>();
queue.add( new Position( startX , startY ) );
Vor der Korrektur.java
return distance - 1;
Ich hasse es wirklich wie dieses Buchschwanz-Matching
Ursprünglich
Durch die Vorbereitung eines Arrays zum Speichern des Abstands jeder Koordinate ist die Schleife von 2 nicht mehr erforderlich. Schleife 2 wurde benötigt, um die Entfernung zu messen, aber aus irgendeinem Grund musste sie schließlich "Entfernung 1" sein
Recommended Posts