Swift solution - DFS, BFS


  • 0
    class Solution {
        let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        
        func pacificAtlantic_BFS(_ matrix: [[Int]]) -> [[Int]] {
            if matrix.count == 0 || matrix[0].count == 0 {
                return [[Int]]()
            }
            
            let n = matrix.count
            let m = matrix[0].count
            var result = [[Int]]()
            var pacific = [[Bool]](repeatElement([Bool](repeatElement(false, count: m)), count: n))
            var atlantic = [[Bool]](repeatElement([Bool](repeatElement(false, count: m)), count: n))
            var pQueue = [[Int]]()
            var aQueue = [[Int]]()
            
            for i in 0..<n {
                pQueue.append([i, 0])
                aQueue.append([i, m - 1])
                pacific[i][0] = true
                atlantic[i][m - 1] = true
            }
            for i in 0..<m {
                pQueue.append([0, i])
                aQueue.append([n - 1, i])
                pacific[0][i] = true
                atlantic[n - 1][i] = true
            }
            BFS(matrix, pQueue, &pacific)
            BFS(matrix, aQueue, &atlantic)
            for i in 0..<n {
                for j in 0..<m {
                    if pacific[i][j] && atlantic[i][j] {
                        result.append([i, j])
                    }
                }
            }
            
            return result
        }
        
        private func BFS(_ matrix: [[Int]], _ queue: [[Int]], _ visited: inout [[Bool]]) {
            let n = matrix.count
            let m = matrix[0].count
            var queue = queue
            
            while !queue.isEmpty {
                let current = queue.removeFirst()
                for direction in self.directions {
                    let x = current[0] + direction[0]
                    let y = current[1] + direction[1]
                    if x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || matrix[x][y] < matrix[current[0]][current[1]] {
                        continue
                    }
                    visited[x][y] = true
                    queue.append([x, y])
                }
            }
        }
        
        func pacificAtlantic_DFS(_ matrix: [[Int]]) -> [[Int]] {
            if matrix.count == 0 || matrix[0].count == 0 {
                return [[Int]]()
            }
            
            let n = matrix.count
            let m = matrix[0].count
            var result = [[Int]]()
            var pacific = [[Bool]](repeatElement([Bool](repeatElement(false, count: m)), count: n))
            var atlantic = [[Bool]](repeatElement([Bool](repeatElement(false, count: m)), count: n))
            
            for i in 0..<n {
                DFS(matrix, Int.min, i, 0, &pacific)
                DFS(matrix, Int.min, i, m - 1, &atlantic)
            }
            for i in 0..<m {
                DFS(matrix, Int.min, 0, i, &pacific)
                DFS(matrix, Int.min, n - 1, i, &atlantic)
            }
            for i in 0..<n {
                for j in 0..<m {
                    if pacific[i][j] && atlantic[i][j] {
                        result.append([i, j])
                    }
                }
            }
            
            return result
        }
        
        private func DFS(_ matrix: [[Int]], _ height: Int, _ x: Int, _ y: Int, _ visited: inout [[Bool]]) {
            let n = matrix.count
            let m = matrix[0].count
            if x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || matrix[x][y] < height {
                return
            }
            visited[x][y] = true
            for direction in self.directions {
                DFS(matrix, matrix[x][y], x + direction[0], y + direction[1], &visited)
            }
        }
    }
    

Log in to reply
 

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