LeetCode 解題筆記：3665. Twisted Mirror Path Count

作者：王一哲
日期：2026年10月31日


LeetCode 題目連結：3665. Twisted Mirror Path Count

解題想法

中等難度題。題目給一個 $m \times n$ 的二維陣列 $grid$，其中 $0$ 代表空地，$1$ 代表鏡子。機器人從 $(0, 0)$ 出發，只能向右或向下走，終點為 $(m-1, n-1)$，保證起點、終點一定是空地。如果原來向右走，遇到鏡子時改成向下走；如果原來向下走，遇到鏡子時改成向右走。計算可能的路徑數量，並對 $mod = 10^9 + 7$ 取餘數。

這題考動態規畫，由於更新走到這一列每一格的方法數時，只會用到上一列及這一列左側格子的方法數，可以開兩個長度皆為 $n$ 的一維陣列 $right, down$，分別記錄向右走、向下走到這格的方法數，預設 $right[0] = 1, down[0] = 1$，其它項皆為 $0$。用兩層迴圈更新每一格的方法數，假設走到 $grid[i][j]$，如果 $j > 0$ 代表可以從左向右走到這格，方法數 $a = right[j-1]$，反之為 $0$；如果 $i > 0$ 代表可以從上向下走到這格，方法數 $b = down[j]$，反之為 $0$；走到這格的總方法數 $total = (a + b) % mod$。如果走到終點，直接回傳 total。如果 $grid[i][j]$ 是空地，$right[j], down[j]$ 方法數更新為 $total$。如果 $grid[i][j]$ 是鏡子，向右、向下走的方法數交換。如果跑完兩層迴圈都沒有走到終點，回傳 $0$。

Python 程式碼

Runtime: 643 ms, beats 84.62%. Memory: 34.02 MB, beats 83.76%.

class Solution:
    def uniquePaths(self, grid: List[List[int]]) -> int:
        mod = 10**9 + 7
        m, n = len(grid), len(grid[0])
        right = [0] * n  # 離開 row[j] 且向右走的方法數
        down = [0] * n  # 離開 row[j] 且向下走的方法數
        right[0] = down[0] = 1  # 起點 (0, 0) 方法數 1

        for i in range(m):
            for j in range(n):
                # 跳過起點
                if i == j == 0: continue

                # 一般狀況
                a = right[j-1] if j > 0 else 0  # 由左邊的格子走過來的方法數
                b = down[j] if i > 0 else 0  # 由上面的格子走過來的方法數

                if grid[i][j] == 0:  # 遇到空地
                    total = (a + b) % mod  # 走到 grid[i][j] 的方法數
                    if i == m-1 and j == n-1:  # 走到終點，直接回傳方法數
                        return total
                    # 更新 right 及 down
                    right[j] = down[j] = total
                else:  # 遇到鏡子，向右走、向下走方法數互換
                    right[j], down[j] = b, a
        
        # 如果沒有觸發第 10 行的條件，走不到終點，回傳 0
        return 0

C++ 程式碼

Runtime: 52 ms, beats 90.83%. Memory: 194.13 MB, beats 87.50%.

class Solution {
public:
    int uniquePaths(vector<vector<int>>& grid) {
        const int mod = 1000000007;
        int m = grid.size(), n = grid[0].size();
        vector<int> right (n, 0), down (n, 0);
        right[0] = 1;
        down[0] = 1;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                // 跳過起點
                if (i == 0 && j == 0) continue;

                // 一般狀況，從左向右走到這格方法數 a，從上向下走到這格方法數 b
                int a = (j > 0 ? right[j-1] : 0);
                int b = (i > 0 ? down[j] : 0);
                int total = (a + b) % mod;

                // 走到終點，直接回傳 total
                if (i == m-1 && j == n-1) return total;

                // 如果這格是空地，right[j], down[j] 方法數更新為 total
                if (grid[i][j] == 0) {
                    right[j] = total;
                    down[j] = total;
                } else {  // 鏡子，向右、向下走的方法數交換
                    right[j] = b;
                    down[j] = a;
                }
            }
        }
        // 如果沒有觸發第 20 行的條件，走不到終點，回傳 0
        return 0;
    }
};

C 語言程式碼

Runtime: 49 ms, beats 100.00%. Memory: 47.66 MB, beats 71.43%.

int uniquePaths(int** grid, int gridSize, int* gridColSize) {
    const int mod = 1000000007;
    int m = gridSize, n = *gridColSize;
    int right[501] = {0}, down[501] = {0};
    right[0] = 1;
    down[0] = 1;

    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            // 跳過起點
            if (i == 0 && j == 0) continue;

            // 一般狀況，從左向右走到這格方法數 a，從上向下走到這格方法數 b
            int a = (j > 0 ? right[j-1] : 0);
            int b = (i > 0 ? down[j] : 0);
            int total = (a + b) % mod;

            // 走到終點，直接回傳 total
            if (i == m-1 && j == n-1) return total;

            // 如果這格是空地，right[j], down[j] 方法數更新為 total
            if (grid[i][j] == 0) {
                right[j] = total;
                down[j] = total;
            } else {  // 鏡子，向右、向下走的方法數交換
                right[j] = b;
                down[j] = a;
            }
        }
    }
    // 如果沒有觸發第 20 行的條件，走不到終點，回傳 0
    return 0;
}