Python lakes and multiple islands Commented


  • 1
    D

    This is a recursive, graph-like deep first traversal approach to this problem.
    And it also works with multiples islands and lakes.

    I left debugging function if you want, just remove # in front of them.


    class Solution(object):
    
        def show(self, i, j):
            print("["+str(j)+"]["+str(i)+"]")
    
        def mark(self, m, i, j):
            m[j][i] = True;
    
        def gi(self, m):
            return len(m[0])
    
        def gj(self, m):
            return len(m)
    
        def ni(self, m, i, j): #check i-axis value
            ret = 0;
            li = self.gi(m)
            lj = self.gj(m)
            if ( i != 0 and i != li - 1 ): #i is not an edge value 0 or li - 1
                ret += (m[j][i - 1] == 0) + (m[j][i + 1] == 0)
            elif ( i == 0 and i < li -1): #left side length not 1
                ret += 1 + (m[j][i + 1] == 0)
            elif ( li == 1): #length is one so add 2 right now
                ret = 2
            elif ( i == li - 1 ): #right side
                ret += 1 + (m[j][i - 1] == 0)
            return ret
    
        def nj(self, m, i, j): #check j-axis
            ret = 0;
            li = self.gi(m)
            lj = self.gj(m)
            if ( j != 0 and j != lj - 1 ): #j is not an edge value 0 or lj - 1
                ret += (m[j - 1][i] == 0) + (m[j + 1][i] == 0)
            elif ( j == 0 and j < lj -1): #up side length not 1
                ret += 1 + (m[j + 1][i] == 0)
            elif( lj == 1): #length is one so add 2 right now
                ret = 2
            elif ( j == lj - 1 ): #down side
                ret += 1 + (m[j - 1][i] == 0)
            return ret
    
        def nij(self, m, i, j): #check (i/j)-axis
            return self.ni(m, i, j) + self.nj(m, i, j)
    
        def rec(self, g, m, i, j):
            self.mark(m, i, j) #mark as seen
            
            #recursive call on direction if possible else 0 #(dayum a pthon ternary in comments)
            left  = self.rec(g, m, i - 1, j) if i != 0 and g[j][i - 1] and not m[j][i - 1] else 0
            right = self.rec(g, m, i + 1, j) if i != self.gi(m) - 1 and g[j][i + 1] and not m[j][i + 1]else 0
            up    = self.rec(g, m, i, j - 1) if j != 0 and g[j - 1][i] == 1 and not m[j - 1][i] else 0
            down  = self.rec(g, m, i, j + 1) if j != self.gj(m) - 1 and g[j + 1][i] == 1 and not m[j + 1][i] else 0
            
            #print("["+str(j) + "][" + str(i) + "] :  i->" + str(self.ni(g, i, j)) + "  j->" + str(self.nj(g, i, j)))
            return self.nij(g, i, j) + left + right + up + down
            
        def islandPerimeter(self, g):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            i = 0
            j = 0
            lj = self.gj(g)
            li = self.gi(g)
            #if it's empty return 0
            if (lj == 1 and li == 0):
                return 0
            
            # create the mark matrix
            m = [ [False for i in range(self.gi(g))] for x in range(self.gj(g)) ]
            sofar = 0
            
            # go thru all the matrix and when it's a 1 call rec() if m[j][i] is not marked as seen
            # add the recurn value to sofar
            while( j < lj ):
                i = 0
                while( i < li ):
                    if (g[j][i] == 1 and not m[j][i]):
                        sofar += self.rec(g, m, i, j)
                    i += 1
                j += 1
            return sofar
    

Log in to reply
 

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