Description
在 8x8 的棋盤上，
'B'代表黑色、'W'代表白色、'.'代表空格。在位置(rMove, cMove)放置顏色color的棋子，判斷是否形成合法的「好線段」（兩端同色，中間至少一個異色，長度至少 3）。
Example:
Input: board = [[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]], rMove = 4, cMove = 3, color = “B” Output: true
Intuition#
從放置位置出發，沿八個方向延伸，檢查是否存在同色棋子夾住異色棋子的線段。
- 從
(rMove, cMove)沿 8 個方向延伸 - 跳過連續的異色棋子
- 若最終遇到同色棋子且中間至少有一個異色棋子，則合法
Approaches#
⭐1: 八方向掃描#
- 概念: 對每個方向，沿路檢查是否有連續異色棋子後接同色棋子
- 時間複雜度:
O(8 * 8) = O(1)（棋盤固定大小） - 空間複雜度:
O(1)
class Solution {
fun checkMove(board: Array<CharArray>, rMove: Int, cMove: Int, color: Char): Boolean {
val dirs = arrayOf(
intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0),
intArrayOf(1, 1), intArrayOf(1, -1), intArrayOf(-1, 1), intArrayOf(-1, -1)
)
for ((dr, dc) in dirs) {
var r = rMove + dr
var c = cMove + dc
var length = 1
while (r in 0..7 && c in 0..7 && board[r][c] != '.' && board[r][c] != color) {
r += dr
c += dc
length++
}
if (length >= 2 && r in 0..7 && c in 0..7 && board[r][c] == color) {
return true
}
}
return false
}
}2: 相同邏輯的另一種寫法#
- 概念: 封裝方向檢查為獨立函式
- 時間複雜度:
O(1) - 空間複雜度:
O(1)
class Solution {
fun checkMove(board: Array<CharArray>, rMove: Int, cMove: Int, color: Char): Boolean {
fun check(dr: Int, dc: Int): Boolean {
var r = rMove + dr
var c = cMove + dc
var count = 0
while (r in 0..7 && c in 0..7 && board[r][c] != '.' && board[r][c] != color) {
r += dr
c += dc
count++
}
return count >= 1 && r in 0..7 && c in 0..7 && board[r][c] == color
}
for (dr in -1..1) {
for (dc in -1..1) {
if (dr == 0 && dc == 0) continue
if (check(dr, dc)) return true
}
}
return false
}
}🔑 Takeaways#
- Pattern: 方向掃描 – 從某點沿固定方向延伸檢查
- 關鍵技巧: 注意中間必須至少有一個異色棋子（
length >= 2）；檢查邊界和終止條件（空格或同色棋子）