Richest Lake

Medium

A map is given as a matrix pond. A cell holding 0 is land; a cell holding a positive value is water, and the value is the number of fish in it. A fisher picks any water cell to start from. From there they may step into an adjacent water cell (up, down, left or right; not diagonally) and catch all the fish in every cell they visit. Land cannot be crossed. Return the largest number of fish that can be caught with the best choice of starting cell, or 0 if the map has no water.

Example 1

pond=[[3, 0, 2], [1, 0, 5], [0, 4, 0]] → 7

There are three lakes: cells 3 and 1 give 4 fish, cells 2 and 5 give 7, and the lone cell at the bottom gives 4. The best catch is 7.

Example 2

pond=[[0, 0], [0, 0]] → 0

There is no water at all, so nothing can be caught.

Example 3

pond=[[1, 2, 0], [0, 3, 0], [6, 0, 0]] → 6

Cells 1, 2 and 3 are connected and give 6. The 6 cell only touches the 3 cell diagonally, so it is a separate lake, also worth 6.

Constraints

1 ≤ number of rows, number of columns ≤ 10
0 ≤ pond[i][j] ≤ 10

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium Largest Forest Patch Medium A Board Cut by Slashes Medium Landlocked Land Cells Medium

Input

pond=[[3, 0, 2], [1, 0, 5], [0, 4, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 101 tests on the server, hidden ones included.