面试必考真题-算法篇：给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻

时间：2025-04-16 07:30:22

面试必考真题-算法篇 牛客网


dfs bfs 搜索

题目描述
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

题目分析：
同样的代码在牛客上会报栈溢出错误！！但是在leetcode上可以AC！！
同样的代码在牛客上会报栈溢出错误！！但是在leetcode上可以AC！！
同样的代码在牛客上会报栈溢出错误！！但是在leetcode上可以AC！！

利用dfs进行遍历，当找到陆地之后，向这个位置的上下左右继续寻找，如果依然找到陆地，则将矩阵中该位置代表陆地的’1’修改为’0’。这样，在之后的遍历中则不会再次计算该处陆地。

下面是Java代码

class Solution {
    public int numIslands(char[][] grid) {

        int lands = 0;
        int N = grid.length;
        int M = grid[0].length;
        for(int i = 0 ; i< N;i++){
            for(int j = 0;j<M;j++){
                if(grid[i][j] == '1'){
                    ++lands;
                    dfs(grid,i,j);
                }
            }
        }
        return lands;

    }

    private void dfs(char[][] grid,int i , int j){
        grid[i][j] ='0';
        if(i-1>=0 && grid[i-1][j]=='1'){
            dfs(grid,i-1,j);
        }
        if(i+1 < grid.length && grid[i+1][j] == '1'){
            dfs(grid,i+1,j);
        }
        if(j-1>=0 && grid[i][j-1] == '1'){
            dfs(grid,i,j-1);
        }
        if(j+1 < grid[0].length && grid[i][j+1] == '1'){
            dfs(grid,i,j+1);
        }
    }
}

参考/practice/0c9664d1554e466aa107d899418e814e?tpId=190&&tqId=35229&rp=1&ru=/ta/job-code-high-rd&qru=/ta/job-code-high-rd/question-ranking

相关文章