6 最小覆盖矩形（Smallest Rectangle Enclosing Black Pixels）

2024-03-03 20:48:10

1 题目
2 描述
3 思路
4 源码

1 题目

最小覆盖矩形（Smallest Rectangle Enclosing Black Pixels）

lintcode：题号——600，难度——hard

2 描述

一个由二进制矩阵表示的图，0 表示白色像素点，1 表示黑色像素点。黑色像素点是联通的，即只有一块黑色区域。像素是水平和竖直连接的，给一个黑色像素点的坐标 (x, y) ，返回囊括所有黑色像素点的矩阵的最小面积。

样例1：

输入：["0010","0110","0100"]，x=0，y=2
输出：6
解释：

矩阵左上角坐标是(0, 1), 右下角的坐标是(2, 2)

样例2：

输入：["1110","1100","0000","0000"], x = 0, y = 1
输出：6
解释：

矩阵左上角坐标是(0, 0), 右下角坐标是(1, 3)

3 思路

从答案反向找思路，要得到面积，需要横向跨度和纵向跨度，横向需要分别找到最左边和最右边，纵向需要分别找到最上面和最下面，题中给出了一个种子点，即其中一个黑子所在的位置，从种子点分别向上、下、左、右四个方向看，例如向左的情况，需要找到最左端的黑子，而最左端的黑子不一定与种子点在同一行，所以我们要考虑整个左半矩阵图，由于只要找到最左端的横向坐标即可，不用关心列坐标，可以将左半矩阵图纵向压缩进同一行，这样只要该列存在任何黑子，则将压缩后形成的点标记为黑，因为所有的黑子是联通的，最后向左看的情况一定会形成“oooxxx”形式的数列，使用二分法即可找到最左端边缘。
按照相同的思路可以找到其他三个方向的边缘，然后得到横纵跨度，再得到面积。

考虑左半矩阵，以每列是否存在黑子为条件，二分查找最左边缘；

分别得到四个方向的边缘；

计算横纵跨度，得到面积。

扩展。

其实题目中给出的种子点有点奇怪，按照常理来判断给不给这个种子点的位置，都是能得到答案的，题中直接给出了，简化了这一步。题目也可以使用广度优先搜索来做，可以思考一下。

3.1 图解

输入：["0000100","0111100","0001100","0011110","0000000"],
x = 2, y = 4
输出：20

graph TD X[0表示白子,1和X表示黑子,X为种子点 '0, 0, 0, 0, 1, 0, 0' '0, 1, 1, 1, 1, 0, 0' '0, 0, 0, 1, X, 0, 0' '0, 0, 1, 1, 1, 1, 0' '0, 0, 0, 0, 0, 0, 0'] X -- 左半矩阵 --> A['0, 0, 0, 0, 1' '0, 1, 1, 1, 1' '0, 0, 0, 1, X' '0, 0, 1, 1, 1' '0, 0, 0, 0, 0'] X -- 上半矩阵 --> B['0, 0, 0, 0, 1, 0, 0' '0, 1, 1, 1, 1, 0, 0' '0, 0, 0, 1, X, 0, 0'] X -- 右半矩阵 --> C['1, 0, 0' '1, 0, 0' 'X, 0, 0' '1, 1, 0' '0, 0, 0'] X -- 下半矩阵 --> D['0, 0, 0, 1, X, 0, 0' '0, 0, 1, 1, 1, 1, 0' '0, 0, 0, 0, 0, 0, 0'] A --> A0[列中出现一个黑子1,则压缩后的点为1] A0 -- 分列 --> A1[0 0 0 0 0] A0 -- 分列 --> A2[0 1 0 0 0] A0 -- 分列 --> A3[0 1 0 1 0] A0 -- 分列 --> A4[0 1 1 1 0] A0 -- 分列 --> A5[1 1 X 1 0] A1 -- 压缩 --> A11[0] A2 -- 压缩 --> A21[1] A3 -- 压缩 --> A31[1] A4 -- 压缩 --> A41[1] A5 -- 压缩 --> A51[1] A11 --> AA['0, 1, 1, 1, 1'] A21 --> AA A31 --> AA A41 --> AA A51 --> AA AA -- 二分查找得到左边缘 下标都是指在整体矩阵中的下标 --> AAA[下标1] B -- 分行,压缩 --> BB['1' '1' '1'] BB -- 上边缘 --> BBB[下标0] C -- 分列,压缩 --> CC['1, 1, 0'] CC -- 右边缘 --> CCC[下标5] D -- 分行,压缩 --> DD['1' '1' '0'] DD -- 下边缘 --> DDD[下标3] AAA --> AC[跨度5] CCC --> AC BBB --> BD[跨度4] DDD --> BD AC --> R[面积20] BD --> R

3.2 时间复杂度

算法在每一个方向使用一次二分法，假定矩阵图有m行n列，相同维度的二分法耗时可以整体来算，横向上二分法操作的时间复杂度为O(log n)，纵向上二分法操作的时间复杂度为O(log m)。
横向的二分法每次判断都包含一次对列的遍历操作的时间复杂度O(m)，纵向的二分法每次判断都包含一次对行的遍历的时间复杂度O(m)。
横向二分法总耗时O(m * log n)，纵向二分法总耗时O(n * log m)。
算法的时间复杂度为O(m * log n + n * log m)，其中m为矩阵图的行数，n为矩阵图的列数。

3.3 空间复杂度

算法的空间复杂度为O(1)。

4 源码

注意事项：

题目给出的种子点坐标(x, y)，x表示二维数组的行序号，y表示二维数组的列序号，所以x是纵向的距离，y是横向的距离，这点和直角坐标系的x方向和y方向刚好相反，很容易想歪，思路要清晰；
求面积的时候，注意一个点代表一距离，不是一条边代表一距离。

C++版本：

/**
 * @param image: 代表包含'0'和'1'为元素的二进制矩阵图
 * @param x: 初始黑点的纵坐标
 * @param y: 初始黑点的横坐标
 * @return: 最小覆盖矩形的面积
 */
int minArea(vector<vector<char>> &image, int x, int y) {
    // write your code here
    if (image.empty() || image.front().empty()) // 横纵都不能为空
    {
        return 0;
    }

    int maxRow = image.size() - 1;
    int maxColumn = image.front().size() - 1;

    // 计算四个方向最边缘点的下标
    int left = calLeftEdge(image, 0, y);
    int right = calRightEdge(image, y, maxColumn);
    int top = calTopEdge(image, 0, x);
    int bottom = calBottomEdge(image, x, maxRow);

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

// 计算最左边缘黑点的横坐标
int calLeftEdge(vector<vector<char>> & image, int start, int end)
{
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (isColWhite(image, mid))
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }

    if (isColWhite(image, start))
    {
        return end;
    }
    else
    {
        return start;
    }
}

// 计算最右边缘黑点的横坐标
int calRightEdge(vector<vector<char>> & image, int start, int end)
{
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (isColWhite(image, mid))
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
    }

    if (isColWhite(image, end))
    {
        return start;
    }
    else
    {
        return end;
    }
}

// 计算最上边缘黑点的纵坐标
int calTopEdge(vector<vector<char>> & image, int start, int end)
{
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (isRowWhite(image, mid))
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }

    if (isRowWhite(image, start))
    {
        return end;
    }
    else
    {
        return start;
    }
}

// 计算最下边缘黑点的纵坐标
int calBottomEdge(vector<vector<char>> & image, int start, int end)
{
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (isRowWhite(image, mid))
        {
            end = mid;
        }
        else
        {
            start = mid;
        }
    }

    if (isRowWhite(image, end))
    {
        return start;
    }
    else
    {
        return end;
    }
}

// 判断行中是否全为白点
bool isRowWhite(vector<vector<char>> & image, int row)
{
    for (int i = 0; i < image.front().size(); i++)
    {
        if (image.at(row).at(i) == '1')
        {
            return false;
        }
    }

    return true;
}

// 判断列中是否全为白点
bool isColWhite(vector<vector<char>> & image, int col)
{
    for (int i = 0; i < image.size(); i++)
    {
        if (image.at(i).at(col) == '1')
        {
            return false;
        }
    }

    return true;
}

码农公寓