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:

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.

Examples

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.

Solution

Method 1 - DFS Like, but Iterative

Here dirs array is helping us to move in every direction repeatedly unless->

  1. We are out of the matrix.
  2. We are at the end of a good line(we encounter the input color again).
  3. We are not at the end of line and we encounter the same input color.

Code

Java
class Solution {
    public boolean checkMove(char[][] board, int rMove, int cMove, char color) {
        int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        
        // Determine the opposite color
        char op = color == 'W' ? 'B' : 'W'; 

        // Iterate over all potential directions
        for (int i = 0; i < 8; i++) {
            int x = rMove;
            int y = cMove;
            int count = 1;
            x += dirs[i][0];
            y += dirs[i][1];

            // Traverse in the current direction until hitting the board edge or an empty cell
            while (x < 8 && y < 8 && x >= 0 && y >= 0 && board[x][y] != '.') {
                // If we have encountered more than one opposite color piece and now see a piece of the original color
                if (count != 1 && board[x][y] == color) return true;
                
                // Break if the cell is neither the opposite color nor the original color
                if (board[x][y] != op) break;
                
                // Move further in the current direction
                x += dirs[i][0];
                y += dirs[i][1];
                count++;
            }
        }
        return false; // No valid move found
    }
}
Python
class Solution:
    def checkMove(board, rMove, cMove, color):
        dirs = [(0, 1), (1, 0), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        
        # Determine the opposite color
        opp_color = 'B' if color == 'W' else 'W'

        # Iterate over all potential directions
        for dir in dirs:
            x, y = rMove, cMove
            count = 1
            x += dir[0]
            y += dir[1]

            # Traverse in the current direction until hitting the board edge or an empty cell
            while 0 <= x < 8 and 0 <= y < 8 and board[x][y] != '.':
                # If we have encountered more than one opposite color piece and now see a piece of the original color
                if count != 1 and board[x][y] == color:
                    return True
                
                # Break if the cell is neither the opposite color nor the original color
                if board[x][y] != opp_color:
                    break
                
                # Move further in the current direction
                x += dir[0]
                y += dir[1]
                count += 1

        return False # No valid move found