🔗 🟡 1958. Check if Move is Legal 1659

tags: `Biweekly Contest 58` `陣列(Array)` `矩陣(Matrix)` `枚舉(Enumeration)`

題意

有一個 $8 \times 8$ 的棋盤，棋盤上的格子狀態以二維陣列 $\text{board}$ 給出，其中 $\text{board}[r][c]$ 表示棋盤上的格子 $(r, c)$ 。棋盤上空格用 '.' 表示，白棋用 'W' 表示，黑棋用 'B' 表示。

每次落子時，可以選擇一個空格，將其變成自己的顏色（白色或黑色）。但是，只有當這個格子變成一條 好線段(good line) 的端點時，這個落子才是合法的。

好線段(good line) 是指一條包含 三個或更多格子（包含端點格子） 的線段，線段的兩個端點格子是 同一種顏色，而中間剩餘的格子是 另一種顏色（線段上不能有任何空格子）。

給定兩個整數 $rMove$ 和 $cMove$ 以及一個字元 $color$ ，表示你將要在 $(rMove, cMove)$ 這個格子上落子，且你執棋的顏色是 $color$ 。請判斷這個操作是否合法，如果合法，返回 $\text{true}$ ，否則返回 $\text{false}$ 。

思路：枚舉所有方向

由於在合法操作時，落子點是一條好線段(good line) 的端點，因此可以透過枚舉所有方向，檢查在 $(rMove, cMove)$ 位置落子後，是否存在一條 好線段(good line) 來判斷落子是否合法。

使用一個函數 check(dx, dy) 來檢查從 $(rMove, cMove)$ 開始，沿著方向 $(dx, dy)$ 是否能形成合法的線段。在檢查過程中，如果遇到了與落子顏色相同的格子，表示找到了另一個端點。如果中間至少有一個格子，則返回 $\text{true}$ 表示找到了好線段。如果遇到了空格子，表示中間不連續，直接返回 $\text{false}$ 。如果走出了棋盤範圍，則表示該方向上沒有找到好線段，同樣返回 $\text{false}$ 。

枚舉所有方向時，可以使用雙重迴圈，分別枚舉 $dx \in [-1, 0, 1]$ 和 $dy \in [-1, 0, 1]$ ，但需要排除 $dx = 0$ 且 $dy = 0$ 的情況。對於每個方向呼叫 check(dx, dy) 函數，如果找到了好線段，則返回 $\text{true}$ ，否則繼續檢查下一個方向。如果所有方向都沒有找到好線段，則返回 $\text{false}$ 。

複雜度分析

時間複雜度： $O(\max(r, c))$ ，其中 $r$ 和 $c$ 分別是棋盤的 橫列(row) 和 直行(column) 數。
空間複雜度： $O(1)$ 。

class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
        def check(dx, dy):
            x, y = rMove + dx, cMove + dy
            cnt = 0 # 中間點的數量
            while 0 <= x < 8 and 0 <= y < 8: 
                if board[x][y] == color: # 找到另外一個端點
                    return True if cnt > 0 else False
                if board[x][y] == ".": # 中間不連續
                    return False
                x += dx
                y += dy
                cnt += 1
            return False
        # 檢查 8 個方向
        for dx in range(-1, 2):
            for dy in range(-1, 2):
                if dx == 0 and dy == 0:
                    continue
                if check(dx, dy):
                    return True
        return False

class Solution {
public:
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        function<bool(int, int)> check = [&](int dx, int dy) {
            int x = rMove + dx, y = cMove + dy;
            int cnt = 0;
            while (0 <= x && x < 8 && 0 <= y && y < 8) {
                if (board[x][y] == color) return cnt > 0;
                if (board[x][y] == '.') return false;
                x += dx;
                y += dy;
                cnt++;
            }
            return false;
        };
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (dx == 0 && dy == 0) continue;
                if (check(dx, dy)) return true;
            }
        }
        return false;
    }
};