Given a 2D board containing ‘X‘
and ‘O‘
(the letter O),capture all regions surrounded by ‘X‘
.
A region is captured by flipPing all ‘O‘
s into ‘X‘
s in that surrounded region.
Example:
X X X XX O O XX X O XX O X X
After running your function,the board should be:
X X X XX X X XX X X XX O X X
Explanation:
Surrounded regions shouldn’t be on the border,which means that any ‘O‘
on the border of the board are not flipped to ‘X‘
. Any ‘O‘
that is not on the border and it is not connected to an ‘O‘
on the border will be flipped to ‘X‘
. Two cells are connected if they are adjacent cells connected horizontally or vertically.
给定一个二维的矩阵,包含 ‘X‘
和 ‘O‘
(字母 O)。
找到所有被 ‘X‘
围绕的区域,并将这些区域里所有的 ‘O‘
用 ‘X‘
填充。
示例:
X X X XX O O XX X O XX O X X
运行你的函数后,矩阵变为:
X X X XX X X XX X X XX O X X
解释:
被围绕的区间不会存在于边界上,换句话说,任何边界上的 ‘O‘
都不会被填充为 ‘X‘
。 任何不在边界上,或不与边界上的 ‘O‘
相连的 ‘O‘
最终都会被填充为 ‘X‘
。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
52ms
1 class Solution { 2 func solve(_ board: inout [[Character]]) { 3 let h = board.count 4 guard h > 2 else { return } 5 6 let w = board[0].count 7 guard w > 2 else { return } 8 9 for i in 0..<h {10 mark(&board,i,0)11 mark(&board,w - 1)12 }13 14 for j in 0..<w {15 mark(&board,0,j)16 mark(&board,h - 1,j)17 }18 19 for i in 0..<h {20 for j in 0..<w {21 if board[i][j] == "O" {22 board[i][j] = "X"23 } else if board[i][j] == "T" {24 board[i][j] = "O"25 }26 }27 }28 }29 30 func mark(_ board: inout [[Character]],_ i: Int,_ j: Int) {31 guard i >= 0 && i < board.count else { return }32 guard j >= 0 && j < board[i].count else { return }33 guard board[i][j] == "O" else { return }34 35 board[i][j] = "T"36 37 mark(&board,i - 1,j)38 mark(&board,i + 1,j)39 mark(&board,j - 1)40 mark(&board,j + 1)41 }42 }
56ms
1 class Solution { 2 func solve(_ board: inout [[Character]]) { 3 for i in 0..<board.count { 4 for j in 0..<board[i].count { 5 if (i == 0 || i == board.count - 1 || j == 0 || j == board[i].count - 1) && board[i][j] == "O" { 6 dfs(&board,j) 7 } 8 9 }10 }11 for i in 0..<board.count {12 for j in 0..<board[i].count {13 if board[i][j] == "O" {14 board[i][j] = "X"15 }16 if board[i][j] == "Y" {17 board[i][j] = "O"18 }19 }20 }21 }22 private func dfs(_ board: inout [[Character]],_ j: Int) {23 if board[i][j] == "O" {24 25 board[i][j] = "Y"26 if i > 0 && board[i - 1][j] == "O" {27 dfs(&board,j)28 }29 30 if j < board[i].count - 1 && board[i][j + 1] == "O" {31 dfs(&board,j + 1)32 }33 34 if i < board.count - 1 && board[i + 1][j] == "O" {35 dfs(&board,j)36 }37 38 if j > 0 && board[i][j - 1] == "O" {39 dfs(&board,j - 1)40 }41 }42 }43 }
60ms
1 class Solution { 2 func solve(_ board: inout [[Character]]) { 3 guard board.count > 0 && board[0].count > 0 else { 4 return 5 } 6 7 let countRow = board.count - 1 8 let countCol = board[0].count - 1 9 10 var visited = [[Bool]](repeating:[Bool](repeating: false,count: countCol+1),count: countRow+1)11 var boarder0Indexs = [(Int,Int)]()12 13 let direction = [(-1,0),(1,(0,-1),1)] // top bot left right14 15 for row in 0...countRow {16 for col in 0...countCol {17 if row == 0 || col == 0 || row == countRow || col == countCol {18 if board[row][col] == "O" {19 board[row][col] = "B"20 boarder0Indexs.append((row,col))21 } 22 }23 }24 }25 26 for item in boarder0Indexs {27 let row = item.028 let col = item.129 30 var tempQueue = [(Int,Int)]()31 tempQueue.append(item)32 33 //bfs34 while (!tempQueue.isEmpty) {35 let count = tempQueue.count36 for _ in 0..<count {37 let curItem = tempQueue.removeFirst()38 let curRow = curItem.039 let curCol = curItem.140 //check adjacent cells 41 for dirt in direction {42 let nextLevelRow = curRow + dirt.043 let nextLevelCol = curCol + dirt.1 44 //make sure not out of bounce45 if nextLevelRow <= countRow && nextLevelRow >= 0 && nextLevelCol <= countCol && nextLevelCol >= 0 {46 if !visited[nextLevelRow][nextLevelCol] {47 if board[nextLevelRow][nextLevelCol] == "O" {48 board[nextLevelRow][nextLevelCol] = "B"49 tempQueue.append((nextLevelRow,nextLevelCol))50 } 51 visited[nextLevelRow][nextLevelCol] = true52 } 53 } 54 }55 }56 } 57 }58 for i in 0...countRow {59 for j in 0...countCol {60 if board[i][j] == "B" {61 board[i][j] = "O"62 } else if board[i][j] == "O" {63 board[i][j] = "X"64 }65 }66 }67 }68 }
80ms
1 class Solution { 2 func solve(_ board: inout [[Character]]) { 3 for i in 0..<board.count{ 4 for j in 0..<board[0].count{ 5 if (i==0 || i == board.count - 1 || j == 0 || j == board[0].count - 1) && board[i][j] == "O" { 6 board[i][j] = "M" 7 connected(i,j,&board) 8 } 9 }10 }11 for i in 0..<board.count{12 for j in 0..<board[0].count{13 if board[i][j] == "O" {14 board[i][j] = "X"15 }16 else if board[i][j] == "M" {17 board[i][j] = "O"18 } 19 }20 }21 }22 private func connected(_ i : Int,_ j : Int,_ board: inout [[Character]]){23 if i-1 > 0 && board[i-1][j] == "O" {24 board[i-1][j] = "M"25 connected(i-1,&board)26 }27 if i+1 < board.count-1 && board[i+1][j] == "O" {28 board[i+1][j] = "M"29 connected(i+1,&board)30 }31 if j-1 > 0 && board[i][j-1] == "O" {32 board[i][j-1] = "M"33 connected(i,j-1,&board)34 }35 if j+1 < board[i].count-1 && board[i][j+1] == "O" {36 board[i][j+1] = "M"37 connected(i,j+1,&board)38 }39 }40 }
176ms
1 let X = Character("X") 2 let O = Character("O") 3 4 class Solution { 5 6 func solve(_ board: inout [[Character]]) { 7 guard let columnCount = board.first?.count else { 8 return 9 } 10 let rowCount = board.count 11 let uf = UnionFind(rowCount: rowCount,columnCount: columnCount) 12 13 board.enumerated().forEach { i,row in 14 row.enumerated().forEach { j,item in 15 guard item == O else { 16 return 17 } 18 19 if i == 0 || i == rowCount - 1 || j == 0 || j == columnCount - 1 { 20 uf.open(i,j) 21 } 22 23 // top 24 if i > 0 && board[i - 1][j] == O { 25 uf.union(i,j) 26 } 27 28 // bottom 29 if i < rowCount - 1 && board[i + 1][j] == O { 30 uf.union(i,j) 31 } 32 33 // left 34 if j > 0 && board[i][j - 1] == O { 35 uf.union(i,j - 1) 36 } 37 38 // right 39 if j < columnCount - 1 && board[i][j + 1] == O { 40 uf.union(i,j + 1) 41 } 42 } 43 } 44 45 for i in 0..<rowCount { 46 for j in 0..<columnCount where board[i][j] == O { 47 if !uf.isOpen(i,j) { 48 board[i][j] = X 49 } 50 } 51 } 52 } 53 54 } 55 56 class UnionFind { 57 58 var parent: [Int] 59 var sizes: [Int] 60 61 private let rowCount: Int 62 private let columnCount: Int 63 64 private var opened: [Bool] 65 66 init(rowCount: Int,columnCount: Int) { 67 self.rowCount = rowCount 68 self.columnCount = columnCount 69 70 let count = rowCount * columnCount 71 72 sizes = Array(repeating: 1,count: count) 73 parent = Array(repeating: 0,count: count) 74 opened = Array(repeating: false,count: count) 75 76 for i in 0..<count { 77 parent[i] = i 78 } 79 } 80 81 func isOpen(_ i: Int,_ j: Int) -> Bool { 82 return opened[find(i,j)] 83 } 84 85 func open(_ i: Int,_ j: Int) { 86 let index = calculateIndex(i,j) 87 opened[index] = true 88 } 89 90 func union(_ li: Int,_ lj: Int,_ ri: Int,_ rj: Int) { 91 let rootleft = find(li,lj) 92 let rootRight = find(ri,rj) 93 94 if li == 0 || li == rowCount - 1 || lj == 0 || lj == columnCount - 1 { 95 open(li,lj) 96 } 97 if ri == 0 || ri == rowCount - 1 || rj == 0 || rj == columnCount - 1 { 98 open(ri,rj) 99 }100 101 if rootleft == rootRight {102 return103 }104 105 if opened[rootleft] {106 parent[rootRight] = parent[rootleft]107 sizes[rootleft] += sizes[rootRight]108 return109 }110 if opened[rootRight] {111 parent[rootleft] = parent[rootRight]112 sizes[rootRight] += sizes[rootleft]113 return114 }115 116 if sizes[rootleft] > sizes[rootRight] {117 parent[rootRight] = parent[rootleft]118 sizes[rootleft] += sizes[rootRight]119 } else {120 parent[rootleft] = parent[rootRight]121 sizes[rootRight] += sizes[rootleft]122 }123 }124 125 func find(_ i: Int,_ j: Int) -> Int {126 var index = calculateIndex(i,j)127 while index != parent[index] {128 parent[index] = parent[parent[index]]129 index = parent[index]130 }131 return index132 }133 134 private func calculateIndex(_ i: Int,_ j: Int) -> Int {135 return i * columnCount + j136 }137 }
316ms
1 class Solution { 2 func solve(_ board: inout [[Character]]) { 3 for i in 0..<board.count 4 { 5 for j in 0..<board[i].count 6 { 7 if (i == 0 || i == board.count - 1 || j == 0 || j == board[i].count - 1) && board[i][j] == "O" 8 { 9 solveDFS(&board,j)10 }11 }12 }13 for i in 0..<board.count14 {15 for j in 0..<board[i].count16 {17 if board[i][j] == "O" {board[i][j] = "X"}18 if board[i][j] == "$" {board[i][j] = "O"}19 }20 }21 }22 23 func solveDFS(_ board: inout [[Character]],_ i:Int,_ j:Int)24 {25 if board[i][j] == "O"26 {27 board[i][j] = "$"28 if i > 0 && board[i - 1][j] == "O"29 {30 solveDFS(&board,j)31 }32 if j < board[i].count - 1 && board[i][j + 1] == "O"33 {34 solveDFS(&board,j + 1)35 }36 if i < board.count - 1 && board[i + 1][j] == "O"37 {38 solveDFS(&board,j)39 }40 if j > 1 && board[i][j - 1] == "O"41 {42 solveDFS(&board,j - 1)43 }44 }45 }46 }总结
以上是内存溢出为你收集整理的[Swift]LeetCode130. 被围绕的区域 | Surrounded Regions全部内容,希望文章能够帮你解决[Swift]LeetCode130. 被围绕的区域 | Surrounded Regions所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)