695. Max Area of Island

Max Area of Island - LeetCode

Algorithm - array, dfs

种子填充法

class Solution {
    let steps = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    var maxNum = 0
    
    func dfs(x: Int, y: Int, grid: inout [[Int]], canUse: inout [[Bool]], num: inout Int) {
        maxNum = max(maxNum, num)
        
        for step in steps {
            let tx = step[0] + x
            let ty = step[1] + y
            if 0 <= tx && tx < grid.count && 0 <= ty && ty < grid[0].count && grid[tx][ty] == 1 && canUse[tx][ty] {
                canUse[tx][ty] = false
                num += 1
                dfs(x: tx, y: ty, grid: &grid, canUse: &canUse, num: &num)
            }
        }
    }
    
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        guard grid.count > 0 else {
            return 0
        }
        
        let a: [Bool] = Array(repeating: true, count: grid[0].count)
        var canUse: [[Bool]] = Array(repeating: a, count: grid.count)
        
        var g = grid
        
        maxNum = 0
        
        for i in 0..<grid.count {
            for j in 0..<grid[i].count {
                if grid[i][j] == 1 && canUse[i][j] {
                    var num = 1
                    canUse[i][j] = false
                    dfs(x: i, y: j, grid: &g, canUse: &canUse, num: &num)
                }
            }
        }
        
        return maxNum
    }
}