LeetCode/go/maximum-number-of-fish-in-a-grid.go

package main

func findMaxFish(grid [][]int) int {
	DIRECTIONS := [][]int{
		{0, 1},
		{0, -1},
		{1, 0},
		{-1, 0},
	}

	width, height := len(grid[0]), len(grid)
	inRange := func(y, x int) bool {
		return y >= 0 && y < height && x >= 0 && x < width
	}

	var dfs func(int, int) int
	dfs = func(y, x int) int {
		if !inRange(y, x) || grid[y][x] == 0 {
			return 0
		}

		// record found fish and reset to zero to mark as irrelevant
		found := grid[y][x]
		grid[y][x] = 0

		for _, dir := range DIRECTIONS {
			dy, dx := dir[0], dir[1]
			found += dfs(y+dy, x+dx)
		}

		return found
	}

	foundMax := 0
	for y, row := range grid {
		for x, _ := range row {
			foundMax = max(foundMax, dfs(y, x))
		}
	}

	return foundMax
}