leetcode-go/hard/403.frog-jump.go

func canCross(stones []int) bool {
	n := len(stones)
	if n == 1 {
		return true
	} else if n == 0 || stones[1] != 1 {
		return false
	}
	m := make(map[int]bool)
	for i := 1; i < n; i++ {
		if 2*stones[i-1]+1 < stones[i] {
			return false // Pruning when the gap is too large.
		}
		m[stones[i]] = true
	}
	return dfs(m, stones[n-1], 1, 1)
}

func dfs(m map[int]bool, end, pos, jump int) bool {
	if pos+jump+1 == end || pos+jump == end || pos+jump-1 == end {
		return true
	}
	if _, ok := m[pos+jump+1]; ok {
		if dfs(m, end, pos+jump+1, jump+1) {
			return true
		}
	}
	if _, ok := m[pos+jump]; ok {
		if dfs(m, end, pos+jump, jump) {
			return true
		}
	}
	if jump == 1 { // 0 is not valid
		return false
	} else if _, ok := m[pos+jump-1]; ok {
		if dfs(m, end, pos+jump-1, jump-1) {
			return true
		}
	}
	return false
}