记面试算法题--01矩阵

算法01岛屿

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

//实现
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        // write code here
        int lands = 0;
        int N = grid.size();
        int M = grid[0].size();
        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;
    }
    
    void dfs(vector<vector<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.size() && 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].size() && grid[i][j+1] == '1')
        {
            dfs(grid,i,j+1);
        }
    }
};

本文由 Ryan 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2022/10/15 15:36