1 題目

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

lintcode：題號——600，難度——hard

2 描述

??一個由二進制矩陣表示的圖，0 表示白色像素點，1 表示黑色像素點。黑色像素點是聯(lián)通的，即只有一塊黑色區(qū)域。像素是水平和豎直連接的，給一個黑色像素點的坐標(biāo) (x, y) ，返回囊括所有黑色像素點的矩陣的最小面積。

??樣例1：

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

矩陣左上角坐標(biāo)是(0, 1), 右下角的坐標(biāo)是(2, 2)

??樣例2：

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

矩陣左上角坐標(biāo)是(0, 0), 右下角坐標(biāo)是(1, 3)

3 思路

??從答案反向找思路，要得到面積，需要橫向跨度和縱向跨度，橫向需要分別找到最左邊和最右邊，縱向需要分別找到最上面和最下面，題中給出了一個種子點，即其中一個黑子所在的位置，從種子點分別向上、下、左、右四個方向看，例如向左的情況，需要找到最左端的黑子，而最左端的黑子不一定與種子點在同一行，所以我們要考慮整個左半矩陣圖，由于只要找到最左端的橫向坐標(biāo)即可，不用關(guān)心列坐標(biāo)，可以將左半矩陣圖縱向壓縮進同一行，這樣只要該列存在任何黑子，則將壓縮后形成的點標(biāo)記為黑，因為所有的黑子是聯(lián)通的，最后向左看的情況一定會形成“oooxxx”形式的數(shù)列，使用二分法即可找到最左端邊緣。
??按照相同的思路可以找到其他三個方向的邊緣，然后得到橫縱跨度，再得到面積。

1. 考慮左半矩陣，以每列是否存在黑子為條件，二分查找最左邊緣；
2. 分別得到四個方向的邊緣；
3. 計算橫縱跨度，得到面積。

??擴展。

其實題目中給出的種子點有點奇怪，按照常理來判斷給不給這個種子點的位置，都是能得到答案的，題中直接給出了，簡化了這一步。題目也可以使用廣度優(yōu)先搜索來做，可以思考一下。

3.1 圖解

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

3.2 時間復(fù)雜度

??算法在每一個方向使用一次二分法，假定矩陣圖有m行n列，相同維度的二分法耗時可以整體來算，橫向上二分法操作的時間復(fù)雜度為O(log n)，縱向上二分法操作的時間復(fù)雜度為O(log m)。
??橫向的二分法每次判斷都包含一次對列的遍歷操作的時間復(fù)雜度O(m)，縱向的二分法每次判斷都包含一次對行的遍歷的時間復(fù)雜度O(m)。
??橫向二分法總耗時O(m * log n)，縱向二分法總耗時O(n * log m)。
??算法的時間復(fù)雜度為O(m * log n + n * log m)，其中m為矩陣圖的行數(shù)，n為矩陣圖的列數(shù)。

3.3 空間復(fù)雜度

??算法的空間復(fù)雜度為O(1)。

4 源碼

??注意事項：

1. 題目給出的種子點坐標(biāo)(x, y)，x表示二維數(shù)組的行序號，y表示二維數(shù)組的列序號，所以x是縱向的距離，y是橫向的距離，這點和直角坐標(biāo)系的x方向和y方向剛好相反，很容易想歪，思路要清晰；
2. 求面積的時候，注意一個點代表一距離，不是一條邊代表一距離。

??C++版本：

/**
 * @param image: 代表包含'0'和'1'為元素的二進制矩陣圖
 * @param x: 初始黑點的縱坐標(biāo)
 * @param y: 初始黑點的橫坐標(biāo)
 * @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;

    // 計算四個方向最邊緣點的下標(biāo)
    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);
}

// 計算最左邊緣黑點的橫坐標(biāo)
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;
    }
}

// 計算最右邊緣黑點的橫坐標(biāo)
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;
    }
}

// 計算最上邊緣黑點的縱坐標(biāo)
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;
    }
}

// 計算最下邊緣黑點的縱坐標(biāo)
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;
}