cpp-flashcards/org/study_deck_02/dsa/graphs/0130-surrounded-regions.org

#+ANKI_DECK: study_deck_02
* TODO 0130. Surrounded Regions :medium:
:PROPERTIES:
:NEETCODE: [[file:../../roadmap.org::*0130. Surrounded Regions][0130. Surrounded Regions]]
:END:

You are given an ~m x n~ matrix ~board~ containing *letters* ~'X'~ and ~'O'~, *capture regions* that are *surrounded*:

 - *Connect*: A cell is connected to adjacent cells horizontally or vertically.

 - *Region*: To form a region *connect every* ~'O'~ cell.

 - *Surround*: A region is surrounded if none of the ~'O'~ cells in that region are on the edge of the board. Such regions are *completely enclosed *by ~'X'~ cells.

To capture a *surrounded region*, replace all ~'O'~s with ~'X'~s *in-place* within the original board. You do not need to return anything.

*Example 1:*

*Input:* board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

*Output:* [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

*Explanation:*

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

*Example 2:*

*Input:* board = [["X"]]

*Output:* [["X"]]

*Constraints:*

 - ~m == board.length~

 - ~n == board[i].length~

 - ~1 <= m, n <= 200~

 - ~board[i][j]~ is ~'X'~ or ~'O'~.

** TODO Approach
Write your approach here.

** TODO Python
#+begin_src python :lc-problem 130 :lc-lang python3
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
#+end_src

** TODO C++
#+begin_src cpp :lc-problem 130
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        
    }
};
#+end_src