> For the complete documentation index, see [llms.txt](https://zhongquan789.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongquan789.gitbook.io/leetcode/leetcode/leetcode_1349.md).

# 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/>