Leetcode 302 Solution

This article provides solution to leetcode question 302 (smallest-rectangle-enclosing-black-pixels)
Categories:
Tags:
Access this page by simply typing in "lcs 302" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels

Solution

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        if (image.size() == 0 || image[0].size() == 0)
            return 0;



        int m = image.size();
        int n = image[0].size();



        queue<pair<int, int>> q;
        vector<vector<bool>> visited(m, vector<bool>(n));
        q.push(make_pair(x, y));
        visited[x][y] = 1;



        int left = y;
        int right = y;
        int top = x;
        int bottom = x;



        while (q.empty() == false)
        {
            auto pair = q.front();
            q.pop();



            int x = pair.first;
            int y = pair.second;



            left = min(left, y);
            right = max(right, y);
            top = min(top, x);
            bottom = max(bottom, x);



            if (x > 0 && image[x - 1][y] == '1')
            {
                if (visited[x - 1][y] == 0)
                {
                    q.push(make_pair(x - 1, y));
                    visited[x - 1][y] = 1;
                }
            }



            if (x < m - 1 && image[x + 1][y] == '1')
            {
                if (visited[x + 1][y] == 0)
                {
                    q.push(make_pair(x + 1, y));
                    visited[x + 1][y] = 1;
                }
            }



            if (y > 0 && image[x][y - 1] == '1')
            {
                if (visited[x][y - 1] == 0)
                {
                    q.push(make_pair(x, y - 1));
                    visited[x][y - 1] = 1;
                }
            }



            if (y < n - 1 && image[x][y + 1] == '1')
            {
                if (visited[x][y + 1] == 0)
                {
                    q.push(make_pair(x, y + 1));
                    visited[x][y + 1] = 1;
                }
            }
        }



        return (right - left + 1) * (bottom - top + 1);
    }
};