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). You can find examples for good lines in the figure below:
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.
Example 1:
Input: board = [[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B" Output: true Explanation: '.', 'W', and 'B' are represented by the colors blue, white, and black respectively, and cell (rMove, cMove) is marked with an 'X'. The two good lines with the chosen cell as an endpoint are annotated above with the red rectangles.
Example 2:
Input: board = [[".",".",".",".",".",".",".","."],[".","B",".",".","W",".",".","."],[".",".","W",".",".",".",".","."],[".",".",".","W","B",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".","B","W",".","."],[".",".",".",".",".",".","W","."],[".",".",".",".",".",".",".","B"]], rMove = 4, cMove = 4, color = "W" Output: false Explanation: While there are good lines with the chosen cell as a middle cell, there are no good lines with the chosen cell as an endpoint.
Constraints:
board.length == board[r].length == 80 <= rMove, cMove < 8board[rMove][cMove] == '.'color is either 'B' or 'W'.This approach involves checking each of the 8 possible directions (vertical, horizontal, and diagonal) from the given move position to determine if forming a good line is possible. For each direction, traverse until you find a move that completes a good line according to the rules.
The C solution defines a helper function checkInDirection that checks if a good line is formed in the specified direction (denoted by dr and dc). The main function, isLegalMove, iterates over all 8 directions and calls checkInDirection for each, returning true if any direction confirms a good line.
C++
Java
Python
C#
JavaScript
Time Complexity: O(8 * n) = O(n), where n is the max possible travel in each direction (here less than or equal to 8).
Space Complexity: O(1).
This approach enhances the directional check by incorporating specific boundary validations. It involves examining the line in both forward and reverse directions from the intended position, ensuring a valid line formation before reverting colors.
This solution refines line checking by validating boundary conditions. The isOutOfBounds function ensures no illegal access occurs, while checkDirection confirms the opposite color count is sufficient prior to accepting the line as valid.
C++
Java
Python
C#
JavaScript
Time Complexity: O(8 * n).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Directional Check Method | Time Complexity: O(8 * n) = O(n), where n is the max possible travel in each direction (here less than or equal to 8). |
| Line Detection with Boundary Check | Time Complexity: O(8 * n). |
Leetcode Interviews • ThePrimeTime • 1,196,221 views views
Watch 9 more video solutions →Practice Check if Move is Legal with our built-in code editor and test cases.
Practice on FleetCode