1568. Minimum Number of Days to Disconnect Island
有一个n*m的binary grid，1表示island、0表示水
如果整个grid只有一个island，那就为connected
反之则为disconnected
我们每天可以把一个岛变成水(1->0)
请问我们最少需要几天可以把grid变成disconnected?
思路:
disconnected代表grid有两个岛以上
首先要知道这题的答案只有可能是0、1、2天
0 : grid一开始就有2个island以上
1 : 把任意一个island变成水，就可以得到2个以上的岛
2 : 不是上述两种的答案就是2天
这里解释一下
如果你没办法用一天把1个岛变成2个以上的岛
那代表一定可以找到一个grid[i][j]=1，且他只有两边跟另外两个值=1的grid相连
这时候把相连的grid断掉就好，所以只要2天
那这题就是去数岛的数目
如果一开始就大于1则为0天
不然你就尝试每次把1个1变为0，再去数岛的数量，如果大于1则为1天
否则就是2天
golang code：
func minDays(grid [][]int) int {
n, m := len(grid), len(grid[0])
cur := 2
findIslandNum := func() bool {
start := cur
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] < start && grid[i][j] != 0 {
region_cnt(grid, i, j, start, cur)
cur++
}
}
}
if cur-start == 1 {
return false
}
return true
}
if findIslandNum() {
return 0
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] != 0 {
temp := grid[i][j]
grid[i][j] = 0
if findIslandNum() {
return 1
}
grid[i][j] = temp
}
}
}
return 2
}
func region_cnt(pixel [][]int, i, j int, start, cur int) {
n := len(pixel)
m := len(pixel[0])
if i < n && j < m && i > -1 && j > -1 && pixel[i][j] > 0 && pixel[i][j] <
start {
pixel[i][j] = cur
region_cnt(pixel, i+1, j, start, cur)
region_cnt(pixel, i, j+1, start, cur)
region_cnt(pixel, i-1, j, start, cur)
region_cnt(pixel, i, j-1, start, cur)
}
}