aboutsummaryrefslogtreecommitdiff
path: root/max_students_taking_exam.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_students_taking_exam.py')
-rw-r--r--max_students_taking_exam.py89
1 files changed, 89 insertions, 0 deletions
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=[
+ ["#", ".", ".", ".", "#"],
+ [".", "#", ".", "#", "."],
+ [".", ".", "#", ".", "."],
+ [".", "#", ".", "#", "."],
+ ["#", ".", ".", ".", "#"],
+ ]
+ )
+ )