{"id":11387,"date":"2022-02-20T23:56:21","date_gmt":"2022-02-20T23:56:21","guid":{"rendered":"https:\/\/www.softwareeverydayblog.com\/?p=11387"},"modified":"2022-02-21T00:00:16","modified_gmt":"2022-02-21T00:00:16","slug":"programming-problem-surrounded-regions","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11387","title":{"rendered":"[Programming Problem] Surrounded Regions"},"content":{"rendered":"

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

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.<\/p>\n

Example 1:
\nInput: board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]]
\nOutput: [[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]]
\nExplanation: 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.
\nExample 2:<\/p>\n

Input: board = [[“X”]]
\nOutput: [[“X”]]<\/p>\n

[Problem Link<\/a>]<\/p>\n

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:-<\/p>\n

    \n
  1. Make a copy of the board<\/li>\n
  2. Run floodfill algorithm on: top and bottom row, first and last column<\/li>\n
  3. After floodfill algorithm, all border islands will be marked as ‘-‘<\/li>\n
  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’<\/li>\n<\/ol>\n
    \r\n\/**\r\n * @param {character[][]} board\r\n * @return {void} Do not return anything, modify board in-place instead.\r\n *\/\r\nvar solve = function(board) {\r\n    \/\/ make a copy of the board\r\n    const boardCopy = board.map((x) => x.map((y) => y));\r\n    \r\n    \/\/ Run floodfill algorithm on: top row and botton row\r\n    for ( let j = 0 ; j < boardCopy[0].length ; j++ ) {\r\n        if (boardCopy[0][j] === 'O') floodFill(boardCopy, 0, j);\r\n        if (boardCopy[boardCopy.length-1][j] === 'O') floodFill(boardCopy, boardCopy.length-1, j);\r\n    }\r\n    \r\n    \/\/ Run floodfill algorithm on: first and last column\r\n    for ( let i = 0 ; i < boardCopy.length ; i++ ) {\r\n        if (boardCopy[i][0] === 'O') floodFill(boardCopy, i, 0);\r\n        if (boardCopy[i][boardCopy[0].length-1] === 'O') floodFill(boardCopy, i, boardCopy[0].length-1);\r\n    }\r\n    \r\n    \/\/ After floodfill algorithm, all border islands will be marked as '-'\r\n    \/\/ We basically set all border islands as 'O'\r\n    \/\/ Other values with 'O' (which are inner islands) will be set as 'X'    \r\n    \/\/ Set appropriate values on board (depending on output from floodfill algorithm)\r\n    boardCopy.forEach((x, i) => {\r\n        return x.forEach((y, j) => {\r\n            if (y === '-') {\r\n                board[i][j] = 'O';\r\n            } else if (y === 'O') {\r\n                board[i][j] = 'X'\r\n            } else { board[i][j] = y };\r\n        })\r\n    })\r\n            \r\n    return board;\r\n};\r\n\r\nvar floodFill = function(board, i, j) {\r\n    if ( i < 0 || i >= board.length || j < 0 || j >= board[0].length ) return;\r\n    \r\n    if (board[i][j] === 'O') {\r\n        board[i][j] = '-';\r\n        floodFill(board, i+1, j);\r\n        floodFill(board, i-1, j);\r\n        floodFill(board, i, j+1);\r\n        floodFill(board, i, j-1);        \r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
    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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-11387","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11387","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11387"}],"version-history":[{"count":5,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11387\/revisions"}],"predecessor-version":[{"id":11389,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11387\/revisions\/11389"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}