My Concise C++ Code using DFS


  • 0
    A

    class Solution {
    public:

    void bfs(int i, int j,vector<vector<char>>&A)
    {
    if(i>0 && A[i-1][j]=='1')
    {
    A[i-1][j]='0';
    bfs(i-1,j,A);
    }

    if(i<(A.size()-1) && A[i+1][j]=='1')
    {
    	A[i+1][j]='0';
    	bfs(i+1,j,A);
    }
    
    if(j>0 && A[i][j-1]=='1')
    {
    	A[i][j-1]='0';
    	bfs(i,j-1,A);
    }
    
    if(j<(A[0].size()-1) && A[i][j+1]=='1')
    {
    	A[i][j+1]='0';
    	bfs(i,j+1,A);
    }
    

    }
    int numIslands(vector<vector<char>>& A)
    {

    if(A.size()==0) 
    return 0;
    
    int n = A.size();
    int m = A[0].size();
    
    int ct=0;
    
    for(int i=0; i<n; i++)
    {
    	for(int j=0; j<m; j++)
    	{
    		if(A[i][j]=='1')
    		{
    			A[i][j]='0';
    			bfs(i,j,A);
    			ct++;
    		}
    	}
    }
    return ct;
    
        
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.