★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號(hào)：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：?https://www.cnblogs.com/strengthen/p/10634516.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強(qiáng)烈建議點(diǎn)擊原文地址閱讀！支持作者！支持原創(chuàng)！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Given a 2D array?A, each cell is 0 (representing sea) or 1 (representing land)

A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.

Return the number of land squares in the grid for which we?cannot?walk off the boundary of the grid in any number of moves.?

Example 1:

Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3 Explanation: There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.

Example 2:

Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] Output: 0 Explanation: All 1s are either on the boundary or can reach the boundary.?

Note:

1 <= A.length <= 500

1 <= A[i].length <= 500

0 <= A[i][j] <= 1

All rows have the same size.

---

給出一個(gè)二維數(shù)組?A，每個(gè)單元格為 0（代表海）或 1（代表陸地）。

移動(dòng)是指在陸地上從一個(gè)地方走到另一個(gè)地方（朝四個(gè)方向之一）或離開(kāi)網(wǎng)格的邊界。

返回網(wǎng)格中無(wú)法在任意次數(shù)的移動(dòng)中離開(kāi)網(wǎng)格邊界的陸地單元格的數(shù)量。?

示例 1：

輸入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] 輸出：3 解釋： 有三個(gè) 1 被 0 包圍。一個(gè) 1 沒(méi)有被包圍，因?yàn)樗谶吔缟稀?

示例 2：

輸入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] 輸出：0 解釋： 所有 1 都在邊界上或可以到達(dá)邊界。?

提示：

1 <= A.length <= 500

1 <= A[i].length <= 500

0 <= A[i][j] <= 1

所有行的大小都相同

---

432ms 1 class Solution { 2 func numEnclaves(_ A: [[Int]]) -> Int { 3 var grid = A 4 for row in 0..<grid.count { 5 dfs(&grid, row, 0) 6 dfs(&grid, row, grid[0].count - 1) 7 } 8 9 if grid.count > 0 && grid[0].count > 0 { 10 for col in 0..<grid[0].count { 11 dfs(&grid, 0, col) 12 dfs(&grid, grid.count - 1, col) 13 } 14 } 15 16 var result = 0 17 for row in 0..<grid.count { 18 for col in 0..<grid[0].count { 19 result += grid[row][col] 20 } 21 } 22 return result 23 } 24 25 func dfs(_ grid: inout [[Int]], _ row: Int, _ col: Int) { 26 if grid.count == 0 || grid[0].count == 0 { 27 return 28 } 29 if row < 0 || row > grid.count - 1 30 || col < 0 || col > grid[0].count - 1 { 31 return 32 } 33 34 if grid[row][col] == 0 { 35 return 36 } 37 38 grid[row][col] = 0 39 40 dfs(&grid, row + 1, col); 41 dfs(&grid, row - 1, col); 42 dfs(&grid, row, col + 1); 43 dfs(&grid, row, col - 1); 44 } 45 }

---

444ms

1 class Solution { 2 func numEnclaves(_ A: [[Int]]) -> Int { 3 guard A.count > 0 else { return 0 } 4 guard A[0].count > 0 else { return 0 } 5 6 let h = A.count 7 let w = A[0].count 8 9 var visited = Array(repeating: Array(repeating: false, count: w), count: h) 10 var queue = [(Int, Int)]() 11 for i in 0..<h { 12 if A[i][0] == 1 { 13 queue.append((i, 0)) 14 visited[i][0] = true 15 } 16 17 if w != 1 && A[i][w - 1] == 1 { 18 queue.append((i, w - 1)) 19 visited[i][w - 1] = true 20 } 21 } 22 23 for j in 0..<w { 24 if A[0][j] == 1 { 25 queue.append((0, j)) 26 visited[0][j] = true 27 } 28 29 if h != 1 && A[h - 1][j] == 1 { 30 queue.append((h - 1, j)) 31 visited[h - 1][j] = true 32 } 33 } 34 35 while queue.count > 0 { 36 var nextQueue = [(Int, Int)]() 37 for point in queue { 38 let row = point.0 39 let col = point.1 40 41 if row - 1 >= 0 && A[row - 1][col] == 1 && !visited[row - 1][col] { 42 visited[row - 1][col] = true 43 nextQueue.append((row - 1, col)) 44 } 45 46 if row + 1 < h && A[row + 1][col] == 1 && !visited[row + 1][col] { 47 visited[row + 1][col] = true 48 nextQueue.append((row + 1, col)) 49 } 50 51 if col - 1 >= 0 && A[row][col - 1] == 1 && !visited[row][col - 1] { 52 visited[row][col - 1] = true 53 nextQueue.append((row, col - 1)) 54 } 55 56 if col + 1 < w && A[row][col + 1] == 1 && !visited[row][col + 1] { 57 visited[row][col + 1] = true 58 nextQueue.append((row, col + 1)) 59 } 60 } 61 queue = nextQueue 62 } 63 64 var count = 0 65 66 for i in 0..<h { 67 for j in 0..<w { 68 if A[i][j] == 1 && !visited[i][j] { 69 count += 1 70 } 71 } 72 } 73 74 return count 75 } 76 }

---

452ms

1 class Solution { 2 var sum = 0 3 var ovSum = 0 4 5 func numEnclaves(_ A: [[Int]]) -> Int { 6 var a = A 7 8 var rowInd = 0 9 var colInd = 0 10 print(ovSum, sum) 11 rowInd = 0 12 while rowInd < A.count { 13 defer { rowInd += 1 } 14 colInd = 0 15 while colInd < A[rowInd].count { 16 defer { colInd += 1 } 17 if a[rowInd][colInd] == 1 { 18 ovSum += 1 19 } 20 } 21 } 22 23 for i in (0..<A.count) { 24 if a[i][0] == 1 { dfs(&a, i, 0) } 25 if a[i][A[0].count-1] == 1 { dfs(&a, i, A[0].count-1)} 26 27 } 28 for i in (0..<A[0].count) { 29 if a[0][i] == 1 { dfs(&a, 0, i) } 30 if a[A.count-1][i] == 1 { dfs(&a, A.count-1, i) } 31 32 } 33 34 print(ovSum, sum) 35 return ovSum - sum 36 } 37 38 func dfs(_ a: inout [[Int]], _ rowInd: Int, _ colInd: Int) { 39 guard rowInd < a.count, colInd < a[0].count, rowInd >= 0, colInd >= 0 else { return } 40 if a[rowInd][colInd] != 1 { return } 41 a[rowInd][colInd] = 2; sum += 1 42 dfs(&a, rowInd - 1, colInd) 43 dfs(&a, rowInd + 1, colInd) 44 dfs(&a, rowInd, colInd - 1) 45 dfs(&a, rowInd, colInd + 1) 46 } 47 }

---

Runtime:?488 ms Memory Usage:?19.1 MB 1 class Solution { 2 var DR:[Int] = [-1, 0, +1, 0] 3 var DC:[Int] = [0, +1, 0, -1] 4 var R:Int = 0 5 var C:Int = 0 6 var grid:[[Int]] = [[Int]]() 7 var visited:[[Bool]] = [[Bool]](repeating:[Bool](repeating:false,count:505),count:505) 8 9 func numEnclaves(_ A: [[Int]]) -> Int { 10 grid = A 11 R = grid.count 12 C = grid[0].count 13 14 for r in 0..<R 15 { 16 for c in 0..<C 17 { 18 if r == 0 || r == R - 1 || c == 0 || c == C - 1 19 { 20 if grid[r][c] == 1 && !visited[r][c] 21 { 22 dfs(r, c) 23 } 24 } 25 } 26 } 27 var ans:Int = 0 28 for r in 0..<R 29 { 30 for c in 0..<C 31 { 32 if grid[r][c] == 1 && !visited[r][c] 33 { 34 ans += 1 35 } 36 } 37 } 38 return ans 39 } 40 41 func dfs(_ r:Int,_ c:Int) 42 { 43 visited[r][c] = true 44 for dir in 0..<4 45 { 46 var nr:Int = r + DR[dir] 47 var nc:Int = c + DC[dir] 48 if nr >= 0 && nr < R && nc >= 0 && nc < C 49 { 50 if grid[nr][nc] == 1 && !visited[nr][nc] 51 { 52 dfs(nr, nc) 53 } 54 } 55 } 56 } 57 }

---

524ms

1 class Solution 2 { 3 func numEnclaves(_ A: [[Int]]) -> Int 4 { 5 guard A.count > 0 else { return 0 } 6 7 var m = A 8 var ret = 0 9 for r in 0..<m.count 10 { 11 for c in 0..<m[r].count 12 { 13 var temp = 0 14 self.dfs(r,c, &m, &temp) 15 if temp != -1 { ret += temp} 16 } 17 } 18 19 return ret 20 } 21 22 // checked: -1 23 private func dfs(_ r: Int, _ c: Int, _ m: inout [[Int]], _ count: inout Int) 24 { 25 guard r >= 0, c >= 0, r < m.count, c < m[r].count, m[r][c] != -1 else { return } 26 27 if m[r][c] == 0 { 28 m[r][c] = -1 29 return 30 } 31 32 if r == 0 || c == 0 || r == m.count - 1 || c == m[r].count - 1 { count = -1 } 33 if count != -1 { count += 1 } 34 m[r][c] = -1 35 // up 36 if r > 0 { self.dfs(r - 1, c, &m, &count) } 37 // down 38 if r < m.count - 1 { self.dfs(r + 1, c, &m, &count) } 39 // left 40 if c > 0 { self.dfs(r, c - 1, &m, &count) } 41 // right 42 if c < m[r].count - 1 { self.dfs(r, c + 1, &m, &count) } 43 } 44 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/strengthen/p/10634516.html

總結(jié)

以上是生活随笔為你收集整理的[Swift]LeetCode1020. 飞地的数量 | Number of Enclaves的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。