在平方二进制矩阵中找到二进制矩形的位置

Question

给定一个二元平方矩阵，我必须找到紧贴矩阵右下角边界的“1”矩形。所以，综上所述，我要找的就是矩形左上角的坐标。

P.S: 1. 总是有一个矩形，最小的是右下角的1*1。

mat 的尺寸基于对 'getupperleft' 函数的调用（n = mat 的尺寸）
1s 仅在矩形内部，0s 始终在外部。

为了说明，

此处矩形从第 4 列第 3 行开始。（左上坐标）

我的想法是使用两次 BinarySearch 来获得 Log(n) 中的答案，但我坚持执行它，这对 c++ 语法来说是不寻常的。非常感谢您的帮助！

void getUpperLeft(int mat[][N], int n, int &row, int &col);
void main()
{
    int row = -1;
    int col = -1;
    int matrix[8][N] = {
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0},
    {0,0,0,0,0,1,1,1},
    {0,0,0,0,0,1,1,1},
    {0,0,0,0,0,1,1,1},
    {0,0,0,0,0,1,1,1},
    {0,0,0,0,0,1,1,1} };

}

void getUpperLeft(int mat[][N], int n, int & row, int & col)
{
    int mid = N - (n / 2);
    if (mat[N][mid] == 1 && mat[N][mid-1] == 0)
    {
        col = mid;
    }
    else if (mat[N][mid] == 0 && mat[N][mid+1] == 0)
    {
        getUpperLeft(mat, n/2 , row, col);
    }
    else if (mat[N][mid] == 1 && mat[N][mid+1] == 1)
    {
        getUpperLeft(mat, N-(n/2), row, col);
    }
}

Answer 1

正如其他人所指出的，您的代码中存在尺寸硬编码问题。显然，你应该在你的代码和下面的代码中解决这个问题。话虽如此，这将起作用：

int findCol(const int matrix[8][8]) {                                                                                                                                                                    
    int lo = 0, hi = 8 - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo)/2;
        if (matrix[7][mid] < 1)
            lo = mid + 1;
        else
            hi = mid;
    }   
    return lo; 
}   


int findRow(const int matrix[8][8]) {
    int lo = 0, hi = 8 - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo)/2;
        if (matrix[mid][7] < 1)
            lo = mid + 1;
        else
            hi = mid;
    }   
    return lo;
}

前一个函数对最后一行进行二分查找，后者对最后一列进行二分查找

Answer 2

您可以对最后一列执行二分搜索以查找值为 1 的第一行，并类似地对最后一行执行另一个二分搜索以查找具有值 1 的第一列。这将为您提供 1s 矩形的左上角。

复杂度为 O(log n) 时间，O(1) space

Answer 3

好的，所以使用 BinarySearch 的迭代版本，这就是我所做的并且效果很好：

void main()
{

}

void getUpperLeft(int mat[][N], int n, int & row, int & col)
{
    col = getCoordinate(mat, true, 0);
    row = getCoordinate(mat, false, col);
}

//getCoordinate function works using BinarySearch algorithm - log(n) until it finds the desirable coordinate.
int getCoordinate(int mat[][N], bool stat, int y) //[stat="true" - horizontal test], [stat="false"  - vertical test (then "y" parameter is the horizontal coordinate)].
{
    int low = 0, high = N;
    int prev, next;

    while (low < high)
    {
        int mid = low + (high - low) / 2;
            if (stat)
            {
                prev = mat[N - 1][mid - 1];
                next = mat[N - 1][mid];
            }
            else
            {
                prev = mat[mid - 1][y];
                next = mat[mid][y];
            }

            /*edge cases*/
        if (mat[0][0] == 1 && mid ==0)
            return 0;
        if (mat[0][N - 1] == 1 && mid ==0)
            return 0;
            /*edge cases*/

        if (next == 1 && prev == 0)
            return mid;
        else if (prev == 0 && next == 0)
            low = mid + 1;
        else if (prev == 1 && next == 1)
            high = mid;
    }
}

在平方二进制矩阵中找到二进制矩形的位置

find location of binary rectangle in a squared binary matrix

c++

algorithm

recursion

binary-search