leetcode-go/leetcode/hard/329.longest-increasing-path-in-a-matrix.go

type pair struct {
	_1 int
	_2 int
}

func longestIncreasingPath(matrix [][]int) (max int) {
	m := len(matrix)
	if m == 0 {
		return 0
	}
	n := len(matrix[0])
	if n == 0 {
		return 0
	}
	mem := make(map[pair]int)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			max = maxInt(max, dfs(matrix, m, n, j-1, i, matrix[i][j], &mem))
			max = maxInt(max, dfs(matrix, m, n, j+1, i, matrix[i][j], &mem))
			max = maxInt(max, dfs(matrix, m, n, j, i-1, matrix[i][j], &mem))
			max = maxInt(max, dfs(matrix, m, n, j, i+1, matrix[i][j], &mem))
		}
	}
	max++
	return
}

func dfs(matrix [][]int, m, n, x, y, val int, mem *map[pair]int) (max int) {
	if x < 0 || y < 0 || m <= y || n <= x || matrix[y][x] <= val {
		return 0
	}
	if l, ok := (*mem)[pair{x, y}]; ok {
		return l
	}
	max = maxInt(max, dfs(matrix, m, n, x-1, y, matrix[y][x], mem))
	max = maxInt(max, dfs(matrix, m, n, x+1, y, matrix[y][x], mem))
	max = maxInt(max, dfs(matrix, m, n, x, y-1, matrix[y][x], mem))
	max = maxInt(max, dfs(matrix, m, n, x, y+1, matrix[y][x], mem))
	max++
	(*mem)[pair{x, y}] = max
	return
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}