<p>Given a <code>m&nbsp;* n</code>&nbsp;matrix <code>seats</code>&nbsp;&nbsp;that represent seats distributions&nbsp;in a classroom.&nbsp;If a seat&nbsp;is&nbsp;broken, it is denoted by <code>&#39;#&#39;</code> character otherwise it is denoted by a <code>&#39;.&#39;</code> character.</p>

<p>Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting&nbsp;directly in front or behind him. Return the <strong>maximum </strong>number of students that can take the exam together&nbsp;without any cheating being possible.</p>

<p>Students must be placed in seats in good condition.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img height="200" src="https://assets.leetcode.com/uploads/2020/01/29/image.png" width="339" />
<pre>
<strong>Input:</strong> seats = [[&quot;#&quot;,&quot;.&quot;,&quot;#&quot;,&quot;#&quot;,&quot;.&quot;,&quot;#&quot;],
&nbsp;               [&quot;.&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;#&quot;,&quot;.&quot;],
&nbsp;               [&quot;#&quot;,&quot;.&quot;,&quot;#&quot;,&quot;#&quot;,&quot;.&quot;,&quot;#&quot;]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Teacher can place 4 students in available seats so they don&#39;t cheat on the exam. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> seats = [[&quot;.&quot;,&quot;#&quot;],
&nbsp;               [&quot;#&quot;,&quot;#&quot;],
&nbsp;               [&quot;#&quot;,&quot;.&quot;],
&nbsp;               [&quot;#&quot;,&quot;#&quot;],
&nbsp;               [&quot;.&quot;,&quot;#&quot;]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Place all students in available seats. 

</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> seats = [[&quot;#&quot;,&quot;.&quot;,&quot;<strong>.</strong>&quot;,&quot;.&quot;,&quot;#&quot;],
&nbsp;               [&quot;<strong>.</strong>&quot;,&quot;#&quot;,&quot;<strong>.</strong>&quot;,&quot;#&quot;,&quot;<strong>.</strong>&quot;],
&nbsp;               [&quot;<strong>.</strong>&quot;,&quot;.&quot;,&quot;#&quot;,&quot;.&quot;,&quot;<strong>.</strong>&quot;],
&nbsp;               [&quot;<strong>.</strong>&quot;,&quot;#&quot;,&quot;<strong>.</strong>&quot;,&quot;#&quot;,&quot;<strong>.</strong>&quot;],
&nbsp;               [&quot;#&quot;,&quot;.&quot;,&quot;<strong>.</strong>&quot;,&quot;.&quot;,&quot;#&quot;]]
<strong>Output:</strong> 10
<strong>Explanation:</strong> Place students in available seats in column 1, 3 and 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>seats</code>&nbsp;contains only characters&nbsp;<code>&#39;.&#39;<font face="sans-serif, Arial, Verdana, Trebuchet MS">&nbsp;and</font></code><code>&#39;#&#39;.</code></li>
	<li><code>m ==&nbsp;seats.length</code></li>
	<li><code>n ==&nbsp;seats[i].length</code></li>
	<li><code>1 &lt;= m &lt;= 8</code></li>
	<li><code>1 &lt;= n &lt;= 8</code></li>
</ul>

from collections import OrderedDict

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        """We can regard the matrix of seats as defining a graph, wherein an
        edge exists from a seat u to a seat v iff u can see v and neither u nor
        v is a broken seat.
    
        Observe that the maximum number of students that can take the exam
        together without the possibility of cheating is equal to the size of a
        maximum independent set in this graph -- that is, a set of vertices no
        two of which are adjacent, and such that no set of larger cardinality
        has this property.
    
        We'll compute the size of a maximum independent set indirectly, by
        first computing the size of a minimum vertex cover -- that is, a set of
        vertices that includes at least one endpoint from each edge, and such
        that no set of smaller cardinality has this property. Since the
        complement of a vertex cover is an independent set, the complement of a
        minimum vertex cover is a maximum independent set. Therefore the size
        of a maximum independent set is equal to the total number of vertices
        minus the size of a minimum vertex cover.
    
        In a further act of indirection, we'll compute the size of a minimum
        vertex cover in terms of the size of a maximum matching -- that is, a
        set of edges no two of which share an endpoint, and such that no set of
        larger cardinality has this property. Konig's theorem tells us that
        these two sizes are equal in any bipartite graph, and we can easily see
        that our graph is bipartite: if we color the seats in even columns red
        and the seats in odd columns green, then no edge connects two vertices
        of the same color.
    
        Finally, through yet one more layer of indirection, we'll compute the
        size of a maximum matching in our bipartite graph by computing the
        maximum flow between a "virtual" source and sink added to our graph,
        where the sink has a unit-weight edge to each red vertex, each red
        vertex has a unit-weight edge to each green vertex, and each green
        vertex has a unit-weight edge to the sink. This computation will
        leverage the Ford-Fulkerson method.
    
        In short, the maximum number of students who can take the exam without
        the possibility of cheating equals the total number of vertices minus
        the maximum flow as computed by the Ford-Fulkerson method.
    
        Time complexity: O(mn + max_flow * V^2)
        - O(mn) to enumerate the nonbroken seats
        - O(max_flow * V^2) to compute maximum flow; using adjacency lists
          instead of an adjacency matrix, and finding augmenting paths with
          BFS instead of DFS would achieve O(mn + V * E^2)
    
        Space complexity: O(V^2)
        - O(V^2) to track capacities and flows; using adjacency lists instead
          of an adjacency matrix would achieve O(E)
    
    
        EXAMPLES:
    
        >>> max_students(
        ...     [
        ...         ["#",".",".",".","#"],
        ...         [".","#",".","#","."],
        ...         [".",".","#",".","."],
        ...         [".","#",".","#","."],
        ...         ["#",".",".",".","#"]
        ...     ]
        ...  )
        10
    
        >>> max_students(
        ...     [
        ...         ["#",".","#","#",".","#"],
        ...         [".","#","#","#","#","."],
        ...         ["#",".","#","#",".","#"]
        ...     ]
        ...  )
        4
    
        >>> max_students(
        ...     [
        ...         [".","#"],
        ...         ["#","#"],
        ...         ["#","."],
        ...         ["#","#"],
        ...         [".","#"]
        ...     ]
        ...  )
        3
    
        >>> max_students(
        ...     [
        ...         ["#","#","#",".","#"],
        ...         [".",".","#",".","."],
        ...         ["#",".","#",".","#"],
        ...         [".",".",".",".","."],
        ...         [".",".",".","#","."]
        ...     ]
        ...  )
        9
        """
        dim_row = len(seats)
        dim_col = len(seats[0])
    
	    # This part is O(mn).
        nonbroken_seats = OrderedDict(
            ((i, j), True)
            for i in range(dim_row)
            for j in range(dim_col)
            if seats[i][j] == "."
        )
    
        # Assign successive integer IDs to the nonbroken seats. These IDs will be
        # the vertices in our flow network.
        vtx_by_seat = {(i, j): u for u, (i, j) in enumerate(nonbroken_seats)}
    
        # Two additional vertices for virtual source and sink, as needed to compute
        # a maximum bipartite matching by way of computing a maximum flow.
        num_vtx = len(vtx_by_seat) + 2
        source = num_vtx - 2
        sink = num_vtx - 1
    
        # Establish edge capacities in the flow network, according to which nonbroken
        # seats can see which other nonbroken seats.
        capacity = [[0] * num_vtx for _ in range(num_vtx)]
        for (i, j), u in vtx_by_seat.items():
            if j % 2 == 0:
                # Every even-column seat has an edge from the source.
                capacity[source][u] = 1
    
                neighbor_positions = (
                    (i, j - 1),
                    (i, j + 1),
                    (i - 1, j - 1),
                    (i - 1, j + 1),
                    (i + 1, j - 1),
                    (i + 1, j + 1),
                )
    
                neighbor_vertices = {
                    vtx_by_seat[v] for v in neighbor_positions if v in nonbroken_seats
                }
    
                # Every even-column seat has an edge to each odd-column seat that
                # either (a) can see the even-column seat, or (b) can be seen by the
                # even-column seat.
                for v in neighbor_vertices:
                    capacity[u][v] = 1
            else:
                # Every odd-column seat has an edge to the sink.
                capacity[u][sink] = 1
    
        flow = [[0] * num_vtx for _ in range(num_vtx)]
        visited = [0 for _ in range(num_vtx)]
        visited_token = 1
        max_flow = 0
    
        def find_flow(u: int, found_flow: float = float("inf")) -> int:
            visited[u] = visited_token
    
            if u == sink and found_flow > 0:
                return int(found_flow)
            else:
                for v in range(num_vtx):
                    residual = capacity[u][v] - flow[u][v]
    
                    if residual > 0 and visited[v] != visited_token:
                        ff = find_flow(v, min(found_flow, residual))
    
                        if ff > 0:
                            flow[u][v] += ff
                            flow[v][u] -= ff
                            return ff
    
            return 0
    
        # Apply the Ford-Fulkerson method to compute the maximum flow. That is, as
        # long as you can find an augmenting path from the source to the sink,
        # apply a unit of flow along that path. This part is O(max_flow * V^2).
        while (found_flow := find_flow(source)) > 0:
            max_flow += found_flow
            visited_token += 1
    
        # Minus two to account for virtual source and sink.
        return num_vtx - 2 - max_flow
        
17000