在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中，除了在 mines 中给出的单元为 0，其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶？返回加号标志的阶数。如果未找到加号标志，则返回 0。

    一个 k” 阶由 1 组成的“轴对称”加号标志具有中心网格 grid[x][y] = 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。下面给出 k” 阶“轴对称”加号标志的示例。注意，只有加号标志的所有网格要求为 1，别的网格可能为 0 也可能为 1。

    k 阶轴对称加号标志示例:

    阶 1:
    000
    010
    000

    阶 2:
    00000
    00100
    01110
    00100
    00000

    阶 3:
    0000000
    0001000
    0001000
    0111110
    0001000
    0001000
    0000000

    示例 1：

    输入: N = 5, mines = [[4, 2]]
    输出: 2
    解释:
    11111
    11111
    11111
    11111
    11011
    在上面的网格中，最大加号标志的阶只能是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# 编程将以稍小的时间限制进行判断.)

    题解思路：分别用dp_left记录每一个grid左边连续1的个数(包含自己)；同理：dp_right, dp_up, dp_down
    结果：max(largest_plus_sign, min(dp_left, dp_right, dp_up, dp_down))

    1. int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
    2.     // generate grid
    3.     vector<vector<int>> grid(N, vector<int> (N, 1));
    4.     int mines_len = mines.size();
    5.     for(int i=0; i<mines_len; ++i){
    6.         grid[mines[i][0]][mines[i][1]] = 0;
    7.     }
    9.     // state definition and initialize
    10.     // dp_left[r][c] record the number of 1 before 
    11.     // a zero starting at r, c (contain itself[r, c]);
    12.     // dp_right[r][c], dp_up[r][c], dp_down[r][c] etc.
    13.     vector<vector<int>> dp_left(N, vector<int>(N, 0));
    14.     vector<vector<int>> dp_right(N, vector<int>(N, 0));
    15.     vector<vector<int>> dp_up(N, vector<int>(N, 0));
    16.     vector<vector<int>> dp_down(N, vector<int>(N, 0));
    18.     // state transfer, dp_left and dp_up
    19.     for(int r = 0; r < N; ++r){
    20.         for(int c = 0; c < N; ++c){
    21.             if (grid[r][c] == 0)
    22.                 continue;
    23.             dp_left[r][c] = 1 + (c > 0 ? dp_left[r][c-1] : 0);
    24.             dp_up[r][c] = 1 + (r > 0 ? dp_up[r-1][c] : 0);
    25.         }
    26.     }
    28.     int largest_plus_sign = 0;
    29.     // state transfer, dp_right and dp_down
    30.     // also calc largest_plus_sign = max(largest_plus_sign, min(dp_left[r][c], 
    31.                                     dp_right[r][c], dp_down[r][c], dp_up[r][c])
    32.     for(int r = N-1; r >= 0; --r){
    33.         for(int c = N-1; c >= 0; --c){
    34.             if(grid[r][c] == 0)
    35.                 continue;
    36.             dp_right[r][c] = 1 + (c < N-1 ? dp_right[r][c+1] : 0);
    37.             dp_down[r][c] = 1 + (r < N-1 ? dp_down[r+1][c] : 0);
    39.             // 
    40.             int curr_plus_sign = min(min(min(dp_left[r][c], dp_right[r][c]), 
    41.                                          dp_up[r][c]), dp_down[r][c]);
    42.             largest_plus_sign = max(largest_plus_sign, curr_plus_sign);
    43.         }
    44.     }
    46.     return largest_plus_sign;
    47. }

    欢迎交流，不吝赐教！如果觉得对比有用，赏杯水喝！
    image.pngWeChat Image_20200714101954.jpg