岛屿系列问题

[TieMuZhen]

一、岛屿数量（LeetCode 200）

/**
 * @param {character[][]} grid
 * @return {number}
 */
let count;

function dfs(grid, row, col){
    if(row < 0 || row > grid.length - 1 || col < 0 || col > grid[0].length - 1 || grid[row][col] == "0"){
        return;
    }
    grid[row][col] = "0";
    dfs(grid, row - 1, col);
    dfs(grid, row + 1, col);
    dfs(grid, row, col - 1);
    dfs(grid, row, col + 1);
}

var numIslands = function(grid) {
    count = 0;
    for(let i = 0; i < grid.length; i++){
        for(let j = 0; j < grid[0].length; j++){
            if(grid[i][j] == "1"){
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
};

二、岛屿的周长（LeetCode 463）

/**
 * @param {number[][]} grid
 * @return {number}
 */
var dfs = function(grid, row, col){
    let count = 0;
    // 上
    if(row - 1 >= 0){
        if(grid[row - 1][col] == 0 && grid[row][col] == 1) count++;
    }else if(row == 0){
        if(grid[row][col] == 1) count++;
    }
    // 下
    if(row + 1 <= grid.length - 1){
        if(grid[row + 1][col] == 0 && grid[row][col] == 1) count++;
    }else if(row == grid.length - 1){
        if(grid[row][col] == 1) count++;
    }
    // 左
    if(col - 1 >= 0){
        if(grid[row][col - 1] == 0 && grid[row][col] == 1) count++;
    }else if(col == 0){
        if(grid[row][col] == 1) count++;
    }
    // 右
    if(col + 1 <= grid[0].length - 1){
        if(grid[row][col + 1] == 0 && grid[row][col] == 1) count++;
    }else if(col == grid[0].length - 1){
        if(grid[row][col] == 1) count++;
    }
    return count;
}
var islandPerimeter = function(grid) {
    let sum = 0;
    for(let i = 0; i < grid.length; i++){
        for(let j = 0; j < grid[0].length; j++){
            sum += dfs(grid, i, j);
        }
    }
    return sum;
};

三、岛屿的最大面积（LeetCode 695）

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    let maxLand = 0;

    function dfs(row, col){
        if(row < 0 || row > grid.length - 1 || col < 0 || col > grid[0].length - 1 || grid[row][col] == 0){
            return 0;
        }else{
            grid[row][col] = 0;
            return 1 + dfs(row - 1, col) + dfs(row + 1, col) + dfs(row, col - 1) + dfs(row, col + 1);
        }
    }

    for(let i = 0; i < grid.length; i++){
        for(let j = 0; j < grid[0].length; j++){
            maxLand = Math.max(maxLand, dfs(i, j));
        }
    }
    return maxLand;
};

四、不同岛屿的数量（LeetCode 694）

/**
 * @param {character[][]} grid
 * @return {number}
 */
function pushReturnArray(arr, data){
    // arr.push()返回值为arr长度，我们这里需要arr数组
    arr.push(data); 
    return arr;
}
function dfs(grid, row, col, arr){
    if(row < 0 || row > grid.length - 1 || col < 0 || col > grid[0].length - 1 || grid[row][col] == "0"){
        return;
    }
    grid[row][col] = "0"; // 标志走过的，防止重复访问
    dfs(grid, row - 1, col, pushReturnArray(arr, "up"));
    dfs(grid, row + 1, col, pushReturnArray(arr, "down"));
    dfs(grid, row, col - 1, pushReturnArray(arr, "left"));
    dfs(grid, row, col + 1, pushReturnArray(arr, "right"));
}

var numIslands = function(grid) {
    let set = new Set(); // 去重
    for(let i = 0; i < grid.length; i++){
        for(let j = 0; j < grid[0].length; j++){
            if(grid[i][j] == "1"){
                const arr = [];
                dfs(grid, i, j, arr);
                set.add(arr.join());
            }
        }
    }
    return Array.from(set).length;
};