you are given a M x N matrix with 0's and 1's find the matrix with largest number of 1, 1. find the largest square matrix with 1's 2. Find the largest rectangular matrix with all 1's
回复在careercup上的: geniusxsy on October 19, 2009 |Edit | Edit for (a), halve the matrix into two pieces, so the largest square can be: in the left region --- recursive call on the left region in the right region --- recursive call on the right region cross the mid separation line --- O(N*M) So, finally: T(N,M) = 2 * T(N/2,M) + O(N*M)
【在 g*******y 的大作中提到】 : 回复在careercup上的: : geniusxsy on October 19, 2009 |Edit | Edit : for (a), halve the matrix into two pieces, so the largest square can be: : in the left region --- recursive call on the left region : in the right region --- recursive call on the right region : cross the mid separation line --- O(N*M) : So, finally: : T(N,M) = 2 * T(N/2,M) + O(N*M)
Here is the code to find the largest square matrix, for the rectangular, it's a bit more difficult. I will share the code if possible. #include #include const int N = 100; int d[N][N]; int m, n; inline int minF(int a, int b, int c) { return a} int main() { freopen("in.txt", "r", stdin); int i, j; while(scanf("%d%d", &m, &n)!=EOF) { memset(d, 0, sizeof(d)); for(i=1; i<=m; i++) { for(j=1; j<=n; j++) {
is this the square matrix start from [0][0] to [i][i]? I think the problem ask the general square matrix, may start from any place to any place.
it's a bit more difficult. I will share the code if possible.
【在 p*********a 的大作中提到】 : Here is the code to find the largest square matrix, for the rectangular, it's a bit more difficult. I will share the code if possible. : #include : #include : const int N = 100; : int d[N][N]; : int m, n; : inline int minF(int a, int b, int c) { : return a: } : int main()
g*y
30 楼
good~
it's a bit more difficult. I will share the code if possible.
【在 p*********a 的大作中提到】 : Here is the code to find the largest square matrix, for the rectangular, it's a bit more difficult. I will share the code if possible. : #include : #include : const int N = 100; : int d[N][N]; : int m, n; : inline int minF(int a, int b, int c) { : return a: } : int main()
p*u
31 楼
实在看不懂矩形的解法。http://www.ddj.com/architect/184410529 说老实话我怀疑错了。哪位大虾解释一下? cache明明是x固定时,y方向上连续0的个数,那 x = min(11.x+c[y]-1, x_max) // Use the cache, Luke!根本就不make sense.
p*u
32 楼
Finally got it. It is similiar to find the biggest rectangle in histogram.