Swift solution - Union Find, DFS, BFS


  • 0
    class Solution {
        func solve(_ board: inout [[Character]]) {
            if board.count == 0 || board[0].count == 0 {
                return
            }
            
            let row = board.count
            let col = board[0].count
            
            for i in 0..<row {
                check(&board, i, 0, row, col)
                if col > 1 {
                    check(&board, i, col - 1, row, col)
                }
            }
            if col > 1 {
                for j in 1..<(col - 1) {
                    check(&board, 0, j, row, col)
                    if row > 1 {
                        check(&board, row - 1, j, row, col)
                    }
                }
            }
            for i in 0..<row {
                for j in 0..<col {
                    if board[i][j] == "O" {
                        board[i][j] = "X"
                    }
                }
            }
            for i in 0..<row {
                for j in 0..<col {
                    if board[i][j] == "#" {
                        board[i][j] = "O"
                    }
                }
            }
        }
        
        func check(_ board: inout [[Character]], _ i: Int, _ j: Int, _ row: Int, _ col: Int) {
            if board[i][j] == "O" {
                board[i][j] = "#"
                if i > 1 {
                    check(&board, i - 1, j, row, col)
                }
                if j > 1 {
                    check(&board, i, j - 1, row, col)
                }
                if i + 1 < row {
                    check(&board, i + 1, j, row, col)
                }
                if j + 1 < col {
                    check(&board, i, j + 1, row, col)
                }
            }
        }
        
        func solve_UnionFind(_ board: inout [[Character]]) {
            if board.count == 0 || board[0].count == 0 {
                return
            }
            
            let n = board.count
            let m = board[0].count
            let unionFind = UnionFind(n * m + 1)
            
            for i in 0..<n {
                for j in 0..<m {
                    if (i == 0 || i == (n - 1) || j == 0 || j == (m - 1)) && board[i][j] == "O" {
                        unionFind.union(i * m + j, n * m)
                    } else if board[i][j] == "O" {
                        if board[i - 1][j] == "O" {
                            unionFind.union(i * m + j, (i - 1) * m + j)
                        }
                        if board[i + 1][j] == "O" {
                            unionFind.union(i * m + j, (i + 1) * m + j)
                        }
                        if board[i][j - 1] == "O" {
                            unionFind.union(i * m + j, i * m + j - 1)
                        }
                        if board[i][j + 1] == "O" {
                            unionFind.union(i * m + j, i * m + j + 1)
                        }
                    }
                }
            }
            
            for i in 0..<n {
                for j in 0..<m {
                    if !unionFind.connected(i * m + j, n * m) {
                        board[i][j] = "X"
                    }
                }
            }
        }
        
        func solve_BFS(_ board: inout [[Character]]) {
            if board.count == 0 || board[0].count == 0 {
                return
            }
            
            let width = board.count
            let length = board[0].count
            
            for i in 0..<length {
                if board[0][i] == "O" {
                    BFS(&board, 0, i)
                }
                if board[width - 1][i] == "O" {
                    BFS(&board, width - 1, i)
                }
            }
            for i in 0..<width {
                if board[i][0] == "O" {
                    BFS(&board, i, 0)
                }
                if board[i][length - 1] == "O" {
                    BFS(&board, i, length - 1)
                }
            }
            for i in 0..<width {
                for j in 0..<length {
                    if board[i][j] == "O" {
                        board[i][j] = "X"
                    } else if board[i][j] == "#" {
                        board[i][j] = "O"
                    }
                }
            }
        }
        
        func BFS(_ board: inout [[Character]], _ w: Int, _ l: Int) {
            let width = board.count
            let length = board[0].count
            var queue = [[Int]]()
            
            queue.append([w, l])
            board[w][l] = "#"
            while !queue.isEmpty {
                let current = queue.removeFirst()
                let adjs = [
                    [current[0] - 1, current[1]],
                    [current[0] + 1, current[1]],
                    [current[0], current[1] - 1],
                    [current[0], current[1] + 1],
                            ]
                for i in 0..<4 {
                    let adjW = adjs[i][0]
                    let adjL = adjs[i][1]
                    if (adjW >= 0) && (adjW < width) && (adjL >= 0) && (adjL < length) && (board[adjW][adjL] == "O") {
                        queue.append([adjW, adjL])
                        board[adjW][adjL] = "#"
                    }
                }
            }
        }
        
        func solve_DFS(_ board: inout [[Character]]) {
            if board.count == 0 || board[0].count == 0 {
                return
            }
            
            let m = board.count
            let n = board[0].count
            
            for i in 0..<m {
                if board[i][0] == "O" {
                    DFS(&board, i, 0)
                }
                if board[i][n - 1] == "O" {
                    DFS(&board, i, n - 1)
                }
            }
            for j in 0..<n {
                if board[0][j] == "O" {
                    DFS(&board, 0, j)
                }
                if board[m - 1][j] == "O" {
                    DFS(&board, m - 1, j)
                }
            }
            for i in 0..<m {
                for j in 0..<n {
                    if board[i][j] == "O" {
                        board[i][j] = "X"
                    } else if board[i][j] == "*" {
                        board[i][j] = "O"
                    }
                }
            }
        }
        
        func DFS(_ board: inout [[Character]], _ i: Int, _ j: Int) {
            if i < 0 || i > board.count - 1 || j < 0 || j > board[0].count - 1 {
                return
            }
            
            if board[i][j] == "O" {
                board[i][j] = "*"
            }
            if i > 1 && board[i - 1][j] == "O" {
                DFS(&board, i - 1, j)
            }
            if i < board.count - 2 && board[i + 1][j] == "O" {
                DFS(&board, i + 1, j)
            }
            if j > 1 && board[i][j - 1] == "O" {
                DFS(&board, i, j - 1)
            }
            if j < board[i].count - 2 && board[i][j + 1] == "O" {
                DFS(&board, i, j + 1)
            }
        }
    }
    
    public class UnionFind {
        var parent: [Int]
        var rank: [Int]
        var count: Int
        
        public init(_ n: Int) {
            self.count = n
            self.parent = [Int](repeatElement(0, count: n))
            self.rank = [Int](repeatElement(0, count: n))
            for i in 0..<n {
                self.parent[i] = i
                self.rank[i] = 0
            }
        }
        
        public func find(_ p: Int) -> Int {
            var p = p
            while p != self.parent[p] {
                self.parent[p] = self.parent[self.parent[p]]
                p = self.parent[p]
            }
            return p
        }
        
        public func getCount() -> Int {
            return self.count
        }
        
        public func connected(_ p: Int, _ q: Int) -> Bool {
            return find(p) == find(q)
        }
        
        public func union(_ p: Int, _ q: Int) {
            let i = find(p)
            let j = find(q)
            
            if i == j {
                return
            }
            if self.rank[i] < self.rank[j] {
                self.parent[i] = j
            } else if self.rank[i] > self.rank[j] {
                self.parent[j] = i
            } else {
                self.parent[j] = i
                self.rank[i] += 1
            }
            self.count -= 1
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.