10-line Simple Python solution based on BFS


  • 0
    class Solution(object):
        def minArea(self, image, r, c):
            m, n, queue = len(image), len(image[0]), [(r, c)]
            visited, minr, minc, maxr, maxc = {(r, c)}, m + 1, n + 1, -1, -1
            for r, c in queue:
                minr, minc, maxr, maxc = min(minr, r), min(minc, c), max(maxr, r), max(maxc, c)
                for d in {(-1, 0), (1, 0), (0, 1), (0, -1)}:
                    nr, nc = r + d[0], c + d[1]
                    if 0 <= nr < m and 0 <= nc < n and image[nr][nc] != "0" and (nr, nc) not in visited:
                        visited |= {(nr, nc)}
                        queue += (nr, nc),
            return (maxr - minr + 1) * (maxc - minc + 1)

  • 0
    W

    My code is almost the same as yours. How come I got Time Limit Exceed? Could you help? Really appreciate it.

    class Solution(object):
    def minArea(self, image, x, y):
        xmin,xmax=x,x
        ymin,ymax=y,y
        visted,frontier=[],[]
        visted.append((x,y))
        frontier.append((x,y))
        for ele in frontier:
                visted.append((ele[0],ele[1]))
                if ele[0]-1>=0 and image[ele[0]-1][ele[1]]=="1" and (not (ele[0]-1,ele[1]) in visted):
                    frontier.append((ele[0]-1,ele[1]))
                    xmin=ele[0]-1
                if ele[0]+1<len(image) and image[ele[0]+1][ele[1]]=="1" and (not (ele[0]+1,ele[1]) in visted):
                    frontier.append((ele[0]+1,ele[1]))
                    xmax=ele[0]+1
                if ele[1]-1>=0 and image[ele[0]][ele[1]-1]=="1" and (not (ele[0],ele[1]-1) in visted):
                    frontier.append((ele[0],ele[1]-1))
                    ymin=ele[1]-1
                if ele[1]+1<len(image[0]) and image[ele[0]][ele[1]+1]=="1" and (not (ele[0],ele[1]+1) in visted):
                    frontier.append((ele[0],ele[1]+1))
                    ymax=ele[1]+1
                
        return (ymax-ymin+1)*(xmax-xmin+1)
    

  • 0

    @wei89 Some quirks in Python. Mine cannot get accepted too and I think the idea is exactly the same.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.