Largest Plus Sign LeetCode solution in C++

1
class Solution {
2
 public:
3
  int orderOfLargestPlusSign(int n, vector<vector<int>> &mines) {
4
    // jai shri ram
5
    int ans = 0;
6
    vector<bool> block(25 * int(1e4) + 1, 0);
7
    vector<vector<int>> dp(n, vector<int>(n, 0));
8
    for (auto x : mines) {
9
      int a = x[0], b = x[1];
10
      block[a * n + b] = true;
11
    }
12
    for (int i = 0; i < n; i++) {
13
      int sum = 0;
14
      for (int j = 0; j < n; j++) {
15
        if (block[i * n + j]) {
16
          sum = 0;
17
        } else {
18
          sum += 1;
19
        }
20
        dp[i][j] = sum;
21
      }
22
    }
23
    for (int j = 0; j < n; j++) {
24
      int sum = 0;
25
      for (int i = 0; i < n; i++) {
26
        if (block[i * n + j]) {
27
          sum = 0;
28
        } else
29
          sum += 1;
30
        dp[i][j] = min(dp[i][j], sum);
31
      }
32
    }
33
    for (int j = n - 1; j >= 0; j--) {
34
      int sum = 0;
35
      for (int i = n - 1; i >= 0; i--) {
36
        if (block[i * n + j]) {
37
          sum = 0;
38
        } else
39
          sum += 1;
40
        dp[i][j] = min(dp[i][j], sum);
41
      }
42
    }
43
    for (int i = n - 1; i >= 0; i--) {
44
      int sum = 0;
45
      for (int j = n - 1; j >= 0; j--) {
46
        if (block[i * n + j]) {
47
          sum = 0;
48
        } else
49
          sum += 1;
50
        dp[i][j] = min(dp[i][j], sum);
51
        ans = max(ans, dp[i][j]);
52
      }
53
    }
54
    return ans;
55
  }
56
};