LeetCode 解題筆記：764. Largest Plus Sign

作者：王一哲
日期：2026年9月25日


LeetCode 題目連結：764. Largest Plus Sign

解題想法

中等難度題，題目一個正整數 $n$，代表一個 $n \times n$ 的二維陣列，陣列之中除了某些位置為 $0$，其它位置都是 $1$。再給一個二維陣列 $mines$，其中每一個元素為長度 $2$ 的陣列，代表數值為 $0$ 的位置。題目定義從 $n \times n$ 的二維陣列中找出 + 號大小的計算方式，從 + 中央開始為長度 1，向上、下、左、右延伸，如果 4 個方向都是 1 則長度加 1，如果任何一個方向是 0 就不能再延伸。題目要回傳最大的 + 大小。

首先為了便於查於指定坐標是否在 mines 之中，如果用 Python 解題，可以先將 $mines$ 轉成 set 會比較快；如果用 C++ 解題，再開另一個二維陣列標記 0 的位置會比較快。接下來定義一個 $n \times n$ 的二維陣列 $dp$，用來記錄以每一格為中心的 + 最大長度，預設值皆設為 $n$。用 for 迴圈掃過 $i = 0$ 到 $i = n-1$；裡面再用一層 for 迴圈掃瞄水平方向，分別更新由左向右、由右向左掃的十字大小，再更新對應位置的 $dp$ 值；再用另用一個 for 迴圈掃瞄鉛直方向，分別更新由上向下、由下向上掃的十字大小，再更新對應位置的 $dp$ 值。全部更新完畢之後，答案為 $dp$ 之中的最大值。

Python 程式碼

Runtime: 1205 ms, beats 21.40%. Memory: 22.84 MB, beats 61.87%.

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: list[list[int]]) -> int:
        # 轉成 set，查詢指定坐標是否在 mines 之中會比較快
        mineset = {tuple(mine) for mine in mines}
        dp = [[n]*n for _ in range(n)]  # 每一格最大的十字大小，預設為最大值 n
        
        for i in range(n):
            # 掃瞄水平方向
            lcnt, rcnt = 0, 0  # 左向右、右向左掃的十字大小
            for j in range(n):  # 改變欄坐標
                # 由左到右，如果 (i, j) 有地雷歸零，反之加 1
                lcnt = 0 if (i, j) in mineset else lcnt + 1
                dp[i][j] = min(dp[i][j], lcnt)

                # 由右到左，如果 (i, n-j-1) 有地雷歸零，反之加 1
                k = n-j-1
                rcnt = 0 if (i, k) in mineset else rcnt + 1
                dp[i][k] = min(dp[i][k], rcnt)
            
            # 掃瞄鉛直方向
            ucnt, dcnt = 0, 0  # 上向下、下向上掃的十字大小
            for j in range(n):  # 改變列坐標
                # 由上到下，如果 (j, i) 有地雷歸零，反之加 1
                ucnt = 0 if (j, i) in mineset else ucnt + 1
                dp[j][i] = min(dp[j][i], ucnt)

                # 由下到上，如果 (n-j-1) 有地雷歸零，反之加 1
                k = n-j-1
                dcnt = 0 if (k, i) in mineset else dcnt + 1
                dp[k][i] = min(dp[k][i], dcnt)
        
        # 掃過所有的格子找最大值
        ans = 0
        for i in range(n):
            for j in range(n):
                ans = max(ans, dp[i][j])
        return ans

C++ 程式碼

用 map 記錄 mines 的位置，很慢。Runtime: 415 ms, beats 13.91%. Memory: 40.26 MB, beats 61.90%.

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        map<pair<int, int>, bool> minemap;
        for(auto mine : mines) {
            minemap[{mine[0], mine[1]}] = true;
        }

        vector<vector<int>> dp (n, vector<int> (n, n));
        for(int i = 0; i < n; i++) {
            int lcnt = 0, rcnt = 0;
            for(int j = 0; j < n; j++) {
                lcnt = (minemap.count({i, j}) == 1 ? 0 : lcnt + 1);
                dp[i][j] = min(dp[i][j], lcnt);

                int k = n-j-1;
                rcnt = (minemap.count({i, k}) == 1 ? 0 : rcnt + 1);
                dp[i][k] = min(dp[i][k], rcnt);
            }

            int ucnt = 0, dcnt = 0;
            for(int j = 0; j < n; j++) {
                ucnt = (minemap.count({j, i}) == 1 ? 0 : ucnt + 1);
                dp[j][i] = min(dp[j][i], ucnt);

                int k = n-j-1;
                dcnt = (minemap.count({k, i}) == 1 ? 0 : dcnt + 1);
                dp[k][i] = min(dp[k][i], dcnt);
            }
        }

        int ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

用二維 vector 記錄 mines 位置，速度快很多。Runtime: 68 ms, beats 73.44%. Memory: 38.65 MB, beats 62.82%.

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        // 建立 minemap
        vector<vector<bool>> minemap (n, vector<bool> (n, false));
        for(auto mine : mines) {
            int r = mine[0], c = mine[1];
            minemap[r][c] = true;
        }

        // 每一格最大的十字大小，預設為最大值 n
        vector<vector<int>> dp (n, vector<int> (n, n));
        
        for(int i = 0; i < n; i++) {
            // 掃瞄水平方向
            int lcnt = 0, rcnt = 0;  // 左向右、右向左掃的十字大小
            for(int j = 0; j < n; j++) {  // 改變欄坐標
                // 由左到右，如果 (i, j) 有地雷歸零，反之加 1
                lcnt = (minemap[i][j] ? 0 : lcnt + 1);
                dp[i][j] = min(dp[i][j], lcnt);

                // 由右到左，如果 (i, n-j-1) 有地雷歸零，反之加 1
                int k = n-j-1;
                rcnt = (minemap[i][k] ? 0 : rcnt + 1);
                dp[i][k] = min(dp[i][k], rcnt);
            }

            // 掃瞄鉛直方向
            int ucnt = 0, dcnt = 0;  // 上向下、下向上掃的十字大小
            for(int j = 0; j < n; j++) {  // 改變列坐標
                // 由上到下，如果 (j, i) 有地雷歸零，反之加 1
                ucnt = (minemap[j][i] ? 0 : ucnt + 1);
                dp[j][i] = min(dp[j][i], ucnt);

                // 由下到上，如果 (n-j-1) 有地雷歸零，反之加 1
                int k = n-j-1;
                dcnt = (minemap[k][i] ? 0 : dcnt + 1);
                dp[k][i] = min(dp[k][i], dcnt);
            }
        }

        // 掃過所有的格子找最大值
        int ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};