aboutsummaryrefslogtreecommitdiff
path: root/min_taps_open_water.c
blob: 77fcf1b8fbf4a572d4259268315392f9f1e9831b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 1326. Minimum Number of Taps to Open to Water a Garden
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

/*
 * there is a one-dimensional garden on the x-axis. the garden starts at the
 * point 0 and ends at the point 'n'. (ie. the length of the garden is 'n')
 * there are 'n +  q' taps located at points '[0, 1, ..., n]' in the garden.
 * given an integer 'n' and an integer array 'ranges' of length 'n + 1' where
 * 'ranges[i]' (0-indexed) means the i'th tap can water the area '[i -
 * ranges[i], i + ranges[i]]' if it was open. return the minimum number of taps
 * that should be open to water the whole garden. if the garden cannot be
 * watered, return -1
 */

int minTaps(int n, int *ranges, int ranges_size) {
  int i, j;
  int *new_ranges = (int *)malloc(sizeof(int) * ranges_size);
  for (i = 0; i < ranges_size; i++)
    new_ranges[i] = ranges[i];
  for (i = ranges_size - 1; i >= 1; i--)
    for (j = 1; j <= ranges[i]; j++) {
      if (i - j == -1)
        break;
      new_ranges[i - j] = fmax(new_ranges[i - j], j + ranges[i]);
    }
  int min_jump;
  int *dp = (int *)malloc(sizeof(int) * ranges_size);
  dp[ranges_size - 1] = 0;
  for (i = 0; i < ranges_size - 1; i++)
    dp[i] = 999999;
  for (i = ranges_size - 2; i >= 0; i--) {
    min_jump = 999999;
    for (j = 1; j <= ranges[i]; j++) {
      if (i + j == ranges_size)
        break;
      min_jump = fmin(min_jump, dp[i + j]);
    }
    dp[i] = min_jump + 1;
  }
  return (dp[0] < 999999) ? dp[0] : -1;
}

int main() {
  int r1[] = {3, 4, 1, 1, 0, 0}, r2[] = {0, 0, 0, 0};
  printf("%d\n", 1);                 // expect: 1
  printf("%d\n", minTaps(3, r2, 4)); // expect: -1
}