代码随想录算法训练营第57天 | 99.岛屿数量 深搜 、99.岛屿数量 广搜 、100.岛屿的最大面积

99.岛屿数量 深搜
注意深搜的两种写法，熟练掌握这两种写法 以及 知道区别在哪里，才算掌握的深搜。
https://www.programmercarl.com/kamacoder/0099.岛屿的数量深搜.html

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let res = 0;
    for (let i=0;i<grid.length;i++) {
        for (let j=0;j<grid[0].length;j++) {
            if (grid[i][j] === '1') {
                res++;
                dfs(grid, i, j);
            }
        }
    }
    return res;
};

const dfs = (grid, row, col) => {
    const nr = grid.length;
    const nc = grid[0].length;
    if (!inArea(grid, row, col)) {
        return;
    }
    if (grid[row][col] !== '1') {
        return;
    }
    grid[row][col] = '2';
    dfs(grid, row - 1, col);
    dfs(grid, row + 1, col);
    dfs(grid, row, col - 1);
    dfs(grid, row, col + 1);
}

function inArea(grid, row, col) {
    return 0<=row&&row < grid.length && 0<=col && col < grid[0].length;
}

99.岛屿数量 广搜
注意广搜的两种写法，第一种写法为什么会超时， 如果自己做的录友，题目通过了，也要仔细看第一种写法的超时版本，弄清楚为什么会超时，因为你第一次 幸运 没那么想，第二次可就不一定了。
https://www.programmercarl.com/kamacoder/0099.岛屿的数量广搜.html

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let count = 0;
    for (let i=0;i<grid.length;i++) {
        for (let j =0;j<grid[0].length;j++) {
            if (grid[i][j]==='1') {
                bfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
};

function bfs(grid, row, col) {
    const queue = [];
    queue.push([row, col]);
    while(queue.length > 0) {
        const item = queue.pop();
        let newR = item[0];
        let newC = item[1];
        if (0<=newR && newR < grid.length && 0<= newC && newC < grid[0].length && grid[newR][newC] === '1') {
            grid[newR][newC] = '2';
            queue.push([newR + 1, newC]);
            queue.push([newR - 1, newC]);
            queue.push([newR, newC + 1]);
            queue.push([newR, newC - 1]);
        }
    }
}

100.岛屿的最大面积
本题就是基础题了，做过上面的题目，本题很快。
https://www.programmercarl.com/kamacoder/0100.岛屿的最大面积.html

function dfs(grid, row, col) {
    if (row >= grid.length || row < 0 || col >= grid[0].length || col<0 || grid[row][col] != '1') {
        return 0;
    }
    let sum = 1;
    console.log(sum)
    grid[row][col] = '2';
    sum += dfs(grid, row+1, col);
    sum += dfs(grid, row-1, col);
    sum += dfs(grid, row, col-1);
    sum += dfs(grid, row, col+1);
    
    return sum;
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    let maxArea = 0;
    for (let i=0;i<grid.length;i++) {
        for (let j=0;j<grid[0].length;j++) {
            if (grid[i][j] == '1') {
                let sum = dfs(grid, i, j);
                maxArea = Math.max(sum, maxArea);
            }
        }
    }
    return maxArea;
};