Maximum Students Taking Exam LeetCode solution in Python

1
class Solution:
2
    def maxStudents(self, seats: List[List[str]]) -> int:
3
        m, n = len(seats), len(seats[0])
4
        match = [[-1] * n for _ in range(m)]
5

6
        def dfs(i, j, visited):
7
            for x, y in [
8
                (i - 1, j - 1),
9
                (i - 1, j + 1),
10
                (i, j - 1),
11
                (i, j + 1),
12
                (i + 1, j - 1),
13
                (i + 1, j + 1),
14
            ]:
15
                if (
16
                    0 <= x < m
17
                    and 0 <= y < n
18
                    and seats[x][y] == "."
19
                    and (x, y) not in visited
20
                ):
21
                    visited.add((x, y))
22
                    if match[x][y] == -1 or dfs(*match[x][y], visited):
23
                        match[x][y] = (i, j)
24
                        match[i][j] = (x, y)
25
                        return True
26
            return False
27

28
        def max_matching():
29
            cnt = 0
30
            for i in range(m):
31
                for j in range(0, n, 2):
32
                    if seats[i][j] == "." and match[i][j] == -1:
33
                        visited = set()
34
                        cnt += dfs(i, j, visited)
35
            return cnt
36

37
        # returns the number of elements of the maximum independent set in the bipartite set
38
        return (
39
            sum(seats[i][j] == "." for i in range(m) for j in range(n)) - max_matching()
40
        )