/**
* @param {number[][]} grid
* @return {number}
*/
var shortestBridge = function(grid) {
let dfs = (i, j) => {
const s = i + "," + j
seen.add(s)
let res = [[i, j]]
for (const [dx, dy] of [[1, 0], [0, 1], [-1, 0], [0, -1]]) {
const [x, y] = [i + dx, j + dy]
if (x >= 0 && x < m && y >= 0 && y < n) {
if (grid[x][y] === 1 && !seen.has(x + "," + y)) {
res = res.concat(dfs(x, y))
}
}
}
return res
}
const [m, n] = [grid.length, grid[0].length]
let points
const seen = new Set()
for (let i = 0; i < m; i++) {
if (!points) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1 && !seen.has(i + "," + j)) {
points = dfs(i, j)
break
}
}
}
}
let result = 0
while (true) {
const temp = []
for (const [i, j] of points) {
for (const [dx, dy] of [[1, 0], [0, 1], [-1, 0], [0, -1]]) {
const [x, y] = [i + dx, j + dy]
if (x >= 0 && x < m && y >= 0 && y < n) {
const s = x + "," + y
if (!seen.has(s)) {
if (grid[x][y] == 1) {
return result
}
grid[x][y] = 1
temp.push([x, y])
seen.add(s)
}
}
}
}
points = temp
result += 1
}
return result
};