Smallest Rectangles Enclosing Black Pixels

这道题关键是二分的四个方向代码太复杂了，虽然可以变为二分行和二分列两种，但是还是很多重复部分，另外这道题最优的时间复杂度应该是O(lgnlgm)，因为我们可以进行在找一个点时进行两次二分，当然代码写起来就很麻烦了，然后是普通的一次二分一次遍历，这样时间复杂度是O(nlgm + mlgn)，还可以用DFS和BFS做，这样就是O(nm)了

class Solution(object):
    def minArea(self, image, x, y):
        """
        :type image: List[List[str]]
        :type x: int
        :type y: int
        :rtype: int
        """
        n = len(image)
        if not n:
            return 0

        m = len(image[0])
        if not m:
            return 0

        left, right = None, None
        up, bottom = None, None

        startRow, startCol = x, y
        end = n - 1

        while startRow + 1 < end:
            mid = startRow + (end - startRow) / 2
            if self.check(image, mid, startCol, n, m, 1):
                startRow = mid
            else:
                end = mid

        if self.check(image, end, startCol, n, m, 1):
            bottom = end
        else:
            bottom = startRow

        startRow, startCol = 0, y
        end = x
        while startRow + 1 < end:
            mid = startRow + (end - startRow) / 2
            if self.check(image, mid, startCol, n, m, 1):
                end = mid
            else:
                startRow = mid

        if self.check(image, startRow, startCol, n, m, 1):
            up = startRow
        else:
            up = end

        startRow, startCol = x, y
        end = m - 1
        while startCol + 1 < end:
            mid = startCol + (end - startCol) / 2
            if self.check(image, startRow, mid, n, m, 0):
                startCol = mid
            else:
                end = mid

        if self.check(image, startRow, end, n, m, 0):
            right = end
        else:
            right = startCol

        startRow, startCol = x, 0
        end = y
        while startCol + 1 < end:
            mid = startCol + (end - startCol) / 2
            if self.check(image, startRow, mid, n, m, 0):
                end = mid
            else:
                startCol = mid

        if self.check(image, startRow, startCol, n, m, 0):
            left = startCol
        else:
            left = end


        return (right - left + 1) * (bottom - up + 1)

    def check(self, image, row, col, n, m, row_or_col):
        if row_or_col:
            return image[row].count('1') > 0
        return [image[i][col] for i in xrange(n)].count('1') > 0