前言

今天的題目在這裡：764. Largest Plus Sign，是一題medium的題目。我直覺把它變成我習慣的dynamic programming格式來寫，先來看看我的思路吧！

動態規劃

不知道大家知不知道dynamic programming，可以參考這邊。簡單來說，就是把大問題倒推回去變成前一個狀態，有點以前數學演繹法的感覺(?) 最簡單的例子就是費氏數列，你要我一口氣算f(100)是多少？我一時算不出來，但我知道f(100)會=f(98)+f(99)，那f(99)又=f(97)+f(98)...以此倒推回去到f(0)跟f(1)的狀態我就可以知道是0和1，就可以算回去了。
但是呢！從後面這樣推回去，如果你用recursive是很不划算的，你看看你算f(99)的時候要去算f(97)和f(98)...直接一路算到底算出f(99)了，下一個數字：f(98) 天啊同樣的動作又要從頭再來推一次？！
聰明如你就可以發現有幾個可以優化的地方─把算過的記錄下來，而我們也不用從後面開始推，從前面開始記就好啦~
於是有了f(0)和f(1)之後你就可以算出f(2)，記下來，下一個f(3)的時候回去找f(1)+f(2)，再把f(3)記下來...如此用個for迴圈遍歷一次到100你就可以獲得答案了。當然，你也可以再優化它的空間複雜度，因為我們發現其實每次都只需要前兩個值就夠了，於是就改成一個prev1，一個prev2，每次都把它更新成當下最新的兩個值，就完成啦！
講了這麼多，跟這題有什麼關係咧？

想法

總之，這題如果我想用O(n^2)的時間去做，肯定需要在遍歷的時候一邊就更新最新結果，不管怎樣，我先把題目的矩陣畫出來吧！
我把可以過的地方設為1，有障礙物的地方設為0：

vector<vector<int>>combined(n,vector<int>(n,1));
for(int i=0; i<mines.size();++i){
    combined[mines[i][0]][mines[i][1]] = 0;
}

那我要怎麼算出最大的可能的十字呢？先把問題拆小一點，我們可以想成求最長的直線/橫線，是不是就簡單很多？
所以我用兩個矩陣來儲存"包含該格"的最長直線，為什麼要包含該格？因為這樣我們才能一直遞推，如果包含這格，有障礙的話就是0，沒障礙的話就會=前面那個的最長長度+1，如下：

vector<vector<int>>row=combined;
vector<vector<int>>col=combined;
for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
        if(combined[i][j]==1){
           if(i>0){
               row[i][j] = row[i-1][j]+1;
           } 
           if(j>0){
               col[i][j] = col[i][j-1]+1;
           }
        }

    }
}

這樣呢，我們已經完成題目的一半了！
怎麼會？你想想，如果現在題目要求的是找到最長的十字左上半邊，是不是就可以直接求出來了XD
若現在我的地圖長這樣

111
011
111

那我的row跟col分別會長這樣

123     111
012     022
123     133

如果要求的是最長的一個」，那是不是就把兩邊取交集的最大值(min(row, col)，代表同時考慮到row和column的話最長可以是多少)，就會是結果了?

111
012
123

你比比看，是不是以每一點當作」的右下角，它最長的邊就是如圖中那樣？
不過現在題目要求的是十字，那我們就倒過來再遍歷一次：

vector<vector<int>>rowR=combined;
vector<vector<int>>colR=combined;
for(int i=n-1;i>=0;--i){
    for(int j=n-1;j>=0;--j){
        if(combined[i][j]==1){
           if(i<n-1){
               rowR[i][j] = rowR[i+1][j]+1;
           } 
            if(j<n-1){
                colR[i][j] = colR[i][j+1]+1;
            }
        }
    }
}

然後再針對每一點求交集的最大值，就好了！
完整程式碼如下：

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        // build the initial matrix
        vector<vector<int>>combined(n,vector<int>(n,1));
        for(int i=0; i<mines.size();++i){
            combined[mines[i][0]][mines[i][1]] = 0;
        }
        
        // save for the longest consecutive 1 including that position
        vector<vector<int>>row=combined;
        vector<vector<int>>col=combined;
        vector<vector<int>>rowR=combined;
        vector<vector<int>>colR=combined;
        
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(combined[i][j]==1){
                   // if the position could be included, else remain 0
                   // avoid computing the first row/column, the position should always equal to itself
                   if(i>0){
                       row[i][j] = row[i-1][j]+1;
                       
                   } 
                    if(j>0){
                        col[i][j] = col[i][j-1]+1;
                    }
                    
                }
                
            }
        }
        
        
        for(int i=n-1;i>=0;--i){
            for(int j=n-1;j>=0;--j){
                if(combined[i][j]==1){
                   if(i<n-1){
                       rowR[i][j] = rowR[i+1][j]+1;
                   } 
                    if(j<n-1){
                        colR[i][j] = colR[i][j+1]+1;
                    }
                }
                
            }
        }
        
        // compute for the intersection(min) of each position
        int ans=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                ans = max(ans,{min({row[i][j], col[i][j], rowR[i][j], colR[i][j]})});
           }
                
        }
    return ans;
    }
};

結語

工作好累QQ 可能有點講不清楚，如果有任何問題歡迎留言提出！