[LeetCode] Surrounded Regions

Problem: 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. 

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.

Example:

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

Will become - 

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

Approach: This looks like Flood Fill problem with new color as 'X' and previous color as 'O'. The only exception is  that a ‘O’ is not replaced by ‘X’ if it lies in region that ends on a boundary so we just have to work around it. Here are the steps which we can follow -

1. Traverse the matrix and replace all 'O' with a special character say '#'.
2. Traverse all the four edges and call FloodFill('#', 'O') for every '#' on edges as we don't want to replace those with 'X'. (Previous Color - '#', New Color - 'X').
3. Traverse the matrix and replace all remaining '#' with 'X' using FloodFill('#', 'X'). (Previous color '#' and New color - 'X')

Implementation in C#:

        public void SolveRegions(char[][] board)

        {

            if (board?.Length <= 0)

            {

                return;

            }

            // Step 1: Replace all 'O' with '#' 

            for(int i = 0; i < board.Length; ++i)

            {

                for (int j = 0; j < board[0].Length; ++i)

                {

                    if (board[i][j] == 'O')

                    {

                        board[i][j] = '#';

                    }

                }

            }

            // Step 2: Replace all boundary '#' with 'O' as we don't want to change those

            // Top Boundary

            for (int i = 0; i < board[0].Length; ++i)

            {

                if (board[0][i] == '#')

                {

                    this.FloodFill(board, 0, i, '#', 'O');

                }

            }

            // Bottom Boundary

            int bottomRow = board.Length - 1;

            for (int i = 0; i < board[0].Length; ++i)

            {

                if (board[bottomRow][i] == '#')

                {

                    this.FloodFill(board, bottomRow, i, '#', 'O');

                }

            }

            // Left Boundary

            for (int i = 0; i < board.Length; ++i)

            {

                if (board[i][0] == '#')

                {

                    this.FloodFill(board, i, 0, '#', 'O');

                }

            }

            // Right Boundary

            int rightColumn = board[0].Length - 1;

            for (int i = 0; i < board.Length; ++i)

            {

                if (board[i][rightColumn] == '#')

                {

                    this.FloodFill(board, i, rightColumn, '#', 'O');

                }

            }

            // Step 3: Replace all remaining '#' with 'X'

            for (int i = 0; i < board.Length; ++i)

            {

                for (int j = 0; j < board[0].Length; ++j)

                {

                    if (board[i][j] == '#')

                    {

                        this.FloodFill(board, i, j, '#', 'X');

                    }

                }

            }

        }

        private void FloodFill(Char[][] board, int x, int y, char previousChar, char newChar)

        {

            if (x < 0 || x >= board.Length || y < 0 || y >= board[0].Length || board[x][y] != previousChar)

            {

                return;

            }

            board[x][y] = newChar;

            this.FloodFill(board, x - 1, y, previousChar, newChar);

            this.FloodFill(board, x + 1, y, previousChar, newChar);

            this.FloodFill(board, x, y - 1, previousChar, newChar);

            this.FloodFill(board, x, y + 1, previousChar, newChar);

        }

Complexity: O(m x n) where m is number of rows and n is number of columns.