题解 | dfs遍历

岛屿数量

https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
 #include <iostream>
#include <fstream>
#include <string>

#define fas(i,a,b) for(int i=a;i<b;++i) //[)
#define fdes(i,b,a) for(int i=b;a<=i;--i) //[]
#define mm memset
#define ll long long
#define pi acos(-1)






void dfs(vector<vector<char> >& matrix,int m,int n,int i,int j)
{
    if(check(m,n,i,j)==false || matrix[i][j]=='0')
    {
        return ;
    }
    // visit
    matrix[i][j]='0';
    dfs(matrix, m, n, i+1, j);
    dfs(matrix, m, n, i-1, j);
    dfs(matrix, m, n, i, j+1);
    dfs(matrix, m, n, i, j+1);
    dfs(matrix, m, n, i, j-1);
}

bool check(int m,int n,int i,int j)
{
    if(i<0||m<=i||j<0||n<=j)
        return false;
    return true;
}

  int solve(vector<vector<char> >& grid) {

	// write code here
	int m=grid.size(),n=grid[0].size();
	int ans=0;

	fas(i,0,m)
	  fas(j,0,n)
	{
	  if(grid[i][j]=='1')
	  {
		dfs(grid,m,n,i,j);
		++ans;
	  }     
	}
	return ans;
  }
};

全部评论

相关推荐

牛客92804383...:在他心里你已经是他的员工了
点赞 评论 收藏
分享
牛客83700679...:简历抄别人的,然后再投,有反馈就是简历不行,没反馈就是学历不行,多投多改只要技术不差机会总会有的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务