LeetCode 764. 最大加号标志（DP）

示例 1：
输入: N = 5, mines = [[4, 2]]
输出: 2
在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

示例 2：
输入: N = 2, mines = []
输出: 1
解释:
11
11
没有 2 阶加号标志，有 1 阶加号标志。
 
示例 3：
输入: N = 1, mines = [[0, 0]]
输出: 0
解释:
0
没有加号标志，返回 0 。
 
提示：
整数N 的范围： [1, 500].
mines 的最大长度为 5000.
mines[i] 是长度为2的由2个 [0, N-1] 中的数组成.
(另外,使用 C, C++, 或者 C# 编程将以稍小的时间限制进行​​判断.)

class Solution {
public:
    int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
        vector<vector<int>> g(N, vector<int>(N, 1));
        for(auto& m : mines)
            g[m[0]][m[1]] = 0;
        vector<vector<int>> up(N, vector<int>(N, 0));//该方向上的连续1的个数
        vector<vector<int>> left(N, vector<int>(N, 0));
        vector<vector<int>> down(N, vector<int>(N, 0));
        vector<vector<int>> right(N, vector<int>(N, 0));
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                if(g[i][j] == 0)
                    continue;
                left[i][j] = (j > 0 ? left[i][j-1] : 0) + 1;
                up[i][j] = (i > 0 ? up[i-1][j] : 0) + 1;
            }
        }
        for(int i = N-1; i >= 0; i--)
        {
            for(int j = N-1; j >= 0; j--)
            {
                if(g[i][j] == 0)
                    continue;
                right[i][j] = (j < N-1 ? right[i][j+1] : 0) + 1;
                down[i][j] = (i < N-1 ? down[i+1][j] : 0) + 1;
            }
        }
        int ans = 0;
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
                ans = max(ans, min(left[i][j], min(right[i][j],min(up[i][j], down[i][j]))));
        }
        return ans;
    }
};