-
Notifications
You must be signed in to change notification settings - Fork 1
/
Largest subsquare surrounded by X.cpp
58 lines (51 loc) · 1.73 KB
/
Largest subsquare surrounded by X.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
int largestSubsquare(int N, vector<vector<char>> A) {
// code here
// Top and left arrays;
vector<vector<int>> top(N,vector<int>(N,0));
vector<vector<int>> left(N,vector<int>(N,0));
// Top metric
for (int i=0;i<N;i++) {
for (int j=0;j<N;j++) {
if (A[i][j] == 'X') {
if (i!=0)
top[i][j] = top[i-1][j]+1;
else
top[i][j] = 1;
}
}
}
// left metric
for (int i=0;i<N;i++) {
for (int j=0;j<N;j++) {
if (A[i][j] == 'X') {
if (j!=0)
left[i][j] = left[i][j-1]+1;
else
left[i][j] = 1;
}
}
}
int maxSubSq = 0;
for (int i=0;i<N;i++) {
for (int j=0;j<N;j++) {
if (top[i][j] == 0 || left[i][j] == 0)
continue;
int currentValue = min(top[i][j],left[i][j]);
int top1 = i-currentValue +1;
int left1 = j-currentValue + 1;
while (currentValue>0) {
int top1 = i-currentValue +1;
int left1 = j-currentValue + 1;
if ((left[top1][j] >= currentValue) && (top[i][left1] >= currentValue)) {
maxSubSq = max(maxSubSq,currentValue);
break;
}
currentValue--;
}
}
}
return maxSubSq;
}
};