# Swift solution - Union Find, DFS, BFS

• ``````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()
[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 {
}
}
}
}

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
}
}
``````

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