leetcode-go/oj/google-2019/candy.go

package main

import "fmt"

type candy struct {
	row int
	col int
}

const INF int = 1000000

func getMinimalTime(candies []candy, n int) int {
	pos := make([][2]int, n)
	for i := range pos {
		pos[i][0] = INF
	}
	for _, c := range candies {
		pos[c.row][0] = minInt(pos[c.row][0], c.col)
		pos[c.row][1] = maxInt(pos[c.row][1], c.col)
	}
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i := range dp[0] {
		dp[0][i] = INF
	}
	dp[0][0] = -1
	for i := 1; i <= n; i++ {
		for j := 0; j < n; j++ {
			if pos[i-1][0] == INF {
				dp[i][j] = 1 + dp[i-1][j]
				continue
			}
			dp[i][j] = INF
			for k := 0; k < n; k++ {
				if beg, end := pos[i-1][0], pos[i-1][1]; k <= beg {
					dp[i][j] = minInt(dp[i][j], 1+dp[i-1][k]+end-k+abs(end-j))
				} else if end <= k {
					dp[i][j] = minInt(dp[i][j], 1+dp[i-1][k]+k-beg+abs(beg-j))
				} else {
					dp[i][j] = minInt(dp[i][j], 1+dp[i-1][k]+end-beg+minInt(k-beg+abs(end-j), end-k+abs(beg-j)))
				}
			}
		}
	}
	min := INF
	for _, i := range dp[n] {
		min = minInt(min, i)
	}
	return min
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

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

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

func main() {
	// Case 1
	// 1 1 0 0 0
	// 0 1 1 0 0
	// 0 0 1 1 0
	// 0 0 0 1 1
	// 0 0 0 0 1
	var candies []candy
	for i := 0; i < 5; i++ {
		candies = append(candies, candy{i, i})
		if i+1 < 5 {
			candies = append(candies, candy{i, i + 1})
		}
	}
	fmt.Println(getMinimalTime(candies, 5) == 8)
	// Case 2
	// Fill all grid with candies
	candies = make([]candy, 0)
	for i := 0; i < 5; i++ {
		for j := 0; j < 5; j++ {
			candies = append(candies, candy{i, j})
		}
	}
	// Case 3
	// No candy
	fmt.Println(getMinimalTime(candies, 5) == 24)
	candies = make([]candy, 0)
	fmt.Println(getMinimalTime(candies, 5) == 4)
}