:orphan:

Surrounded Regions
==================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/surrounded-regions/

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**: The region is surrounded with ``'X'`` cells if you can
  **connect the region** with ``'X'`` cells and none of the region
  cells are on the edge of the ``board``.

A **surrounded** region is captured by replacing all ``'O'``\ s with
``'X'``\ s in the input matrix ``board``.



**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"]]

**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'``.

.. highlight:: python

Pattern
-------
Graph, DFS, Matrix

Approaches
----------

.. tab-set::

    .. tab-item:: DFS

        **Code**

        .. literalinclude:: ../problems/medium/surrounded-regions/surrounded_regions__dfs.py
            :language: python
            :lines: 14-

        **Test**

        >>> from surrounded_regions__dfs import solve
        >>> board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
        >>> solve(board)
        >>> board
        [['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]
        >>> board = [["X"]]
        >>> solve(board)
        >>> board
        [['X']]

        .. autofunction:: surrounded_regions__dfs.solve