764. 最大加号标志（难度：中等）

题目链接：https://leetcode.cn/problems/largest-plus-sign/

题目描述：

在一个 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 。

示例 1：

img

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

示例 2：

img

输入: n = 1, mines = [[0, 0]]
输出: 0
解释: 没有加号标志，返回 0 。

提示：

• 1 <= n <= 500
• 1 <= mines.length <= 5000
• 0 <= xi, yi < n
• 每一对 (xi, yi) 都 不重复

解法：暴力遍历

我们可以遍历每一个坐标，然后向四周扩散，计算出加号的最大阶数。

代码：

class Solution {
    int n = 0;
    int[][] mines;
    int[][] d = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[][] nums;

    public int orderOfLargestPlusSign(int n, int[][] mines) {
        this.n = n;
        this.mines = mines;
        this.nums = new int[n][n];
        int result = 0;
        for (int[] mine : mines) {
            this.nums[mine[0]][mine[1]] = 1;
        }
        for (int i = 0; i <= n - 1; i++) {
            for (int j = 0; j <= n - 1; j++) {
                if(nums[i][j] == 0) {
                    int calc = calc(i, j);
                    result = Math.max(calc, result);
                }
            }
        }
        return result;
    }

    public int calc(int x, int y) {
        int result = 1;
        boolean flag = true;
        while (flag) {
            for (int[] t : this.d) {
                int nextX = x + t[0] * result;
                int nextY = y + t[1] * result;
                if (!isFlag(nextX, nextY)) {
                    flag = false;
                    break;
                }
            }
            if (flag) result++;
        }
        return result;
    }

    public boolean isFlag(int nextX, int nextY) {
        return nextX >= 0 && nextX <= n - 1 && nextY >= 0 && nextY <= n - 1 && this.nums[nextX][nextY] != 1;
    }
}