岛屿数量（C++牛客网）

柔情只为你懂 2022-11-17 13:37 153阅读 0赞

解题思路：

（1）dfs

class Solution {
    private:
        vector<vector<int>> d={
       {1,0},{-1,0},{0,1},{0,-1}};
        int m,n;
    public:
        
        void helper(vector<vector<int>> &v,vector<vector<char> >& grid,int x,int y) {
            v[x][y]=1;
            for(int i=0;i<d.size();i++) {
                int x1=x+d[i][0];
                int y1=y+d[i][1];
                if(0<=x1 && x1<m && 0<=y1 && y1<n && grid[x1][y1]=='1' && v[x1][y1]==0) 
                    helper(v,grid,x1,y1);
            }
            return;
        }
        int solve(vector<vector<char> >& grid) {
            int count=0;
            m=grid.size();
            n=grid[0].size();
            vector<vector<int>> v(m,vector<int>(n,0));
            for(int i=0;i<m;i++) {
                for(int j=0;j<n;j++) {
                    if(grid[i][j]=='1' && v[i][j]==0) {
                        count++;
                        helper(v,grid,i,j);
                    }
                }
            }
            return count;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，153人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客在线编程101-57 岛屿数量

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

灰太狼/ 2023年10月04日 20:20/ 0 赞/ 23 阅读

相关阶乘末尾0的数量（C++牛客网）

解题思路：（1）5、25、125......的倍数 class Solution { public: / the nu

旧城等待，/ 2023年01月13日 09:28/ 0 赞/ 156 阅读

相关岛屿数量（C++牛客网）

解题思路：（1）dfs class Solution { private: vector<vector<int>> d={

柔情只为你懂/ 2022年11月17日 13:37/ 0 赞/ 154 阅读

相关等差数列（C++牛客网）

解题思路：（1）数学思想 include<iostream> using namespace std; int helper(

女爷i/ 2022年11月13日 10:29/ 0 赞/ 202 阅读

相关字符串通配符（C++牛客网）

解题思路：（1）使用递归 include<iostream> using namespace std; bool helper

怼烎@/ 2022年11月13日 00:46/ 0 赞/ 222 阅读

相关截取字符串（C++牛客网）

解题思路：（1）substr include<iostream> using namespace std; int main(

亦凉/ 2022年11月12日 01:59/ 0 赞/ 240 阅读

相关迷宫问题（C++牛客网）

解题思路：（1）回溯法，注意值传递而非址传递 include<iostream> include<vector> using names

骑猪看日落/ 2022年11月11日 05:27/ 0 赞/ 237 阅读

相关字符串排序（C++牛客网）

解题思路：（1）保存字母并排序（2）将非字母按顺序插入 include<iostream> include<cctype> include<u

矫情吗；*/ 2022年11月09日 12:58/ 0 赞/ 290 阅读

相关合法IP（C++牛客网）

解题思路：（1）判断范围 include<iostream> include<vector> using namespace std;

￡神魔★判官ぃ/ 2022年10月22日 09:23/ 0 赞/ 225 阅读

相关【牛客网】C/C++牛客网专项刷题（04）

以下为牛客网C/C++专项刷题： 1、有以下程序： include <stdio.h> include <string.h> voi

青旅半醒/ 2022年05月18日 04:49/ 0 赞/ 3274 阅读