【LeetCode】 130. Surrounded Regions

Description

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

給予一個二維面板包含'X'和'O' (字母 O)，佔領所有被'X'包圍的地區。

反轉所有'O'使其成為'X'來佔領一個區域。

解釋：
被佔領的區域不應該在邊界上，因此任何在邊界上的'O'都不應該被反轉為'X'。任何'O'不在邊界上或是沒有和邊界連接到的都會被翻轉成'X'。兩個格子連接是指他們水平或垂直連接。

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Solution

• 這一類的題目已經出現好幾次了，一看到2D面板就先想到DFS。
• 我們要做的事情是保留住從邊界上DFS遍歷到的所有'O'。
• 我先將O轉換為暫時符號'N'，接著DFS遍歷所有邊界上的'N'，將其轉回'O'。最後將所有沒有被遍歷到的暫時符號'N'轉成'X'。
• 注意邊界限制。

Code

class Solution {
public:
    void dfs(vector<vector<char>>& board, int y, int x)
    {
        board[y][x] = 'O';
        if(y > 0 && board[y - 1][x] == 'N')
            dfs(board, y - 1, x);
        if(x > 0 && board[y][x - 1] == 'N')
            dfs(board, y, x - 1);
        if(y < board.size() - 1 && board[y + 1][x] == 'N')
            dfs(board, y + 1, x);
        if(x < board[0].size() - 1 && board[y][x + 1] == 'N')
            dfs(board, y, x + 1);
    }
    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
                if(board[i][j] == 'O') board[i][j] = 'N';
        
        for(int i = 0; i < board.size(); i++)
        {
            if(board[i][0] == 'N') dfs(board, i, 0);
            if(board[i][board[0].size() - 1] == 'N') dfs(board, i, board[0].size() - 1);
        }
        for(int j = 0; j < board[0].size(); j++)
        {
            if(board[0][j] == 'N') dfs(board, 0, j);
            if(board[board.size() - 1][j] == 'N') dfs(board, board.size() - 1, j);
        }

        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
                if(board[i][j] == 'N') board[i][j] = 'X';
    }
};

tags: LeetCode C++