[Programming Problem] Surrounded Regions

Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.

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

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: 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.
Example 2:

Input: board = [[“X”]]
Output: [[“X”]]

[Problem Link]

The high level idea here is to traverse the borders and run the floodfill algorithm to identify regions touching borders. Once we’ve identified those, we’ve identified regions we should leave alone vs. regions we need to flip. To do this we:-

  1. Make a copy of the board
  2. Run floodfill algorithm on: top and bottom row, first and last column
  3. After floodfill algorithm, all border islands will be marked as ‘-‘
  4. We then traverse our (copied) board to set appropriate values on board (depending on output from floodfill algorithm). We set all border islands (depicted by ‘-‘) as ‘O’ and inner islands (depicted by ‘O’) set as ‘X’
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
    // make a copy of the board
    const boardCopy = board.map((x) => x.map((y) => y));
 
    // Run floodfill algorithm on: top row and botton row
    for ( let j = 0 ; j < boardCopy[0].length ; j++ ) {
        if (boardCopy[0][j] === 'O') floodFill(boardCopy, 0, j);
        if (boardCopy[boardCopy.length-1][j] === 'O') floodFill(boardCopy, boardCopy.length-1, j);
    }
 
    // Run floodfill algorithm on: first and last column
    for ( let i = 0 ; i < boardCopy.length ; i++ ) {
        if (boardCopy[i][0] === 'O') floodFill(boardCopy, i, 0);
        if (boardCopy[i][boardCopy[0].length-1] === 'O') floodFill(boardCopy, i, boardCopy[0].length-1);
    }
 
    // After floodfill algorithm, all border islands will be marked as '-'
    // We basically set all border islands as 'O'
    // Other values with 'O' (which are inner islands) will be set as 'X'    
    // Set appropriate values on board (depending on output from floodfill algorithm)
    boardCopy.forEach((x, i) => {
        return x.forEach((y, j) => {
            if (y === '-') {
                board[i][j] = 'O';
            } else if (y === 'O') {
                board[i][j] = 'X'
            } else { board[i][j] = y };
        })
    })
 
    return board;
};
 
var floodFill = function(board, i, j) {
    if ( i < 0 || i >= board.length || j < 0 || j >= board[0].length ) return;
 
    if (board[i][j] === 'O') {
        board[i][j] = '-';
        floodFill(board, i+1, j);
        floodFill(board, i-1, j);
        floodFill(board, i, j+1);
        floodFill(board, i, j-1);        
    }
}

softwareeveryday

4,374 thoughts on “[Programming Problem] Surrounded Regions”

  21. I wish to voice my affection for your kindness supporting all those that really want assistance with the study. Your personal dedication to getting the message all over was wonderfully interesting and has specifically allowed women like me to realize their objectives. This informative recommendations indicates a great deal to me and somewhat more to my peers. With thanks; from everyone of us.

    Reply

  23. I wish to get across my passion for your generosity for those people who have the need for help with your content. Your special commitment to passing the message along came to be definitely important and has continually made regular people like me to get to their ambitions. Your warm and friendly key points signifies a great deal a person like me and far more to my office colleagues. Thanks a lot; from each one of us.

    Reply

  24. My husband and i got absolutely fortunate Peter could carry out his investigation from your ideas he had through the weblog. It is now and again perplexing to just find yourself releasing information which usually men and women may have been selling. And we figure out we now have you to appreciate for that. The specific illustrations you have made, the straightforward blog navigation, the friendships you can aid to foster – it’s got many amazing, and it’s really assisting our son in addition to our family understand the concept is pleasurable, and that is particularly vital. Thanks for the whole thing!

    Reply

  36. I wish to voice my respect for your kind-heartedness for folks that really want assistance with this important question. Your personal dedication to getting the solution across had become pretty interesting and has consistently made associates much like me to reach their dreams. Your important tips and hints indicates so much a person like me and a whole lot more to my office workers. Warm regards; from everyone of us.

    Reply

  39. I wish to point out my admiration for your generosity giving support to folks who really need assistance with the niche. Your personal dedication to passing the solution throughout had been particularly beneficial and have in every case helped girls like me to achieve their pursuits. Your warm and friendly key points means a lot a person like me and still more to my mates. Best wishes; from everyone of us.

    Reply

  456. The entrance to joker the popular 1st floor online slot game in 2022, easy to play, just register pgslot as a member with us. Register for a new member. JOKER has found a new dimension.

    Reply

  489. Slot Games Play Free Slot Games No cost to play Test play pg slots for free, get real money by our website, play slots, test play for free, get real money, you need our website.

    Reply

  490. Free slots games are the most popular games in casinos. First and foremost, pgslot is a game that requires long-term play. or keep playing for a spin Still need to rely on the horoscope for play

    Reply