刷粉网站推广免费,免费查询企业信息的软件,大渡口网站建设,dw做网站链接数据库★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号#xff1a;山青咏芝#xff08;shanqingyongzhi#xff09;➤博客园地址#xff1a;山青咏芝#xff08;https://www.cnblogs.com/strengthen/#xff09;➤GitHub地址山青咏芝shanqingyongzhi➤博客园地址山青咏芝https://www.cnblogs.com/strengthen/➤GitHub地址https://github.com/strengthen/LeetCode➤原文地址 https://www.cnblogs.com/strengthen/p/10634516.html ➤如果链接不是山青咏芝的博客园地址则可能是爬取作者的文章。➤原文已修改更新强烈建议点击原文地址阅读支持作者支持原创★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 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 isnt 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 5001 A[i].length 5000 A[i][j] 1All rows have the same size.给出一个二维数组 A每个单元格为 0代表海或 1代表陆地。 移动是指在陆地上从一个地方走到另一个地方朝四个方向之一或离开网格的边界。 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。 示例 1 输入[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出3
解释
有三个 1 被 0 包围。一个 1 没有被包围因为它在边界上。 示例 2 输入[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出0
解释
所有 1 都在边界上或可以到达边界。 提示 1 A.length 5001 A[i].length 5000 A[i][j] 1所有行的大小都相同432ms 1 class Solution {2 func numEnclaves(_ A: [[Int]]) - Int {3 var grid A4 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.count7 let w A[0].count8 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 03 var ovSum 04 5 func numEnclaves(_ A: [[Int]]) - Int {6 var a A7 8 var rowInd 09 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 05 var C:Int 06 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 A8 var ret 09 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 } 转载于:https://www.cnblogs.com/strengthen/p/10634516.html
