Medium

题目描述

给你一个 8 × 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
解释：选择的单元格作为端点的两条好线段用红色矩形标注。

示例 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'

解题思路

这道题需要检查在指定位置放置指定颜色棋子后，是否能形成合法的线段。

解题思路

核心概念理解：

  • 好线段：长度至少为3，两个端点颜色相同，中间所有格子都是相反颜色
  • 合法移动：放置棋子后，该位置成为至少一条好线段的端点

算法步骤：

  1. 遍历8个方向：水平（左右）、垂直（上下）、对角线（4个方向）
  2. 对每个方向：
    • 从目标位置开始，沿该方向前进
    • 跳过连续的相反颜色格子
    • 检查是否遇到相同颜色的格子，且中间至少有一个相反颜色格子
  3. 如果任一方向能形成好线段，返回true

关键点：

  • 必须确保中间有相反颜色的格子（长度≥3）
  • 不能有空格子
  • 端点颜色必须相同

时间复杂度O(1)，因为棋盘大小固定8×8，最多检查8个方向×7个位置。空间复杂度O(1)。

代码实现

class Solution {
public:
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        int directions[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        char opposite = (color == 'B') ? 'W' : 'B';
        
        for (auto& dir : directions) {
            int r = rMove + dir[0];
            int c = cMove + dir[1];
            int count = 0;
            
            // 跳过连续的相反颜色格子
            while (r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] == opposite) {
                r += dir[0];
                c += dir[1];
                count++;
            }
            
            // 检查是否找到相同颜色且中间有相反颜色格子
            if (count > 0 && r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] == color) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
        directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        opposite = 'W' if color == 'B' else 'B'
        
        for dr, dc in directions:
            r, c = rMove + dr, cMove + dc
            count = 0
            
            # 跳过连续的相反颜色格子
            while 0 <= r < 8 and 0 <= c < 8 and board[r][c] == opposite:
                r += dr
                c += dc
                count += 1
            
            # 检查是否找到相同颜色且中间有相反颜色格子
            if count > 0 and 0 <= r < 8 and 0 <= c < 8 and board[r][c] == color:
                return True
        
        return False

public class Solution {
    public bool CheckMove(char[][] board, int rMove, int cMove, char color) {
        int[,] directions = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        char opposite = (color == 'B') ? 'W' : 'B';
        
        for (int i = 0; i < 8; i++) {
            int dr = directions[i, 0];
            int dc = directions[i, 1];
            int r = rMove + dr;
            int c = cMove + dc;
            int count = 0;
            
            // 跳过连续的相反颜色格子
            while (r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] == opposite) {
                r += dr;
                c += dc;
                count++;
            }
            
            // 检查是否找到相同颜色且中间有相反颜色格子
            if (count > 0 && r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] == color) {
                return true;
            }
        }
        
        return false;
    }
}

var checkMove = function(board, rMove, cMove, color) {
    const directions = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]];
    const opposite = color === 'W' ? 'B' : 'W';
    
    for (let [dr, dc] of directions) {
        let r = rMove + dr;
        let c = cMove + dc;
        let hasOpposite = false;
        
        while (r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] === opposite) {
            hasOpposite = true;
            r += dr;
            c += dc;
        }
        
        if (hasOpposite && r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] === color) {
            return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(1) - 棋盘大小固定8×8，最多检查8个方向×7个位置
空间复杂度O(1) - 只使用常数额外空间