1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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=[
["#", ".", ".", ".", "#"],
[".", "#", ".", "#", "."],
[".", ".", "#", ".", "."],
[".", "#", ".", "#", "."],
["#", ".", ".", ".", "#"],
]
)
)
|