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

Question

给定一个二元平方矩阵，我必须找到紧贴矩阵右下角边界的“1”矩形。因此，总而言之，我必须找到矩形左上角的坐标。

P.S: 1. 总是有一个矩形，最小的是 1*1 在buttom-right mat的角落。

1. mat 的尺寸基于对“getupperleft”函数的调用(n = mat 的尺寸)

2. 1 仅在矩形内部，0 始终在外部。

为了说明，

此处矩形从第 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;
}

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