leetcode：LCP 41. 黑白翻转棋【bfs + 翻转棋模拟】

分析

注意一开始是不存在翻转情况的
新下的一个棋子才会导致翻转
翻转了之后会继续套娃翻转

实现

暴力枚举每个第一步下棋的位置，然后开始用一个函数模拟翻转
注意，新下的棋子以及新翻转的棋子才有可能会引起新的翻转
因此，他们我们把它记录到一个deque中
然后八个方向延展，必须满足先是一连串的白，最后第一个非白的必须是黑
在这种情况下，中间的白可以全部翻转为黑

注意：传入grid参数的时候注意使用深拷贝copy.deepcopy，不然函数里面的修改也会被带出来

ac code

class Solution:
    def flipChess(self, chessboard: List[str]) -> int:
        # 新的黑节点才有可能发生作用...
        # bfs
        n, m = len(chessboard), len(chessboard[0])
        # str -> list才可以修改
        for i in range(n):
            chessboard[i] = list(chessboard[i])
            
        ans = 0

        def cal(i, j, grid):
            
            #print('---------')
            cnt = 0
            dq = deque([[i, j]])
            # 修改一下自己
            grid[i][j] = 'X'
            # 八个方向
            dir = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
            while dq:
                #print(dq)
                x, y = dq.popleft()
                for dx, dy in dir:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < m:
                        # 第一个必须白色才有下文
                        if grid[nx][ny] == 'O':
                            # 后面继续找连续的白色
                            while 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 'O':
                                nx += dx
                                ny += dy
                            # 紧接着连续的白色，必须是一个黑色
                            # 这样才可以翻转中间的
                            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 'X':
                                # 记录中间全部的翻转
                                
                                cur_x, cur_y = x + dx, y + dy
                                # 未到终点的黑棋
                                while cur_x != nx or cur_y != ny:
                                    # print(cur_x, cur_y)
                                    # 赶紧翻转改变状态为黑色
                                    # 不然会重复
                                    grid[cur_x][cur_y] = 'X'
                                    cnt += 1
                                    dq.append([cur_x, cur_y])
                                    cur_x += dx
                                    cur_y += dy
            return cnt



        



        for i in range(n):
            for j in range(m):
                if chessboard[i][j] == '.':
                    # 深拷贝问题，不然会被修改
                    #print(chessboard)
                    ans = max(ans, cal(i, j, copy.deepcopy(chessboard)))
        
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

总结

经典bfs模拟
这个还是八个方向的
而且还要判断先一连串白再来一个黑
可以说是bfs里面的模拟战斗机了