<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>

'''
grid[i][j]
    i = rows
    j = columns

1 = land
0 = water
land is surrounded by water & "water inside isn't connected to the water around the island."
one cell is a square with side length 1
out of bounds => water
if no only 1 cell with land -> 4
if no only 1 cell with water -> 0

Find Perimeter
Constraints:
    at least 1 row and cell
    1 island per grid so [[0]] won't happen
    either 0 or 1 of type int


1. Iterate n^2 through map
2. Conditions to adhere to:
    if vis -> return 0 thus ends that recursive call
    if grid cell is 1 -> run DFS 
    if grid cell is 0 -> return 0 thus ends that recursive call
    if grid cell is out of bounds -> return 0 thus ends that recursive call

T: worst case n^2 if whole map is 0.  => O(n^2)
S: visited taking the whole map is n^2 + call stack if every cell is 1 -> n^2 => O(n^2)

iterate through whole grid, and run DFS recursively based on conditions above. Return final count

Can we do better?
    1. rewrite original grid to another mark if visited or 0. then only run DFS if grid cell value is 1
        - no space complexity needed except recursive stack which again is n^2
        - just rewrite the 1 value to x and since we are only running DFS if grid value is 1, we simply don't need to do vis anymore
    2. Time simply can't be better, must visit every cell


    x | x | 0 | 0
    1 | x | 0 | 0
    0 | 0 | 0 | 0
    0 | 0 | 0 | 0

     
if grid value is not 1 return 0
if i is outside grid boundaries return 0
if grid value is 1 run DFS and when DFS is done mark it as x

dfs(grid, i, j, total)
    if out of range -> return 1
    if val == 0 -> return 1
    if val == x -> return 0

    # if val == 1:    
    run dfs on range(URDL):
        val of neighbor = 'x'
        total[0] += dfs(grid, i, j, total) # where i and j either i+1, i-1, j+1, j-1
    return total

main:
    total = [0]
    for i in range x
        for j in range y
            if cell == 1:
                cell = x
                return dfs(grid, i, j, total)

    
iterate through map. after we find the first land we mark it and run dfs on it and also return its returned value. since only at worst 1 island we don't have to do anything more for the recursion nested main loop

in the dfs, based on conditions we return 0 or 1. then we run dfs on neighbors. first "sink" the neighbor and then run dfs on the neighbor. make sure to add the result of that neighbor to running total . Continue with the rest of the neighbors recursively the same commands

time: n^2
space: recursive stack call -> n^2


    if out of range -> return 1
    if val == 0 -> return 1
    if val == x -> return 0

    # if val == 1:    
    run dfs on range(URDL):
        val of neighbor = 'x'
        total[0] += dfs(grid, i, j, total) # where i and j either i+1, i-1, j+1, j-1
    return total
'''

class Solution:
    def dfs(self, grid: List[List[int]], row: int, col: int) -> int:
        if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]):
            return 1
        value = grid[row][col]
        if value == 0:
            return 1
        if value == 2:
            return 0
        directions = [[1,0], [0,1], [-1,0], [0,-1]]
        grid[row][col] = 2
        perimeter = 0
        for r, c in directions:
            new_row, new_col = row + r, col + c
            perimeter += self.dfs(grid, new_row, new_col)
        return perimeter

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

19983