Give you an m * n matrix seats to represent the seat distribution in a classroom.If the seat is bad (unavailable), use'#'to indicate it; otherwise, use'.'.

The student can see the answers of the students who are close to him in the four directions of left, right, upper left and upper right, but he cannot see the answers of the students who are sitting directly in front of or behind him.Please calculate and return the maximum number of students that can take the exam together and cannot cheat.

Students must sit in good condition.

Example 1:

Input: seats = [['#','.', #','#','.','#'], [".","#","#","#","#","."], ["#",".","#","#",".","#"]] Output: 4 Explanation: Teachers can have four students sit in available seats so that they can't cheat in the exam.

Example 2:

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

Example 3:

Input: seats = [['#','.','.','.','#'], [".","#",".","#","."], [".",".","#",".","."], [".","#",".","#","."], ["#",".",".",".","#"]] Output: 10 Explanation: Have the students sit in the available seats in columns 1, 3 and 5.

Tips:

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

Solving problems

First, it is not difficult to think of a combination approach, that is, enumerate each seat position and not put two states, and then find the best solution.Similar problems Leetcode 39: Combination Sum

class Solution: def maxStudents(self, seats: List[List[str]]) -> int: r, c = len(seats), len(seats[0]) data = [(i, j) for i in range(r) for j in range(c) if seats[i][j] == '.'] n = len(data) fan = set() def dfs(u): if u == n: return 0 res = dfs(u + 1) # Maybe a chair i, j = data[u] for x, y in [[0, -1], [0, 1], [-1, -1], [-1, 1]]: nx, ny = i + x, j + y if 0 <= nx < r and 0 <= ny < c and (nx, ny) in fan: break else: fan.add(data[u]) res = max(res, dfs(u + 1) + 1) # Can sit chair fan.remove(data[u]) return res return dfs(0)

But the time complexity is too high.So is there overlapping calculation of thinking?The maximum number of people to sit in the current row is determined by the status of the previous row (independent of the latter).With this dependency, we can optimize the code by memory.

from functools import lru_cache class Solution: def maxStudents(self, seats: List[List[str]]) -> int: r, c = len(seats), len(seats[0]) @lru_cache(None) def dfs(x, y, pre, cur): if x == r: return 0 if not y: pre, cur = cur, 0 nex, ney = (x, y + 1) if y < c - 1 else (x + 1, 0) res = dfs(nex, ney, pre, cur) if seats[x][y] == '#': return res for i, j in ((0, -1), (-1, 1), (-1, -1)): nx, ny = x + i, y + j if 0 <= nx < r and 0 <= ny < c and \ ((nx == x and cur & 1 << ny) or \ (nx != x and pre & 1 << ny)): break else: res = max(res, dfs(nex, ney, pre, cur | 1 << y) + 1) return res return dfs(0, 0, 0, 0)

In fact, when I see this problem, the first thing I think about is splitting a set into two opposing sets, and then finding the maximum number of sets, which is not Maximum Matching of Bipartite Graphs Are you?Here we consider odd and even columns to be better handled as opposed (note that even and odd rows cannot be viewed as opposed, because the direction of detection in the middle of the topic is horizontal, but vertical only upward).

When building an edge, point to the odd edge through the point on the even edge.For each seat there may be six sides (left, right, left upper, right upper, left lower, right lower), and finally the Hungarian algorithm is used.

class Solution: def maxStudents(self, seats: List[List[str]]) -> int: r, c = len(seats), len(seats[0]) match = [[-1] * c for _ in range(r)] def find(node, vis): x, y = node for i, j in [[-1, -1], [0, -1], [1, -1], [-1, 1], [0, 1], [1, 1]]: nx, ny = i + x, j + y if 0 <= nx < r and 0 <= ny < c and not vis[nx][ny] and seats[nx][ny] == '.': vis[nx][ny] = True if match[nx][ny] == -1 or find(match[nx][ny], vis): match[nx][ny] = node return True return False res, cnt = 0, 0 for i in range(0): for j in range(0, c, 2): if seats[i][j] != '.': continue vis = [[False] * c for _ in range(r)] if find((i, j), vis): res += 1 for i in range(r): for j in range(c): if seats[i][j] == '.': cnt += 1 return cnt - res

I added a different language version of the problem to my GitHub Leetcode

If there are any questions, I hope you can point out!!!