Задача: 130. Surrounded Regions
Сложность: medium

Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:
Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.

Пример:

Input: board = [["X"]]

Output: [["X"]]

👨‍💻 Алгоритм:

1️⃣Выбор начальных ячеек и инициация DFS:
Начинаем с выбора всех ячеек, расположенных на границах доски.
Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS).

2️⃣Логика и выполнение DFS:
Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'.
Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'.

3️⃣Классификация и финальная обработка ячеек:
После обхода всех граничных ячеек мы получаем три типа ячеек:
Ячейки с буквой 'X': эти ячейки можно считать стеной.
Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'.
Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'.

😎 Решение:

var solve = function (board) {
    if (board == null || board.length == 0) {
        return;
    }
    let ROWS = board.length;
    let COLS = board[0].length;
    let borders = [];
    for (let r = 0; r < ROWS; ++r) {
        borders.push([r, 0]);
        borders.push([r, COLS - 1]);
    }
    for (let c = 0; c < COLS; ++c) {
        borders.push([0, c]);
        borders.push([ROWS - 1, c]);
    }
    borders.forEach((pair) => {
        dfs(board, pair[0], pair[1]);
    });
    for (let r = 0; r < ROWS; ++r) {
        for (let c = 0; c < COLS; ++c) {
            if (board[r][c] == "O") board[r][c] = "X";
            if (board[r][c] == "E") board[r][c] = "O";
        }
    }
    function dfs(board, row, col) {
        if (board[row][col] != "O") return;
        board[row][col] = "E";
        if (col < COLS - 1) dfs(board, row, col + 1);
        if (row < ROWS - 1) dfs(board, row + 1, col);
        if (col > 0) dfs(board, row, col - 1);
        if (row > 0) dfs(board, row - 1, col);
    }
};

Ставь 👍 и забирай 📚 Базу знаний