aboutsummaryrefslogtreecommitdiff
path: root/map_highest_peak.c
blob: d98e563a045d526ed77ece349d23ec7b18cd709f (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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// 1765. Map of Highest Peak
#include "leetcode.h"

/*
 * you are given an integer matrix 'isWater' of size 'm x n' that represents a
 * map of land and water cells. if 'isWater[i][j] == 0' cell '(i, j)' is a land
 * cell. if 'isWater[i][j] == 1', cell '(i, j)' is a water cell. you must assign
 * each cell a height in a way that follows the given rules. find an assignment
 * of heights such that the maximum height in the matrix is maximised.
 */

struct land {
  int x;
  int y;
  int val;
  struct land *next;
};

struct land *head, *tail;

void push(int x, int y, int val) {
  struct land *tmp = (struct land *)malloc(sizeof(struct land));
  tmp->x = x;
  tmp->y = y;
  tmp->val = val;
  tmp->next = NULL;
  if (!head) {
    head = tmp;
    tail = tmp;
  } else {
    tail->next = tmp;
    tail = tmp;
  }
}

void bfs(int **isWater, int row, int col, struct land *curr) {
  isWater[curr->x][curr->y] = curr->val ? curr->val : -1;
  if (curr->x - 1 >= 0)
    if (!isWater[curr->x - 1][curr->y]) {
      isWater[curr->x - 1][curr->y] = -1;
      push(curr->x - 1, curr->y, curr->val + 1);
    }
  if (curr->x + 1 < row)
    if (!isWater[curr->x + 1][curr->y]) {
      isWater[curr->x + 1][curr->y] = -1;
      push(curr->x + 1, curr->y, curr->val + 1);
    }
  if (curr->y - 1 >= 0)
    if (!isWater[curr->x][curr->y - 1]) {
      isWater[curr->x][curr->y - 1] = -1;
      push(curr->x, curr->y - 1, curr->val + 1);
    }
  if (curr->y + 1 < col)
    if (!isWater[curr->x][curr->y + 1]) {
      isWater[curr->x][curr->y + 1] = -1;
      push(curr->x, curr->y + 1, curr->val + 1);
    }
  if (curr->next)
    bfs(isWater, row, col, curr->next);
  free(curr);
}

int **highestPeak(int **isWater, int isWaterSize, int *isWaterColSize,
                  int *returnSize, int **returnColumnSizes) {
  head = NULL, tail = NULL;
  for (int i = 0; i < isWaterSize; i++)
    for (int j = 0; j < *isWaterColSize; j++)
      if (isWater[i][j])
        push(i, j, 0);
  int col = *isWaterColSize;
  bfs(isWater, isWaterSize, *isWaterColSize, head);
  for (int i = 0; i < isWaterSize; i++)
    for (int j = 0; j < *isWaterColSize; j++)
      if (isWater[i][j] == -1)
        isWater[i][j] = 0;
  *returnSize = isWaterSize;
  *returnColumnSizes = (int *)malloc(isWaterSize * sizeof(int));
  for (int i = 0; i < *returnSize; i++)
    (*returnColumnSizes)[i] = *isWaterColSize;
  return isWater;
}

int main() {
  int iw1i[2][2] = {{0, 1}, {0, 0}},
      iw2i[3][3] = {{0, 0, 1}, {1, 0, 0}, {0, 0, 0}};
  struct two_d_arr iw1, iw2;
  two_d_arr_init(&iw1, ARRAY_SIZE(iw1i), ARRAY_SIZE(iw1i[0]), iw1i);
  two_d_arr_init(&iw2, ARRAY_SIZE(iw2i), ARRAY_SIZE(iw2i[0]), iw2i);
  int rs1, rs2, *rcs1, *rcs2;
  int **hp1 = highestPeak(iw1.arr, iw1.row_size, iw1.col_size, &rs1, &rcs1);
  int **hp2 = highestPeak(iw2.arr, iw2.row_size, iw2.col_size, &rs2, &rcs2);
  for (int i = 0; i < rs1; i++) {
    for (int j = 0; j < rcs1[i]; j++)
      printf("%d ", hp1[i][j]); // expect: 1 0 2 1
    printf("\n");
  }
  printf("\n");
  for (int i = 0; i < rs2; i++) {
    for (int j = 0; j < rcs2[i]; j++)
      printf("%d ", hp2[i][j]); // expect: 1 1 0 0 1 1 1 2 2
    printf("\n");
  }
  printf("\n");
  for (int i = 0; i < rs1; i++)
    free(hp1[i]);
  free(hp1);
  free(rcs1);
  two_d_arr_free(&iw1);
  for (int i = 0; i < rs2; i++)
    free(hp2[i]);
  free(hp2);
  free(rcs2);
  two_d_arr_free(&iw2);
}