ac solution code


  • 0
    /*
         * Solutio1. Mine. DFS - O(mn) O(mn)
         The basic idea is using DFS to found all independent connecting areas with '1' in a graph.
         Time complexity=O(mn), because every point in the grid is only checked once approximately.
    
         */
        func numIslands1(_ grid: [[Character]]) -> Int {
            var number = 0
            let directions = [CGPoint(x: 0, y: 1), CGPoint(x: 0, y: -1), CGPoint(x: 1, y: 0), CGPoint(x: -1, y: 0)]
            if grid.count == 0 || grid[0].count == 0 {
                return 0
            }
            let n = grid.count, m = grid[0].count
            let oneGrid = [Bool](repeating: false, count: m)
            var visited = [[Bool]](repeating: oneGrid, count: n)
            for i in 0 ..< n {
                for j in 0 ..< m {
                    if !visited[i][j] && grid[i][j] == "1" {// Found new island
                        number += 1
                        DFS(grid, i, j, &visited, directions)// Use DFS to connect all "1" nodes on this island, mark as visited
                    }
                }
            }
            return number
        }
        // DFS on one island
        func DFS(_ grid: [[Character]], _ i: Int, _ j: Int, _ visited: inout [[Bool]], _ directions: [CGPoint]) {
            if i < 0 || i > grid.count - 1 || j < 0 || j > grid[0].count - 1 { return }
            if visited[i][j] || grid[i][j] != "1" { return }// Visited
            visited[i][j] = true
            for direction in directions {// expend on 4 adjacent directions to connect "1" nodes
                DFS(grid, i + Int(direction.y), j + Int(direction.x), &visited, directions)
            }
        }
    
        /*
         Solution2. DFS Non-Recursive with Stack - Runtime =O(mn); Space = O(mn) - stack
         Set 'v' to visited node in grid, to spare the space for 'visited' array.
         */
        func numIslands(_ grid: [[Character]]) -> Int {
            if grid.count == 0 {return 0}
            var grid = grid
            var res = 0, n = grid.count, m = grid[0].count
            let directions = [CGPoint(x: 0, y: 1), CGPoint(x: 0, y: -1), CGPoint(x: 1, y: 0), CGPoint(x: -1, y: 0)]
    
            for i in 0 ..< n {
                for j in 0 ..< m {
                    if grid[i][j] == "1" && grid[i][j] != "v" {// Found new island
                        res += 1
                        DFS(&grid, i, j, directions)// Use DFS to connect all "1" nodes on this island, mark as visited
                    }
                }
            }
            return res
        }
        // DFS on one island
        func DFS(_ grid: inout [[Character]], _ iIn: Int, _ jIn: Int, _ directions: [CGPoint]) {// Set 'v' to visited node in grid
            var stack = Stack<CGPoint>()
    
            stack.push(CGPoint(x: CGFloat(iIn), y: CGFloat(jIn)))
            while !stack.isEmpty() {
                let node = stack.pop()!
                let i = Int(node.x), j = Int(node.y)
                if i < 0 || i > grid.count - 1 || j < 0 || j > grid[0].count - 1 {// Exceed bounds of grids
                    continue
                }
                if grid[i][j] == "v" || grid[i][j] == "0" {// Visited or water
                    continue
                }
                grid[i][j] = "v"
                for direction in directions {// DFS: Extend to 4 directions
                    let x = CGFloat(i) + direction.x
                    let y = CGFloat(j) + direction.y
                    stack.push(CGPoint(x: x, y: y ))
                }
            }
        }
    

    0_1485724988312_Evernote Camera Roll 20170129 131847.jpg


Log in to reply
 

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