aboutsummaryrefslogtreecommitdiff
path: root/max_students_taking_exam.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-22 10:26:50 -0700
committerJack Sangdahl <[email protected]>2024-12-22 10:26:50 -0700
commit54f080060fcc02331855b1958bd371f9769d35da (patch)
treeaa792207f273fc391dd1f438beea284420d8b5a1 /max_students_taking_exam.c
parent27f5c468d6732af671cebc250ad5079e98f2b7e2 (diff)
downloadleetcode-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.c55
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
+}