Surrounded Regions

Description

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.

Example:

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

After running your function, the board should be:

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

Explanation:

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.

Solution(javascript)

/*
 * @lc app=leetcode id=130 lang=javascript
 *
 * [130] Surrounded Regions
 */

// @lc code=start
// /** BFS
//  * @param {character[][]} board
//  * @return {void} Do not return anything, modify board in-place instead.
//  */
// const solve = function (board) {
//   if (!board.length) {
//     return
//   }
//   const visited = {
//   }
//   const key = (row, column) => `${row}-${column}`
//   const bfs = (row, column) => {
//     let current = [[row, column]]
//     visited[key(row, column)] = true
//     while (current.length > 0) {
//       const next = []
//       current.forEach(([row, column]) => {
//         if (board[row][column + 1] === 'O' && !visited[key(row, column + 1)]) {
//           visited[key(row, column + 1)] = true
//           next.push([row, column + 1])
//         }
//         if (board[row][column - 1] === 'O' && !visited[key(row, column - 1)]) {
//           visited[key(row, column - 1)] = true
//           next.push([row, column - 1])
//         }
//         if (board[row - 1] && board[row - 1][column] === 'O' && !visited[key(row - 1, column)]) {
//           visited[key(row - 1, column)] = true
//           next.push([row - 1, column])
//         }
//         if (board[row + 1] && board[row + 1][column] === 'O' && !visited[key(row + 1, column)]) {
//           visited[key(row + 1, column)] = true
//           next.push([row + 1, column])
//         }
//         current = next
//       })
//     }
//   }
//   [0, board.length - 1].forEach((row) => {
//     for (let column = 0; column < board[row].length; column++) {
//       if (!visited[key(row, column)] && board[row][column] === 'O') {
//         bfs(row, column)
//       }
//     }
//   });
//   [0, board[0].length - 1].forEach((column) => {
//     for (let row = 0; row < board.length; row++) {
//       if (!visited[key(row, column)] && board[row][column] === 'O') {
//         bfs(row, column)
//       }
//     }
//   })
//   board.forEach((items, row) => {
//     items.forEach((item, column) => {
//       if (!visited[key(row, column)]) {
//         board[row][column] = 'X'
//       }
//     })
//   })
// }

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((val, index) => index)
    this.size = new Array(n).fill(1)
    this.count = n
  }

  root(i) {
    while (this.parent[i] !== undefined && i !== this.parent[i]) {
      this.parent[i] = this.parent[this.parent[i]] // Path compression
      i = this.parent[i]
    }
    return i
  }

  connected(a, b) {
    return this.root(a) === this.root(b)
  }

  union(a, b) {
    const rootA = this.root(a)
    const rootB = this.root(b)
    if (rootA === rootB) {
      return
    }
    if (this.parent[rootA] < this.parent[rootB]) {
      this.parent[rootA] = rootB
      this.size[rootB] += this.size[rootA]
    } else {
      this.parent[rootB] = rootA
      this.size[rootA] += this.size[rootB]
    }
    this.count -= 1
  }

  getCount() {
    return this.count
  }
}

/** Union Find: create a dummy node
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
const solve = function (board) {
  if (!board.length) {
    return
  }
  const row = board.length
  const column = board[0].length
  const uf = new UnionFind(row * column + 1)
  const dummyNode = row * column
  board.forEach((items, currentRow) => {
    items.forEach((item, currentColumn) => {
      const currentNode = currentRow * column + currentColumn
      if (
        item === 'O'
         && (
           currentRow === 0
          || currentRow === row - 1
          || currentColumn === 0
          || currentColumn === column - 1)
      ) {
        uf.union(currentNode, dummyNode)
      } else if (item === 'O') {
        if (board[currentRow][currentColumn + 1] === 'O') {
          uf.union(currentRow * column + currentColumn + 1, currentNode)
        }
        if (board[currentRow][currentColumn - 1] === 'O') {
          uf.union(currentRow * column + currentColumn - 1, currentNode)
        }
        if (board[currentRow - 1][currentColumn] === 'O') {
          uf.union((currentRow - 1) * column + currentColumn, currentNode)
        }
        if (board[currentRow + 1][currentColumn] === 'O') {
          uf.union((currentRow + 1) * column + currentColumn, currentNode)
        }
      }
    })
  })
  board.forEach((items, currentRow) => {
    items.forEach((item, currentColumn) => {
      if (!uf.connected(currentRow * column + currentColumn, dummyNode)) {
        board[currentRow][currentColumn] = 'X'
      }
    })
  })
}