aboutsummaryrefslogtreecommitdiff
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
parent27f5c468d6732af671cebc250ad5079e98f2b7e2 (diff)
downloadleetcode-54f080060fcc02331855b1958bd371f9769d35da.tar.gz
leetcode-54f080060fcc02331855b1958bd371f9769d35da.zip
1349. maximum students taking exam
-rw-r--r--max_students_taking_exam.c55
-rw-r--r--max_students_taking_exam.py89
2 files changed, 144 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
+}
diff --git a/max_students_taking_exam.py b/max_students_taking_exam.py
new file mode 100644
index 0000000..2a7882c
--- /dev/null
+++ b/max_students_taking_exam.py
@@ -0,0 +1,89 @@
+# 1349. Maximum Students Taking Exam
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def maxStudents(self, seats):
+ """
+ :type seats: List[List[str]]
+ :rtype: int
+ """
+ n, m = len(seats), len(seats[0])
+ match = [[-1] * m for _ in range(n)]
+
+ def dfs(node, seen):
+ r, c = node
+ for nr, nc in [
+ [r - 1, c - 1],
+ [r, c - 1],
+ [r, c + 1],
+ [r - 1, c + 1],
+ [r + 1, c - 1],
+ [r + 1, c + 1],
+ ]:
+ if (
+ 0 <= nr < n
+ and 0 <= nc < m
+ and not seen[nr][nc]
+ and seats[nr][nc] == "."
+ ):
+ seen[nr][nc] = True
+ if match[nr][nc] == -1 or dfs(match[nr][nc], seen):
+ match[nr][nc] = (r, c)
+ return True
+ return False
+
+ def hungarian():
+ res = 0
+ for c in range(0, m, 2):
+ for r in range(n):
+ if seats[r][c] == ".":
+ seen = [[False] * m for _ in range(n)]
+ if dfs((r, c), seen):
+ res += 1
+ return res
+
+ ans, cnt = hungarian(), 0
+ for r in range(n):
+ for c in range(m):
+ if seats[r][c] == ".":
+ cnt += 1
+ return cnt - ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxStudents(
+ seats=[
+ ["#", ".", "#", "#", ".", "#"],
+ [".", "#", "#", "#", "#", "."],
+ ["#", ".", "#", "#", ".", "#"],
+ ]
+ )
+ )
+ print(
+ obj.maxStudents(
+ seats=[[".", "#"], ["#", "#"], ["#", "."], ["#", "#"], [".", "#"]]
+ )
+ )
+ print(
+ obj.maxStudents(
+ seats=[
+ ["#", ".", ".", ".", "#"],
+ [".", "#", ".", "#", "."],
+ [".", ".", "#", ".", "."],
+ [".", "#", ".", "#", "."],
+ ["#", ".", ".", ".", "#"],
+ ]
+ )
+ )