Java实现 LeetCode 764 最大加号标志（暴力递推）

ゝ一纸荒年。 2023-05-22 06:37 16阅读 0赞

## 764. 最大加号标志 ##

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

提示：

整数N 的范围： \[1, 500\].  
mines 的最大长度为 5000.  
mines\[i\] 是长度为2的由2个 \[0, N-1\] 中的数组成.  
(另外,使用 C, C++, 或者 C\# 编程将以稍小的时间限制进行判断.)

class Solution {  
         
        public int orderOfLargestPlusSign(int N, int[][] mines) { 
            if (N==0)return 0;
    
            int max_k=0;
    
            //填充一个2D网格matrix出来
            int matrix[][] = new int[N][N];
            for (int i=0;i<N;i++)
                Arrays.fill(matrix[i],1);
            int m = mines.length;
            for (int i=0;i<m;i++)
                matrix[mines[i][0]][mines[i][1]]=0;
    
            int dp[][] = new int[N][N];
            int count = 0;
            //初始化
            //求左、右
            for (int i=0;i<N;i++){ 
    
                //求左臂并将值放入dp left->right
                count = 0;
                for (int j=0;j<N;j++){ 
                    count = matrix[i][j]==1?count+1:0;
                    dp[i][j]= count;
                }
    
                //求右臂 并将当前dp与右臂之间的最小值放入dp right->left
                count = 0;
                for (int j=N-1;j>=0;j--){ 
                    count = matrix[i][j]==1?count+1:0;
                    dp[i][j]=Math.min(dp[i][j],count);
                }
            }
            //求上、下
            for (int j=0;j<N;j++){ 
                //求上臂 并将当前dp与上臂间的最小值放入dp up->down
                count = 0;
                for (int i=0;i<N;i++){ 
                    count = matrix[i][j]==1?count+1:0;
                    dp[i][j]=Math.min(dp[i][j],count);
                }
                //求下臂 并将当前dp与下臂间的最小值放入dp down->up
                //此时的整个dp数组中的最大值就是所求的k
                count = 0;
                for (int i=N-1;i>=0;i--){ 
                    count = matrix[i][j]==1?count+1:0;
                    dp[i][j]=Math.min(dp[i][j],count);
                    max_k=Math.max(max_k,dp[i][j]);
                }
            }
    
            return max_k;
        }
    }