Re: [閒聊] 每日leetcode
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)
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.51.54 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723350982.A.9B0.html
推
08/11 12:38,
1年前
, 1F
08/11 12:38, 1F
→
08/11 12:38,
1年前
, 2F
08/11 12:38, 2F
→
08/11 12:39,
1年前
, 3F
08/11 12:39, 3F
推
08/11 20:29,
1年前
, 4F
08/11 20:29, 4F
討論串 (同標題文章)
完整討論串 (本文為第 693 之 1548 篇)：