302. Smallest Rectangle Enclosing Black Pixels

Similar solution to the problem of "Number of Islands". Use DFS and flip 1 to 0 after visiting a position. I have no idea about how to use binary search to solve the problem.

1:  class Solution {  
2:  private:  
3:    int minI, minJ, maxI, maxJ;  
4:    int row, col;  
5:    vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
6:  public:  
7:    int minArea(vector<vector<char>>& image, int x, int y) {  
8:      minI = minJ = INT_MAX;  
9:      maxI = maxJ = INT_MIN;  
10:      row = image.size();  
11:      if (row == 0) return 0;  
12:      col = image[0].size();  
13:      dfs(image, x, y);  
14:      return (maxI - minI+1) * (maxJ - minJ+1);  
15:    }  
16:    void dfs(vector<vector<char>> &image, int i, int j) {  
17:      image[i][j] = '0';  
18:      minI = min(minI, i);  
19:      minJ = min(minJ, j);  
20:      maxI = max(maxI, i);  
21:      maxJ = max(maxJ, j);  
22:      for (int d = 0; d < dir.size(); d++) {  
23:        int ii = i + dir[d].first;  
24:        int jj = j + dir[d].second;  
25:        if (ii < 0 || ii == row || jj < 0 || jj == col || image[ii][jj] == '0') continue;  
26:        dfs(image, ii, jj);  
27:      }  
28:    }  
29:  };