My C++ Accepted Code


  • 0
    T
    void minArea(vector<vector<char>>& image, int x, int y, int& minX, int& maxX, int& minY, int& maxY)
    {
    	if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] == '0')
    		return;
    	image[x][y] = '0';
    
    	minX = min(minX, x);
    	maxX = max(maxX, x);
    	minY = min(minY, y);
    	maxY = max(maxY, y);
    
    	minArea(image, x - 1, y, minX, maxX, minY, maxY);
    	minArea(image, x + 1, y, minX, maxX, minY, maxY);
    	minArea(image, x, y - 1, minX, maxX, minY, maxY);
    	minArea(image, x, y + 1, minX, maxX, minY, maxY);
    
    }
    int minArea(vector<vector<char>>& image, int x, int y) 
    {
    	int minX = image.size(), maxX = -1, minY = image[0].size(), maxY = -1;
    	minArea(image, x, y, minX, maxX, minY, maxY);
    	return (maxX - minX + 1)*(maxY - minY + 1);
    }

  • 0

    Good DFS solution! We can also use BFS. Just a little suggestion to make the code cleaner, define the 4 directions (up, down, left, right) like so:

    int dx[] = {0, 0, -1, 1};
    int dy[] = {-1, 1, 0, 0};
    

    then replace the following code

    minArea(image, x - 1, y, minX, maxX, minY, maxY);
    minArea(image, x + 1, y, minX, maxX, minY, maxY);
    minArea(image, x, y - 1, minX, maxX, minY, maxY);
    minArea(image, x, y + 1, minX, maxX, minY, maxY);
    

    to:

    for (int i = 0; i < 4; i++) {
      minArea(image, x + dx[i], y + dy[i], minX, maxX, minY, maxY);
    }

Log in to reply
 

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