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
115
116
117
118
119
120
121
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);
}
|