秒杀所有岛屿题目|合集

463. 岛屿的周长

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function(grid) {
    let res=0;    
    let m=grid.length;
    let n=grid[0].length;
    //只需要计算海水和边界
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(grid[i][j]===1){
                if(i-1<0||grid[i-1][j]===0) res++;
                if(i+1==m||grid[i+1][j]===0) res++;
                if(j-1<0||grid[i][j-1]===0) res++;
                if(j+1==n||grid[i][j+1]===0) res++;

            }
        }
    }        
    return res;
};

200. 岛屿数量

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

    }
    return res;

};

function dfs(grid,i,j){
    let m=grid.length;
    let n=grid[0].length;
    //判断终止条件
    if(i<0||j>n-1||i>m-1||j<0){
        return;
    }
    if(grid[i][j]==='0'){
        return;
    }
    grid[i][j]='0';
    //上下左右进行深度遍历
    dfs(grid,i-1,j);
    dfs(grid,i+1,j);
    dfs(grid,i,j-1);
    dfs(grid,i,j+1);
    
}

1254. 统计封闭岛屿的数目

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

    }
    return res;



};

function dfs(grid,i,j){
    let m=grid.length;
    let n=grid[0].length;
    //判断终止条件
    if(i<0||j>n-1||i>m-1||j<0){
        return;
    }
    if(grid[i][j]===1){
        return;
    }
    grid[i][j]=1;
    //上下左右进行深度遍历
    dfs(grid,i-1,j);
    dfs(grid,i+1,j);
    dfs(grid,i,j-1);
    dfs(grid,i,j+1);
    
}

1020. 飞地的数量

/**
 * @param {number[][]} grid
 * @return {number}
 */
var numEnclaves = function(grid) {
    let m=grid.length;
    let n=grid[0].length;
    let res=0;
    //把上下左右都淹掉
const dfs=function(grid,i,j){
    let m=grid.length;
    let n=grid[0].length;
    //判断终止条件
    if(i<0||j>n-1||i>m-1||j<0){
        return;
    }
    if(grid[i][j]===0){
        return;
    }
    res++;
    grid[i][j]=0;
    //上下左右进行深度遍历
    dfs(grid,i-1,j);
    dfs(grid,i+1,j);
    dfs(grid,i,j-1);
    dfs(grid,i,j+1);
}
    for(let i=0;i<m;i++){
        if(grid[i][0]===1 ){
            dfs(grid,i,0);
        }
        
        if(grid[i][n-1]==1){
            dfs(grid,i,n-1);
        }        
    }
    for(let j=0;j<n;j++){
        if(grid[0][j]===1 ){
            dfs(grid,0,j);
        }
        
        if(grid[m-1][j]==1){
            dfs(grid,m-1,j);
        }        
    }    
    res=0;
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(grid[i][j]===1){
                dfs(grid,i,j);
            }
        }
    }
    return res;
};

1905. 统计子岛屿

/**
 * @param {number[][]} grid1
 * @param {number[][]} grid2
 * @return {number}
 */
var countSubIslands = function(grid1, grid2) {
    let m=grid1.length;
    let n=grid1[0].length;
    let res=0;
    //把上下左右都淹掉

const dfs=function(grid,i,j){
    let m=grid.length;
    let n=grid[0].length;
    //判断终止条件
    if(i<0||j>n-1||i>m-1||j<0){
        return;
    }
    if(grid[i][j]===0){
        return;
    }
    grid[i][j]=0;
    //上下左右进行深度遍历
    dfs(grid,i-1,j);
    dfs(grid,i+1,j);
    dfs(grid,i,j-1);
    dfs(grid,i,j+1);
}    

    //先把不是子岛屿的淹掉
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(grid1[i][j]===0&&grid2[i][j]===1){
                dfs(grid2,i,j);
            }
        }
    }
    //再统计
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(grid2[i][j]===1){
                res++;
                dfs(grid2,i,j);
            }
        }
    }    

    return res;
};

剑指 Offer II 105. 岛屿的最大面积

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    let m=grid.length;
    let n=grid[0].length;
    let count=0;
    let max=0;

const dfs=function(grid,i,j){
    let m=grid.length;
    let n=grid[0].length;
    //判断终止条件
    if(i<0||j>n-1||i>m-1||j<0){
        return;
    }
    if(grid[i][j]===0){
        return;
    }
    count++;
    grid[i][j]=0;
    //上下左右进行深度遍历
    dfs(grid,i-1,j);
    dfs(grid,i+1,j);
    dfs(grid,i,j-1);
    dfs(grid,i,j+1);
}    

    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(grid[i][j]===1){
                dfs(grid,i,j);
                if(count>max) max=count;
                count=0;
            }
        }
    }    

    return max;
};

剑指 Offer 12. 矩阵中的路径

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    if(word.length===0) return false;
    let m=board.length;
    let n=board[0].length;

    const dfs=(board,w,i,j)=>{
        if(w==="") return true;
        if(i<0||i>=m||j<0||j>=n) return false;//判断边界
        if(w[0]!=board[i][j]) return false;
        let temp=board[i][j];//暂存，以后还原
        board[i][j]="#";
        
        if(
            dfs(board,w.slice(1),i-1,j)||
            dfs(board,w.slice(1),i+1,j)||
            dfs(board,w.slice(1),i,j-1)||
            dfs(board,w.slice(1),i,j+1)
        )
        {   board[i][j]=temp;
            return true;
        }
        else{
            board[i][j]=temp;
            return false;
        }
        //注意要还原，以免其他遍历需要这个变量
    }

    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(board[i][j]===word[0]){
                if( dfs(board,word,i,j))
                return true;
            }
        }
    }
    return false;

};

剑指 Offer 13. 机器人的运动范围

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function(m, n, k) {
    let visited=Array(m).fill(0).map(item =>{ return Array
    (n).fill(false)});//创建m*n数组
    //去除重复
    console.log(visited)
    const dfs=(visited,i,j)=>{
        console.log(bitsum(i)+'#'+bitsum(j))
        console.log('-----'+i)
        if(i>=m || j>=n || bitsum(i)+bitsum(j)>k || visited[i][j]) return 0;
        //向右和向下
        visited[i][j]=true;        
        return 1+dfs(visited,i+1,j)+dfs(visited,i,j+1);
    }

    const bitsum=(u)=>{
        let sum=0;
        while(u) {
            sum += u % 10;
            u = Math.floor(u / 10); 
        }
        return sum;
        
    }

    return dfs(visited,0,0);
};