“This is the 10th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Ten consecutive days of Leetcode is also a small milestone. I have been working on the topic of dynamic programming for a long time. After I find the feeling, I can do it much faster.

The title

In a 2D grid with sizes from (0, 0) to (n-1, n-1), every cell is 1 except for the 0 given in mines. What is the largest axis alignment plus sign in the grid that contains 1? Returns the order of the plus flag. If the plus flag is not found, 0 is returned.

An “axisymmetric” plus sign of k” rank 1 has a center grid[x][y] = 1, and four arms of length K-1 extending up, down, left, and right from the center, consisting of 1. An example of an “axisymmetric” plus sign of order K is given below. Note that only the plus flag requires all grids to be 1, while other grids may be 0 or 1.

K order axisymmetric plus sign example: Order 1: 0 0 0 0 1 0 0 0 0 0 0 0 0

Step 2:1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0

Step 3:0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

Example 1: Input: N = 5, mines = [[4, 2]] Output: 2 Explanation: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 In the grid above, the maximum plus flag can only have rank 2. A mark has been marked out on the drawing.

Example 2: Input: N = 2, mines = [] Output: 1 Explanation: 1 1 1 1 does not have the rank 2 plus flag, but has the rank 1 plus flag.

Example 3: Input: N = 1, mines = [[0, 0]] Output: 0 Explanation: 0 has no plus sign and returns 0.

Train of thought

This is kind of interesting, but it’s the biggest plus sign of 1 in the 01 matrix. I don’t have a lot of ideas at first, so I start with the violent method, and I think about what I would do if I went straight to the violent solution. The natural thing to think about is: Traverse the entire matrix, if the current point is zero, skip, if the current point is 1, then at least is the order of 1 plus 1, and then, respectively, up, down, left and right four direction outspread 1, the four direction of maximum length of l, r, t, d, then to the current point as the center of the biggest plus order number is min (l, r, t, d). Now, with this brute force method as the base, we have the state determined, and then we can think about how to do state compression. In fact, for each point, the length of the four directions are related to one of the elements of the same length, we from the perspective of the direction to the right of the most easy to understand, if the current element is 0, then to the right length is zero, if the current is 1, the length is equal to the left to the right of a point to the right length + 1, for example the following matrix:

0 1 1 1 1 0 1 1 0 1 1 1 1 1 1

The corresponding matrix with the length to the right of each point is:

0 1 2 3

1 0 1 2

0 1 2 3

1 2 3 4

In the same way, the length matrix of the left, down and up directions can be obtained

0 3 2 1 0 2 1 0 3 2 1 4 3 2 1

0 1 1 1 0 2 2 0 1 3 3 1 1 4 4

0 1 4 4 1 0 3 3 0 2 2 1 1 1 1

Once you have these matrices, you can quickly figure out the maximum plus order at the center of a point, which is min(L, R, t, d), and then iterate through the matrix to find the maximum.

Of course, there are some optimizations you can take when coding:

  • Because when evaluating a matrix in one direction, the value of each point depends only on itself and the value of the point before it, you can define a temporary variable current to store the value of the previous node
  • Moreover, the final result of each point is min(L, R, t, D), so there is no need to store the values of the four matrices corresponding to the four directions, just define a matrix to store the min values of each point
  • Finally, the step of maximizing the result matrix can be placed in the matrix of the last method, and it can also reduce an n by n matrix traversal

Java version code

class Solution { public int orderOfLargestPlusSign(int n, int[][] mines) { int ans = 0; Boolean [][] m = new Boolean [n][n]; Boolean [] m = new Boolean [n]; for (int[] point : mines) { m[point[0]][point[1]] = true; } int[][] dp = new int[n][n]; for (int i = 0; i < n; I++) {// int current = 0; for (int j = 0; j < n; j++) { if (m[i][j]) { current = 0; dp[i][j] = 0; } else { current = current + 1; dp[i][j] = current; }} // current = 0; for (int j = n-1; j >= 0; j--) { if (m[i][j]) { current = 0; dp[i][j] = 0; } else { current = current + 1; dp[i][j] = Integer.min(dp[i][j], current); } } } for (int j = 0; j < n; // down int current = 0; for (int i = 0; i < n; i++) { if (m[i][j]) { current = 0; dp[i][j] = 0; } else { current = current + 1; dp[i][j] = Integer.min(dp[i][j], current); }} // current = 0; for (int i = n-1; i >= 0; i--) { if (m[i][j]) { current = 0; dp[i][j] = 0; } else { current = current + 1; dp[i][j] = Integer.min(dp[i][j], current); } ans = integer. Max (ans, dp[I][j]); } } return ans; }}Copy the code