Introduction aux algorithmes avec java-Search (recherche prioritaire en profondeur)

Résumé de l'article

Il s'agit d'une série d'articles que j'ai compilés dans mon étude et mon mémo. Ceci est une suite de cet article. Introduction aux algorithmes avec java-Search (recherche complète, recherche de bisection) Dans cet article

• Recherche de priorité en profondeur

Je vais étudier sur. Je l'ai écrit dans la suite de l'article précédent.

Recherche de priorité de profondeur

C'est comme ça à partir d'ici, mais allons-y. Tout en apprenant et en résumant. Recherche de priorité de profondeur. Il semble qu'il s'appelle également DFS (depth-first-search). Au fait, je vois souvent ce mot. La recherche de priorité de profondeur et la recherche de priorité de largeur semblent être utiles pour rechercher des arbres et des graphiques. Je vais omettre l'explication des arbres et des graphiques. La figure est illustrée ci-dessous. (De wikipedia) C'est comme DFS de rechercher les arbres dans cet ordre avec la priorité donnée à la profondeur.

Pour ceux qui disent: "Je ne sais pas quelle est la priorité sur la profondeur!", Je pense que c'est un coup si vous regardez l'ordre de recherche de la recherche de priorité de largeur.

Avez-vous vu la différence dans les nombres? Dans la recherche de priorité de profondeur, la recherche est effectuée en ligne droite de la racine au nœud n'ayant pas d'enfants, et dans la recherche de priorité de largeur, les nœuds avec une profondeur de 1 sont recherchés dans l'ordre à partir de la racine.

À propos, il existe deux types de méthodes de mise en œuvre.

• Comment utiliser la pile (structure de données dernier entré, premier sorti) --Comment utiliser la fonction récursive

... j'ai peur parce que c'est fou. Vous ne pouvez pas comprendre sans voir un exemple. Si vous recherchez un exemple simple, vous ne pouvez pas le trouver intuitivement. .. Comme le montre la figure ci-dessus, c'est juste un moyen de rechercher dans cet ordre! C'est comme ça? Je le comprendrai en regardant les exemples de problèmes et en les résolvant. Si vous pouvez le comprendre, vous pouvez peut-être faire un exemple simple?

Exemple: AtCoder --arc031-b "landfill"

\(A1,1\)\(A1,2\)...\(A1,10\)
\(A2,1\)\(A2,2\)...\(A2,10\)
:
\(A10,1\)\(A10,2\)...\(A10,10\)

J'ai étudié en regardant les sources d'autres personnes et divers blogs. La politique est la suivante. Peut-être que beaucoup de gens l'ont fait.

――Dans 10 * 10 terrains, recherchez une case qui «si vous remplissez cette case, vous pouvez transformer le tout en une seule île». ―― Comptez le nombre de carrés sur l'île par recherche de priorité de profondeur à partir du premier carré sélectionné. Si le nombre de carrés recherchés à ce moment est le carré de l'île reçu dans la première entrée + 1 carré (si la mer est récupérée), la condition est remplie.

[Exemple de réponse]

main.java

import java.util.Scanner;

public class Main {

	//Carte de l'île
	static char[][] islandMap;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		//Carte de l'île
		islandMap = new char[10][10];

		//Nombre de places sur l'île
		int countIsland = 0;

		//Sortie finale
		String ans = "NO";

		//Recevez des informations et complétez la carte de l'île, comptez le nombre de carrés de l'île
		for (int i = 0; i < 10; i++) {
			islandMap[i] = sc.next().toCharArray();
			for (int j = 0; j < 10; j++) {
				if (islandMap[i][j] == 'o') {
					countIsland++;
				}
			}
		}

		//Rechercher des carrés dans le carré supérieur gauche avec une double boucle
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {

				//Variable temporaire du nombre d'îles
				int countIslandInLoop = countIsland;

				//Dans le cas de la mer, faites-la atterrir. Augmentez également le nombre d'îles d'une unité
				if (islandMap[i][j] == 'x') {
					islandMap[i][j] = 'o';
					countIslandInLoop = countIsland + 1;
				}

				/*
				 *Effectuez une recherche de priorité de profondeur.
				 *dfsCountIsland ・ ・ ・ Le nombre d'îles terrestres comptées par dfs
				 *vérifié ・ ・ ・ Jugement si le carré a été fouillé par dfs
				 */
				dfsIslandCount = 0;
				boolean[][] checked = new boolean[10][10];

				dfs(i, j, checked);

				if (dfsIslandCount == countIslandInLoop) {
					ans = "YES";
					break;
				}

				//Remettez la place enfouie et passez à la boucle suivante
				if (countIslandInLoop == countIsland + 1) {
					islandMap[i][j] = 'x';
				}
			}
			if ("YES".equals(ans)) {
				break;
			}
		}

		System.out.println(ans);

	}

	//Nombre de carrés sur les îles terrestres actuellement comptés par le DFS
	static int dfsIslandCount;

	//Recherche de priorité de profondeur
	static void dfs(int i, int j, boolean[][] checked) {
		//S'il est au-delà du carré, a été fouillé ou s'il s'agit de la mer, changez de direction.
		if (i < 0 || i > 9 || j < 0 || j > 9 || checked[i][j] || islandMap[i][j] == 'x') {
			return;
		}

		//Si le carré que vous recherchez est un terrain, augmentez le nombre de terrains
		if (islandMap[i][j] == 'o') {
			dfsIslandCount++;
		}

		//Rechercher le carré actuel
		checked[i][j] = true;

		//Rechercher les carrés haut, bas, gauche et droite
		dfs(i + 1, j, checked);
		dfs(i - 1, j, checked);
		dfs(i, j + 1, checked);
		dfs(i, j - 1, checked);

		return;

	}
}

Non, c'était vraiment difficile. Il est très difficile de le mettre dans une variable globale ou comment répéter la recherche.

Cela n'a pas d'importance, mais AtCoder a préparé un exemple d'un tel algorithme. AtCoder --atc001-a "Recherche de priorité en profondeur"

Pour le moment, je l'ai utilisé comme code pour ce problème, alors regardons la partie dfs ci-dessus.

Je me demande si je peux voir environ 2 carrés. Tout d'abord, l'exemple d'entrée est le suivant:

xxxxxxxxxx
xoooooooxx
xxoooooxxx
xxxoooxxxx
xxxxoxxxxx
xxxxxxxxxx
xxxxoxxxxx
xxxoooxxxx
xxoooooxxx
xxxxxxxxxx

• × est la mer et ○ est l'île. La carte à ce moment ressemble à ce qui suit. (Eh bien, vous pouvez le dire à partir de la chaîne de caractères.)

Pensons au DFS pour le carré ① et au DFS pour le carré ②.

Dans la méthode dfs du code ci-dessus pour plus de clarté, Le premier processus est l'instruction if de "// Si elle dépasse le carré, a été recherchée, et si c'est la mer, changez de direction." Le deuxième processus est "// Si la cellule que vous recherchez est un terrain, le nombre de terrains est incrémenté", Le processus du n ° 3 est "// Faire le carré courant recherché", Le 4ème processus est le processus de "// Recherche de carrés en haut, en bas, à gauche et à droite". (J'expliquerai lequel est appelé à chaque fois.)

DFS en cas de ①

Suivons la source. J'expliquerai principalement comment déplacer la masse avec dfs.

Voici la figure dans laquelle le carré de ① a été rempli par le deuxième processus.

J'ai également ajouté les valeurs de i et j. Ensuite, c'est DFS. Après avoir recherché la cellule actuelle par le 3ème processus, passez au 4ème processus. La première chose à appeler dfs(i + 1, j, checked); est. i = 0, j = 0 dfs(1, 0, checked); n'est-ce pas. Avec cela, je suis passé au carré de i = 1, j = 0, mais comme la destination est la mer, je suis pris dans l'instruction if dans le premier processus. Sera retourné.

Ensuite, passez à la deuxième ligne du 4ème processus. dfs(i - 1, j, checked); Plus précisément dfs(-1, 0, checked); n'est-ce pas. Il se déplace vers le carré de i = -1, j = 0 (en dehors de la carte) et est renvoyé dans le premier processus.

Il en va de même pour les 3e et 4e lignes. Ceci termine la recherche de la cellule ①. C'est difficile à comprendre car ce n'est pas encore récursif. Cependant, je pense qu'il serait bon de penser à partir d'un exemple aussi simple à comprendre.

DFS en cas de ②

Voici un exemple de réponse. Soyons enthousiastes et DFS. Voici un diagramme de la décharge avec les nombres i et j.

Après le premier appel, la partie rouge est appelée, les mouvements sont programmés en retrait et écrits dans l'ordre. Avec l'indentation, cela ressemble à une récurrence. Nous commencerons par le quatrième processus du premier appel dfs. ** Allons-y tous! !! ** ** Actuellement (i, j) = (5,4). L'ordre dans lequel ils sont appelés, y compris récursifs, est le suivant:

1. dfs(6, 4, checked);
2. dfs(7, 4, checked);
3. dfs(8, 4, checked);
4. dfs (9, 4, vérifié); ← Parce que c'est la mer, ça finit
5. dfs (7, 4, vérifié); ← Terminé car il a été recherché sur la 02ème ligne
6. dfs(8, 5, checked);
7. dfs (9, 5, vérifié); ← Parce que c'est la mer, ça finit
8. dfs(7, 5, checked);
9. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥ dix. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
10. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
11. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
12. dfs(8, 6, checked);
13. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
14. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
15. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
16. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
17. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
18. dfs(8, 3, checked);
19. dfs (9, 3, vérifié); ← Parce que c'est la mer, ça finit
20. dfs(7, 3, checked);
21. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
22. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
23. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
24. dfs (7, 2, vérifié); ← Parce que c'est la mer, ça finit
25. dfs(8, 2, checked);
26. dfs (9, 2, vérifié); ← Parce que c'est la mer, ça finit
27. dfs (7, 2, vérifié); ← Parce que c'est la mer, ça finit
28. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
29. dfs (8, 1, vérifié); ← Parce que c'est la mer, ça finit
30. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
31. dfs (6, 4, vérifié); ← Terminé car il a été recherché sur la 01e ligne
32. dfs (7, 5, vérifié); ← Terminé car il a été recherché sur la 08ème ligne
33. dfs (7, 3, vérifié); ← Terminé car il a été recherché sur la 21e ligne
34. dfs (5, 4, vérifié); ← Fin car il a été recherché en premier
35. dfs (6, 5, vérifié); ← Parce que c'est la mer, ça finit
36. dfs (6, 3, vérifié); ← Parce que c'est la mer, ça finit
37. dfs(4, 4, checked);
38. dfs (5, 4, vérifié); ← Fin car il a été recherché en premier
39. dfs(3, 4, checked);
40. dfs (4, 4, vérifié); ← Terminé car il a été recherché sur la 38ème ligne
41. dfs(2, 4, checked);
42. dfs (3, 4, vérifié); ← Terminé car il a été recherché sur la 40e ligne
43. dfs(1, 4, checked);
44. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
45. dfs (0, 4, vérifié); ← Parce que c'est la mer, ça finit
46. dfs(1, 5, checked);
47. dfs(2, 5, checked);
48. dfs(3, 5, checked);
49. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
50. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
51. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
52. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
53. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
54. dfs(2, 6, checked);
55. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
56. dfs(1, 6, checked);
57. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
58. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
59. dfs(1, 7, checked);
60. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
61. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
62. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
63. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
64. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
65. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
66. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
67. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
68. dfs (0, 5, vérifié); ← Parce que c'est la mer, ça finit
69. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
70. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
71. dfs(1, 3, checked);
72. dfs(2, 3, checked);
73. dfs(3, 3, checked);
74. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
75. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
76. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
77. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
78. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
79. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
80. dfs(2, 2, checked);
81. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
82. dfs(1, 2, checked);
83. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
84. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
85. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
86. dfs(1, 1, checked);
87. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
88. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
89. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
90. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
91. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
92. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
93. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
94. ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
95. ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
96. dfs (2, 5, vérifié); ← Terminé car il a été recherché sur la 42ème ligne
97. dfs (2, 3, vérifié); ← Terminé car il a été recherché sur la 74e ligne
98. dfs (3, 5, vérifié); ← Terminé car la recherche a été effectuée sur la 50e ligne
99. dfs (3, 3, vérifié); ← Terminé car il a été recherché sur la 75e ligne
100. dfs (4, 5, vérifié); ← Parce que c'est la mer, ça finit
101. dfs (4, 3, vérifié); ← Parce que c'est la mer, ça finit
102. dfs (5, 5, vérifié); ← Parce que c'est la mer, ça finit
103. dfs (5, 3, vérifié); ← Parce que c'est la mer, ça finit

** Oh ... c'est fini ... ** Je suis super fatigué. Ce n'était pas quelque chose que les gens feraient à la main. Eh bien, je l'ai tellement fait, alors vérifions quel type de mouvement était recherché. J'ai essayé d'exprimer l'ordre de recherche en lettres blanches.

Vous pouvez le voir en regardant la figure, et vous pouvez le voir en regardant la sensation de boucle, mais DFS est comme "Si vous ne pouvez pas aller au point, vous changerez de direction."

Je pense aussi que le mot «pile» est sorti, mais on a l'impression que cette méthode récursive est exactement dans l'ordre des piles du premier entré, dernier sorti. Même si vous n'utilisez pas la structure de données appelée stack, vous pouvez voir que si vous écrivez l'implémentation de manière récursive, elle sera traitée comme une pile.

Avez-vous compris la recherche de priorité de profondeur? Je pourrais comprendre un peu. (Oh, je suis fatigué ...)

Cela fait longtemps, donc je reparlerai de la recherche de priorité de largeur la prochaine fois. La prochaine fois, nous attendons avec impatience! !!