Island Perimeter

You are given a two-dimensional integer array matrix. Each cell is one of:

• 0: an empty cell
• 1: a cell that belongs to the shape

Return the perimeter of the shape.

The perimeter is the total length of the shape's outline: every side of a 1 cell that borders a 0 cell or the edge of the grid counts as length 1.

You can assume every 1 cell in matrix is connected to every other 1 cell horizontally or vertically, forming exactly one shape, and that the shape has no holes in it.

Examples

Example 1

Input: matrix = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16

Example 2

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

Example 3

Input: matrix = [[1,1],[1,1]]
Output: 8