Update 803.Bricks-Falling-When-Hit_DFS.cpp

wisdompeak · web-flow · commit d72b0c540154 · 2021-04-15T00:31:23.000-07:00
diff --git a/DFS/803.Bricks-Falling-When-Hit/803.Bricks-Falling-When-Hit_DFS.cpp b/DFS/803.Bricks-Falling-When-Hit/803.Bricks-Falling-When-Hit_DFS.cpp
@@ -1,55 +1,46 @@
 class Solution {
     vector<vector<int>>visited; // 1: land, -1 : erased, 2 : connected
-    vector<pair<int,int>>dir;
+    vector<pair<int,int>>dir{{1,0},{-1,0},{0,1},{0,-1}};
+    int m,n;
 public:
     vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) 
     {
-        int m = grid.size();
-        int n = grid[0].size();
-        dir = {{1,0},{-1,0},{0,1},{0,-1}};
-        
+        m = grid.size();
+        n = grid[0].size();
+                
         visited = grid;
         for (auto point:hits)        
             visited[point[0]][point[1]] *= -1;        
                         
         for (int j=0; j<n; j++)        
             if (visited[0][j]==1)
-            {
-                int num = 0;
-                dfs(0,j,num);                        
-            }
+                dfs(0,j);                        
         
         vector<int>ret;
         reverse(hits.begin(),hits.end());
         for (auto point:hits)
         {
-            int i = point[0];
-            int j = point[1];
-                        
+            int i = point[0], j = point[1];
             if (visited[i][j]!=-1) 
             {
                 ret.push_back(0);
                 continue;
             }
-            bool find = (i==0);
+            bool connectRoof = (i==0);
             for (int k=0; k<4; k++)
             {
                 int x = i+dir[k].first;
                 int y = j+dir[k].second;
-                if (!isValid(x,y)) continue;
+                if (x<0||x>=m||y<0||y>=n) continue;
                 if (visited[x][y]==2)
                 {
-                    find = true;
+                    connectRoof = true;
                     break;
                 }                
             }
             
-            if (find)
-            {
-                int num = -1;
-                dfs(i,j,num);                        
-                ret.push_back(num);
-            }
+            if (connectRoof)
+                ret.push_back(dfs(i,j-1);
             else
             {
                 visited[i][j] = 1;            
@@ -61,24 +52,18 @@ class Solution {
         return ret;
     }
     
-    bool isValid(int x, int y)
-    {
-        int m = visited.size();
-        int n = visited[0].size();
-        return !(x<0||x>=m||y<0||y>=n);
-    }
-    
-    void dfs(int i, int j, int &num)
+    int dfs(int i, int j)
     {
         visited[i][j] = 2;
-        num++;
+        int count = 1;        
         for (int k=0; k<4; k++)
         {
             int x = i+dir[k].first;
             int y = j+dir[k].second;
-            if (!isValid(x,y)) continue;
+            if (x<0||x>=m||y<0||y>=n) continue;
             if (visited[x][y]==1)
-                dfs(x,y,num);
+                count += dfs(x,y);
         }        
+        return count;
     }
 };
