C++ DFS Solution - Have no idea how to apply binary search in a proper way for this problem


  • 2
    Y
    class Solution {
    public:
        int minArea(vector<vector<char>>& image, int x, int y) {
            if(image.size() == 0)
                return 0;
            int n = image.size(), m = image[0].size();
            int miny = m - 1, maxy = 0, maxx = 0, minx = n;
            dfs(image, minx, maxx, miny, maxy, x, y);
            return (maxx - minx + 1)*(maxy - miny + 1);
        }
    private:
        void dfs(vector<vector<char>>& image, int &minx, int &maxx, int &miny, int &maxy, int x, int y){
            minx = min(minx, x);
            maxx = max(maxx, x);
            miny = min(miny, y);
            maxy = max(maxy, y);
            image[x][y] = '0';
            if(x >= 1 && image[x - 1][y] == '1')
                dfs(image, minx, maxx, miny, maxy, x - 1, y);
            if(x < image.size() - 1 && image[x + 1][y] == '1')
                dfs(image, minx, maxx, miny, maxy, x + 1, y);
            if(y >= 1 && image[x][y - 1] == '1')
                dfs(image, minx, maxx, miny, maxy, x, y - 1);
            if(y < image[0].size() - 1 && image[x][y + 1] == '1')
                dfs(image, minx, maxx, miny, maxy, x, y + 1);
        }
    };

  • 1

    I see how to do it in binary search.

    Just do it by rows and columns.

    Posted, see the solution here.


Log in to reply
 

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