130. Surrounded Regions

leetcode medium

#array#csharp#graph#leetcode#matrix#medium#string

Task

Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:

Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.

Регион: Для формирования региона соедините каждую ячейку 'O'.

Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.

Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.

Пример:

Input: board = [["X"]]

Output: [["X"]]

C# solution

matched/original

public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0) {
            return;
        }
        this.ROWS = board.Length;
        this.COLS = board[0].Length;
        List<int[]> borders = new List<int[]>();
        for (int r = 0; r < this.ROWS; ++r) {
            borders.Add(new int[] { r, 0 });
            borders.Add(new int[] { r, this.COLS - 1 });
        }
        for (int c = 0; c < this.COLS; ++c) {
            borders.Add(new int[] { 0, c });
            borders.Add(new int[] { this.ROWS - 1, c });
        }
        foreach (var pair in borders) {
            this.DFS(board, pair[0], pair[1]);
        }
        for (int r = 0; r < this.ROWS; ++r) {
            for (int c = 0; c < this.COLS; ++c) {
                if (board[r][c] == 'O')
                    board[r][c] = 'X';
                if (board[r][c] == 'E')
                    board[r][c] = 'O';
            }
        }
    }
    int ROWS, COLS;
    protected void DFS(char[][] board, int row, int col) {
        if (board[row][col] != 'O')
            return;
        board[row][col] = 'E';
        if (col < this.COLS - 1)
            DFS(board, row, col + 1);
        if (row < this.ROWS - 1)
            DFS(board, row + 1, col);
        if (col > 0)
            DFS(board, row, col - 1);
        if (row > 0)
            DFS(board, row - 1, col);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public void Solve(char[][] board) {
        if (board == null || board.size() == 0) {
            return;
        }
        this.ROWS = board.size();
        this.COLS = board[0].size();
        List<int[]> borders = new List<int[]>();
        for (int r = 0; r < this.ROWS; ++r) {
            borders.push_back(new int[] { r, 0 });
            borders.push_back(new int[] { r, this.COLS - 1 });
        }
        for (int c = 0; c < this.COLS; ++c) {
            borders.push_back(new int[] { 0, c });
            borders.push_back(new int[] { this.ROWS - 1, c });
        }
        foreach (var pair in borders) {
            this.DFS(board, pair[0], pair[1]);
        }
        for (int r = 0; r < this.ROWS; ++r) {
            for (int c = 0; c < this.COLS; ++c) {
                if (board[r][c] == 'O')
                    board[r][c] = 'X';
                if (board[r][c] == 'E')
                    board[r][c] = 'O';
            }
        }
    }
    int ROWS, COLS;
    protected void DFS(char[][] board, int row, int col) {
        if (board[row][col] != 'O')
            return;
        board[row][col] = 'E';
        if (col < this.COLS - 1)
            DFS(board, row, col + 1);
        if (row < this.ROWS - 1)
            DFS(board, row + 1, col);
        if (col > 0)
            DFS(board, row, col - 1);
        if (row > 0)
            DFS(board, row - 1, col);
    }
}

Java solution

matched/original

public class Solution {
    protected Integer ROWS = 0;
    protected Integer COLS = 0;

    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        this.ROWS = board.length;
        this.COLS = board[0].length;

        List<Pair<Integer, Integer>> borders = new LinkedList<Pair<Integer, Integer>>();
        for (int r = 0; r < this.ROWS; ++r) {
            borders.add(new Pair(r, 0));
            borders.add(new Pair(r, this.COLS - 1));
        }
        for (int c = 0; c < this.COLS; ++c) {
            borders.add(new Pair(0, c));
            borders.add(new Pair(this.ROWS - 1, c));
        }

        for (Pair<Integer, Integer> pair : borders) {
            this.DFS(board, pair.first, pair.second);
        }

        for (int r = 0; r < this.ROWS; ++r) {
            for (int c = 0; c < this.COLS; ++c) {
                if (board[r][c] == 'O') board[r][c] = 'X';
                if (board[r][c] == 'E') board[r][c] = 'O';
            }
        }
    }

    protected void DFS(char[][] board, int row, int col) {
        if (board[row][col] != 'O') return;

        board[row][col] = 'E';
        if (col < this.COLS - 1) this.DFS(board, row, col + 1);
        if (row < this.ROWS - 1) this.DFS(board, row + 1, col);
        if (col > 0) this.DFS(board, row, col - 1);
        if (row > 0) this.DFS(board, row - 1, col);
    }
}

class Pair<U, V> {
    public U first;
    public V second;

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}

JavaScript solution

matched/original

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);
    }
};

Python solution

matched/original

class Solution(object):
    def solve(self, board: List[List[str]]) -> None:
        if not board or not board[0]:
            return

        self.ROWS = len(board)
        self.COLS = len(board[0])

        from itertools import product
        borders = list(product(range(self.ROWS), [0, self.COLS - 1])) + list(
            product([0, self.ROWS - 1], range(self.COLS))
        )

        for row, col in borders:
            self.DFS(board, row, col)

        for r in range(self.ROWS):
            for c in range(self.COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "E":
                    board[r][c] = "O"

    def DFS(self, board: List[List[str]], row: int, col: int) -> None:
        if board[row][col] != "O":
            return
        board[row][col] = "E"
        if col < self.COLS - 1:
            self.DFS(board, row, col + 1)
        if row < self.ROWS - 1:
            self.DFS(board, row + 1, col)
        if col > 0:
            self.DFS(board, row, col - 1)
        if row > 0:
            self.DFS(board, row - 1, col)

Go solution

matched/original

func solve(board [][]byte) {
    if board == nil || len(board) == 0 {
        return
    }
    ROWS := len(board)
    COLS := len(board[0])
    borders := [][]int{}
    for r := 0; r < ROWS; r++ {
        borders = append(borders, []int{r, 0})
        borders = append(borders, []int{r, COLS - 1})
    }
    for c := 0; c < COLS; c++ {
        borders = append(borders, []int{0, c})
        borders = append(borders, []int{ROWS - 1, c})
    }
    var DFS func([][]byte, int, int)
    DFS = func(board [][]byte, row int, col int) {
        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)
        }
    }
    for _, pair := range borders {
        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'
            }
        }
    }
}

Explanation

Algorithm

1️⃣

Выбор начальных ячеек и инициация DFS:

Начинаем с выбора всех ячеек, расположенных на границах доски.

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

2️⃣

Логика и выполнение DFS:

Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'.

Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'.

3️⃣

Классификация и финальная обработка ячеек:

После обхода всех граничных ячеек мы получаем три типа ячеек:

Ячейки с буквой 'X': эти ячейки можно считать стеной.

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

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

😎