Задача: 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'.

😎 Решение:

function solve(&$board) {
    if ($board == null || count($board) == 0) {
        return;
    }
    $ROWS = count($board);
    $COLS = count($board[0]);
    $borders = [];
    for ($r = 0; $r < $ROWS; ++$r) {
        array_push($borders, [$r, 0], [$r, $COLS - 1]);
    }
    for ($c = 0; $c < $COLS; ++$c) {
        array_push($borders, [0, $c], [$ROWS - 1, $c]);
    }
    foreach ($borders as $pair) {
        dfs($board, $pair[0], $pair[1]);
    }
    for ($r = 0; $r < $ROWS; ++$r) {
        for ($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";
    $ROWS = count($board);
    $COLS = count($board[0]);
    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);
}

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