140 lines
2.6 KiB
Markdown
140 lines
2.6 KiB
Markdown
---
|
|
layout: page
|
|
title: Island Perimeter
|
|
last_solved: 2020-06-19
|
|
category: matrix
|
|
leetcode_url: https://leetcode.com/problems/island-perimeter
|
|
status: 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 %} |