Sponsored
Sponsored
This approach involves using dynamic programming to store the maximum possible length of arms of a plus sign centered at each cell, checking in all four directions (left, right, up, down).
We initialize four matrices (left, right, up, down) that store the length of ones segment that ends at each cell in the corresponding direction. We update these matrices while iterating through the grid.
By iterating over the grid, first from top-left to bottom-right, and then from bottom-right to top-left, we can fill these matrices. The maximum order of the plus sign centered at any cell is the minimum value among the four directions at that cell.
Time Complexity: O(n^2) since each cell is visited and calculated twice.
Space Complexity: O(n^2) due to the four direction matrices.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int orderOfLargestPlusSign(int n, int** mines, int minesSize, int* minesColSize) {
6 int grid[n][n];
7 memset(grid, 1, sizeof(grid));
8
9 for (int i = 0; i < minesSize; i++) {
10 grid[mines[i][0]][mines[i][1]] = 0;
11 }
12
13 int left[n][n], right[n][n], up[n][n], down[n][n];
14 memset(left, 0, sizeof(left));
15 memset(right, 0, sizeof(right));
16 memset(up, 0, sizeof(up));
17 memset(down, 0, sizeof(down));
18
19 // Fill left and up
20 for (int i = 0; i < n; i++) {
21 for (int j = 0; j < n; j++) {
22 if (grid[i][j]) {
23 left[i][j] = (j == 0 ? 0 : left[i][j-1]) + 1;
24 up[i][j] = (i == 0 ? 0 : up[i-1][j]) + 1;
25 }
26 }
27 }
28
29 // Fill right and down
30 for (int i = n - 1; i >= 0; i--) {
31 for (int j = n - 1; j >= 0; j--) {
32 if (grid[i][j]) {
33 right[i][j] = (j == n - 1 ? 0 : right[i][j+1]) + 1;
34 down[i][j] = (i == n - 1 ? 0 : down[i+1][j]) + 1;
35 }
36 }
37 }
38
39 // Find the order of the largest plus sign
40 int maxOrder = 0;
41 for (int i = 0; i < n; i++) {
42 for (int j = 0; j < n; j++) {
43 if (grid[i][j]) {
44 int order = left[i][j];
45 if (up[i][j] < order)
46 order = up[i][j];
47 if (right[i][j] < order)
48 order = right[i][j];
49 if (down[i][j] < order)
50 order = down[i][j];
51 if (order > maxOrder)
52 maxOrder = order;
53 }
54 }
55 }
56
57 return maxOrder;
58}
59
60int main() {
61 // Example usage:
62 int n = 5;
63 int *mines[1];
64 int mine1[] = {4, 2};
65 mines[0] = mine1;
66 int result = orderOfLargestPlusSign(n, mines, 1, NULL);
67 printf("%d\n", result); // Output: 2
68 return 0;
69}The implementation starts by initializing a grid and converting the mines positions to zero. Four matrices (left, right, up, down) store the consecutive 1 segments up to that point from each direction respectively.
We iterate through the grid twice. The first pass, filling left and up, goes top-to-bottom and left-to-right; the second, filling right and down, goes bottom-to-top and right-to-left. Finally, we calculate the minimum of the maximum possible lengths at each point to determine the largest possible plus sign.
This approach uses a greedy algorithm with the aid of hash sets to track each encountered zero from the mines. By using sets, we quickly check if any particular cell disrupts a potential plus sign, and can avoid unnecessary calculations.
For every arm of each potential plus sign in the grid, checks are performed to determine continuation down an arm or reset due to zeroes from mines.
Time Complexity: O(n^2) due to the requirement to scan both axes when looking for maximum stretches of ones.
Space Complexity: O(n^2) as the boolean grid requires space for each cell to track presence of mine locations.
This C program uses a 2D boolean array to track where mines are located, to avoid recalculating grid states unnecessarily. It also checks for maximum arm lengths from prior initializations to limit the search scope while calculating potential plus signs.