aboutsummaryrefslogtreecommitdiff
path: root/max_num_point_grid_query.c
diff options
context:
space:
mode:
Diffstat (limited to 'max_num_point_grid_query.c')
-rw-r--r--max_num_point_grid_query.c122
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);
+}