1.深搜

func numIslands(_ grid: [[Character]]) -> Int {
        var visit = Array.init(repeating: Array.init(repeating: false, count: grid[0].count), count: grid.count)
        var count = 0
        for i in 0..<grid.count {
            for j in 0..<grid[0].count {
                if grid[i][j] == "1" && !visit[i][j] {
                    count += 1
                    dfs(grid, &visit, i, j)
                }
            }
        }
        return count
    }
    
    func dfs(_ grid: [[Character]],_ visit:inout [[Bool]],_ x:Int,_ y:Int) {
        if grid[x][y] == "0" {
            return
        }
        
        if visit[x][y] {
            return
        }
        
        visit[x][y] = true
        
        let directions = [[1,0],[-1,0],[0,1],[0,-1]]
        for dir in directions {
            let newX = x+dir[0]
            let newY = y+dir[1]
            if newX>=0 && newX<grid.count && newY>=0 && newY<grid[0].count && !visit[newX][newY] {
                dfs(grid, &visit, newX, newY)
            }
        }
    }

2.宽搜

func numIslands(_ grid: [[Character]]) -> Int {
        var visit = Array.init(repeating: Array.init(repeating: false, count: grid[0].count), count: grid.count)
        var count = 0
        var queue = [[Int]]()
        
        for i in 0..<grid.count {
            for j in 0..<grid[0].count {
                if grid[i][j] == "1" && !visit[i][j] {
                    count += 1
                    queue.append([i,j])
                    bfs(grid, &visit,&queue)
                }
            }
        }
        return count
    }
    
    func bfs(_ grid: [[Character]],_ visit:inout [[Bool]],_ queue:inout [[Int]]) {
        let directions = [[1,0],[-1,0],[0,1],[0,-1]]
        
        while !queue.isEmpty {
            let first = queue.removeFirst()
            let x = first[0]
            let y = first[1]
                
            if grid[x][y] == "0" {
                continue
            }
            
            if visit[x][y] {
                continue
            }
            
            visit[x][y] = true
                
            for dir in directions {
                let newX = x+dir[0]
                let newY = y+dir[1]
                if newX>=0 && newX<grid.count && newY>=0 && newY<grid[0].count && !visit[newX][newY] {
                    queue.append([newX,newY])
                }
            }
        }
        
    }

3. 并查集

class UnionFind: NSObject {
        var parent:[Int]!
        var count = 0
        var rank:[Int]!
        
        public init(_ grid:[[Character]]) {
            let m = grid.count
            let n = grid[0].count
            
            parent = Array.init(repeating: 0, count: m*n)
            rank = Array.init(repeating: 0, count: m*n)

            for i in 0..<grid.count {
                for j in 0..<grid[0].count {
                    if grid[i][j] == "1" {
                        parent[i*n+j] = i*n+j
                        count += 1
                    }
                    rank[i*n+j] = 0
                }
            }
        }
        
        func find(_ x:Int) -> Int {
            var x1 = x
            while x1 != parent[x1] {
                x1 = parent[x1]
            }
            return x1
        }
        
        func union(_ x:Int,_ y:Int) {
            let rootx = find(x)
            let rooty = find(y)
            
            if rootx != rooty {
                if rank[rootx] > rank[rooty] {
                    parent[rooty] = rootx
                }else if rank[rootx] < rank[rooty]{
                    parent[rootx] = rooty
                }else{
                    parent[rooty] = rootx
                    rank[rootx] += 1
                }
                count -= 1
            }
        }
    }
    
    func numIslands(_ oldGrid: [[Character]]) -> Int {
        if oldGrid.count == 0 || oldGrid[0].count == 0 {
            return 0
        }
        var grid = oldGrid
        
        let nr = grid.count
        let nc = grid[0].count
        
        let uf = UnionFind.init(grid)
        
        let directions = [[-1,0],[1,0],[0,1],[0,-1]]
        
        for i in 0..<nr {
            for j in 0..<nc {
                if grid[i][j] == "1" {
                    grid[i][j] = "0"
                    
                    for dir in directions {
                        let newx = i+dir[0]
                        let newy = j+dir[1]
                        if newx>=0 && newx<grid.count && newy>=0 && newy<grid[0].count && grid[newx][newy] == "1" {
                            uf.union(i*nc+j, newx*nc+newy)
                        }
                    }
                    
                }
            }
        }
        return uf.count
    }

4.路径优化并查集

func find(_ x:Int,_ parent:[Int]) -> Int {
        var x1 = x
        while parent[x1] != x1 {
            x1 = parent[x1]
        }
        return x1
    }
    
    func union(_ i:Int,_ j:Int,_ parent:inout [Int],_ count:inout Int) {
        let x1 = find(i, parent)
        let y1 = find(j, parent)
        if x1 != y1 {//合并
            parent[x1] = y1
            count -= 1
        }
    }
    /*
     1. 访问过的状态置为0
     2. 在区间范围内，且是1可以连通
     */
    func numIslands(_ grid: [[Character]]) -> Int {
        let row = grid.count
        let col = grid[0].count
        
        var count = 0//记录1的个数
        var parent:[Int] = Array.init(repeating: 0, count: row*col)

        for i in 0..<row {
            for j in 0..<col {
                if grid[i][j] == "1" {
                    count += 1
                }
                parent[i*col+j] = i*col+j
            }
        }
        
        let directions = [[-1,0],[1,0],[0,1],[0,-1]]
        var grid = grid
        
        for i in 0..<row {
            for j in 0..<col {
                if grid[i][j] == "1" {
                    grid[i][j] = "0"
                    for dir in directions {
                        let newX = i+dir[0]
                        let newY = j+dir[1]
                        if newX>=0 && newX<row && newY>=0 && newY<col && grid[newX][newY] == "1"{
                            union(i*col+j, newX*col+newY, &parent,&count)
                        }
                    }
                }
            }
        }
        return count
    }