2658. Maximum Number of Fish in a Grid

Medium

You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:

• A land cell if grid[r][c] = 0, or

• A water cell containing grid[r][c] fish, if grid[r][c] > 0.

A fisher can start at any water cell (r, c) and can do the following operations any number of times:

• Catch all the fish at cell (r, c), or

• Move to any adjacent water cell.

Return the maximum number of fish the fisher can catch if he chooses his starting cell optimally, or 0 if no water cell exists.

An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) or (r - 1, c) if it exists.

Example 1:

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7
Explanation: The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1
Explanation: The fisher can start at cells (0,0) or (3,3) and collect a single fish. 

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 10

• 0 <= grid[i][j] <= 10

解題

func findMaxFish(grid [][]int) int {
    ans := 0
    sum := 0 

    var helper func(int, int)
    helper = func(x, y int) {
        if x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) {
            return
        }

        if grid[x][y] == 0 || grid[x][y] == -1 { return }

        sum += grid[x][y]
        if sum > ans { ans = sum }

        grid[x][y] = -1

        helper(x+1, y)
        helper(x-1, y)
        helper(x, y+1)
        helper(x, y-1)
    }

    for i:=0; i<len(grid); i++ {
        for j:=0; j<len(grid[0]); j++ {
            if grid[i][j] == 0 || grid[i][j] == -1 { continue }
            sum = 0
            helper(i, j)
        }
    }

    return ans
}