← 返回 snapchat 的题目列表Return the Sizes of All Islands
类型：online_judge
Given a binary matrix grid containing only 0s and 1s:
0 represents water;
1 represents land;
An island is formed by land cells connected vertically or horizontally. Diagonal connections do not count.
Return an integer array containing the area of every island. The area of an island is the number of land cells in that island.
To make the output deterministic, return areas in the order in which islands are first encountered while scanning the matrix row by row, from left to right.
Also implement or explain how to return the maximum island area. If there are no islands, the maximum area is 0.
Input Format
First line: two integers m n, the number of rows and columns.
Next m lines: n space-separated integers (0 or 1) per line.
Output Format
First line: all island areas in discovery order, separated by spaces; print an empty line if there are no islands.
Second line: the maximum island area.
Example
Input:
4 5
1 1 0 0 0
1 0 0 1 1
0 0 1 0 0
0 0 0 1 1
Output:
3 2 1 2
3
Constraints
1 <= m, n <= 500
grid[i][j] is either 0 or 1
Avoid recursive DFS because a large grid may exceed the recursion limit.
Example
Input
4 5
1 1 0 0 0
1 0 0 1 1
0 0 1 0 0
0 0 0 1 1
Output
3 2 1 2
3