Le problème des régions encerclées consiste à modifier une matrice bidimensionnelle composée des caractères 'X' et 'O'. L'objectif est d'identifier tous les groupes de 'O' qui sont complètement entourés par des 'X' et de les remplacer par des 'X'. Une règle fondamentale s'aplique : les 'O' situés sur les bords de la matrice, ou connectés à un 'O' de bord (horizontalement ou verticalement), ne peuvent pas être encerclés et doivent donc rester inchangés.

Exemple d'illustrasion

Prenons la matrice initiale suivante :

X X X X
X O O X
X X O X
X O X X

Après l'exécution de l'algorithme, la matrice est transformée ainsi :

X X X X
X X X X
X X X X
X O X X

Dans cet exemple, les 'O' internes sont capturés et remplacés, tandis que le 'O' situé sur le bord inférieur gauche et ses connexions potentielles restent intacts.

Approche algorithmique

Plutôt que de chercher directement les régions à capturer, il est plus efficace d'aodpter une approche inverse. Nous pouvons identifier tous les 'O' "sûrs" (ceux sur les bords et leurs voisins connectés) et les marquer temporairement avec un caractère distinct, par exemple '#'. Une fois cette étape terminée, il suffit de parcourir l'ensemble de la grille : les 'O' restants sont nécessairement encerclés et doivent devenir des 'X', tandis que les caractères '#' sont reconvertis en 'O'.

Pour explorer les connexions à partir des bords, nous utiliserons ici un parcours en largeur (BFS) à l'aide d'une file d'attente, ce qui évite les risques de dépassement de pile liés à la récursivité profonde sur de grandes matrices.

Implémentation en JavaScript

/**
 * Modifie la grille sur place pour capturer les régions entourées.
 * @param {character[][]} grid
 * @return {void}
 */
function captureSurroundedRegions(grid) {
    if (!grid || grid.length === 0 || grid[0].length === 0) return;

    const totalRows = grid.length;
    const totalCols = grid[0].length;
    const queue = [];

    // Fonction pour ajouter les coordonnées à la file et marquer la cellule
    const enqueueAndMark = (r, c) => {
        if (r >= 0 && r < totalRows && c >= 0 && c < totalCols && grid[r][c] === 'O') {
            grid[r][c] = '#'; // Marquage temporaire
            queue.push([r, c]);
        }
    };

    // 1. Parcourir les bordures et initialiser la file avec les 'O' trouvés
    for (let r = 0; r < totalRows; r++) {
        enqueueAndMark(r, 0);             // Colonne de gauche
        enqueueAndMark(r, totalCols - 1); // Colonne de droite
    }
    for (let c = 1; c < totalCols - 1; c++) {
        enqueueAndMark(0, c);             // Ligne du haut
        enqueueAndMark(totalRows - 1, c); // Ligne du bas
    }

    // 2. Parcours en largeur (BFS) pour propager le marquage aux 'O' connectés
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    
    while (queue.length > 0) {
        const [currentRow, currentCol] = queue.shift();
        
        for (const [dr, dc] of directions) {
            enqueueAndMark(currentRow + dr, currentCol + dc);
        }
    }

    // 3. Conversion finale : 'O' -> 'X' (capturés) et '#' -> 'O' (sauvés)
    for (let r = 0; r < totalRows; r++) {
        for (let c = 0; c < totalCols; c++) {
            if (grid[r][c] === 'O') {
                grid[r][c] = 'X';
            } else if (grid[r][c] === '#') {
                grid[r][c] = 'O';
            }
        }
    }
}