You are given a row x col integer matrix grid representing a map, where grid[i][j] = 1 denotes land and grid[i][j] = 0 denotes water.

Cells in the grid are connected only in the horizontal and vertical directions (not diagonally). The entire grid is surrounded by water, and there is exactly one island consisting of one or more connected land cells.

The island has no internal "lakes," meaning there are no water cells completely enclosed by land. Each cell is a square with a side length of 1. The grid has a rectangular shape, with both width and height not exceeding 100.

Return the perimeter of the island.

Example 1:

Input: grid = [[1,0,1,0],[1,1,1,1],[0,0,1,1],[0,0,0,0]]
Output: 16
Explanation: The perimeter is the 16 red stripes in the image above.

Example 2:

Input: grid = [[0,1]]
Output: 4

Example 3:

Input: grid = [[1]]
Output: 4

Constraints

row == grid.length

col == grid[0].length, and every row in grid has exactly col cells.

1 <= row, col <= 100

grid[i][j] is 0 or 1.

There is exactly one island in grid.

56. Perimeter of Island