1958-检查操作是否合法

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个下标从 0 开始的 8 x 8 网格 board ，其中 board[r][c] 表示游戏棋盘上的格子 (r, c)
。棋盘上空格用 '.' 表示，白色格子用 'W' 表示，黑色格子用 'B' 表示。

游戏中每次操作步骤为：选择一个空格子，将它变成你正在执行的颜色（要么白色，要么黑色）。但是， 合法 操作必须满足：涂色后这个格子是
好线段的一个端点 （好线段可以是水平的，竖直的或者是对角线）。

好线段 指的是一个包含 三个或者更多格子（包含端点格子） 的线段，线段两个端点格子为 同一种颜色 ，且中间剩余格子的颜色都为
另一种颜色 （线段上不能有任何空格子）。你可以在下图找到好线段的例子：

给你两个整数 rMove 和 cMove 以及一个字符 color ，表示你正在执行操作的颜色（白或者黑），如果将格子 (rMove, cMove) 变成颜色 color 后，是一个 合法 操作，那么返回 true ，如果不是合法操作返回 false 。

示例 1：

**输入：** board = [[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B"
**输出：** true
**解释：** '.'，'W' 和 'B' 分别用颜色蓝色，白色和黑色表示。格子 (rMove, cMove) 用 'X' 标记。
以选中格子为端点的两个好线段在上图中用红色矩形标注出来了。

示例 2：

**输入：** board = [[".",".",".",".",".",".",".","."],[".","B",".",".","W",".",".","."],[".",".","W",".",".",".",".","."],[".",".",".","W","B",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".","B","W",".","."],[".",".",".",".",".",".","W","."],[".",".",".",".",".",".",".","B"]], rMove = 4, cMove = 4, color = "W"
**输出：** false
**解释：** 虽然选中格子涂色后，棋盘上产生了好线段，但选中格子是作为中间格子，没有产生以选中格子为端点的好线段。

提示：

  • board.length == board[r].length == 8
  • 0 <= rMove, cMove < 8
  • board[rMove][cMove] == '.'
  • color 要么是 'B' 要么是 'W' 。

方法一：枚举每个方向验证

思路与算法

由题意可知，当前操作合法当且仅当从该点开始的 8 个方向（上下左右与对角线）中，至少有一个方向存在一个以该点为起点的好线段。

那么，我们可以枚举这 8 个方向，并对于每个方向验证是否存在以该点为起点的好线段。如果该点与对应方向下一个相同颜色的格点之间的所有格点（至少一个）均为另一种颜色，那么它们构成一个好线段。

我们用数对 (\textit{dx}, \textit{dy}) 来表示每个方向下一个格点相对于当前格点的行列下标变化量，并用函数 check}(\textit{dx}, \textit{dy}) 来判断该方向是否存在以操作位置为起点的好线段。如果我们寻找到了符合要求的好线段，则返回 true；反之亦然。

代码

[sol1-C++]
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
class Solution {
public:
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        // 判断每个方向是否存在以操作位置为起点的好线段
        auto check = [&](int dx, int dy) -> bool{
            int x = rMove + dx;
            int y = cMove + dy;
            int step = 1;   // 当前遍历到的节点序号
            while (x >= 0 && x < 8 && y >= 0 && y < 8){
                if (step == 1){
                    // 第一个点必须为相反颜色
                    if (board[x][y] == '.' || board[x][y] == color){
                        return false;
                    }
                }
                else{
                    // 好线段中不应存在空格子
                    if (board[x][y] == '.'){
                        return false;
                    }
                    // 遍历到好线段的终点，返回 true
                    if (board[x][y] == color){
                        return true;
                    }
                }
                ++step;
                x += dx;
                y += dy;
            }
            // 不存在符合要求的好线段
            return false;
        };
        
        // 从 x 轴正方向开始逆时针枚举 8 个方向
        vector<int> dx = {1, 1, 0, -1, -1, -1, 0, 1};   // 行改变量
        vector<int> dy = {0, 1, 1, 1, 0, -1, -1, -1};   // 列改变量
        for (int k = 0; k < 8; ++k){
            if (check(dx[k], dy[k])){
                return true;
            }
        }
        return false;
    }
};
[sol1-Python3]
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
class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
        # 判断每个方向是否存在以操作位置为起点的好线段
        def check(dx: int, dy: int) -> bool:
            x, y = rMove + dx, cMove + dy
            step = 1   # 当前遍历到的节点序号
            while 0 <= x < 8 and 0 <= y < 8:
                if step == 1:
                    # 第一个点必须为相反颜色
                    if board[x][y] == "." or board[x][y] == color:
                        return False
                else:
                    # 好线段中不应存在空格子
                    if board[x][y] == ".":
                        return False
                    # 遍历到好线段的终点，返回 true
                    if board[x][y] == color:
                        return True
                step += 1
                x += dx
                y += dy
            # 不存在符合要求的好线段
            return False
        
        # 从 x 轴正方向开始逆时针枚举 8 个方向
        dx = [1, 1, 0, -1, -1, -1, 0, 1]   # 行改变量
        dy = [0, 1, 1, 1, 0, -1, -1, -1]   # 列改变量
        for k in range(8):
            if check(dx[k], dy[k]):
                return True
        return False

复杂度分析

  • 时间复杂度：O(\max(r, c))，其中 r, c 为 board 的行数与列数。验证每个方向的时间复杂度为 O(\max(r, c))，我们最多需要验证 8 个方向。

  • 空间复杂度：O(1)。

 Comments
On this page
1958-检查操作是否合法