<p>You are given <code>row x col</code> <code>grid</code> representing a map where <code>grid[i][j] = 1</code> represents&nbsp;land and <code>grid[i][j] = 0</code> represents water.</p>

<p>Grid cells are connected <strong>horizontally/vertically</strong> (not diagonally). The <code>grid</code> is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).</p>

<p>The island doesn&#39;t have &quot;lakes&quot;, meaning the water inside isn&#39;t connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don&#39;t exceed 100. Determine the perimeter of the island.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img src="https://assets.leetcode.com/uploads/2018/10/12/island.png" style="width: 221px; height: 213px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
<strong>Output:</strong> 16
<strong>Explanation:</strong> The perimeter is the 16 yellow stripes in the image above.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0]]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>row == grid.length</code></li>
	<li><code>col == grid[i].length</code></li>
	<li><code>1 &lt;= row, col &lt;= 100</code></li>
	<li><code>grid[i][j]</code> is <code>0</code> or <code>1</code>.</li>
	<li>There is exactly one island in <code>grid</code>.</li>
</ul>

'''
time: O(m x n)
        O(m x n)
      return total

space: O(m x n) because of the recursive stack


Optimal method but i wasn't able to figure out the grid syntax, a small part of the DFS was wrong, also my complexity wasn't 'exact'

for loops:
    len(grid)
    len(grid[0])

for exceptions:
    if row in range 0 to len(grid)
    if col in range 0 to len(grid[row])

parameterized vs functional recursions:
    stick to one of them
    parameter = update total[0]
    functional = return 1 or 0 and return it as well

neighbors DFS:
    for i, j in range(directions)
        new_col, new_row = col + i, row + j
        dfs(i, j, grid, total)

    for i, j in range(directions)
        dfs(i, j, grid, total)

5 problems

run grid search on grid and if value is 1 we call dfs on it and then return right after.
dfs:
    check for exceptions -> return 1
    check for 0 neighbor --> return 1
    check for marked/vis --> return 0

    perimeter = 0
    for r, c in directions:
        new_row = r + row
        new_col = c + col
        perimeter += self.dfs(new_row, new_col, grid)
    return perimeter

main:
    for i in range(grid):
        for j in range(grid[0]):
            if grid[i][j] == 1:
                return self.dfs(i, j, grid)

Summary: run the grid search and if 1 is found call dfs on it and return that result via functional recursion. in the dfs, check for exceptions, marked and return respectively. Then collect neighbors total perimiter and return it. That will return back to initial grid search main where we return that same value.

Complexity:
    time: m x n 
    space: m x n bc of call stack but 0 additional space complexity



'''

class Solution:
    def dfs(self, row: int, col: int, grid: List[List[int]]) -> int:

        # out of range or neighbor, return 1 because a yellow perimeter stick:
        if row >= len(grid) or row < 0 or col < 0 or col >= len(grid[0]):
            return 1
        if grid[row][col] == 0:
            return 1

        # 2 represents visited so return 0
        if grid[row][col] == 2:
            return 0

        # mark curr as visited:
        grid[row][col] = 2

        # if cell value is 1, we collect the perimiter of its neighbors and return it to parent:
        perimeter = 0
        directions = [[1,0], [0,1], [-1,0], [0,-1]]
        for r, c in directions:
            new_row = r + row
            new_col = c + col
            perimeter += self.dfs(new_row, new_col, grid)
        return perimeter



    def islandPerimeter(self, grid: List[List[int]]) -> int:
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 1:
                    return self.dfs(row, col, grid)

19879