題目描述:
給定一個 8x8 的棋盤(Othello/黑白棋),棋盤上有 'B'(黑)、'W'(白)和 '.'(空)三種狀態。給定一個位置 (rMove, cMove) 和顏色 color,判斷在該位置放置一個棋子是否為合法操作。
一個操作是合法的,當且僅當至少存在一個「好線段」:從放置的棋子出發,沿八個方向之一,經過一個或多個對方顏色的棋子,最後以己方顏色的棋子結束,且線段長度至少為 3。
解題思路:
(rMove, cMove) 出發向外延伸。true。時間複雜度:O(1) — 棋盤大小固定為 8x8,每個方向最多延伸 7 步,8 個方向共最多 56 步。
空間複雜度:O(1) — 只使用常數額外空間。
1. Define 8 directions: up, down, left, right, and 4 diagonals
2. For each direction (dr, dc):
a. Start from (rMove + dr, cMove + dc), set length = 1
b. While in bounds and cell == opponent color:
- Move to next cell in direction, increment length
c. If length >= 3 and current cell is in bounds and equals our color:
- Return true (valid good line found)
3. Return false (no valid direction found)直接模擬法:邏輯相同,但可以用遞迴代替迭代沿方向延伸。時間複雜度同為 O(1),但遞迴可能有額外的函式呼叫開銷。
預處理法:對每個空格預計算所有方向的合法性,適用於需要多次查詢的場景。時間複雜度 O(64 * 8 * 7) 預處理,之後每次查詢 O(1)。