Swift, using dfs to find connection


  • 0
    X

    Use 2 matrixes to record which grid could connect FROM ocean,
    we use 'inout' to pass the array by reference while in dfs function;

    class Solution {
        var result = [[Int]]()
        func pacificAtlantic(_ matrix: [[Int]]) -> [[Int]] {
            if matrix.count == 0 { return result }
            let maxY = matrix.count, maxX = matrix[0].count
            
            //use 2 matrixes to record those "able to connect to ocean" grides; 
            var markPac = [[Bool]](repeating: [Bool](repeating:false, count: maxX), count: maxY)
            var markAtl = [[Bool]](repeating: [Bool](repeating:false, count: maxX), count: maxY)
            
            for y in 0...(maxY-1) {
                dfs(matrix, Int(UInt8.min), y, 0, maxY, maxX, &markPac)
                dfs(matrix, Int(UInt8.min), y, maxX-1, maxY, maxX, &markAtl)
            }
            for x in 0...(maxX-1) {
                dfs(matrix, Int(UInt8.min), 0, x, maxY, maxX, &markPac)
                dfs(matrix, Int(UInt8.min), maxY-1, x, maxY, maxX, &markAtl)
            }
            // mark into result: 
            for y in 0...(maxY-1) {
                for x in 0...(maxX-1) {
                    if markPac[y][x], markAtl[y][x] { result.append( [y,x] ) }
                }
            }
            return result
        }
    
        func dfs(_ m: [[Int]], _ preHight:Int, _ y:Int, _ x:Int, _ maxY:Int, _ maxX:Int, _ ocean:inout [[Bool]]) {
            if y < 0 || x < 0 || y >= maxY || x >= maxX || ocean[y][x] || m[y][x] < preHight { return }
            ocean[y][x] = true;
            dfs(m, m[y][x], y-1, x, maxY, maxX, &ocean)
            dfs(m, m[y][x], y+1, x, maxY, maxX, &ocean)
            dfs(m, m[y][x], y, x+1, maxY, maxX, &ocean)
            dfs(m, m[y][x], y, x-1, maxY, maxX, &ocean)
        }
        
    }
    

Log in to reply
 

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