My simple to understand solution in c++


  • 0
    W
     class Solution {
        private:
        	int count;
        	bool ValidAdjacent(int x,int y,int xsize,int ysize) {
        		if(x < 0 || y < 0) return false;
        		if(x >= xsize || y >= ysize)return false;
        		return true;
        	}
        public:
        	Solution():count(0){}
        	~Solution(){}
            int numIslands(vector< vector<char> >& grid) {
            	int s = grid.size();
        
            	//this->marked = new bool[s*s + 1];
        
                for (int i = 0; i < s; ++i)
                {
                	for (int j = 0; j < grid[0].size(); ++j)
                	{
                		if(grid[i][j] == '1'){
                			grid[i][j] = '0';
                			dfs(i,j,grid);
                			this->count++;
                		}
                	}
                }
                return this->count;
            }
        
            //depth-first-search
            void dfs(int i,int j,vector< vector<char> >& grid) {
            	if(ValidAdjacent(i - 1,j,grid.size(),grid[0].size()) && grid[i - 1][j] == '1'){grid[i - 1][j] = '0';dfs(i - 1,j,grid);}
            	if(ValidAdjacent(i,j - 1,grid.size(),grid[0].size()) && grid[i][j - 1] == '1'){grid[i][j - 1] = '0';dfs(i,j - 1,grid);}
            	if(ValidAdjacent(i + 1,j,grid.size(),grid[0].size()) && grid[i + 1][j] == '1'){grid[i + 1][j] = '0';dfs(i + 1,j,grid);}
            	if(ValidAdjacent(i,j + 1,grid.size(),grid[0].size()) && grid[i][j + 1] == '1'){grid[i][j + 1] = '0';dfs(i,j + 1,grid);}
            	return;
            }
        };

Log in to reply
 

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