##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1958.html

# 1958. Check if Move is Legal

Medium

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

## Solution

Starting from (rMove, cMove), search all eight direction to find whether there exists at least one direction that makes it a legal move. In each direction, find the first cell that is at least two steps away from (rMove, cMove) and has color, which is the other endpoint, and check whether all cells between the two endpoints are all the opposite color.

• class Solution {
public boolean checkMove(char[][] board, int rMove, int cMove, char color) {
board[rMove][cMove] = color;
if (rMove >= 2) {
if (isGoodLine(board, rMove, cMove, color, -1, 0))
return true;
}
if (rMove < 6) {
if (isGoodLine(board, rMove, cMove, color, 1, 0))
return true;
}
if (cMove >= 2) {
if (isGoodLine(board, rMove, cMove, color, 0, -1))
return true;
}
if (cMove < 6) {
if (isGoodLine(board, rMove, cMove, color, 0, 1))
return true;
}
if (rMove >= 2 && cMove >= 2) {
if (isGoodLine(board, rMove, cMove, color, -1, -1))
return true;
}
if (rMove < 6 && cMove < 6) {
if (isGoodLine(board, rMove, cMove, color, 1, 1))
return true;
}
if (rMove >= 2 && cMove < 6) {
if (isGoodLine(board, rMove, cMove, color, -1, 1))
return true;
}
if (rMove < 6 && cMove >= 2) {
if (isGoodLine(board, rMove, cMove, color, 1, -1))
return true;
}
return false;
}

public boolean isGoodLine(char[][] board, int rMove, int cMove, char color, int rDelta, int cDelta) {
int rEndpoint = -1, cEndpoint = -1;
for (int i = rMove + rDelta * 2, j = cMove + cDelta * 2; i >= 0 && i < 8 && j >= 0 && j < 8; i += rDelta, j += cDelta) {
if (board[i][j] == color) {
rEndpoint = i;
cEndpoint = j;
break;
}
}
if (rEndpoint < 0 || cEndpoint < 0)
return false;
char midColor = color == 'W' ? 'B' : 'W';
for (int i = rMove + rDelta, j = cMove + cDelta; i != rEndpoint || j != cEndpoint; i += rDelta, j += cDelta) {
if (board[i][j] != midColor)
return false;
}
return true;
}
}

############

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

• 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

############

# 1958. Check if Move is Legal
# https://leetcode.com/problems/check-if-move-is-legal

class Solution:
def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
d = [-1, 0, 1]

for di in d:
for dj in d:
x, y = rMove + di, cMove + dj

if 0 <= x < 8 and 0 <= y < 8 and board[x][y] != color:
count = 0
clr = color
while 0 <= x < 8 and 0 <= y < 8 and board[x][y] != '.':
if clr != board[x][y]:
count += 1
if count == 2: return True
clr = board[x][y]
x += di
y += dj

return False

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

• func checkMove(board [][]byte, rMove int, cMove int, color byte) bool {
dirs := [8][2]int{ {1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} }
n := 8
for _, d := range dirs {
a, b := d[0], d[1]
i, j := rMove, cMove
t := 0
for 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
}