diff options
Diffstat (limited to 'max_num_point_grid_query.c')
-rw-r--r-- | max_num_point_grid_query.c | 122 |
1 files changed, 122 insertions, 0 deletions
diff --git a/max_num_point_grid_query.c b/max_num_point_grid_query.c new file mode 100644 index 0000000..1fbe18a --- /dev/null +++ b/max_num_point_grid_query.c @@ -0,0 +1,122 @@ +// 2503. Maximum Number of Points From Grid Queries +#include "leetcode.h" + +/* + * you are given an 'm x n' integer matrix 'grid' and an array 'queries' of size + * 'k'. find an array 'answer' of size 'k' such that for each integer + * 'queries[i]' start in the top left cell of the matrix and repeat the + * following process: if 'queries[i]' is strictly greater than the value of the + * current cell that you are in, then you get one point if it is your first time + * visiting that cell, and you can move to any adjacent cell in all 4 + * directions, otherwise you do not get any points, and you end this process. + * after the process 'answer[i]' is the maximum number of ponts you can get. + * note that for each query, yu are allowed to visit the same cell multiple + * times. + */ + +struct list { + int val; + int x; + int y; +}; + +struct pp { + int val; + int place; +}; + +int cmp(const void *a, const void *b) { + return (*(struct pp *)a).val - (*(struct pp *)b).val; +} + +void input(int **grid, int gridSize, int gridColSize, int i, int j, + struct list *helper, int *cnt, bool **used, int *curr_point, + int curr_val) { + used[i][j] = true; + if (curr_val > grid[i][j]) { + *curr_point += 1; + if (i - 1 >= 0 && !used[i - 1][j]) + input(grid, gridSize, gridColSize, i - 1, j, helper, cnt, used, + curr_point, curr_val); + if (i + 1 < gridSize && !used[i + 1][j]) + input(grid, gridSize, gridColSize, i + 1, j, helper, cnt, used, + curr_point, curr_val); + if (j - 1 >= 0 && !used[i][j - 1]) + input(grid, gridSize, gridColSize, i, j - 1, helper, cnt, used, + curr_point, curr_val); + if (j + 1 < gridColSize && !used[i][j + 1]) + input(grid, gridSize, gridColSize, i, j + 1, helper, cnt, used, + curr_point, curr_val); + } else { + helper[*cnt].val = grid[i][j]; + helper[*cnt].x = i; + helper[*cnt].y = j; + (*cnt)++; + } +} + +int *maxPoints(int **grid, int gridSize, int *gridColSize, int *queries, + int queriesSize, int *returnSize) { + int curr_point = 0, c1 = 0, c2 = 0; + struct list *h1 = (struct list *)malloc((gridSize * (*gridColSize)) * + sizeof(struct list *)); + struct list *h2 = (struct list *)malloc((gridSize * (*gridColSize)) * + sizeof(struct list *)); + struct pp *revis = (struct pp *)malloc(queriesSize * sizeof(struct pp)); + for (int i = 0; i < queriesSize; i++) { + revis[i].val = queries[i]; + revis[i].place = i; + } + qsort(revis, queriesSize, sizeof(struct pp), cmp); + *returnSize = queriesSize; + int *ans = (int *)malloc(queriesSize * sizeof(int)); + bool **used = (bool **)malloc(queriesSize * sizeof(bool *)); + for (int i = 0; i < gridSize; i++) + used[i] = (bool *)calloc(*gridColSize, sizeof(bool)); + input(grid, gridSize, *gridColSize, 0, 0, h1, &c1, used, &curr_point, + revis[0].val); + ans[revis[0].place] = curr_point; + for (int i = 1; i < queriesSize; i++) { + if ((i & 1) == 1) { + c2 = 0; + for (int j = 0; j < c1; j++) + input(grid, gridSize, *gridColSize, h1[j].x, h1[j].y, h2, &c2, used, + &curr_point, revis[i].val); + } else { + c1 = 0; + for (int j = 0; j < c2; j++) + input(grid, gridSize, *gridColSize, h2[j].x, h2[j].y, h1, &c1, used, + &curr_point, revis[i].val); + } + ans[revis[i].place] = curr_point; + } + free(revis); + free(h1); + free(h2); + for (int i = 0; i < gridSize; i++) + free(used[i]); + free(used); + return ans; +} + +int main() { + int g1i[3][3] = {{1, 2, 3}, {2, 5, 7}, {3, 5, 1}}, q1[] = {5, 6, 2}, rs1; + int g2i[2][3] = {{5, 2, 1}, {1, 1, 2}}, q2[] = {3}, rs2; + struct two_d_arr g1, g2; + two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i); + two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i); + int *mp1 = + maxPoints(g1.arr, g1.row_size, g1.col_size, q1, ARRAY_SIZE(q1), &rs1); + int *mp2 = + maxPoints(g2.arr, g2.row_size, g2.col_size, q2, ARRAY_SIZE(q2), &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", mp1[i]); // expect: 5 8 1 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", mp2[i]); // expect: 0 + printf("\n"); + free(mp1); + free(mp2); + two_d_arr_free(&g1); + two_d_arr_free(&g2); +} |