Participez à ABC151 et résumez comme un examen qui n'a pas pu résoudre le problème D
Regardez le diagramme wiki parce qu'il est si facile à comprendre ...
Eh bien, je pensais qu'il y avait un arbre comme celui-ci
Parent A
├ Enfant AA
│ ├ Fils AAA
│ └ Fils AAB
├ Enfant AB
│ └ Fils ABA
└ Enfant AC
├ Fils ACA
├ Son ACB
└ Son ACC
https://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
Recherchez tous les nœuds enfants suspendus au nœud parent, puis recherchez tous les nœuds petits-enfants suspendus au nœud enfant recherché.
Résoudre à l'aide d'une file d'attente
L'ordre de recherche est Parent A → Enfant AA → Enfant AB → Enfant AC → Petit-enfant AAA → Petit-enfant AAB → Petit-enfant ABA → Petit-enfant ACA → Petit-enfant ACB → Petit-enfant ACC
La recherche de priorité de largeur consiste à rechercher dans l'ordre parent → enfant → petit-enfant
https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2
Allez aussi loin que possible du nœud parent, puis revenez en arrière et recherchez d'autres nœuds enfants.
Ceci est une pile, c'est premier entré, premier sorti
L'ordre de recherche est Parent A → Enfant AC → Petit-enfant ACC → Petit-enfant ACB → Petit-enfant ACA → Enfant AB → Petit-enfant ABA → Enfant AA → Petit-enfant AAA → Petit-enfant AAB
C'est une image de regarder la circonférence extérieure de l'arbre dans l'ordre, mais elle est transmise ...
J'ai écrit qu'il utilise une pile, mais si vous effectuez une recherche récursive, ce sera une recherche prioritaire en profondeur (ne pouvez-vous pas dire cela en général?)
https://atcoder.jp/contests/abc151/tasks/abc151_d
D - Maze Master
M. Takahashi a un labyrinthe composé de carrés H × W avec des carrés H verticaux et des carrés W horizontaux.
La cellule (i, j) dans la i-ème rangée à partir du haut et la j-ème colonne à partir de la gauche est le mur lorsque Sij est # '' et la route lorsque Sij est. ''.
À partir de la place de la route, vous pouvez vous déplacer vers la place de la route qui est adjacente en haut, en bas, à gauche et à droite.
Vous ne pouvez pas sortir du labyrinthe, vous déplacer vers un carré de mur ou vous déplacer en diagonale.
Takahashi décide librement du départ et du but depuis la place de la route et remet le labyrinthe à Aoki.
Aoki se déplace du début au but avec le nombre minimum de coups.
Quand Takahashi positionne correctement le départ et le but, combien de fois Aoki se déplacera-t-il au maximum?
1≤H,W≤20
Sij est .'` Ou # ''
S contient au moins deux ``. ''
Vous pouvez atteindre n'importe quelle place de route à partir de n'importe quelle place de route avec 0 mouvements ou plus
L'entrée est donnée à partir de l'entrée standard dans le format suivant.
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];
}
}
//Répondez à la plus longue distance à partir de tous les lieux
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);
}
/**
*Renvoie la plus longue distance dans la recherche de priorité de largeur
* @tableau de labyrinthe param ss
* @param startY Coordonnée Y du point de départ
* @param startX Coordonnée X du point de départ
* @retour la plus longue distance
*/
private static int getMaxDistanceWithBfs( String[][] ss , int startY , int startX ) {
int[][] distances = new int[ss.length][ss[0].length];
Queue<Integer> queue = new ArrayDeque<>();
//Définition des distances de tous côtés en haut à gauche en bas à droite
int[] dx = { -1 , 0 , 1 , 0 };
int[] dy = { 0 , 1 , 0 , -1 };
int maxDistance = 0;
//Ajouter la position de départ à la file d'attente
queue.add( startX );
queue.add( startY );
//Lorsque la file d'attente est vide=Quand il n'y a plus d'endroits à explorer
//Nombre de boucles=Distance par rapport à la position de départ
while( !queue.isEmpty() ) {
int x = queue.remove();
int y = queue.remove();
//Si l'emplacement actuel est un mur, ne traitez pas
if( "#".equals( ss[y][x] ) ){
continue;
}
maxDistance = Math.max( maxDistance , distances[y][x] );
//Vérifiez tous les côtés
for( int i = 0 ; i < 4 ; i++ ){
//Confirmation des coordonnées de destination
int xx = x + dx[i];
int yy = y + dy[i];
//Les coordonnées de destination de confirmation ne sont pas en dehors du tableau
if( !( 0 <= yy && yy < ss.length && 0 <= xx && xx < ss[0].length ) ) {
continue;
}
//Les coordonnées de destination de confirmation ne sont pas des murs
if( !".".equals( ss[yy][xx] ) ) {
continue;
}
//Pas la route que tu as déjà prise
if( distances[yy][xx] != 0 ){
continue;
}
//Pas le point de départ
if( xx == startX && yy == startY ){
continue;
}
queue.add( xx );
queue.add( yy );
distances[yy][xx] = distances[y][x] + 1;
}
}
return maxDistance;
}
}
Vérifiez tous les côtés des coordonnées extraites de la file d'attente et ajoutez-le à la file d'attente s'il s'agit d'un chemin À ce moment-là, stockez-le dans un endroit où vous pouvez dépasser la distance actuelle +1
Parce que j'ai écrit le tableau de jugement pour savoir s'il est passé ou non avec le tableau qui stocke la distance depuis le point de départ Je devais aussi voir si les coordonnées de destination de confirmation étaient le point de départ
3 5
#####
#..##
#####
Répondez 1 avec S22 comme point de départ et S23 comme point de but est la bonne réponse lorsque c'est le cas. Lorsque vous mesurez la distance depuis le point de départ,
#####
#0.##
#####
#####
#01##
#####
#####
#21##
#####
Ainsi, l'itinéraire le plus long est de revenir en arrière après avoir jugé que le point de départ (distance du point de départ: 0) n'est pas encore passé. Il semble qu'il y avait quelque chose de similaire à ce qui précède dans le jugement, donc quand j'ai décoché, c'est devenu WA correctement
Java a une classe de coordonnées appelée Point en standard, alors j'aurais peut-être dû l'utiliser Je n'en avais pas besoin car j'ai décidé d'en ajouter / supprimer 2 chacun dans l'ordre X → Y dans la file d'attente.
Le problème cette fois est que la taille du tableau bidimensionnel est jusqu'à 20 x 20 Même si j'ai vérifié tous les emplacements comme point de départ, il y avait une marge dans le temps d'exécution. Est-ce impossible s'il s'élargit? Souhaitez-vous utiliser le même calcul d'itinéraire? Sera-ce plus rapide que cette écriture?
J'ai regardé les réponses des autres Il semble que ce problème doit être balayé
Il serait peut-être préférable d'examiner d'autres problèmes en utilisant la recherche de priorité de largeur
Quand j'ai écrit cet article, je l'ai écrit comme ça au début https://atcoder.jp/contests/abc151/submissions/9485696
C'est le vôtre
System.arraycopy car nous devons préparer un tableau pour mesurer la distance de chaque coordonnée.Avant correction.java
//Passez une copie lorsque vous manipulez le tableau pendant la recherche
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 );
C'est pratique ...
Avant correction.java
int distance = getMaxDistanceWithBfs( copy , i , j );
if (maxDistance < distance) {
maxDistance = distance;
}
Avant correction.java
/**
*Classe de coordonnées
*/
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 ) );
Avant correction.java
return distance - 1;
Je déteste vraiment ce livre qui suit
À l'origine
En préparant un tableau pour stocker la distance de chaque coordonnée, la boucle de 2 n'est plus nécessaire.
La boucle 2 était nécessaire pour mesurer la distance, mais pour une raison quelconque, elle devait finalement être distance-1
Recommended Posts