1473. Paint House III Hard

1/**
2 * [1473] Paint House III
3 *
4 * There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that have been painted last summer should not be painted again.
5 * A neighborhood is a maximal group of continuous houses that are painted with the same color.
6 * 
7 * 	For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}].
8 * 
9 * Given an array houses, an m x n matrix cost and an integer target where:
10 * 
11 * 	houses[i]: is the color of the house i, and 0 if the house is not painted yet.
12 * 	cost[i][j]: is the cost of paint the house i with the color j + 1.
13 * 
14 * Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods. If it is not possible, return -1.
15 *  
16 * Example 1:
17 * 
18 * Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
19 * Output: 9
20 * Explanation: Paint houses of this way [1,2,2,1,1]
21 * This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
22 * Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.
23 * 
24 * Example 2:
25 * 
26 * Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
27 * Output: 11
28 * Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
29 * This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
30 * Cost of paint the first and last house (10 + 1) = 11.
31 * 
32 * Example 3:
33 * 
34 * Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
35 * Output: -1
36 * Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	m == houses.length == cost.length
42 * 	n == cost[i].length
43 * 	1 <= m <= 100
44 * 	1 <= n <= 20
45 * 	1 <= target <= m
46 * 	0 <= houses[i] <= n
47 * 	1 <= cost[i][j] <= 10^4
48 * 
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/paint-house-iii/
53// discuss: https://leetcode.com/problems/paint-house-iii/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57impl Solution {
58    pub fn min_cost(houses: Vec<i32>, cost: Vec<Vec<i32>>, m: i32, n: i32, target: i32) -> i32 {
59        0
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_1473() {
71    }
72}
73