[leetcode]动态规划之Largest Plus Sign

快来打我* 2021-09-29 00:58 233阅读 0赞

### 动态规划之Largest Plus Sign ###

*  题目
 *  思考
 *  代码
 *   *  暴力法
     *  DP法

# 题目 #

[leetcode入口][leetcode]

# 思考 #

刚开始在想一个位置(i,j)是否在mines容器中要怎么查找  
想过直接开一个数组存储，但是怕太大了爆掉，  
后来看了解析发现N的范围也不是很大，于是就应该直接开数组存储。。。  
暴力法可以过但是非常慢。

dp法：选择所在点中，四个方向1的个数最小的那个最为该点处的阶

# 代码 #

## 暴力法 ##

class Solution { 
    public:
        int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) { 
            vector<vector<int>> mat(N,vector<int>(N,1));
            for(auto mine : mines) mat[mine[0]][mine[1]]=0;
            
            int order=0;
            for(int i=0;i<N;i++){ 
                for(int j=0;j<N;j++){ 
                    if(mat[i][j])
                        order=max(order,judge(i,j,mat,mines));
                }
            }
            
            
            return order;
        }
        
        
        int judge(int i,int j,vector<vector<int>>& mat,vector<vector<int>>& mines){ 
            int order=1;
            
            while(true){ 
                int arm=order;
                if(i-arm>=0 && i+arm<mat.size() && j+arm<mat.size() && j-arm>=0){ 
                    if( mat[i-arm][j] && mat[i+arm][j] && mat[i][j-arm]&& mat[i][j+arm] ){ 
                        order++;
                    }
                    else{ 
                        break;
                    }
                }
                else { 
                    break;
                }
            }
            
            return order;
        }
        
        
    };

## DP法 ##

class Solution { 
    public:
        int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) { 
            
            //初始化为一个最大值，因为最后是要求四个方向的最小值
            vector<vector<int>> dp(N,vector<int>(N,N));
            
            unordered_set<int> s;
            for (auto mine : mines) s.insert(mine[0] * N + mine[1]);
            
            
            for(int j=0;j<N;j++){ 
                int cnt=0;
                
                //up
                for(int i=0;i<N;i++){ 
                    cnt=s.count(i*N+j)?0:cnt+1;
                    dp[i][j]=cnt;
                }
                
                cnt=0;
                //down
                for(int i=N-1;i>=0;i--){ 
                    cnt=s.count(i*N+j)?0:cnt+1;
                    dp[i][j]=min(dp[i][j],cnt);
                }
            }
            
            int res=0;
            for(int i=0;i<N;i++){ 
                int cnt=0;
                //left
                for(int j=0;j<N;j++){ 
                    cnt=s.count(i*N+j)?0:cnt+1;
                    dp[i][j]=min(dp[i][j],cnt);
                }                                           
                cnt=0;
                //right
                for(int j=N-1;j>=0;j--){ 
                    cnt=s.count(i*N+j)?0:cnt+1;
                    dp[i][j]=min(dp[i][j],cnt);
                    res=max(res,dp[i][j]);
                }
            }
            
            return res;
        }
    };

[leetcode]: https://leetcode.com/problems/largest-plus-sign/