# Largest Plus Sign

2018-02-03 10:19:37来源:oschina作者:叶枫啦啦人点击

In a 2Dgridfrom (0, 0) to (N-1, N-1), every cell contains a1, except those cells in the given listmineswhich are0. What is the largest axis-aligned plus sign of1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "axis-aligned plus sign of1sof orderk" has some centergrid[x][y] = 1along with 4 arms of lengthk-1going up, down, left, and right, and made of1s. This is demonstrated in the diagrams below. Note that there could be0s or1s 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:

Order 1:
000
010
000
Order 2:
00000
00100
01110
00100
00000
Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000

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.

Note:

Nwill be an integer in the range[1, 500].
mineswill have length at most5000.
mines[i]will be length 2 and consist of integers in the range[0, N-1].
(Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)

【题意】

“k阶十字形全1区域”中心点[x] [y] = 1以及长度为k-1的四向上，向下，向左和向右方向的点，均由1构成。

Input: N = 5, mines = [[4, 2]]

Input: N = 2, mines = []

Input: N = 1, mines = [[0, 0]]

0 因为没有满足十字形全1区域的值，所以返回0.

① https://leetcode.com/problems/largest-plus-sign/discuss/113314

grid[i][j]表示第i行第j列的元素的十字形全1区域的阶。时间复杂度O（n^2），空间复杂度O（n^2）

class Solution { //143ms public int orderOfLargestPlusSign(int N, int[][] mines) { int[][] grid = new int[N][N]; for (int i = 0;i < N;i ++){//初始化为矩阵的长度，阶一定会小于该值，遍历到每一个位置时会更新它Arrays.fill(grid[i],N); } for(int[] m : mines){grid[m[0]][m[1]] = 0; } for (int i = 0;i < N;i ++){for (int j = 0,l = 0;j < N;j ++){//j表示列，由左至右遍历,检查左侧可以到达多远，如果grid[i][j]=0，l需要再次从0开始，否则l递增grid[i][j] = Math.min(grid[i][j],l = (grid[i][j] == 0 ? 0 : l + 1));}for (int k = N - 1,r = 0;k >= 0;k --){//k表示列，从右向左遍历，每次检查右侧可以到达多远，如果grid[i][j]=0,r需要再次从0开始，否则r递增grid[i][k] = Math.min(grid[i][k],r = (grid[i][k] == 0 ? 0 : r + 1));}for (int j = 0,u = 0;j < N;j ++){//j表示行，从上到下遍历，每次检查上侧可以到达多远，如果grid[i][j]=0，u需要再次从0开始，否则u递增grid[j][i] = Math.min(grid[j][i],u = (grid[j][i] == 0 ? 0 : u + 1));}for (int k = N - 1,d = 0;k >= 0;k --){grid[k][i] = Math.min(grid[k][i],d = (grid[k][i] == 0 ? 0 : d + 1));} } int res = 0; for (int i = 0;i < N;i ++){for (int j = 0;j < N;j ++){res = Math.max(res,grid[i][j]);} } return res; } }