764. Largest Plus Sign最大的dfs十字架

［抄题］：

求挖掉一些区域后，能允许出现的最大十字架

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "axis-aligned plus sign of 1s of order k" has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

Examples of Axis-Aligned Plus Signs of Order k:

Example 1:

Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.  One of them is marked in bold.

Example 2:

Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.

Example 3:

Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

每个有数的点先初始化为N，再逐步缩小为能扩展的最小值

［思维问题］：

知道是dfs，不知道怎么写。太需要数学技巧了，感觉就是背

［英文数据结构或算法，为什么不用别的数据结构或算法］：

新建一个数组，然后 dfs就是直接在图上操作就行

［一句话思路］：

max - min -max, 对所有点，在其四个方向中扩展的最大值中找个最小的，然后在所有点中找最大的作为整张图的结果

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

最外层循环是一个可以重复用的变量，不只是表示从左往右扫时行不变，也可以表示从上往下扫时列不变。

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

for loop中的i & j 只在当前的循环中起作用，所以每次都要重复declare

［总结］：

［复杂度］：Time complexity: O(n^4) Space complexity: O(n^2)

［算法思想：递归/分治/贪心］：递归

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

class Solution {
    public int orderOfLargestPlusSign(int N, int[][] mines) {
        //cc
        if (N == 0) return 0;
        
        //ini grids: set N， set 0
        int[][] grids = new int[N][N];
        for (int[] row : grids) Arrays.fill(row, N);
        for (int[] mine : mines) grids[mine[0]][mine[1]] = 0;
        
        //for loop: i, 4 directions
        for (int i = 0; i < N; i++) {
            //l - r
            for (int j = 0, l = 0; j < N; j++) {
                grids[i][j] = Math.min(grids[i][j], l = (grids[i][j] == 0 ? 0 : l + 1));
            }
            
            //r - l
            for (int j = N -1, r = 0; j >= 0; j--) {
                grids[i][j] = Math.min(grids[i][j], r = (grids[i][j] == 0 ? 0 : r + 1));
            }
            
            //u - d
            for (int k = 0, u = 0; k < N; k++) {
                grids[k][i] = Math.min(grids[k][i], u = (grids[k][i] == 0 ? 0 : u + 1));
            }
            
            //d - u
            for (int k = N -1, d = 0; k >= 0; k--) {
                grids[k][i] = Math.min(grids[k][i], d = (grids[k][i] == 0 ? 0 : d + 1));
            }
        }
        
        //for loop: for the biggest
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) 
                res = Math.max(res, grids[i][j]);
        }
        
        return res;
    }
}

View Code