在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ In a given 2D binary array Now, we may change Return the smallest number of Example 1: Input: [[0,1],[1,0]]
Output: 1
Example 2: Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Example 3: Input: [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1
Note:
在给定的二维二进制数组 现在,我们可以将 返回必须翻转的 示例 1: 输入:[[0,1],[1,0]] 输出:1 示例 2: 输入:[[0,1,0],[0,0,0],[0,0,1]] 输出:2 示例 3: 输入:[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] 输出:1 提示:
404ms 1 class Solution { 2 func shortestBridge(_ A: [[Int]]) -> Int { 3 let rowCount = A.count 4 if rowCount == 0 { 5 return 0 6 } 7 8 let colCount = A[0].count 9 10 var A = A 11 12 let coordinates = findFirstIsland(A: A) 13 let r1 = coordinates[0] 14 let c1 = coordinates[1] 15 16 var nextRiver = [Int]() 17 removeFirstIsland(A: &A, r: r1, c: c1, river: &nextRiver) 18 19 var distance = 0 20 while nextRiver.count > 0 { 21 let river = nextRiver 22 nextRiver = [Int]() 23 24 for coordinates in river { 25 let r = coordinates / rowCount 26 let c = coordinates % rowCount 27 28 let cell = A[r][c] 29 if cell == 0 { 30 A[r][c] = -1 31 32 if r > 0 { 33 // top 34 nextRiver.append((r - 1) * rowCount + c) 35 } 36 if (r + 1) < rowCount { 37 // bottom 38 nextRiver.append((r + 1) * rowCount + c) 39 } 40 if c > 0 { 41 nextRiver.append(r * rowCount + c - 1) 42 } 43 if (c + 1) < colCount { 44 nextRiver.append(r * rowCount + c + 1) 45 } 46 } else if cell == 1 { 47 return distance 48 } 49 } 50 distance += 1 51 } 52 return distance 53 } 54 55 func removeFirstIsland(A: inout [[Int]], r: Int, c: Int, river: inout [Int]) { 56 let rowCount = A.count 57 let colCount = A[0].count 58 59 let cell = A[r][c] 60 if cell == 0 { 61 // A[r][c] = 2 62 river.append(r * rowCount + c) 63 return 64 } else if cell == -1 { 65 return 66 } 67 A[r][c] = -1 68 69 if r > 0 { 70 // top 71 removeFirstIsland(A: &A, r: r - 1, c: c, river: &river) 72 } 73 if (r + 1) < rowCount { 74 // bottom 75 removeFirstIsland(A: &A, r: r + 1, c: c, river: &river) 76 } 77 if c > 0 { 78 removeFirstIsland(A: &A, r: r, c: c - 1, river: &river) 79 } 80 if (c + 1) < colCount { 81 removeFirstIsland(A: &A, r: r, c: c + 1, river: &river) 82 } 83 } 84 85 func findFirstIsland(A: [[Int]]) -> [Int] { 86 let rowCount = A.count 87 let colCount = A[0].count 88 var coordinates = Array(repeating: 0, count: 2) 89 var r = 0 90 var c = 0 91 while r < rowCount { 92 c = 0 93 while c < colCount { 94 if A[r][c] == 1 { 95 coordinates[0] = r 96 coordinates[1] = c 97 return coordinates 98 } 99 c += 1 100 } 101 r += 1 102 } 103 return coordinates 104 } 105 } 428ms 1 class Solution { 2 func shortestBridge(_ A: [[Int]]) -> Int { 3 var a = A 4 var q = [(Int, Int)]() 5 6 loop: for i in 0 ..< A.count { 7 for j in 0 ..< A[i].count { 8 if A[i][j] == 1 { 9 dfs(&a, i, j, &q) 10 break loop 11 } 12 } 13 } 14 15 let dir = [0 , 1 , 0 , -1 , 0] 16 var step = 0 17 while !q.isEmpty { 18 19 var size = q.count 20 while size > 0 { 21 let (i, j) = q.removeFirst() 22 for index in 0 ..< 4 { 23 let ti = i + dir[index] 24 let tj = j + dir[index + 1] 25 if ti < 0 || ti >= a.count || tj < 0 || tj >= a[i].count || a[ti][tj] == 2 { 26 continue 27 } 28 if a[ti][tj] == 1 { 29 return step 30 } else { 31 a[ti][tj] = 2 32 q.append((ti,tj)) 33 34 } 35 } 36 size -= 1 37 } 38 step += 1 39 } 40 41 return -1 42 } 43 44 func dfs(_ A: inout [[Int]], _ i: Int, _ j: Int, _ q: inout [(Int, Int)]) { 45 if i < 0 || i >= A.count || j < 0 || j >= A[i].count || A[i][j] != 1 { 46 return 47 } else { 48 A[i][j] = 2 49 q.append((i, j)) 50 dfs(&A, i - 1, j, &q) 51 dfs(&A, i + 1, j, &q) 52 dfs(&A, i, j - 1, &q) 53 dfs(&A, i, j + 1, &q) 54 } 55 } 56 } 476ms 1 class Solution { 2 func shortestBridge(_ A: [[Int]]) -> Int { 3 let R = A.count 4 let C = A[0].count 5 var qs = [(Int, Int)]() 6 var color = 1 7 var v = [[Int]](repeating: [Int](repeating: 0, count: C), count: R) 8 var ans = 0 9 func next(_ r: Int, _ c: Int, _ d: inout [String: (Int, Int)]) -> Bool { 10 var ns = [(r+1, c), (r-1, c), (r, c+1), (r, c-1)] 11 for n in ns { 12 guard 0 ..< R ~= n.0, 0 ..< C ~= n.1 else { 13 continue 14 } 15 guard v[n.0][n.1] == 0 else { 16 if v[n.0][n.1] != v[r][c] { 17 //print(n, r, c) 18 return true 19 } 20 continue 21 } 22 v[n.0][n.1] = v[r][c] 23 d["\(n.0), \(n.1)"] = (n.0, n.1) 24 } 25 return false 26 } 27 func paint(_ r: Int, _ c: Int) { 28 guard v[r][c] == 0 else { 29 return 30 } 31 v[r][c] = color 32 var qs = [(r, c)] 33 while !qs.isEmpty { 34 for i in 0 ..< qs.count { 35 let (r, c) = qs.remove(at: 0) 36 let ns = [(r+1, c), (r-1, c), (r, c+1), (r, c-1)] 37 for n in ns { 38 guard 0 ..< R ~= n.0, 0 ..< C ~= n.1 else { 39 continue 40 } 41 guard v[n.0][n.1] == 0, A[n.0][n.1] == 1 else { 42 continue 43 } 44 v[n.0][n.1] = color 45 qs.append(n) 46 } 47 } 48 } 49 color += 1 50 } 51 for r in 0 ..< R { 52 for c in 0 ..< C { 53 if A[r][c] == 1 { 54 paint(r, c) 55 if v[r][c] == 1 { 56 qs.append((r, c)) 57 } 58 } 59 } 60 } 61 //print(v) 62 while !qs.isEmpty { 63 //print(qs) 64 var d = [String: (Int, Int)]() 65 for i in 0 ..< qs.count { 66 let (r, c) = qs.remove(at: 0) 67 guard next(r, c, &d) == false else { 68 //print(v) 69 return ans 70 } 71 } 72 ans += 1 73 qs = Array(d.values) 74 } 75 76 return ans 77 } 78 } 484ms 1 class Solution { 2 struct Coor { 3 var x:Int; 4 var y:Int; 5 } 6 var visited:[[Bool]] = [[Bool]](); 7 var grids:[[Int]]!; 8 func shortestBridge(_ A: [[Int]]) -> Int { 9 var step:Int = -1; 10 grids = A; 11 for i in 0 ..< A.count{ 12 let oneRow = Array<Bool>(repeating: false, count: A[i].count); 13 visited.append(oneRow); 14 } 15 var i = 0; 16 var j = 0; 17 for ii in 0 ..< A.count{ 18 for jj in 0 ..< A[ii].count{ 19 if (A[ii][jj] == 1){ 20 i = ii; 21 j = jj; 22 break; 23 } 24 } 25 } 26 let island_A = completeThisIsland(x: i, y: j); 27 // resetVisited() 28 var queue = Array<Coor>(); 29 var steps = Array<Int>(repeating: 0, count: island_A.count); 30 queue.append(contentsOf: island_A); 31 var found = false; 32 while (!found){ 33 let co = queue.removeFirst(); 34 let thisStep = steps.removeFirst(); 35 let neighbors = [Coor(x: co.x-1, y: co.y),Coor(x: co.x+1, y: co.y),Coor(x: co.x, y: co.y+1),Coor(x:co.x,y:co.y-1)]; 36 for neighbor in neighbors{ 37 if valid(coor: neighbor) && !visited[neighbor.x][neighbor.y]{ 38 if grids[neighbor.x][neighbor.y] == 1{ 39 step = thisStep; 40 found = true; 41 break; 42 }else{ 43 queue.append(neighbor) 44 steps.append(thisStep+1) 45 visited[neighbor.x][neighbor.y] = true; 46 } 47 // queue.append(neighbor); 48 // visited[neighbor.x][neighbor.y] = true; 49 } 50 } 51 } 52 53 return step; 54 } 55 func resetVisited() -> Void { 56 for var i in visited{ 57 for j in 0 ..< i.count{ 58 i[j] = false; 59 } 60 } 61 } 62 func valid(coor:Coor) -> Bool { 63 return coor.x > -1 && coor.x < grids.count && coor.y > -1 && coor.y < grids[coor.x].count; 64 } 65 func completeThisIsland(x:Int,y:Int) -> [Coor] { 66 var result = [Coor](); 67 var queue = [Coor](); 68 queue.append(Coor(x: x, y: y)) 69 visited[x][y] = true; 70 while(!queue.isEmpty){ 71 let co = queue.removeFirst(); 72 // visited[co.x][co.y] = true; 73 result.append(co); 74 let neighbors = [Coor(x: co.x-1, y: co.y),Coor(x: co.x+1, y: co.y),Coor(x: co.x, y: co.y+1),Coor(x:co.x,y:co.y-1)]; 75 for neighbor in neighbors{ 76 if valid(coor: neighbor) && grids[neighbor.x][neighbor.y] == 1 && !visited[neighbor.x][neighbor.y]{ 77 queue.append(neighbor); 78 visited[neighbor.x][neighbor.y] = true; 79 } 80 } 81 } 82 return result; 83 } 84 } 624ms 1 class Solution { 2 func shortestBridge(_ A: [[Int]]) -> Int { 3 var a = A 4 //print(A) 5 var edI = -1 6 var edJ = -1 7 for i in (0..<A.count) { 8 for j in (0..<A[i].count) { 9 if A[i][j] == 1 { 10 edI = i 11 edJ = j 12 break 13 } 14 } 15 if edI != -1 { break } 16 } 17 18 //print(edI, edJ) 19 bfs(&a, edI, edJ) 20 21 for i in (0..<a.count) { 22 for j in (0..<a[i].count) { 23 if a[i][j] == 1 { 24 a[i][j] = -2 25 } 26 } 27 } 28 //print(a) 29 30 return dfs(&a, edI, edJ) - 1 31 } 32 33 func bfs(_ A: inout [[Int]], _ i: Int, _ j: Int) { 34 A[i][j] = -1 35 if i+1 < A.count && A[i+1][j] == 1 { 36 A[i+1][j] = -1 37 bfs(&A, i+1, j) 38 } 39 40 if j + 1 < A[i].count && A[i][j+1] == 1 { 41 A[i][j+1] = -1 42 bfs(&A, i, j+1) 43 } 44 45 if i > 0 && A[i-1][j] == 1 { 46 A[i-1][j] = -1 47 bfs(&A, i-1, j) 48 } 49 全部评论
专题导读
热门推荐
热门话题
阅读排行榜
|
请发表评论