Код 130: Окруженные регионы

Постановка проблемы:

Учитывая матричную плату mxn, содержащую “X” и “O”, захватите все области, которые 4-направленно окружены “X”.

Область захватывается путем переворачивания всех “О” в “Х” в этой окруженной области.

Тестовые примеры:

Ограничения:

м.длина n[i]. длина 1, n доска[i][j] – это “X” или “O”.

Подход:

Главное отметить, что мы не можем просто перевернуть разрешение на X. Окруженные области не должны находиться на границе, что означает, что любая буква “О” на границе доски не будет перевернута на “X”. Любая буква “О”, которая не находится на границе и не связана с буквой “О” на границе, будет перевернута на “X”. Две ячейки соединены, если они являются соседними ячейками, соединенными горизонтально или вертикально.

Таким образом, нас интересуют только те O, которые находятся на границе 4, то есть либо в верхней строке, нижней строке, крайнем левом столбце, либо в самом правом столбце.

Это заставляет нас сначала найти те O, которые находятся на границах матрицы, и выполнить DFS/BFS из этого O, чтобы найти другие O, которые связаны. Затем мы обычно проходим матрицу и меняем только те O на X, которые не имеют никакой связи с этими O.

Например:

XOX XOX XOX

Рассмотрим этот пример, здесь мы имеем O на самом верху. Итак, мы находим ячейку с буквой O на самом верху и делаем либо DFS, либо BFS. Во время поиска мы временно изменим O на любой другой символ, скажем “+”. Таким образом, после DFS/BFS результирующая матрица будет выглядеть следующим образом:

Х + Х Х + Х Х + Х

Теперь мы выполняем обычный обход матрицы, и если мы видим O в матрице, она преобразуется обратно в O, если мы видим “+”, это означает, что они нарушают правило, которое должно быть перевернуто на X, поэтому мы сохраняем его как O. Таким образом, ответ на приведенный выше пример будет простым:

XOX XOX XOX

Теперь рассмотрим другой пример: Х Х Х Х Х Х О О Х Х Х Х О Х Х О Х Х Х

Мы проверяем те O, которые находятся на границе. Существует только 1 O, который находится на границе, которая находится в нижнем ряду (3, 1). Мы делаем DFS/BFS и временно меняем его на “+”.

X X X X X X О О X X X О X X X + X X

Теперь, как было сказано ранее, мы выполняем обычный обход матрицы и смотрим, есть ли O, если O присутствует, то переворачиваем его в X. Если мы увидим “+”, то оставим его как “О”.

Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х О Х Х

Код:

Подход DFS

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        if (board.length < 3 || board[0].length < 3)
            return;
        int row = board.length;
        int col = board[0].length;
        for (int i=0; i= board.length || j >= board[0].length || board[i][j] != 'O')
            return;
        board[i][j] = '+';
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j-1);
        dfs(board, i, j+1);
    }
}

Подход BFS

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        int row = board.length;
        int col = board[0].length;
        Queue queue = new LinkedList<>();
        // add all the edge on top left right botom to queue
       for (int i=0; i queue, int row, int col, char [][] board) {
        final int [][] directions = new int [][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        while (!queue.isEmpty()) {
            int [] currentPos = queue.poll();
            int x = currentPos[0];
            int y = currentPos[1];
            for (int [] dir : directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (newX < 0 || newY < 0 || newX >= row || newY >= col || board[newX][newY] != 'O')
                    continue;
                board[newX][newY] = '+';
                queue.offer(new int [] {newX, newY});
            }
        }
    }
}

Временная сложность и пространственная сложность:

Время (строка * col) Пространство (строка * col)

Rohithv07/Код доступа

Проблемы с LeetCode, которые решены.

Оригинал: “https://dev.to/rohithv07/leetcode-130-surrounded-regions-3dog”