Cet article explore l'algorithme de recherche de mots dans une grille bidimensionnelle en utilisant une approche de parcours en profondeur (DFS). L'accent est mis sur la nécessité d'un mécanisme de marquage des cellules visitées et de restauration de ces marques (backtracking) pour garantir l'exactitude des résultats.

Problématique

Étant donné une grille de caractères de dimensions m x n et une chaîne de caractères word, le but est de déterminer s'il existe un chemin dans la grille permettant de former la chaîne word. Les règles stipulent que les déplacements ne sont autorisés qu'horizontalement ou verticalement (haut, bas, gauche, droite) et qu'une même cellulle ne peut être utilisée qu'une seule fois au sein d'un même chemin.

Approche Fondamentale : DFS Itératif depuis Chaque Cellule

L'essence du problème réside dans une exploration par backtracking sur la grille. Pour chaque cellule (r, c) et chaque caractère word[idx] à faire correspondre :

1. Vérifier si les coordonnées sont hors limites ou si le caractère de la cellule ne correspond pas à word[idx]. Si c'est le cas, retourner False.
2. Si idx atteint la fin de word et que le caractère correspond, retourner True.
3. Marquer la cellule courante comme "visitée". Initier une exploration DFS dans les quatre directions adjacentes pour le caractère suivant (idx + 1).
4. Effectuer le "backtracking" : annuler le marquage de la cellule courante pour permettre son utilisation dans d'autres chemins potentiels.

Une technique courante pour économiser de l'espace supplémentaire consiste à modifier directement le caractère de la cellule board[r][c] à une valeur improbable (par exemple, '#') et à le restaurer à sa valeur d'origine lors du backtracking.

Implémentation en Python

from typing import List

class Solution:
   def exist(self, board: List[List[str]], word: str) -> bool:
       if not board or not board[0]:
           return False

       rows, cols = len(board), len(board[0])

       def search(r: int, c: int, index: int) -> bool:
           # Condition de sortie : caractère non correspondant
           if board[r][c] != word[index]:
               return False
           
           # Condition de succès : fin du mot atteinte
           if index == len(word) - 1:
               return True

           # Sauvegarde du caractère et marquage comme visité
           temp_char = board[r][c]
           board[r][c] = '#'

           # Exploration des voisins
           # Vérification haut
           if r > 0 and search(r - 1, c, index + 1):
               board[r][c] = temp_char  # Restauration
               return True
           # Vérification bas
           if r + 1 < rows and search(r + 1, c, index + 1):
               board[r][c] = temp_char  # Restauration
               return True
           # Vérification gauche
           if c > 0 and search(r, c - 1, index + 1):
               board[r][c] = temp_char  # Restauration
               return True
           # Vérification droite
           if c + 1 < cols and search(r, c + 1, index + 1):
               board[r][c] = temp_char  # Restauration
               return True

           # Backtracking : restauration du caractère si aucune branche n'a abouti
           board[r][c] = temp_char
           return False

       # Lancement de la recherche depuis chaque cellule
       for i in range(rows):
           for j in range(cols):
               if search(i, j, 0):
                   return True
       
       return False

   

L'Importance Cruciale du Backtracking

La contrainte stipulant qu'une cellule ne peut être réutilisée dans le même chemin est fonadmentale. Cependant, une cellule peut faire partie de plusieurs chemins distincts explorés depuis différents points de départ ou différentes branches de l'exploration.

Par conséquent, le marquage comme "visitée" doit être temporaire :

• Lors de l'entrée dans une fonction DFS pour la cellule (r, c), le caractère board[r][c] est remplacé par '#'.
• Lors de la sortie de la fonction DFS (que ce soit par succès, échec ou retour après exploration des voisins), le caractère d'origine est restauré.

Omettre cette étape de restauration compromettrait la recherche ultérieure depuis d'autres points de départ ou d'autres branches, conduisant à des résultats incorrects.

Mécanisme de Protection contre la Réutilisation

Le marquage avec '#' empêche efficacement la réutilisation d'une cellule au sein du même chemin. Si le DFS tente de revenir à une cellule déjà marquée ('#'), la condition initiale suviante échouera immédiatement :

if board[r][c] != word[idx]:
   return False
   

Étant donné que '#' ne correspondra jamais à un caractère valide de word, cela interdit de facto la réutilisation d'une cellule dans le chemin en cours.

Analyse de Complexité

Soit m*n la taille de la grille et L la longueur du mot à rechercher :

• Complexité Temporelle : Dans le pire des cas, la complexité est de O(m*n * 4^L). Chaque cellule peut être un point de départ, et à partir de chaque cellule, l'exploration peut se ramifier dans 4 directions jusqu'à une profondeur L. En pratique, la complexité est souvent bien moindre grâce aux élagages rapides dus aux non-correspondances de caractères.
• Complexité Spatiale : La complexité est de O(L), correspondant à la profondeur maximale de la pile d'appels récursifs. Ceci n'inclut pas l'espace occupé par l'entrée (la grille et le mot).

Conclusion

L'exploration de grilles par DFS suit un schéma récurrent : initier une exploration depuis chaque cellule en utilisant le backtracking pour chercher le caractère suivant du mot. La contrainte de non-réutilisation des cellules impose soit l'utilisation d'un tableau auxiliaire de visited, soit la modification in-situ de la grille avec restauration lors du backtracking. Une implémentation correcte de cette logique de marquage et de restauration est la clé pour résoudre ce type de problème.