Leetcode 1349: Maximum number of students taking the exam (super-detailed solution!!!)

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!!!

732 original articles published, 457 awarded, 830,000 visits+
His message board follow

Tags: github

Posted on Tue, 11 Feb 2020 20:27:00 -0800 by PaulRyan