b***y
发帖数: 2799 | 1 ☆─────────────────────────────────────☆
observer (笑看人生) 于 (Tue Jun 12 13:04:21 2007) 提到:
N * N的 点阵，点有黑有白，找一个矩形，四角点全黑，面积最大
好象还没人给解法，继续攒人品。
1. Scan 矩阵，找黑点，记录坐标(xi,yi)，存到array， O(N^2)
得到 M 个黑点
2.a 土办法是scan 黑点array, 对任意2个点(x1, y1), (x2, y2)
如果(x1, y2), (x2, y1)也是黑点，（直接查原点阵）
那么是一个合格矩形,
找出max area O(M^2)
2.b 另外一个办法，根据x,y坐标，sort 黑点array，
得到2个sorted array, AX, AY, O(MlgM)
scan AX, 对2个x座标相同的黑点，(x0, y1), (x0, y2)
查 AY找y1, y2, 在y1, y2的黑点中找x座标相同的点,
(x3,y1), (x3,y2), x3 != x0, 那么就是一个合格的矩形
找到max area
一般情 |
|
