Skills101
← All coding problems

Max Area of Island

easyGraphs II+10 XPTime limit 2s

A map is a grid of 0 (water) and 1 (land). An island is a group of land cells connected up, down, left or right (not diagonally). Its area is the number of cells in it. Find the area of the largest island.

Input:

  • line 1: r c
  • next r lines: c values (0 or 1) separated by spaces

Output: the largest island's area, or 0 if there is no land.

Constraints: 1 ≤ r, c ≤ 300.

Think about it: scan every cell; when you find unvisited land, flood-fill its whole island (DFS or BFS), counting cells and marking them visited. A grid that is all land is one island of 90 000 cells — use an explicit stack, not deep recursion.

Sample input 1

4 5
1 1 0 0 0
1 1 0 1 1
0 0 0 1 0
0 1 0 0 1

Sample output 1

4

Sample input 2

2 2
0 0
0 0

Sample output 2

0

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.