200. Number of Islands
Medium
Given an <code>m x n</code> 2D binary grid <code>grid</code> which represents a map of <code>'1'</code>s (land) and <code>'0'</code>s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Example 2:
Constraints:
<code>m == grid.length</code>
<code>n == grid[i].length</code>
<code>1 <= m, n <= 300</code>
<code>grid[i][j]</code> is <code>'0'</code> or <code>'1'</code>.
DFS
BFS
时间复杂度：O(MN)
860 · Number of Distinct Islands
Algorithms
Description
Given a non-empty 2D array <code>grid</code> of 0's and 1's, an island is a group of <code>1</code>'s (representing land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by water.
Count the number of distinct islands. An island is considered to be the same as another if and only if one island has the same shape as another island (and not rotated or reflected).
Notice that:
and
are considered different island, because we do not consider reflection / rotation.
The length of each dimension in the given <code>grid</code> does not exceed <code>50</code>.
Example
时间复杂度：O(MN)
434 · Number of Islands II
Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.You need to return an array of size K.
0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
时间复杂度：近似于O(MN)，因为我们认为UnionFind时间复杂度接近O(1)
934. Shortest Bridge
You are given an <code>n x n</code> binary matrix <code>grid</code> where <code>1</code> represents land and <code>0</code> represents water.
An island is a 4-directionally connected group of <code>1</code>'s not connected to any other <code>1</code>'s. There are exactly two islands in <code>grid</code>.
You may change <code>0</code>'s to <code>1</code>'s to connect the two islands to form one island.
Return the smallest number of <code>0</code>'s you must flip to connect the two islands.
Example 3:
<code>n == grid.length == grid[i].length</code>
<code>2 <= n <= 100</code>
<code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.
There are exactly two islands in <code>grid</code>.
<code> </code>
695. Max Area of Island
You are given an <code>m x n</code> binary matrix <code>grid</code>. An island is a group of <code>1</code>'s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value <code>1</code> in the island.
Return the maximum area of an island in <code>grid</code>. If there is no island, return <code>0</code>.
<code>1 <= m, n <= 50</code>
463. Island Perimeter
Easy
You are given <code>row x col</code> <code>grid</code> representing a map where <code>grid[i][j] = 1</code> represents land and <code>grid[i][j] = 0</code> represents water.
Grid cells are connected horizontally/vertically (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).
The island doesn't have "lakes", meaning the water inside isn'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't exceed 100. Determine the perimeter of the island.
Example 1:
<code>row == grid.length</code>
<code>col == grid[i].length</code>
<code>1 <= row, col <= 100</code>
<code>grid[i][j]</code> is <code>0</code> or <code>1</code>.
There is exactly one island in <code>grid</code>.