1349. Maximum number of students taking the exam Status Compression

1349. Maximum number of students taking the test

You are given a m * n matrix seats representing the distribution of seats in the classroom.If the seat is bad (unusable), use '#' ; otherwise, use '.' .

Students can see the answer sheets of students who are next to him in four directions: left, right, upper left, and upper right, but cannot see the answer sheets of students sitting directly in front or behind him.Please calculate and return the maximum number of students that the test room can accommodate to take the test together without cheating.

Students must be seated in good condition.

Example 1:

Enter:seats = [["#",".","#","#",".","#"],[".","#","#","#","#","."],["#",".","#","#",".","#"]]Output:4Explanation: The teacher can place 4 students in the available seats so they cannot cheat on the exam.

Example 2:

Enter:seats = [[".","#"],["#","#"],["#","."],["#","#"],[".","#"]]Output:3Explanation: Have all students take available seats.

Example 3:

Enter:seats = [["#",".",".",".","#"],[".","#",".","#","."],[".",".","#",".","."],[".","#",".","#","."],["#",".",".",".","#"]]Output:10Explanation: Have students take available seats in columns 1, 3, and 5.

Tip:

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

Source: LeetCode
Link: https://leetcode.cn/problems/maximum-students-taking-exam
The copyright belongs to LeetCode.com.For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.

Results of the questions

Successful, the state compresses the enumeration subset, and the length is 8 and it is finished (in fact, WA is done once, because dfs has not written memoization)

Method: State Compression + Memory Search

1. Set the seat to 1 and the status to 0 to get a binary array
2. Considering that there may be a large number of empty states, the dfs method can be used to process the state pressure data
3. For a certain index, if the previous state is consistent, the maximum value of subsequent elements obtained must be consistent, and can be cached. The index length is 8, and the previous state is 1e8. There are 256 types in total, so store dp[8][256]
4. Enumerate the subset of the current seat (binary is v), use v&(i-1), at this time the enumeration is a non-empty subset (do not enumerate the empty subset in the loop, it will be an infinite loop), the subsequent enumeration is not selected in this bank, and the occupied seat is 0.
5. Specifically, the left and right translation of the current seat cannot coincide with the original allocation, that is, (i&(i<<1))==0 && (i&(i>>1))==0, or you canOnly one side is judged, because the left edge is 11. During the left shift, the leftmost is 1, and the latter is not 0, which does not affect the judgment. During the right edge shift, the right shift is 1, and the result is 1, which does not affect the judgment.
6. To judge whether it is adjacent to the previous row as an allocation, it is required that the current row is shifted left and right by one position and cannot be the same as the previous row. Note that at this time, both sides must be judged, for example, 10,1 is shifted to the right by one position and 1,1 is the same as the previous row.The result is 1, but the result of a left shift is 100 and 1, not coincident

class Solution {public int maxStudents(char[][] seats) {List list = new ArrayList<>();for(char[] seat:seats){int v = 0;for(char c:seat){int curr = c=='.'?1:0;v = v*2+curr;}list.add(v);}for(int i = 0; i < 8; i++) Arrays.fill(dp[i],-1);return dfs(list,0,0);}int[][] dp = new int[8][256];private int dfs(List list,int index,int preVal){if(index==list.size()) return 0;if(dp[index][preVal]!=-1) return dp[index][preVal];int ans = 0;int v = list.get(index);for(int i=v;i>0;i=v&(i-1)){if((i&(i<<1))==0 (preVal&(i<<1))==0 && (preVal&(i>>1))==0){ans = Math.max(dfs(list,index+1,i)+Integer.bitCount(i),ans);}}ans = Math.max(ans,dfs(list,index+1,0));dp[index][preVal] = ans;return ans;}}