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 | |
parent | 27f5c468d6732af671cebc250ad5079e98f2b7e2 (diff) | |
download | leetcode-54f080060fcc02331855b1958bd371f9769d35da.tar.gz leetcode-54f080060fcc02331855b1958bd371f9769d35da.zip |
1349. maximum students taking exam
-rw-r--r-- | max_students_taking_exam.c | 55 | ||||
-rw-r--r-- | max_students_taking_exam.py | 89 |
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=[ + ["#", ".", ".", ".", "#"], + [".", "#", ".", "#", "."], + [".", ".", "#", ".", "."], + [".", "#", ".", "#", "."], + ["#", ".", ".", ".", "#"], + ] + ) + ) |