# leetcode\_1349

Given a m \* 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 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 directly in front or behind him. 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.

```
Example 1:

Input: seats = [["#",".","#","#",".","#"],
                [".","#","#","#","#","."],
                ["#",".","#","#",".","#"]]
Output: 4
Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam. 

Example 2:

Input: seats = [[".","#"],
                ["#","#"],
                ["#","."],
                ["#","#"],
                [".","#"]]
Output: 3
Explanation: Place all students in available seats. 

Example 3:

Input: seats = [["#",".",".",".","#"],
                [".","#",".","#","."],
                [".",".","#",".","."],
                [".","#",".","#","."],
                ["#",".",".",".","#"]]
Output: 10
Explanation: Place students in available seats in column 1, 3 and 5.
```

## Constraints:

* seats contains only characters '.' and'#'.
* m == seats.length
* n == seats\[i].length
* 1 <= m <= 8
* 1 <= n <= 8

## Solutions

1. **dynamic programming with iteration O(m \* 2^2n)**
2. Since each row only depends on the previous row, we can solve this problem by dynamic programming.
3. `dp[i][state]` represents the total number of students that can take the exam without any cheating in first `i` rows and the arrangement of the `i'th` row is `state`.
   * An arrangement can be represented by an `integer` as the number of columns is smaller than `8`.
   * For example, `##0##1#10` can be represented as `2^5 + 2^7`.

```cpp
class Solution {
public:
    inline int countone(int n) {
        int res = 0;
        while (n) {
            res++; n &= (n - 1);
        }
        return res;
    }

    int maxStudents(vector<vector<char>>& seats) {
        int m = seats.size(), n = seats[0].size();
        int mstate = 1 << n;
        vector<int> dp(mstate);

        for (int i = 1; i <= m; i++) {
            vector<int> dp1(mstate);
            for (int prev = 0; prev < mstate; prev++) {
                for (int cur = 0; cur < mstate; cur++) {
                    bool valid = true;
                    for (int j = 0; j < n; j++) {
                        int bit = 1 << j;
                        // only check seat positions in the current arrangement.
                        if (!(cur & (1 << j))) continue;
                        if (seats[i - 1][j] == '#' // broken seat
                        || ((bit << 1) & cur)      // left cheating
                        || ((bit >> 1) & cur)      // right cheating
                        || (1 & (prev >> (j + 1))) // left-up and right-up cheatings
                        || (j && (1 & (prev >> (j - 1))))) {
                            valid = false;
                            break;
                        }
                    }
                    if (valid)
                        dp1[cur] = max(dp1[cur], dp[prev] + countone(cur));
                }
            }
            swap(dp1, dp);
        }
        return *max_element(dp.begin(), dp.end());
    }
};
```

1. **recursion with memoization**
2. In the first version, the calculation of all states is unnecessary, a top-down strategy can save a huge amount of running time though the time complexity is the same.

```cpp
```

1. **graph**
2. reference: <https://leetcode-cn.com/problems/maximum-students-taking-exam/solution/er-fen-tu-zui-da-du-li-ji-by-lightcml/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhongquan789.gitbook.io/leetcode/leetcode/leetcode_1349.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.