k********w
发帖数: 1 | 1 一个矩阵比如是n*n的， 然后每个元素要么黑色要么白色，可以用一个值为0 或者1的
二位整数数组来模拟。 要求找出纯色的最大的正方形子矩阵，比如全是一片的0或者1.
想了很久没有什么特别好的方案，
请大家指教！ |
a****n
发帖数: 1887 | |
b********h
发帖数: 119 | 3 This is the maximal rectangle problem:
http://www.drdobbs.com/184410529
In particular, the last solution provided in the article is the application
of the solution of another interesting problem: Largest rectangle in a
Histogram (problem H in the following link).
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
Both of them have many solutions that are of different complexity. |
a****n
发帖数: 1887 | 4 正方形和矩形解法不一样
application
【在 b********h 的大作中提到】
: This is the maximal rectangle problem:
: http://www.drdobbs.com/184410529
: In particular, the last solution provided in the article is the application
: of the solution of another interesting problem: Largest rectangle in a
: Histogram (problem H in the following link).
: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
: Both of them have many solutions that are of different complexity.
|
b********h
发帖数: 119 | 5 True. I misread the problem. I think the correct solution is DP with the
following recurrence:
S[i][j] = min{ S[i-1][j], S[i][j-1], S[i-1][j-1] } + 1, where S[i][j] is the maximal
size of the square with its bottom right at (i,j) and (i,j) contains the
value you are looking for (either 0 or 1). The largest S[i][j] is the answer
. |
l**********3
发帖数: 161 | 6 S[i,j]怎么初始化？
递归公式不是很懂，能不能举个例子解释一下？谢谢！
the maximal
answer
【在 b********h 的大作中提到】
: True. I misread the problem. I think the correct solution is DP with the
: following recurrence:
: S[i][j] = min{ S[i-1][j], S[i][j-1], S[i-1][j-1] } + 1, where S[i][j] is the maximal
: size of the square with its bottom right at (i,j) and (i,j) contains the
: value you are looking for (either 0 or 1). The largest S[i][j] is the answer
: .
|
