diff options
author | Jack Sangdahl <[email protected]> | 2024-12-22 10:26:50 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-22 10:26:50 -0700 |
commit | 54f080060fcc02331855b1958bd371f9769d35da (patch) | |
tree | aa792207f273fc391dd1f438beea284420d8b5a1 /max_students_taking_exam.c | |
parent | 27f5c468d6732af671cebc250ad5079e98f2b7e2 (diff) | |
download | leetcode-54f080060fcc02331855b1958bd371f9769d35da.tar.gz leetcode-54f080060fcc02331855b1958bd371f9769d35da.zip |
1349. maximum students taking exam
Diffstat (limited to 'max_students_taking_exam.c')
-rw-r--r-- | max_students_taking_exam.c | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/max_students_taking_exam.c b/max_students_taking_exam.c new file mode 100644 index 0000000..170e5cd --- /dev/null +++ b/max_students_taking_exam.c @@ -0,0 +1,55 @@ +// 1349. Maximum Students Taking Exam +#include "leetcode.h" + +/* + * given an 'm x n' matrix 'seats' that represent seats distributions in a + * classroom. if a seat is broken, it is denoted by '#' character otherwise it + * is denoted by a '.' character. students can see theanswers of those sitting + * next to the left, right, upper left, and upper right, but cannot see the + * answers of the student sitting directly in front of or behind them. return + * the maximum number of students that can take the exam together without any + * cheating being possible. students must be placed in seats in good condition. + */ + +int maxStudents(char **seats, int seatsSize, int *seatsColSize) { + int n = seatsSize, m = *seatsColSize, ans = 0, dp[9][(1 << 8) + 2], avail[9]; + memset(dp, -1, sizeof(dp)); + for (int i = 1; i <= n; i++) + for (int j = 0; j < m; j++) + if (seats[i - 1][j] == '.') + avail[i] |= (1 << j); + for (int mask = 0; mask < (1 << m); mask++) + dp[0][mask] = 0; + for (int i = 1; i <= n; i++) + for (int pre = 0; pre < (1 << m); pre++) { + if (dp[i - 1][pre] == -1) + continue; + for (int mask = 0; mask < (1 << m); mask++) { + if ((mask & avail[i]) != mask) + continue; + if (mask & (mask >> 1)) + continue; + if (mask & (pre << 1) || mask & (pre >> 1)) + continue; + dp[i][mask] = + fmax(dp[i][mask], dp[i - 1][pre] + __builtin_popcount(mask)); + } + } + for (int mask = 0; mask < (1 << m); mask++) + ans = fmax(ans, dp[n][mask]); + return ans; +} + +int main() { + char *s1[] = {"#", ".", "#", "#", ".", "#", ".", "#", "#", + "#", "#", ".", "#", ".", "#", "#", ".", "#"}; + int ss1 = 3, scs1 = 6; + char *s2[] = {".", "#", "#", "#", "#", ".", "#", "#", ".", "#"}; + int ss2 = 5, scs2 = 2; + char *s3[] = {"#", ".", ".", ".", "#", ".", "#", ".", "#", ".", ".", ".", "#", + ".", ".", ".", "#", ".", "#", ".", "#", ".", ".", ".", "#"}; + int ss3 = 5, scs3 = 5; + printf("%d\n", maxStudents((char **)s1, ss1, &scs1)); // expect: 4 + printf("%d\n", maxStudents((char **)s2, ss2, &scs2)); // expect: 3 + printf("%d\n", maxStudents((char **)s3, ss3, &scs3)); // expect: 10 +} |