c++ clever dfs code with explantation in comment.


  • 0
    class Solution {
    public:
      int numIslands(vector<vector<char> >& grid) {
        int ret = 0;
        for (int i = 0; i < grid.size(); i ++)
        {
          for (int j = 0; j < grid[i].size(); j ++)
          {
    	if (grid[i][j] == '1')
    	{
    	  dfs(grid, i, j);
    	  ret ++;
    	}
          }
        }
        return ret;
      }
    
      void dfs(vector<vector<char> > &grid, int x, int y)
      {
        // Change point value.
        grid[x][y] = '0';
        // Four directions
        for (int dx = -1; dx <= 1; dx ++)
        {
          for (int dy = -1; dy <= 1; dy ++)
          {
    	// Make sure directions is horizontally or vertically.
    	if (dx != dy && dx != -dy)
    	{
    	  int nx = x + dx;
    	  int ny = y + dy;
    	  // Judge wether the point is in field and is adjacent to its neighbors.
    	  if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == '1')
    	  {
    	    dfs(grid, nx, ny);
    	  }
            }
          }
        }
      }
    };
    

Log in to reply
 

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