130.surrounded-regions.md

130. Surrounded Regions

TODO: Review the notes + implementations

Test Cases

Edge / Corner Cases

Input: 
O X X
O O X
O X X
Output: 

Traversal

We can traverse all O that are "surrounded" by X. (Finding the closed island, DFS or BFS both work), we define dfs() function that returns true if the region is surrounded by X:

• O: Keep traversing the adjacent cells.
• X: True, because it's surrounded by X.
• Visited: True, because we don't need to traverse the visited cell.
• Out of bound: False, because it's not surrounded by X.

Pitfalls

Here is an important note: We don't early return false if the cell is out of bound or visited, because we need to traverse the whole region to mark the visited cells.

There are some pitfalls that leads to WA:

directions.forEach { adj ->
    // If `result` is false, it will short circuit and the dfs() won't be invoke, this leads to WA.
    result = result & dfs(grid, x + adj[0], y + adj[1])
}

// Or early return in this way, this leads to WA as well.
directions.forEach { adj ->
    if (!dfs(grid, x + adj[0], y + adj[1])) return false
}

fun solve(board: Array<CharArray>): Unit {
    val m = board.size
    val n = board[0].size
    
    // All surrounded regions
    val regions = hashSetOf<Pair<Int, Int>>()
    for (x in 0 until m) {
        for (y in 0 until n) {
            if (board[x][y] == 'O' && !regions.contains(x to y)) {
                val visited = hashSetOf<Pair<Int, Int>>()
                if (dfs(board, x, y, visited)) {
                    regions.addAll(visited)
                }
            }
        }
    }
    
    regions.forEach {
        board[it.first][it.second] = 'X'
    }
}

private fun dfs(board: Array<CharArray>, x: Int, y: Int, visited: HashSet<Pair<Int, Int>>): Boolean {
    val m = board.size
    val n = board[0].size
    if (x !in 0 until m || y !in 0 until n) return false
    if (visited.contains(x to y)) return true
    if (board[x][y] == 'X') return true

    visited.add(x to y)
    var result = true
    for (d in directions) {
        val newX = x + d[0]
        val newY = y + d[1]
        result = dfs(board, newX, newY, visited) && result
    }
    return result
}

Bounary Traversal

Alternatively, we can find "non-closed" region first. We start traversing from four boundaries (DFS or BFS), and find the regions that are not surrounded, and iterate the whole board again to capture the closed regions.

private val notCapture = 'A'

fun solve(board: Array<CharArray>): Unit {
    val m = board.size
    val n = board[0].size
    // First row
    for (c in 0 until n) {
        dfs(board, 0, c)
    }
    // First col
    for (r in 0 until m) {
        dfs(board, r, 0)
    }
    
    // Last row
    for (c in 0 until n) {
        dfs(board, m - 1, c)
    }
    
    // Last col
    for (r in 0 until m) {
        dfs(board, r, n - 1)
    }
    
    for (i in 0 until m) {
        for (j in 0 until n) {
            // Capture
            if (board[i][j] == 'O') board[i][j] = 'X'
            // Recover
            else if (board[i][j] == notCapture) board[i][j] = 'O' 
        }
    }
}

private fun dfs(board: Array<CharArray>, x: Int, y: Int) {
    if (x < 0 || x >= board.size || y < 0 || y >= board[0].size || board[x][y] != 'O') return
    board[x][y] = notCapture
    directions.forEach { d -> 
        dfs(board, x + d[0], y + d[1])
    }
}