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

😎 Решение:

class Solution {
    private var rows: Int = 0
    private var cols: Int = 0

    func solve(_ board: inout [[Character]]) {
        rows = board.count
        guard rows > 0 else { return }
        cols = board[0].count
        guard cols > 0 else { return }

        for i in 0..<rows {
            for j in 0..<cols {
                if i == 0 || j == 0 || i == rows - 1 || j == cols - 1 {
                    dfs(&board, i, j)
                }
            }
        }

        for i in 0..<rows {
            for j in 0..<cols {
                if board[i][j] == "O" {
                    board[i][j] = "X"
                } else if board[i][j] == "E" {
                    board[i][j] = "O"
                }
            }
        }
    }

    private func dfs(_ board: inout [[Character]], _ i: Int, _ j: Int) {
        if board[i][j] != "O" { return }
        board[i][j] = "E"
        if j < cols - 1 { dfs(&board, i, j + 1) }
        if i < rows - 1 { dfs(&board, i + 1, j) }
        if j > 0 { dfs(&board, i, j - 1) }
        if i > 0 { dfs(&board, i - 1, j) }
    }
}

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