y******o
发帖数: 921 | 1 一个N * M 矩阵A，里面的值是1或0，现在求矩阵里面子矩阵(square)最大边长L，满足
1. 0 < L <= min(N, M),
2. 0 <= X <= N - L,
3. 0 <= Y <= M - L,
4. A[X + I][Y + J] = 1 for all 0 <= I < L and 0 <= J < L.
5. 子矩阵能够移动, 从(X, Y)移动到(X + 1, Y)或者(X, Y + 1)
同时满足子矩阵能从左上角(0, 0)走到右下角(N - L, M - L)，
即求能从左上角走到右下角的子矩阵边长最大，使子矩阵任何时刻里面全部是1,有则返
回L，没有返回0
For example, given array A:
1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 1
0 1 1 1
1 0 1 1
the function should return 2.
Given array A:
1 1 0 0
1 0 0 0
0 1 0 1
the function should return 0.
Given array A:
1
the function should return 1.
要求时间O(N * M * log(N + M)), 空间O(N * M)
求大神指点 | l*********8
发帖数: 4642 | 2 L是边长吧？
【在 y******o 的大作中提到】
: 一个N * M 矩阵A，里面的值是1或0，现在求矩阵里面子矩阵(square)最大边长L，满足
: 1. 0 < L <= min(N, M),
: 2. 0 <= X <= N - L,
: 3. 0 <= Y <= M - L,
: 4. A[X + I][Y + J] = 1 for all 0 <= I < L and 0 <= J < L.
: 5. 子矩阵能够移动, 从(X, Y)移动到(X + 1, Y)或者(X, Y + 1)
: 同时满足子矩阵能从左上角(0, 0)走到右下角(N - L, M - L)，
: 即求能从左上角走到右下角的子矩阵边长最大，使子矩阵任何时刻里面全部是1,有则返
: 回L，没有返回0
: For example, given array A:
| y******o
发帖数: 921 | 3
是的，我写错了，是边长
【在 l*********8 的大作中提到】
: L是边长吧？
| y******o
发帖数: 921 | | R*****i
发帖数: 2126 | 5 这个题感觉很有难度。第一步大概是扫描整个M*N的矩阵，把以它为左上角的最大非零
方阵的尺寸存成另外一个矩阵，接下来是找连通，这一步我还没有想明白。 | y******o
发帖数: 921 | 6 是呀，我也卡在找连通这里
【在 R*****i 的大作中提到】
: 这个题感觉很有难度。第一步大概是扫描整个M*N的矩阵，把以它为左上角的最大非零
: 方阵的尺寸存成另外一个矩阵，接下来是找连通，这一步我还没有想明白。
| e***l
发帖数: 710 | 7 二维dp, 设dp(i j)为子矩阵0,0到i, j上的解,
它依赖于dp (i-1, j) 和dp (i, j-1)。只需要检查多出来的行或列, 而且可以预先算
好连续1的数目, 这一步应该是常数时间。 | e***l
发帖数: 710 | 8 假设row (i j)是从点(i j)向左最长的连续1的数目, 可以在o (mn)时间内求出所有的
row (i j). 同样求出col(i j).
则dp (i j) = max ( min (dp (i-1, j), col (i, j)), min (dp (i, j-1), row (i
, j))) | c*******y
发帖数: 98 | 9 DP好难，我来贴个无脑的，不知道题目理解对了没有。。
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int findMaxAllOneTopLeftSquare(vector>& matrix)
{
int i, j;
int m = matrix.size(); if (!m) return 0;
int n = matrix[0].size(); if (!n) return 0;
int max = min(m, n);
for (i=0; i
for (j=0; j<=i; j++){
if (matrix[i][j] == 0 || matrix[j][i] == 0){
return i;
}
}
}
return i;
}
bool isAbleToMoveToRightDown(vector>& matrix, int& L, int y1,
int x1, int y2, int x2)
{
cout << L << ", (" << y1 << ", " << x1 << "), (" << y2 << ", " << x2 <<
")" << endl;
if (y1 == y2 && x1 == x2) return true;
int i;
bool bRight = true, bDown = true;
// check right
if (x1 < x2){
for (i=0; i
if (matrix[y1+i][x1+L] == 0){
bRight = false;
break;
}
}
}
else{
bRight = false;
}
// check down
if (y1 < y2){
for (i=0; i
if (matrix[y1+L][x1+i] == 0){
bDown = false;
break;
}
}
}
else{
bDown = false;
}
return bRight && isAbleToMoveToRightDown(matrix, L, y1, x1+1, y2, x2
) || bDown && isAbleToMoveToRightDown(matrix, L, y1+1, x1, y2, x2);
}
int main (int argc, char** argv) {
vector> matrix;
matrix.push_back({1, 1, 1, 0});
matrix.push_back({1, 1, 1, 0});
matrix.push_back({1, 1, 1, 0});
matrix.push_back({1, 1, 1, 0});
matrix.push_back({0, 0, 1, 1});
matrix.push_back({1, 0, 1, 1});
int L = findMaxAllOneTopLeftSquare(matrix);
int i;
int m = matrix.size(); if (!m) return 0;
int n = matrix[0].size(); if (!n) return 0;
cout << "m = " << m << endl;
cout << "n = " << n << endl;
cout << "L = " << L << endl;
for (i=L; i>=1; i--){
cout << "i = " << i << endl;
if (isAbleToMoveToRightDown(matrix, i, 0, 0, m-i, n-i)){
break;
}
}
cout << "Min L for square is " << i << endl;
return 0;
} | l******6
发帖数: 340 | 10 build a matrix of N by M, each cell contain a number as the bigest square
with all 1 end at this cell using DP
Mat[i][j] = 0 if src[i][j] == 0
max(Mat[i][j - 1] , Mat[i - 1][j] , Mat[i - 1][j - 1]) + 1
otherwise
start from right bottom cell, do binary search from 1 to Mat[M - 1][N - 1]
each itaration, with value i, using bfs/dfs to check if there is a path from
Mat[M - 1][N - 1] to Mat[i - 1][i - 1], a path is connected if Mat[x][y] >=
i;
Space : M * N
time: binary iteration log(M + N)
each iteration, bfs/dfs worst time M*N total M*N*log(M + N) | | | h*******e
发帖数: 1377 | 11 以size 搜索通路bfs 每次移动增加 2* size ，O(M*N) 然后 二分size O(log min(m
, n)) | f*****e
发帖数: 2992 | 12 题目都看晕了，这个是面试题吗？
【在 y******o 的大作中提到】
: 一个N * M 矩阵A，里面的值是1或0，现在求矩阵里面子矩阵(square)最大边长L，满足
: 1. 0 < L <= min(N, M),
: 2. 0 <= X <= N - L,
: 3. 0 <= Y <= M - L,
: 4. A[X + I][Y + J] = 1 for all 0 <= I < L and 0 <= J < L.
: 5. 子矩阵能够移动, 从(X, Y)移动到(X + 1, Y)或者(X, Y + 1)
: 同时满足子矩阵能从左上角(0, 0)走到右下角(N - L, M - L)，
: 即求能从左上角走到右下角的子矩阵边长最大，使子矩阵任何时刻里面全部是1,有则返
: 回L，没有返回0
: For example, given array A:
| y******o
发帖数: 921 | 13
from
>=
start from right bottom cell, do binary search from 1 to Mat[M - 1][N - 1]
没明白，能具体解释一下吗
【在 l******6 的大作中提到】
: build a matrix of N by M, each cell contain a number as the bigest square
: with all 1 end at this cell using DP
: Mat[i][j] = 0 if src[i][j] == 0
: max(Mat[i][j - 1] , Mat[i - 1][j] , Mat[i - 1][j - 1]) + 1
: otherwise
: start from right bottom cell, do binary search from 1 to Mat[M - 1][N - 1]
: each itaration, with value i, using bfs/dfs to check if there is a path from
: Mat[M - 1][N - 1] to Mat[i - 1][i - 1], a path is connected if Mat[x][y] >=
: i;
: Space : M * N
| l******6
发帖数: 340 | 14 The final answer, must be a value between 0 and Mat[M - 1][N - 1]
let low = 1 high = Mat[M - 1][N - 1]
using binary search to find that value . If a value i is working , there
must be a path between Mat[i - 1][i - 1] and Mat[M - 1][N - 1] with all the
cell value greater or equal to i
If such path exists, search between i + 1 and high for next i
otherwise search between low and i - 1 for next i;
for a i to determine whether the path exists , using bfs/dfs
【在 y******o 的大作中提到】
:
: from
: >=
: start from right bottom cell, do binary search from 1 to Mat[M - 1][N - 1]
: 没明白，能具体解释一下吗
| e***l
发帖数: 710 | 15 1, 1, 1
0, 0, 1
0, 0, 1
Mat[M-1][N-1]是0，Mat[M][N]是1.
the | l******6
发帖数: 340 | 16
I think index is usually 0 based
【在 e***l 的大作中提到】
: 1, 1, 1
: 0, 0, 1
: 0, 0, 1
: Mat[M-1][N-1]是0，Mat[M][N]是1.
: the
| e***l
发帖数: 710 | 17 我是说你的dp不对。递推只和上面和左边的位置有关, 跟斜上方的无关
【在 l******6 的大作中提到】
:
: I think index is usually 0 based
|
|
