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: Surrounded regions should not 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.

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {

    /* -------------------------------------------------------------------------- */
    /*                          130. Surrounded Regions                           */
    /* -------------------------------------------------------------------------- */

    /* ---------------------------- Solution Concept ---------------------------- */

    // We need to capture all regions that are not bordered to the edge of the matrix.
    // We could perform Depth First Search on all the cells in the matrix and ask
    // if any of them border the edge. Instead, we're going to do all the edges
    // of the matrix and convert all island that border the island to temp nodes.
    // We do this because we already know that the bad nodes border the edge 
    // of the matrix.

    // Once we've marked all the bad islands. We run through the entire matrix
    // automatically capturing all the nodes that are not marked as bad. And all
    // the previously marked bad nodes are converted to back to islands.

    /* ---------------------------- Solution as Code ---------------------------- */

    // Matrix Maxes (Makes our life's easier)
    const max_rows = board.length - 1;
    const max_cols = board[0].length - 1;

    // During our search, we can go up, down, left and right.
    // We cannot go diagonally! We can only go up, down, left and right.
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    // Our helper depth first function that converts all bad
    // islands to marked nodes.
    const depth_first_search = (row_index, col_index) => {

        // Is it within bounds of the matrix?
        // And are we allowed to do dfs on this node?
        if (row_index > max_rows || col_index > max_cols || col_index < 0 || row_index < 0 || board[row_index][col_index] != "O"){
            return false
        }

        // So node is within bounds, it bordered the edges of the matrix
        // and thus it's a invalid island. As we cannot Surround the Region
        // So let's mark it as a 't'. We do this to let us know not to 
        // convert this node into a 'x'.

        board[row_index][col_index] = "T";

        // Search in all directions for the rest of the island.
        for (const [x, y] of directions){
            depth_first_search(row_index + x, col_index + y);
        }
    }


    // let's check all the edges of the matrix checking 
    // for these bad nodes. If we ever find one, we run 
    // DFS on it to mark it. Starting with:

    // Top and Bottom of matrix
    for (let i = 0; i <= max_cols ; i++){
        const top = board[0][i];
        const bottom = board[max_rows][i];

        if (top === "O"){
            depth_first_search(0, i);
        }

        if (bottom === "O"){
            depth_first_search(max_rows, i);
        }
    }

    // Left and Right of matrix
    for (let i = 0; i <= max_rows ; i++){
        const left = board[i][0];
        const right = board[i][max_cols];

        if (left === "O"){
            depth_first_search(i, 0);
        }

        if (right === "O"){
            depth_first_search(i, max_cols);
        }
    }

    // Now we have gone through the entire border of the matrix
    // we have now marked all bad islands if their was any.
    // Meaning we can automatically capture all regions that 
    // didn't border that edge.

    // We will also unmark all the marked nodes that did border 
    // the edge of the matrix. We do this because we know that it's an invalid island.
    board.forEach((row, row_index) => {
        row.forEach((col, col_index) => {

            // Capture unmarked regions.
            if (col === "O") board[row_index][col_index] = "X"

            // Converted marked regions back to a normal island
            if (col === "T") board[row_index][col_index] = "O"
        })
    })

    // Return Nothing. We modified our input in place.

};