We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if Move is Legal

Difficulty: Medium

Problem Description

You are given a 0-indexed 8 x 8 grid board, where board[r][c] represents the cell (r, c) on a game board. On the board, free cells are represented by '.', white cells are represented by 'W', and black cells are represented by 'B'. Each move in this game consists of choosing a free cell and changing it to the color you are playing as (either white or black). However, a move is only legal if, after changing it, the cell becomes the endpoint of a good line (horizontal, vertical, or diagonal). A good line is a line of three or more cells (including the endpoints) where the endpoints of the line are one color, and the remaining cells in the middle are the opposite color (no cells in the line are free). Given two integers rMove and cMove and a character color representing the color you are playing as (white or black), return true if changing cell (rMove, cMove) to color color is a legal move, or false if it is not legal.

Key Insights

  • The grid is fixed at 8x8, making boundary checks manageable.
  • A "good line" requires two endpoints of the same color with a sequence of the opposite color in between.
  • We need to check in four directions: horizontal, vertical, and two diagonals.
  • The cell being changed must not be free (denoted by '.').

Space and Time Complexity

Time Complexity: O(n) where n is the number of cells to check in each direction (at most 3 for a good line). Space Complexity: O(1) since we are using a constant amount of extra space.

Solution

To determine if a move is legal, we need to check for good lines in four directions (horizontal, vertical, and two diagonals) from the cell being changed. We will check each direction for potential good lines by counting consecutive cells of the opposite color until we hit a cell of the same color or go out of bounds. If we find a valid configuration of a good line (two endpoints of the same color with the opposite color in between), we can confirm the move is legal.

Code Solutions

def checkMove(board, rMove, cMove, color):
    # Define the opposite color
    opposite_color = 'B' if color == 'W' else 'W'
    
    # Directions to check: (delta_row, delta_col)
    directions = [(1, 0), (0, 1), (1, 1), (1, -1)]
    
    for dr, dc in directions:
        # Check in both directions
        count = 0
        # Check in the positive direction
        row, col = rMove, cMove
        while 0 <= row < 8 and 0 <= col < 8:
            if board[row][col] == opposite_color:
                count += 1
            elif board[row][col] == color:
                if count >= 2:
                    return True
                break
            else:
                break
            row += dr
            col += dc
        
        count = 0
        # Check in the negative direction
        row, col = rMove - dr, cMove - dc
        while 0 <= row < 8 and 0 <= col < 8:
            if board[row][col] == opposite_color:
                count += 1
            elif board[row][col] == color:
                if count >= 2:
                    return True
                break
            else:
                break
            row -= dr
            col -= dc
    
    return False
← Back to All Questions