leetcode_gym/_problems/islandPerimeter.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Island Perimeter	2020-06-19	matrix	https://leetcode.com/problems/island-perimeter	Solved

Problem

Input:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Output: 16

Explanation: The perimeter is the 16 yellow stripes in the image below:

Solution

Iterate thru matrix. If cell==1, add 4.

If it has a left or top border, subtract 2.

{% highlight python %}

class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int:

    R = len(grid)
    C = len(grid[0])
    perimeter = 0
    
    for x,y in product(range(R), range(C)):
        
        if grid[x][y]==1:
            
            perimeter+=4
        
            if x>0 and grid[x-1][y]==1:
                perimeter-=2

            if y>0 and grid[x][y-1]==1:
                perimeter-=2

    
    return perimeter

{% endhighlight %}

---

Using DFS and nonlocal

{% highlight python %}

def islandPerimeter(self, grid: List[List[int]]) -> int:

R = len(grid)
C = len(grid[0])

perimeter=0

def dfs(i,j):
    
    nonlocal perimeter
    
    if i<0 or i>=R or j<0 or j>=C or grid[i][j]==0:     # if border or water, add 1
        perimeter+=1
        return
    
    if grid[i][j]==1:
        grid[i][j]=2    # mark as visited
        dfs(i-1,j)
        dfs(i+1,j)
        dfs(i,j-1)
        dfs(i,j+1)

for i in range(R):
    for j in range(C):
        if grid[i][j]==1:
            dfs(i,j)

return perimeter

{% endhighlight %}

---

using self.variable instead of nonlocal

{% highlight python %}

def islandPerimeter(self, grid: List[List[int]]) -> int:
    
    R = len(grid)
    C = len(grid[0])
    
    self.perimeter = 0
    
    def dfs(i,j):
        
        
        # if out of bounds, add 1 to perimeter
        if i<0 or i>=R or j<0 or j>=C or grid[i][j]==0:
            self.perimeter+=1
            return
        
        # recurse
        if grid[i][j]==1:
            grid[i][j] = 2  # mark visited
            dfs(i-1,j)
            dfs(i+1,j)
            dfs(i,j-1)
            dfs(i,j+1)
        
    for i in range(R):
        for j in range(C):
            
            if grid[i][j]==1:
                dfs(i,j)
                
    return self.perimeter

{% endhighlight %}