diff options
author | Jack Sangdahl <[email protected]> | 2025-01-21 20:58:46 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-21 20:58:46 -0700 |
commit | 62ff4e0b7a5495e2fd061e606a0781ccb0f2894c (patch) | |
tree | a2d7d45ccaa61b552ab4dd4b4c261368e5647748 | |
parent | 9a3155d502b44f90ee671b23c8b76dec0079a98f (diff) | |
download | leetcode-master.tar.gz leetcode-master.zip |
-rw-r--r-- | map_highest_peak.c | 114 | ||||
-rw-r--r-- | map_highest_peak.py | 42 |
2 files changed, 156 insertions, 0 deletions
diff --git a/map_highest_peak.c b/map_highest_peak.c new file mode 100644 index 0000000..d98e563 --- /dev/null +++ b/map_highest_peak.c @@ -0,0 +1,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); +} diff --git a/map_highest_peak.py b/map_highest_peak.py new file mode 100644 index 0000000..78bae7d --- /dev/null +++ b/map_highest_peak.py @@ -0,0 +1,42 @@ +# 1765. Map of Highest Peak +from collections import deque + +""" +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. +""" + + +class Solution(object): + def highestPeak(self, isWater): + """ + :type isWater: List[List[int]] + :rtype: List[List[int]] + """ + m, n = len(isWater), len(isWater[0]) + height = [[-1] * n for _ in range(m)] + bfs = deque([]) + for r in range(m): + for c in range(n): + if isWater[r][c] == 1: + bfs.append((r, c)) + height[r][c] = 0 + dir = [0, 1, 0, -1, 0] + while bfs: + r, c = bfs.popleft() + for i in range(4): + nr, nc = r + dir[i], c + dir[i + 1] + if nr < 0 or nr == m or nc < 0 or nc == n or height[nr][nc] != -1: + continue + height[nr][nc] = height[r][c] + 1 + bfs.append((nr, nc)) + return height + + +if __name__ == "__main__": + obj = Solution() + print(obj.highestPeak(isWater=[[0, 1], [0, 0]])) + print(obj.highestPeak(isWater=[[0, 0, 1], [1, 0, 0], [0, 0, 0]])) |