# Check if Move is Legal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-move-is-legal)
Canonical: https://scaleengineer.com/dsa/problems/check-if-move-is-legal
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Matrix
---
## Problem
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:

![](https://assets.glich.co/dsa/check-if-move-is-legal/image0.png) 

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:**

![](https://assets.glich.co/dsa/check-if-move-is-legal/image1.png) 

**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:**

![](https://assets.glich.co/dsa/check-if-move-is-legal/image2.png) 

**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 == 8`
* `0 <= rMove, cMove < 8`
* `board[rMove][cMove] == '.'`
* `color` is either `'B'` or `'W'`.

# Approaches
## Directional Scan with a Single Loop
This approach directly simulates the process of checking for a "good line" in all 8 possible directions (horizontal, vertical, and diagonals) from the given move coordinates. For each direction, it traverses the board cell by cell, keeping track of the line's length and the colors encountered.
**Time:** O(1). The board size is fixed at 8x8. We iterate through 8 directions, and for each direction, we traverse at most 7 cells. The total number of operations is constant. · **Space:** O(1). We only use a constant amount of extra space for the directions array and a few variables.
**Pros:** Efficient and directly solves the problem.; Implementation is relatively compact.
**Cons:** The logic within the single loop, which handles multiple conditions (empty cell, same color, opposite color), can be slightly less intuitive to follow compared to a more structured approach.
### Explanation
The core idea is to check every one of the 8 directions radiating from `(rMove, cMove)`. We can represent these 8 directions using an array of `(dr, dc)` pairs, like `{{0, 1}, {0, -1}, {1, 0}, ...}`. For each direction, we start a loop that begins at the cell adjacent to the move location. A counter `length` is used, initialized to 1 to account for the piece at `(rMove, cMove)`. Inside the loop, we advance one step at a time. With each step, we increment `length` and check the color of the current cell. If the cell is empty ('.') or we go out of bounds, the line is broken. If the cell has the same `color` as our move, it's a potential endpoint. A "good line" must have at least 3 cells, so if our current `length` is 3 or more, we've found a valid line and can return `true`. If the cell has the opposite color, it's part of the middle section of a potential good line, so we continue traversing. If we check all 8 directions and none are valid, the move is not legal.

```java
class Solution {
    public boolean checkMove(char[][] board, int rMove, int cMove, char color) {
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        
        for (int[] dir : directions) {
            if (isGoodLineInDirection(board, rMove, cMove, color, dir)) {
                return true;
            }
        }
        
        return false;
    }
    
    private boolean isGoodLineInDirection(char[][] board, int rStart, int cStart, char color, int[] dir) {
        int dr = dir[0];
        int dc = dir[1];
        int r = rStart + dr;
        int c = cStart + dc;
        int length = 1;
        
        while (r >= 0 && r < 8 && c >= 0 && c < 8) {
            length++;
            char currentCell = board[r][c];
            
            if (currentCell == '.') {
                return false; // Line broken by empty cell
            }
            
            if (currentCell == color) {
                // Found an endpoint of the same color.
                // Check if the line has at least one piece in the middle.
                return length >= 3;
            }
            
            // If we are here, it's the opposite color, so continue.
            r += dr;
            c += dc;
        }
        
        return false; // Reached board edge without finding a valid endpoint.
    }
}
```
### Algorithm
- Define an array of 8 direction vectors `(dr, dc)` representing horizontal, vertical, and diagonal moves.
- Iterate through each of the 8 direction vectors.
- For each direction, create a helper function or an inner loop to check for a "good line".
- Inside the check for a single direction:
  - Start a traversal from the cell adjacent to `(rMove, cMove)`.
  - Use a `length` counter, initialized to 1 (for the starting move cell).
  - In a loop, move one step at a time in the current direction:
    - Increment the `length`.
    - Check the cell's color:
      - If it's an empty cell ('.') or out of bounds, this direction is invalid. Stop and try the next direction.
      - If it's the same color as the move (`color`), check if `length >= 3`. If so, a good line is found, return `true`. Otherwise, this direction is invalid (e.g., `B` `B`).
      - If it's the opposite color, it's part of the middle section. Continue traversing.
- If the loop completes (reaches the board edge) without finding a same-colored endpoint, this direction is invalid.
- If all 8 directions are checked and no good line is found, return `false`.

## Structured Two-Phase Scan
This approach improves upon the direct simulation by adding more structure to the check for each direction. It breaks the process into two clear phases: first, ensuring the line starts correctly (with an adjacent piece of the opposite color), and second, scanning for the endpoint. This enhances code readability and maintainability.
**Time:** O(1). The logic is fundamentally the same as the first approach. For a fixed 8x8 board, the number of operations is constant. · **Space:** O(1). Constant extra space is used for the directions array and a few variables.
**Pros:** Highly readable and easy to understand due to the clear separation of logic.; Just as efficient as the single-loop approach, with O(1) complexity.
**Cons:** The code might be slightly more verbose than the single-loop implementation.
### Explanation
Similar to the previous approach, we iterate through all 8 directions from `(rMove, cMove)`. However, the logic for checking each direction is split into two distinct steps for clarity.

**Phase 1: Validate the Start of the Line.**
For a given direction, we first check the immediate neighbor of `(rMove, cMove)`. A valid "good line" must start with `(move_color, opposite_color, ...)`. Therefore, this immediate neighbor must exist (be within board bounds) and must be of the opposite color. If this condition is not met, we can immediately discard this direction.

**Phase 2: Scan for the Endpoint.**
If the first neighbor is valid, we know we have a potential line of length 2. We now need to find an endpoint of our `color` to complete the line. We continue traversing in the same direction, cell by cell. If we encounter an empty cell ('.') or go off the board, the line is invalid. If we encounter a cell of our `color`, we have successfully found a "good line". Since we already passed Phase 1, the length is guaranteed to be at least 3, so we can return `true`.

```java
class Solution {
    public boolean checkMove(char[][] board, int rMove, int cMove, char color) {
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        char oppositeColor = (color == 'W') ? 'B' : 'W';
        
        for (int[] dir : directions) {
            int dr = dir[0];
            int dc = dir[1];
            
            // Start from the cell adjacent to the move
            int r = rMove + dr;
            int c = cMove + dc;
            
            // Phase 1: Check if the line starts with an opposite-colored piece
            if (r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] == oppositeColor) {
                // Phase 2: Scan for an endpoint of the same color
                while (true) {
                    r += dr;
                    c += dc;
                    
                    if (r < 0 || r >= 8 || c < 0 || c >= 8 || board[r][c] == '.') {
                        // Reached edge or empty cell, this direction is not a good line
                        break;
                    }
                    
                    if (board[r][c] == color) {
                        // Found a valid endpoint, making it a good line
                        return true;
                    }
                    // If it's the opposite color, continue the loop
                }
            }
        }
        
        return false;
    }
}
```
### Algorithm
- Define an array of 8 direction vectors `(dr, dc)`.
- Determine the `oppositeColor` based on the input `color`.
- Iterate through each direction vector.
- **Phase 1: Validate the Start of the Line.**
  - Check the immediate neighbor of `(rMove, cMove)` in the current direction.
  - If this cell is out of bounds or is not the `oppositeColor`, this direction is invalid. Continue to the next direction.
- **Phase 2: Scan for the Endpoint.**
  - If Phase 1 passed, we have a potential line. Start a loop from the cell *after* the immediate neighbor.
  - Traverse in the same direction:
    - If the cell is out of bounds or empty ('.'), the line is broken. Stop and check the next direction.
    - If the cell is the `oppositeColor`, continue traversing.
    - If the cell is the same `color` as the move, a valid endpoint is found. The line is guaranteed to have a length of at least 3. Return `true`.
- If all 8 directions are exhausted without finding a valid line, return `false`.

# Solutions
### Java

```java
class Solution {
private
  static final int[][] DIRS = {{1, 0}, {0, 1},  {-1, 0}, {0, -1},
                               {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
private
  static final int N = 8;
public
  boolean checkMove(char[][] board, int rMove, int cMove, char color) {
    for (int[] d : DIRS) {
      int i = rMove, j = cMove;
      int t = 0;
      int a = d[0], b = d[1];
      while (0 <= i + a && i + a < N && 0 <= j + b && j + b < N) {
        ++t;
        i += a;
        j += b;
        if (board[i][j] == '.' || board[i][j] == color) {
          break;
        }
      }
      if (board[i][j] == color && t > 1) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> dirs = {{1, 0}, {0, 1},  {-1, 0}, {0, -1},
                              {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
  int n = 8;
  bool checkMove(vector<vector<char>> &board, int rMove, int cMove,
                 char color) {
    for (auto &d : dirs) {
      int a = d[0], b = d[1];
      int i = rMove, j = cMove;
      int t = 0;
      while (0 <= i + a && i + a < n && 0 <= j + b && j + b < n) {
        ++t;
        i += a;
        j += b;
        if (board[i][j] == '.' || board[i][j] == color)
          break;
      }
      if (board[i][j] == color && t > 1)
        return true;
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool: dirs = [(1, 0), (0, 1), (- 1, 0), (0, - 1), (1, 1), (1, - 1), (- 1, 1), (- 1, - 1)] n = 8 for a, b in dirs: i, j = rMove, cMove t = 0 while 0 <= i + a < n and 0 <= j + b < n: t += 1 i, j = i + a, j + b if board[i][j] in ['.', color]: break if board[i][j] == color and t > 1: return True return False

```