每日一题——764.最大加号标志

题干

在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0

返回 grid 中包含 1 的最大的 轴对齐 加号标志的阶数。如果未找到加号标志，则返回 0 。

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

思路

一开始想到的是DFS，即对于边界以外的每个点，

先判断当前数字是否为1，

接着往四个方向去探寻数字1的数量，

结果取四个值的最小值，最后再和res进行比较，取最大值

但是后面发现这样会有很多重复的步骤（比如说某个点右边1的数量，是可以被下一个数复用的；不是说DFS不行，这里理解为空间换时间吧）

所以可以用动态规划来解决

对于每个点，都记录以该点作为其他点的上下左右四个方向时，1的数量是多少

这里可以用数据结构record来记录

最后依次遍历边界以外的每个点，求四个方向的最小值，接着和res进行比较，取最大值

代码：

struct record {
    record():up(0), down(0), left(0), right(0) {}
    int up;
    int down;
    int left;
    int right;
};

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<int>> f(n, vector<int>(n, 1));
        for (auto& mine: mines) {
            f[mine[0]][mine[1]] = 0;
        }

        vector<vector<record>> records(n, vector<record>(n, record{}));
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < n; ++ j) {
                if (f[i][j] == 0) continue;
                if (i == 0) records[i][j].up = 1;
                else records[i][j].up = records[i - 1][j].up + 1;
                if (j == 0) records[i][j].left = 1;
                else records[i][j].left = records[i][j - 1].left + 1;
            }
        }

        for (int i = n - 1; i >= 0; -- i) {ty
            for (int j = n - 1; j >= 0; -- j) {
                if (f[i][j] == 0) continue;
                if (i == n - 1) records[i][j].down = 1;
                else records[i][j].down = records[i + 1][j].down + 1;
                if (j == n - 1) records[i][j].right = 1;
                else records[i][j].right = records[i][j + 1].right + 1;
            }
        }

        int res{};
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < n; ++ j) {
                if (f[i][j] == 0) continue;
                if (i == 0 || j == 0 || i == n - 1 || j == n - 1) {
                    res = max(res, 1);
                    continue;
                }
                int ans = min(INT_MAX, records[i - 1][j].up);
                ans = min(ans, records[i + 1][j].down);
                ans = min(ans, records[i][j - 1].left);
                ans = min(ans, records[i][j + 1].right);
                res = max(res, ans + 1);
            }
        }
        return res;
    }
};

反思

这道题我一开始就是DFS去做的

后面是看了标签才意识到是动态规划

只能说题目做少了，很多题都没有意识到大概是啥方向的

另一方面，思路有了，coding的时候思绪被堵住了

说明代码也是写少了，需要每日一题来提高熟练度