Shortest Bridge

Description

In a given 2D binary array A, there are two islands.  (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped.  (It is guaranteed that the answer is at least 1.)

 

Example 1:

Input: A = [[0,1],[1,0]]
Output: 1

Example 2:

Input: A = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

 

Constraints:

• 2 <= A.length == A[0].length <= 100
• A[i][j] == 0 or A[i][j] == 1

Solution(javascript)

/*
 * @lc app=leetcode id=934 lang=javascript
 *
 * [934] Shortest Bridge
 */

// @lc code=start
/** 1. Union Find 貌似不好搞，因为要算出最后两个集合的距离，
 *  但是不知道两个集合里有什么
 * 2. DFS/BFS 找出两个集合, 然后两个集合做 N^2 运算，效率不好
 * 3，DFS 找到一个集合， BFS 遍历这个集合
 * @param {number[][]} A
 * @return {number}
 */
// const shortestBridge = function (A) {
//   let source = null
//   for (let i = 0; i < A.length; i++) {
//     for (let j = 0; j < A[0].length; j++) {
//       if (A[i][j] === 1) {
//         source = [i, j]
//         break
//       }
//     }
//   }
//   const visited = new Array(A.length).fill(false).map(() => new Array(A[0].length).fill(false))
//   const part1 = []
//   const dfs = (s) => {
//     const [i, j] = s
//     if (visited[i][j]) {
//       return
//     }
//     part1.push(s)
//     visited[i][j] = true
//     if (A[i][j + 1] === 1) {
//       dfs([i, j + 1])
//     }
//     if (A[i][j - 1] === 1) {
//       dfs([i, j - 1])
//     }
//     if (A[i + 1] && A[i + 1][j] === 1) {
//       dfs([i + 1, j])
//     }
//     if (A[i - 1] && A[i - 1][j] === 1) {
//       dfs([i - 1, j])
//     }
//   }
//   dfs(source)
//   let distance = Infinity
//   const part2 = []
//   for (let i = 0; i < A.length; i++) {
//     for (let j = 0; j < A[0].length; j++) {
//       if (A[i][j] === 1 && !visited[i][j]) {
//         part2.push([i, j])
//       }
//     }
//   }
//   part1.forEach((pointA) => {
//     part2.forEach((pointB) => {
//       distance = Math.min(distance,
//         Math.abs(pointA[0] - pointB[0]) + Math.abs(pointB[1] - pointA[1]) - 1)
//     })
//   })
//   return distance
// }

const shortestBridge = function (A) {
  let source = null
  for (let i = 0; i < A.length; i++) {
    for (let j = 0; j < A[0].length; j++) {
      if (A[i][j] === 1) {
        source = [i, j]
        break
      }
    }
  }
  const visited = new Array(A.length).fill(false).map(() => new Array(A[0].length).fill(false))
  let part1 = []
  const dfs = (s) => {
    const [i, j] = s
    if (visited[i][j]) {
      return
    }
    part1.push(s)
    visited[i][j] = true
    if (A[i][j + 1] === 1) {
      dfs([i, j + 1])
    }
    if (A[i][j - 1] === 1) {
      dfs([i, j - 1])
    }
    if (A[i + 1] && A[i + 1][j] === 1) {
      dfs([i + 1, j])
    }
    if (A[i - 1] && A[i - 1][j] === 1) {
      dfs([i - 1, j])
    }
  }
  dfs(source)
  let distance = -1

  while (part1.length > 0) {
    const next = []
    distance += 1
    const isFind = (i, j) => {
      if (i < 0 || i >= A.length || j < 0 || j >= A[0].length) {
        return false
      }
      if (!visited[i][j]) {
        visited[i][j] = true
        next.push([i, j])
        return A[i][j] === 1
      }
      return false
    }
    for (const [i, j] of part1) {
      if (isFind(i, j + 1) || isFind(i, j - 1) || isFind(i + 1, j) || isFind(i - 1, j)) {
        return distance
      }
    }
    part1 = next
  }
  return distance
}
// @lc code=end