检查操作是否合法

1958. 检查操作是否合法

给你一个下标从 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' 。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) { } };

javascript 解法, 执行用时: 58 ms, 内存消耗: 51.1 MB, 提交时间: 2024-07-07 14:10:53

/**
 * @param {character[][]} board
 * @param {number} rMove
 * @param {number} cMove
 * @param {character} color
 * @return {boolean}
 */
var checkMove = function(board, rMove, cMove, color) {
    const m = board.length, n = board[0].length;
    for (const [dx, dy] of [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]) {
        let x = rMove + dx, y = cMove + dy;
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] === '.' || board[x][y] === color) {
            continue;
        }
        while (true) {
            x += dx;
            y += dy;
            if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] === '.') {
                break;
            }
            if (board[x][y] === color) {
                return true;
            }
        }
    }
    return false;
};

rust 解法, 执行用时: 1 ms, 内存消耗: 2.2 MB, 提交时间: 2024-07-07 14:10:31

impl Solution {
    pub fn check_move(board: Vec<Vec<char>>, r_move: i32, c_move: i32, color: char) -> bool {
        let m = board.len() as i32;
        let n = board[0].len() as i32;
        for (dx, dy) in [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)] {
            let mut x = r_move + dx;
            let mut y = c_move + dy;
            if x < 0 || x >= m || y < 0 || y >= n || board[x as usize][y as usize] == '.' || board[x as usize][y as usize] == color {
                continue;
            }
            loop {
                x += dx;
                y += dy;
                if x < 0 || x >= m || y < 0 || y >= n || board[x as usize][y as usize] == '.' {
                    break;
                }
                if board[x as usize][y as usize] == color {
                    return true;
                }
            }
        }
        false
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2023-09-28 15:27:03

// 8 个方向遍历
func checkMove(board [][]byte, rMove int, cMove int, color byte) bool {
	var steps [][]int

	steps = [][]int{}
	for i := 0; i < 8; i++ {
		steps = append(steps, []int{i, cMove})
	}

	if hasGoodLine(board, color, revert(steps[:rMove])) || hasGoodLine(board, color, steps[rMove+1:]) {
		return true
	}

	steps = [][]int{}
	for i := 0; i < 8; i++ {
		steps = append(steps, []int{rMove, i})
	}
	if hasGoodLine(board, color, revert(steps[:cMove])) || hasGoodLine(board, color, steps[cMove+1:]) {
		return true
	}

	steps = [][]int{}
	r, c := rMove-1, cMove-1
	for r >= 0 && c >= 0 {
		steps = append(steps, []int{r, c})
		r--
		c--
	}
	if hasGoodLine(board, color, steps) {
		return true
	}

	steps = [][]int{}
	r, c = rMove-1, cMove+1
	for r >= 0 && c <= 7 {
		steps = append(steps, []int{r, c})
		r--
		c++
	}
	if hasGoodLine(board, color, steps) {
		return true
	}

	steps = [][]int{}
	r, c = rMove+1, cMove-1
	for r <= 7 && c >= 0 {
		steps = append(steps, []int{r, c})
		r++
		c--
	}
	if hasGoodLine(board, color, steps) {
		return true
	}

	steps = [][]int{}
	r, c = rMove+1, cMove+1
	for r <= 7 && c <= 7 {
		steps = append(steps, []int{r, c})
		r++
		c++
	}
	if hasGoodLine(board, color, steps) {
		return true
	}

	return false
}

func hasGoodLine(board [][]byte, color byte, steps [][]int) bool {
	if len(steps) < 2 {
		return false
	}
	if board[steps[0][0]][steps[0][1]] == color || board[steps[0][0]][steps[0][1]] == '.' {
		return false
	}
	for i := 1; i < len(steps); i++ {
		if board[steps[i][0]][steps[i][1]] == '.' {
			return false
		}
		if board[steps[i][0]][steps[i][1]] == color {
			return true
		}
	}
	return false
}

func revert(nums [][]int) [][]int {
	l, r := 0, len(nums)-1
	for l < r {
		nums[l], nums[r] = nums[r], nums[l]
		l++
		r--
	}
	return nums
}

java 解法, 执行用时: 0 ms, 内存消耗: 40.2 MB, 提交时间: 2023-09-28 15:25:48

class Solution {
    public boolean check(char[][] board, int r, int c, int dx, int dy, char color) {
        int x = r + dx;
        int y = c + 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;
                }
                if (board[x][y] == color) {
                    return true;
                }
            }
            step++;
            x += dx;
            y += dy;
        }
        return false;
    }

    public boolean checkMove(char[][] board, int r, int c, char color) {
        int[] dx = {1, 1, 0, -1, -1, 0, 1, -1};
        int[] dy = {0, 1, 1, 0, -1, -1,-1, 1};

        for (int k = 0; k < 8; k++) {
            if (check(board, r, c, dx[k], dy[k], color)) {
                return true;
            }
        }
        return false;
    }
}

python3 解法, 执行用时: 48 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-28 15:25:22

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

cpp 解法, 执行用时: 8 ms, 内存消耗: 11.2 MB, 提交时间: 2023-09-28 15:25:05

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;
    }
};

上一题

下一题

详情