根據(jù)題意的話就是在非0的地方開始尋找上下左右分別能夠走到的最大步長的。

那么使用暴力的方法竟然leetcode還是給過了。

class Solution { public:int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {int res=0;vector<vector<int>> vis(N, vector<int>(N,1));for(int i=0;i<mines.size();i++){vis[mines[i][0]][mines[i][1]]=0;}for(int i=0;i<N;i++){for(int j=0;j<N;j++){if(vis[i][j]){int step=1;while(judge(vis,N,i,j,step)) step++;res=max(res,step);}}}return res;}bool judge(vector<vector<int>>&vis,int N, int i,int j, int step){if(i-step<0||i+step>=N||j-step<0||j+step>=N) return false;return vis[i-step][j] &&vis[i+step][j]&&vis[i][j-step]&&vis[i][j+step];} };

在這里會發(fā)現(xiàn)存在大量的計算冗余的，考慮使用dp的動態(tài)規(guī)劃，利用dp[i][j]來標(biāo)記在方向上能夠移動的最長距離的。

簡化算法參考：http://www.cnblogs.com/grandyang/p/8679286.html

向左移動： [i][j]: j在內(nèi)層循環(huán)，從小到大；

向右移動： [i][j]: j在內(nèi)層循環(huán)，從大到小；

向下移動： [i][j]: i在內(nèi)層循環(huán)，從小到大；

向上移動： [i][j]: i在內(nèi)層循環(huán)，從大到小；

class Solution { public:int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {int res=0;vector<vector<int>> dp(N, vector<int>(N,N));for(int i=0;i<mines.size();i++){dp[mines[i][0]][mines[i][1]]=0;}for(int i=0;i<N;i++){int l=0,r=0,u=0,d=0;for(int j=0,k=N-1; j<N,k>=0; j++,k--){dp[i][j]=min(dp[i][j], l=(dp[i][j]==0)?0:l+1); // left方向dp[i][k]=min(dp[i][k], r=(dp[i][k]==0)?0:r+1); // right方向dp[j][i]=min(dp[j][i], d=(dp[j][i]==0)?0:d+1); // down方向dp[k][i]=min(dp[k][i], u=(dp[k][i]==0)?0:u+1); // up方向 }}for(int i=0;i<N*N;i++) res=max(res, dp[i/N][i%N]);return res;} };

?

轉(zhuǎn)載于:https://www.cnblogs.com/newnoobbird/p/9635304.html

總結(jié)

以上是生活随笔為你收集整理的leetcode 764.Largest Plus Sign的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。