记面试算法题--01矩阵

/ C++ / 没有评论 / 162浏览

给一个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);
        }
    }
};