a***e
发帖数: 413 | 1 抱怨一下，开始按算面积的想，后来发现题没理解对。有人面试碰到这种题吗？感觉不
像DP | k****p
发帖数: 9 | | b******i
发帖数: 914 | 3 请问你指的是这个吗？
http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
1-b)看不懂啊，为什么是这三个里面最小的？
【在 k****p 的大作中提到】
: 如果是square就可以DP
| b******i
发帖数: 914 | 4 哦，画了个图，想通了。
【在 b******i 的大作中提到】
: 请问你指的是这个吗？
: http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1
: 1) Construct a sum matrix S[R][C] for the given M[R][C].
: a) Copy first row and first columns as it is from M[][] to S[][]
: b) For other entries, use following expressions to construct S[][]
: If M[i][j] is 1 then
: S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
: Else /*If M[i][j] is 0*/
: S[i][j] = 0
: 2) Find the maximum entry in S[R][C]
|
|
